On Tue, 2011-05-17 at 15:03 +0200, Michel Dänzer wrote: > From: Michel Dänzer <daen...@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. 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? If libc rand() is too slow, then some inlined linear-congruential generator could shave a few cycles. - Owen [ I haven't done any testing of cache replacement strategies for this code for actual texts, my preference for random replacement is more general - that it's not necessary to worry about whether the test cases are exercising some sweet spot of the algorithm or hitting some pathology. ] > Signed-off-by: Michel Dänzer <daen...@vmware.com> > --- > exa/exa_glyphs.c | 4 ++-- > exa/exa_priv.h | 2 +- > 2 files changed, 3 insertions(+), 3 deletions(-) > > diff --git a/exa/exa_glyphs.c b/exa/exa_glyphs.c > index 5c46ec9..28aa01f 100644 > --- a/exa/exa_glyphs.c > +++ b/exa/exa_glyphs.c > @@ -219,7 +219,7 @@ exaRealizeGlyphCaches(ScreenPtr pScreen, > for (j = 0; j < cache->hashSize; j++) > cache->hashEntries[j] = -1; > > - cache->evictionPosition = rand() % cache->size; > + cache->evictionPosition = 0; > } > > /* Each cache references the picture individually */ > @@ -500,7 +500,7 @@ exaGlyphCacheBufferGlyph(ScreenPtr pScreen, > exaGlyphCacheHashInsert(cache, pGlyph, pos); > > /* And pick a new eviction position */ > - cache->evictionPosition = rand() % cache->size; > + cache->evictionPosition = (pos + 1) % cache->size; > } > > exaGlyphCacheUploadGlyph(pScreen, cache, x, y, pGlyph); > diff --git a/exa/exa_priv.h b/exa/exa_priv.h > index 70de4bd..8c5ea15 100644 > --- a/exa/exa_priv.h > +++ b/exa/exa_priv.h > @@ -132,7 +132,7 @@ typedef struct { > PicturePtr picture; /* Where the glyphs of the cache are stored */ > int yOffset; /* y location within the picture where the cache > starts */ > int columns; /* Number of columns the glyphs are layed out in */ > - int evictionPosition; /* Next random position to evict a glyph */ > + int evictionPosition; /* Next position to evict a glyph */ > } ExaGlyphCacheRec, *ExaGlyphCachePtr; > > #define EXA_NUM_GLYPH_CACHES 4 _______________________________________________ xorg-devel@lists.x.org: X.Org development Archives: http://lists.x.org/archives/xorg-devel Info: http://lists.x.org/mailman/listinfo/xorg-devel