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

[Owen Taylor]

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.

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 <daenzer at 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