md5 is faster than fnv1a

[Uzlopak]

Prerequisites

• I have written a descriptive issue title
• I have searched existing issues to ensure the issue has not already been raised

Issue

We use by default fnv1a for weak hashing. But md5 is faster than fnv1a

Here is a benchmark with an impememtation of the Java hashCode algorithm and crc32

'use strict'

const crc32 = require('crc-32').buf
const crypto = require('crypto')
const benchmark = require('benchmark')

const LoremString = 'Lorem ipsum dolor sit amet, consectetuer adipiscing elit. Aenean commodo ligula eget dolor. Aenean massa. Cum sociis natoque penatibus et magnis dis parturient montes, nascetur ridiculus mus. Donec quam felis, ultricies nec, pellentesque eu, pretium quis, sem. Nulla consequat massa quis enim. Donec pede justo, fringilla vel, aliquet nec, vulputate eget, arcu. In enim justo, rhoncus ut, imperdiet a, venenatis vitae, justo. Nullam dictum felis eu pede mollis pretium. Lorem ipsum dolor sit amet, consectetuer adipiscing elit. Aenean commodo ligula eget dolor. Aenean massa. Cum sociis natoque penatibus et magnis dis parturient montes, nascetur ridiculus mus. Donec quam felis, ultricies nec, pellentesque eu, pretium quis, sem. Nulla consequat massa quis enim. Donec pede justo, fringilla vel, aliquet nec, vulputate eget, arcu. In enim justo, rhoncus ut, imperdiet a, venenatis vitae, justo. Nullam dictum felis eu pede mollis pretium. Lorem ipsum dolor sit amet, consectetuer adipiscing elit. Aenean commodo ligula eget dolor. Aenean massa. Cum sociis natoque penatibus et magnis dis parturient montes, nascetur ridiculus mus. Donec quam felis, ultricies nec, pellentesque eu, pretium quis, sem. Nulla consequat massa quis enim. Donec pede justo, fringilla vel, aliquet nec, vulputate eget, arcu. In enim justo, rhoncus ut, imperdiet a, venenatis vitae, justo. Nullam dictum felis eu pede mollis pretium.'
const LoremBuffer = Buffer.from(LoremString)

function hashCode (input) {
  let hash = 0
  let i = 0
  const il = input.length
  for (i = 0; i < il; ++i) {
    hash = (((hash << 5) - hash) + input[i]) & 0xFFFFFFFF
  }

  return hash >>> 0
}

const OFFSET_BASIS_32 = 2166136261

function fnv1a (buf) {
  let hash = OFFSET_BASIS_32

  for (let i = 0; i < buf.length;) {
    hash ^= buf[i++]

    // 32-bit FNV prime: 2**24 + 2**8 + 0x93 = 16777619
    // Using bitshift for accuracy and performance. Numbers in JS suck.
    hash += (hash << 1) + (hash << 4) + (hash << 7) + (hash << 8) + (hash << 24)
  }

  return hash >>> 0
}

new benchmark.Suite()
  .add('crc32', function () {
    crc32(LoremBuffer) >>> 0
  }, { minSamples: 100 })
  .add('md5', function () {
    crypto.createHash('md5').update(LoremBuffer).digest().toString('base64')
  }, { minSamples: 100 })
  .add('hashCode', function () {
    hashCode(LoremBuffer)
  }, { minSamples: 100 })
  .add('fnv1a', function () {
   fnv1a(LoremBuffer)
  }, { minSamples: 100 })
  .on('cycle', function onCycle(event) { console.log(String(event.target)) })
  .run()

result:

node benchmarks/weakHash.js

crc32 x 1,314,889 ops/sec ±0.19% (195 runs sampled)
md5 x 293,537 ops/sec ±2.10% (175 runs sampled)
hashCode x 1,019,507 ops/sec ±0.40% (190 runs sampled)
fnv1a x 154,034 ops/sec ±0.11% (195 runs sampled)

[jsumners]

See https://stackoverflow.com/a/44171095

[Uzlopak]

Well md5 has a 128bit digest and fnv1a has a 32 bit digest. Thats why I looked for crc32 and hashCode as they are also have 32 bit digests.

Here with the in SO-Thread mentioned murmurhash

btw.: renamed hashCode to djb2

murmurhash x 766,803 ops/sec ±0.41% (194 runs sampled)
crc32 x 1,310,009 ops/sec ±0.29% (195 runs sampled)
md5 x 286,639 ops/sec ±2.97% (178 runs sampled)
djb2 x 1,033,964 ops/sec ±0.24% (194 runs sampled)
fnv1a x 152,752 ops/sec ±0.05% (194 runs sampled)

'use strict'

const crc32 = require('crc-32').buf
const crypto = require('crypto')
const benchmark = require('benchmark')

const LoremString = 'Lorem ipsum dolor sit amet, consectetuer adipiscing elit. Aenean commodo ligula eget dolor. Aenean massa. Cum sociis natoque penatibus et magnis dis parturient montes, nascetur ridiculus mus. Donec quam felis, ultricies nec, pellentesque eu, pretium quis, sem. Nulla consequat massa quis enim. Donec pede justo, fringilla vel, aliquet nec, vulputate eget, arcu. In enim justo, rhoncus ut, imperdiet a, venenatis vitae, justo. Nullam dictum felis eu pede mollis pretium. Lorem ipsum dolor sit amet, consectetuer adipiscing elit. Aenean commodo ligula eget dolor. Aenean massa. Cum sociis natoque penatibus et magnis dis parturient montes, nascetur ridiculus mus. Donec quam felis, ultricies nec, pellentesque eu, pretium quis, sem. Nulla consequat massa quis enim. Donec pede justo, fringilla vel, aliquet nec, vulputate eget, arcu. In enim justo, rhoncus ut, imperdiet a, venenatis vitae, justo. Nullam dictum felis eu pede mollis pretium. Lorem ipsum dolor sit amet, consectetuer adipiscing elit. Aenean commodo ligula eget dolor. Aenean massa. Cum sociis natoque penatibus et magnis dis parturient montes, nascetur ridiculus mus. Donec quam felis, ultricies nec, pellentesque eu, pretium quis, sem. Nulla consequat massa quis enim. Donec pede justo, fringilla vel, aliquet nec, vulputate eget, arcu. In enim justo, rhoncus ut, imperdiet a, venenatis vitae, justo. Nullam dictum felis eu pede mollis pretium.'
const LoremBuffer = Buffer.from(LoremString)

function djb2 (input) {
  let hash = 0
  let i = 0
  const il = input.length
  for (i = 0; i < il; ++i) {
    hash = (((hash << 5) - hash) + input[i]) & 0xFFFFFFFF
  }

  return hash >>> 0
}

const OFFSET_BASIS_32 = 2166136261

function fnv1a (buf) {
  let hash = OFFSET_BASIS_32

  for (let i = 0; i < buf.length;) {
    hash ^= buf[i++]

    // 32-bit FNV prime: 2**24 + 2**8 + 0x93 = 16777619
    // Using bitshift for accuracy and performance. Numbers in JS suck.
    hash += (hash << 1) + (hash << 4) + (hash << 7) + (hash << 8) + (hash << 24)
  }

  return hash >>> 0
}

function murmurhash2_32_gc(buf, seed) {
  var
    l = buf.length,
    h = seed ^ l,
    i = 0,
    k;
  
  while (l >= 4) {
  	k = 
  	  ((buf[i] & 0xff)) |
  	  ((buf[++i] & 0xff) << 8) |
  	  ((buf[++i] & 0xff) << 16) |
  	  ((buf[++i] & 0xff) << 24);
    
    k = (((k & 0xffff) * 0x5bd1e995) + ((((k >>> 16) * 0x5bd1e995) & 0xffff) << 16));
    k ^= k >>> 24;
    k = (((k & 0xffff) * 0x5bd1e995) + ((((k >>> 16) * 0x5bd1e995) & 0xffff) << 16));

	h = (((h & 0xffff) * 0x5bd1e995) + ((((h >>> 16) * 0x5bd1e995) & 0xffff) << 16)) ^ k;

    l -= 4;
    ++i;
  }
  
  switch (l) {
  case 3: h ^= (buf[i + 2] & 0xff) << 16;
  case 2: h ^= (buf[i + 1] & 0xff) << 8;
  case 1: h ^= (buf[i] & 0xff);
          h = (((h & 0xffff) * 0x5bd1e995) + ((((h >>> 16) * 0x5bd1e995) & 0xffff) << 16));
  }

  h ^= h >>> 13;
  h = (((h & 0xffff) * 0x5bd1e995) + ((((h >>> 16) * 0x5bd1e995) & 0xffff) << 16));
  h ^= h >>> 15;

  return h >>> 0;
}

new benchmark.Suite()
  .add('murmurhash', function () {
    murmurhash2_32_gc(LoremBuffer)
  }, { minSamples: 100 })
  .add('crc32', function () {
    crc32(LoremBuffer) >>> 0
  }, { minSamples: 100 })
  .add('md5', function () {
    crypto.createHash('md5').update(LoremBuffer).digest().toString('base64')
  }, { minSamples: 100 })
  .add('djb2', function () {
    djb2(LoremBuffer)
  }, { minSamples: 100 })
  .add('fnv1a', function () {
   fnv1a(LoremBuffer)
  }, { minSamples: 100 })
  .on('cycle', function onCycle(event) { console.log(String(event.target)) })
  .run()

[climba03003]

If a new algorithm is needed because of speed. I will go for Murmur2.
It has better randomness, fair collision problem and faster speed.

[Uzlopak]

Do you have a good performant implemention of murmur2 you recommend?

[mcollina]

The 32bit digest is great for this case. Adding bytes to the response will slow down transfers long term.

[climba03003]

Do you have a good performant implemention of murmur2 you recommend?

No, I vote on the algorithm. But I never use it in my application.

The comparison is pretty solid and I believe it is a good choice

Refs #3

[Uzlopak]

Well my recommendation is not to set md5 as default hashing algorithm. It is just, that it seems odd, that the Weak entity tag is 50% slower than using md5. Even hashing it through md5 and then just taking 4 bytes should be faster than fnv1a. So I assume that at the time fastify-etag was developed md5/sha1 was slower in nodejs than doing the fnv1a hashing.
When i now benchmark it, it seems that it is the total opposite.

So I am actualy suggesting to replace fnv1a with a faster weak hashing algorithm. Currently the crc32 implementation seems to be the fastest on my machine. According to the comparison of @climba03003 murmur can be faster. So lets see if there is somewhere already a faster implementation than the one i found

[climba03003]

Here is benchmark using the benchmarks/run.js.
I believe the result of comparing plan hashing method is contradicting because the payload is not compared in small to large.

You can see the in 32b / 2k, murmur2 and fnv1a is nearly the same.
In 2M, murmur2 start out perform fnv1a and near to md5.

32 bytes
--------

  string
  ------
   1. No etag             21279.20 req/sec
   2. murmur2             20739.24 req/sec       -2.538%
   3. fnv1a               20208.20 req/sec       -5.033%
   4. md5                 16854.41 req/sec      -20.794%

  buffer
  ------
   1. No etag             20950.29 req/sec
   2. murmur2             19791.81 req/sec       -5.530%
   3. fnv1a               19394.60 req/sec       -7.426%
   4. md5                 16271.00 req/sec      -22.335%


2 kb
----

  string
  ------
   1. No etag             18067.00 req/sec
   2. murmur2             15429.60 req/sec      -14.598%
   3. fnv1a               14124.00 req/sec      -21.824%
   4. md5                 13760.00 req/sec      -23.839%

  buffer
  ------
   1. No etag             20701.41 req/sec
   2. murmur2             17877.80 req/sec      -13.640%
   3. md5                 15624.80 req/sec      -24.523%
   4. fnv1a               10357.71 req/sec      -49.966%


2 Mb
----

  string
  ------
   1. No etag                73.28 req/sec
   2. md5                    49.95 req/sec      -31.837%
   3. murmur2                48.15 req/sec      -34.293%
   4. fnv1a                  36.65 req/sec      -49.986%

  buffer
  ------
   1. No etag                74.00 req/sec
   2. md5                    70.11 req/sec       -5.257%
   3. murmur2                69.74 req/sec       -5.757%
   4. fnv1a                  51.16 req/sec      -30.865%

[mcollina]

When are we sending JSON data of 2MBs? It does not seem a usual case.

Anyway, I'm happy to add murmur2 to the options (why not murmur3? https://en.m.wikipedia.org/wiki/MurmurHash)

[Uzlopak]

I have a local branch with integrated murmur2 and jbl2. Crc32 is loaded from the package crc-32. Do you want it?

[mcollina]

I prefer not to take an additional dependency. How about adding an option to specify a function to compute this hash?

[kurtextrem]

I benchmarked on node v18.13.0, M1 Pro:

32 bytes
--------

  string
  ------
   1. crc32               55889.80 req/sec
   2. murmur3             54688.80 req/sec       -2.149%
   3. fnv1a               54016.80 req/sec       -3.351%
   4. murmur2             53529.00 req/sec       -4.224%
   5. djb2                50503.60 req/sec       -9.637%
   6. sha1                48489.40 req/sec      -13.241%
   7. md5                 47425.40 req/sec      -15.145%

  buffer
  ------
   1. crc32               55871.00 req/sec
   2. murmur2             55805.60 req/sec       -0.117%
   3. djb2                55018.20 req/sec       -1.526%
   4. MurmurHash3         54400.20 req/sec       -2.632%
   5. murmur3             54174.60 req/sec       -3.036%
   6. fnv1a               53179.20 req/sec       -4.818%
   7. md5                 48790.80 req/sec      -12.672%
   8. sha1                48017.20 req/sec      -14.057%
   9. murmur3wasm         20159.20 req/sec      -63.918%


2 kb
----

  string
  ------
   1. sha1                34247.81 req/sec
   2. crc32               32182.60 req/sec       -6.030%
   3. murmur2             31616.00 req/sec       -7.685%
   4. murmur3             30362.74 req/sec      -11.344%
   5. md5                 29260.00 req/sec      -14.564%
   6. fnv1a               23937.20 req/sec      -30.106%
   7. djb2                 8023.52 req/sec      -76.572%

  buffer
  ------
   1. crc32               49125.40 req/sec
   2. djb2                48597.60 req/sec       -1.074%
   3. sha1                46698.20 req/sec       -4.941%
   4. murmur3             44641.00 req/sec       -9.128%
   5. murmur2             44610.20 req/sec       -9.191%
   6. md5                 39599.60 req/sec      -19.391%
   7. MurmurHash3         21560.00 req/sec      -56.112%
   8. murmur3wasm         19975.91 req/sec      -59.337%
   9. fnv1a               19789.86 req/sec      -59.716%


2 Mb
----

  string
  ------
   1. sha1                   98.54 req/sec
   2. md5                    69.89 req/sec      -29.074%
   3. murmur2                64.95 req/sec      -34.088%
   4. crc32                  63.44 req/sec      -35.620%
   5. murmur3                47.88 req/sec      -51.411%
   6. fnv1a                  36.80 req/sec      -62.655%
   7. djb2                    0.03 req/sec      -99.970% (396 errors - 396 timeouts)

  buffer
  ------
   1. murmur3wasm         20414.20 req/sec
   2. djb2                  116.00 req/sec      -99.432%
   3. sha1                  111.75 req/sec      -99.453%
   4. murmur3               110.26 req/sec      -99.460%
   5. murmur2                87.45 req/sec      -99.572%
   6. MurmurHash3            86.62 req/sec      -99.576%
   7. crc32                  85.84 req/sec      -99.580%
   8. md5                    81.49 req/sec      -99.601%
   9. fnv1a                  33.44 req/sec      -99.836%