[Mesa-dev] [PATCH 3/3] util/disk_cache: use rand_xorshift128plus() to get our random int

[Nicolai Hähnle]

On 21.03.2017 11:50, Timothy Arceri wrote:
>
>
> On 21/03/17 21:10, Nicolai Hähnle wrote:
>> On 21.03.2017 09:57, Timothy Arceri wrote:
>>> Otherwise for apps that don't seed the regular rand() we will always
>>> remove old cache entries from the same dirs.
>>> ---
>>>  src/util/disk_cache.c | 9 +++++++--
>>>  1 file changed, 7 insertions(+), 2 deletions(-)
>>>
>>> diff --git a/src/util/disk_cache.c b/src/util/disk_cache.c
>>> index f2d67c9..f6ecf0b 100644
>>> --- a/src/util/disk_cache.c
>>> +++ b/src/util/disk_cache.c
>>> @@ -34,20 +34,21 @@
>>>  #include <sys/statvfs.h>
>>>  #include <sys/mman.h>
>>>  #include <unistd.h>
>>>  #include <fcntl.h>
>>>  #include <pwd.h>
>>>  #include <errno.h>
>>>  #include <dirent.h>
>>>  #include "zlib.h"
>>>
>>>  #include "util/crc32.h"
>>> +#include "util/rand_xor.h"
>>>  #include "util/u_atomic.h"
>>>  #include "util/u_queue.h"
>>>  #include "util/mesa-sha1.h"
>>>  #include "util/ralloc.h"
>>>  #include "main/errors.h"
>>>  #include "util/macros.h"
>>>
>>>  #include "disk_cache.h"
>>>
>>>  /* Number of bits to mask off from a cache key to get an index. */
>>> @@ -354,20 +355,23 @@ disk_cache_create(const char *gpu_name, const
>>> char *timestamp)
>>>     cache->max_size = max_size;
>>>
>>>     /* A limit of 32 jobs was choosen as observations of Deus Ex
>>> start-up times
>>>      * showed that we reached at most 11 jobs on an Intel i5-6400
>>> CPU at 2.70GHz
>>>      * (a fairly modest desktop CPU). 1 thread was chosen because we
>>> don't
>>>      * really care about getting things to disk quickly just that it's
>>> not
>>>      * blocking other tasks.
>>>      */
>>>     util_queue_init(&cache->cache_queue, "disk_cache", 32, 1);
>>>
>>> +   /* Seed our rand function */
>>> +   s_rand_xorshift128plus();
>>> +
>>>     ralloc_free(local);
>>>
>>>     return cache;
>>>
>>>   fail:
>>>     if (fd != -1)
>>>        close(fd);
>>>     if (cache)
>>>        ralloc_free(cache);
>>>     ralloc_free(local);
>>> @@ -569,22 +573,23 @@ evict_lru_item(struct disk_cache *cache)
>>>     const char hex[] = "0123456789abcde";
>>>     char *dir_path;
>>>     int a, b;
>>>     size_t size;
>>>
>>>     /* With a reasonably-sized, full cache, (and with keys generated
>>>      * from a cryptographic hash), we can choose two random hex digits
>>>      * and reasonably expect the directory to exist with a file in it.
>>>      * Provides pseudo-LRU eviction to reduce checking all cache files.
>>>      */
>>> -   a = rand() % 16;
>>> -   b = rand() % 16;
>>> +   uint64_t rand64 = rand_xorshift128plus();
>>> +   a = (rand64 >> 32) % 16;
>>> +   b = (rand64 & 0xFFFFFFFF) % 16;
>>
>> Why not just
>>
>> a = rand64 & 0xf;
>> b = (rand64 >> 4) & 0xf;
>>
>> ?
>
> Because % 16 is meant to give you a uniform distribution of random
> numbers between 0-15. Thinking about this some more I don't think I
> should really be splitting the number in half. I should really call it
> twice, I was looking for an open-source 32-bit generator but only found
> papers not code so settled with this existing one.

A PRNG is supposed to give you basically a stream of independent, 
uniformly distributed bits (obviously they're not exactly independent 
because they can't be, but that's the idea), and AFAIK modern PRNGs are 
reasonably good at that.

So in terms of quality of the randomness, it shouldn't make a difference 
whether you call the generator twice and extract 4 bits from each call, 
or whether you call it once and extract 8 bits, but of course the second 
option is faster.


>> Actually, why not simplify even further by saying:
>>
>>>
>>>     if (asprintf(&dir_path, "%s/%c%c", cache->path, hex[a], hex[b]) < 0)
>>
>> asprintf(..., "%s/%02x", ..., rand64 & 0xff)
>>
>> That would also fix the bug that the hex string is missing the final 'f'
>> ;-)
>
> Huh, hadn't noticed that. The joys of finish off prototype code :)

That (and bike-shedding) is why we have reviews :)

Cheers,
Nicolai

>
>>
>> Cheers,
>> Nicolai
>>
>>>        return;
>>>
>>>     size = unlink_lru_file_from_directory(dir_path);
>>>
>>>     free(dir_path);
>>>
>>>     if (size) {
>>>        p_atomic_add(cache->size, - (uint64_t)size);
>>>
>>