LXR Hash Properties
Sequential runs were done using a base of LXRHash("foo") appended by a nonce. The nonces are generated using the NonceIncrementer in the pegnet/mining package with the id 1.
The way modern CPU caches work is that essentially the RAM is divided into 64 byte chunks. If a request to RAM is made, the CPU will grab an entire 64-byte chunk (the "cache line") and store it in its L1/L2/L3 caches. Any further requests to an address inside that chunk are faster than grabbing it from RAM, until the cache line expires from the cache.
How many cache lines fit into the cache depends on the CPU. A 1 MiB L3 cache can hold 16,384 cache lines.
Calculated from a sequential run of 125,000 hashes. Every 100 hashes a sample was taken that tallied up the number of unique cache lines accessed in ByteMap.
The usage converges to 100% of the ByteMap, with 75,000+ hashes having used virtually the entire table at least once.
Calculated from a sequential run of 1,000,000 hashes. For every hash, the difficulty was calculated and sorted into the percentile of 0 to 2^64-1. If the distribution is uniform, we would expect every percentile to have around 10,000 entries.
All of the percentile buckets are within a small range of the expected amount (+/- 300).
Further, if we look at the histogram of the above data:
We can see that these results appear like a normal distribution, which is expected of a pseudo-random function.
To simulate the cache of a CPU, a simple LRU cache was used to keep track of the cache lines accessed. If a request to ByteMap was made that was in the LRU cache, it counts as a cache hit. The total number of hits divided by the total number of accesses is the hit frequency.
The smallest cache is 1 MiB (1024 KiB), increasing by 1 MiB every sample until 128 MiB. Modern CPUs have between 1 MiB and 4 MiB cache.
Bigger caches will make a difference but only to a degree of around 7%. This works well with LXRHash's goal of requiring high RAM usage.