[LEDE-DEV] [Cake] Cake SQM killing my DIR-860L - was: [17.01] Kernel: bump to 4.4.51

[John Yates]

On Thu, Mar 2, 2017 at 4:10 PM, Dave Täht <dave at taht.net> wrote:

> As for speeding up hashing, I've been looking over various algorithms to
> do that for years now, I'm open to suggestions. The fastest new ones
> tend to depend on co-processor support. The fastest I've seen relies on
> the CRC32 instruction which is only in some intel platforms.

This is an area where I have a fair amount of experience.

It is a misconception that CRC is a good hash function.  It is good
at detecting errors but has poor avalanche performance.

What are the requirements for this hashing function?
- How much data is being hashed?  (I would guess a limited number
  of bytes rather than an entire packet payload.)
- What is the typical number of hash table buckets?  Must it be a
  power of 2?  Or are you willing to make it a prime number?

Assuming you can afford a 1KB lookup table I would suggest
the SBox hash in figure four of this article:

http://papa.bretmulvey.com/post/124028832958/hash-functions

The virtue of a prime number of buckets is that when you mod
your 32-bit hash value to get a bucket index you harvest _all_
of the entropy in the hash, not just the entropy in the bits you
preserve.

/john