Testing hash functions in python for zlib-ng

hash_test.py

import matplotlib.pyplot as plt
import numpy as np
import random
import timeit
import time
import math
import argparse
import zlib
from random import seed
import struct



parser = argparse.ArgumentParser(description='Hash algorithm testing')
parser.add_argument('--file', help='File to test', default=None, action='store', required=False)
args, unknown = parser.parse_known_args()

print("Arguments - Known/Unknown")
print(args)
print(unknown)


def crc32_hash(val):
    return zlib.crc32(val)


def zlib_hash(val):
    # (h = (((h)<<s->hash_shift) ^ (c)) & s->hash_mask)
    return ((val & 0xff) << 8) ^ ((val >> 16) & 0xff)


def zlib_ng_hash(val):
    return ((3483  * ((val) & 0xff)) +
            (23081 * (((val) >> 8) & 0xff)) +
            (6954  * (((val) >> 16) & 0xff)) +
            (20947 * (((val) >> 24) & 0xff)))


def knuth_hash(val):
    return ((val * np.uint32(2654435761)) >> (32 - 15))


def knuth_hash_mod(val):
    val ^= val >> (32 - 15)
    return ((val * np.uint32(2654435761)) >> (32 - 15))


def fib_hash(val):
    return (np.uint64(val) * np.uint64(11400714819323198485)) >> 12


def fib_hash_mod(val):
    val = np.uint64(val)
    val ^= val >> (12)
    return (val * np.uint64(11400714819323198485)) >> 12


hashes = [
    {"name": "crc32", "func": crc32_hash, "color": "darkblue"},
    {"name": "zlib-ng", "func": zlib_ng_hash, "color": "darkslateblue"},
    {"name": "knuth", "func": knuth_hash, "color": "mediumorchid"},
    {"name": "knuth-mod", "func": knuth_hash, "color": "plum"},
    {"name": "fib", "func": fib_hash, "color": "palevioletred"},
    {"name": "fib-mod", "func": fib_hash, "color": "pink"}
]

max_wsize = 32*1024

seed(time.time())

int_vals = []

if not args.file:
    # Get random values to hash
    for i in range(0, max_wsize):
        val = np.uint32(random.getrandbits(32))
        int_vals.append(val)
else:
    # Read data from binary file
    with open(args.file, "rb") as f:
        j = 0
        while True:
            buf = f.read(4)
            if not buf or len(buf) < 4:
                break
            i = np.frombuffer(buf, dtype=np.uint32)
            int_vals.append(i)
            j += 1
            if time.time() % 2 == 0:
                print("reads ints from input " + str(j) + "..")
        f.close()

print("total number of integers to hash " + str(len(int_vals)))

# Get collision map
def gen_collision_map(values, hash_func):
    collision_map = {}
    for i in range(0, len(values)):
        h = int(hash_func(values[i]) % (max_wsize))
        if h not in collision_map:
            collision_map[h] = []
        if values[i] not in collision_map[h]:
            collision_map[h].append(values[i])
    return collision_map


def flatten_collision_map(collision_map):
    flat_collision_map = np.zeros(max_wsize, dtype=np.uint32)
    max_collisions = 0
    total_collisions = 0
    for (h, v) in collision_map.items():
        collisions = 0
        hashes_in_bucket = len(v)
        if hashes_in_bucket >= 1:
            collisions = hashes_in_bucket
        flat_collision_map[h] = collisions
        if max_collisions < hashes_in_bucket:
            max_collisions = hashes_in_bucket
        total_collisions += collisions
    return (flat_collision_map, max_collisions, total_collisions)


def gen_heat_map(collision_map):
    heat_map = []
    for i in range(0, len(collision_map)):
        row = int(i % math.sqrt(max_wsize))
        if len(heat_map) <= row:
            heat_map.append([])
        heat_map[row].append(collision_map[i])
    return heat_map


max_collisions = 0
for hash in hashes:
    # Calculate collision map and time spent
    start = time.time()
    hash["collision_map"] = gen_collision_map(int_vals, hash["func"])
    end = time.time()

    hash["flat_collision_map"], hash["max_collisions"], hash["total_collisions"] = \
        flatten_collision_map(hash["collision_map"])

    print(hash["name"] + " hash time " + str(end - start) + "s")
    print(hash["name"] + " max collisions per hash " + str(hash["max_collisions"]))
    print(hash["name"] + " total collisions " + str(hash["total_collisions"]))

    # Get the maximum number of collisions per hash out of all the
    # hashes, this is used to make the collision count array the same
    # length for graphing
    if hash["max_collisions"] > max_collisions:
        max_collisions = hash["max_collisions"]

    if max_wsize <= 16*1024:  # Max image size
        # Generate heat map
        hash["heat_map"] = gen_heat_map(hash["flat_collision_map"])

        # Show heat map
        fig, ax = plt.subplots()
        im = ax.imshow(np.real(hash["heat_map"]))
        ax.set_title(hash["name"] + " distribution heat map")
        fig.tight_layout()
        plt.show()

print("max collisions for all hashes " + str(max_collisions))

for hash in hashes:
    # Count the number of collisions per hash
    hash["collision_count"] = np.zeros(max_collisions, dtype=int)
    print("Flat collision map for " + hash["name"])
    #print(np.matrix(hash["flat_collision_map"]))
    #np.savetxt(hash["name"] + "-flat.csv", hash["collision_count"], delimiter=",")
    for i in range(0, len(hash["flat_collision_map"])):
        hash_bucket_collisions = hash["flat_collision_map"][i]
        if hash_bucket_collisions > 0:
            hash["collision_count"][hash_bucket_collisions-1] += 1

# Show multi-bar graph using hash collision counts
bar = 0
width = 0.15
widths = []

fig, ax = plt.subplots()
for hash in hashes:
    if bar == 0:
        widths = np.arange(len(hash["collision_count"]))
    else:
        widths = [x + width for x in widths]
    ax.bar(widths, hash["collision_count"], color=hash["color"], width=width, label=hash["name"])
    bar += 1

x_labels = []
for i in range(0, max_collisions):
    x_labels.append(i+1)

x = np.arange(max_collisions)
ax.set_xticks(x + width + width/2)
ax.set_xticklabels(x_labels)
ax.set_xlabel('number of collisions')
ax.set_ylabel('number of hash buckets')
ax.legend()

fig.tight_layout()
plt.show()

Shouldn't line 13 be return (val * 2654435761) >> (32-15)?

Looks like that 24 corresponds to MIN_MATCH=3 from the code.

#define UPDATE_HASH(s, h, val) \
    h = ((val * 2654435761U) >> ((MIN_MATCH * 8) - s->hash_bits));

I am unsure whether that is the right bitshifting for the use-case, but it might be, I haven't played a lot with bit shifts.

@Dead2 We want as many significant bits for the hash as possible... for 16-bit variable, only 1 bit is wasted. Because we are actually hashing 4 bytes, not 3 bytes, it needs to be 4 * 8 = 32.

@mtl1979 I have updated the value, but I don't know that it makes much of a difference.

@Dead2 I don't know that fibonacci hash is too dissimilar to knuth except it uses 64-bits.

In this test hash table size is 16k:

They seem to perform about the same on random integer values. It is possible they may perform differently on different sets of data.

It is also possible that we don't see much of a difference between the hash functions, because our hash table is only 32k. When I increase the hash table size to 128k the difference is more apparent, but this doesn't apply to us.

Hmm, we might want to test with 64k hash tables too if we go for a static size, to see if that improves compression speed if memory is not at a premium.

I ran a test and didn't see a significant performance increase. However, my performance tests are not as exact as yours.

So the heat maps are essentially useless for my input data - which is random values. As long as my random function is truly random then the heat map will also have good distribution. The heat maps would tell us if there is a significant distribution degrade, say if I only used the first byte of the integer for the hash, then the heat map would look very poor but I don't expect to use such a hash method. What matters here the most is the number of collisions from the hash.

I have updated my script and here are some results with 32k hash table size:

earth.bmp

lcet10.txt

asl16.nii

dickens

Having the hash shift mod makes no difference to the algorithm.

The graph charts the number of hash buckets that had a certain number of collisions. The best hash algorithm will have a higher number of hash buckets on with lower number of collisions.

So in the graph, the best algorithm will have higher number of buckets (y-axis) as the number of collisions per hash bucket (x-axis) decreases. I suspect that knuth will perform the best, of course it may vary due to type of input data.

I did a test on asl16.ni that is in pigz-bench-python corpus.

05/09/2020  01:36 AM        10,209,230 asl16.nii-crc32.gz
05/09/2020  01:42 AM        10,209,251 asl16.nii-knuth-32.gz
05/09/2020  03:55 AM        10,209,263 asl16.nii-fib-mod.gz
05/09/2020  01:37 AM        10,212,436 asl16.nii-ng.gz
05/09/2020  01:35 AM        10,315,591 asl16.nii-knuth-24.gz
05/09/2020  01:39 AM        10,377,594 asl16.nii-hashshift.gz
05/09/2020  03:56 AM        10,571,103 asl16.nii-fib.gz
03/26/2020  09:47 PM        19,071,328 asl16.nii

knuth32 is (32 - s->hash_bits)
knuth24 is ((MIN_MATCH * 8) - s->hash_bits)
hashshift is the weird h = (s->ins_h = ((s->ins_h << s->hash_shift) ^ ((val) >> ((MIN_MATCH - 1) * 8))) & s->hash_mask)

Also it appears fib-mod does make a difference, just not in python - thou it is still not significantly better than knuth.