[PATCH xserver 2/7] EXA: Use round robin instead of rand() for choosing eviction position.

[Owen Taylor]

On Tue, 2011-05-17 at 18:32 +0200, Michel Dänzer wrote:
> On Die, 2011-05-17 at 11:53 -0400, Owen Taylor wrote: 
> > On Tue, 2011-05-17 at 15:03 +0200, Michel Dänzer wrote:
> > > From: Michel Dänzer <daenzer at vmware.com>
> > > 
> > > This should be just as good on average but is less expensive.
> > 
> > If we're not hitting the cache, isn't the cost of rand() pretty much
> > noise? On my system, rand() seems to take about 10ns.
> 
> I wrote this patch because rand() showed up in profiles, and it
> increased x11perf -aa10text numbers.

If rand() shows up in profiles at all, then x11perf -aa10text is
exceeding the cache size, right? (this really suprises me, how many
different glyphs does aa10text show?) 

If x11perf -aa10text is exceeding the cache size then the exact details
of the cache replacement strategy will affect the numbers a lot more
than rand().

> > The nice thing about random replacement is that it reliable sticks to
> > being about "as good" as the average, while predictable strategies tend
> > to have cases where they work well, and cases which they work badly.
> > 
> > That is, if you have cache of size 10, does performance degrade smoothly
> > when you go from 9 glyphs to 11 glyphs, or do you drop off a cliff?
> 
> I haven't tested this specifically.
> 
> 
> > If libc rand() is too slow, then some inlined linear-congruential
> > generator could shave a few cycles.
> 
> I'm afraid I'm not really interested in working on that though.

Add an unsigned int evictionRand to ExaGlyphCacheRec, then when
updating:

 cache->evictionRand = cache->evictionRand * 1103515245 + 12345;
 cache->evictionPosition = cache->evictionRand % cache->size;

would be good enough. (Things could be done to improve the quality,
but just doesn't matter here)

- Owen