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

Michel Dänzer michel at daenzer.net
Tue May 17 09:32:50 PDT 2011

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.

> 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.

Earthling Michel Dänzer           |                http://www.vmware.com
Libre software enthusiast         |          Debian, X and DRI developer

More information about the xorg-devel mailing list