[Mesa-dev] [PATCH 3/3] util/disk_cache: use rand_xorshift128plus() to get our random int
Nicolai Hähnle
nhaehnle at gmail.com
Tue Mar 21 11:19:43 UTC 2017
On 21.03.2017 12:16, Timothy Arceri wrote:
>
>
> On 21/03/17 21: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.
>
> Actually it should probably just be % 32, getting the two letters from a
> single call. Or possibly % 33 with the modulo bias remove or some other
> workaround to keep uniform distribution so that we fix the missing upper
> limited you pointed out below.
You mean % 256 (== 16 * 16). Which is the same as the 0xff that I
suggested in the asprintf below.
Cheers,
Nicolai
>
>>
>>>
>>> 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 :)
>>
>>>
>>> Cheers,
>>> Nicolai
>>>
>>>> return;
>>>>
>>>> size = unlink_lru_file_from_directory(dir_path);
>>>>
>>>> free(dir_path);
>>>>
>>>> if (size) {
>>>> p_atomic_add(cache->size, - (uint64_t)size);
>>>>
>>>
>> _______________________________________________
>> mesa-dev mailing list
>> mesa-dev at lists.freedesktop.org
>> https://lists.freedesktop.org/mailman/listinfo/mesa-dev
More information about the mesa-dev
mailing list