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

[Jonathan Morton]

> On 3 Mar, 2017, at 07:00, Eric Luehrsen <ericluehrsen at hotmail.com> wrote:
> 
> That's not what I was going for. Agree, it would not be good to depend 
> on an inferior hash. You mentioned divide as a "cost." So I was 
> proposing a thought around a "benefit" estimate. If hash collisions are 
> not as important (or are they), then what is "benefit / cost?"

The computational cost of one divide is not the only consideration I have in mind.

Cake’s set-associative hash is fundamentally predicated on the number of hash buckets *not* being prime, as it requires further decomposing the hash into a major and minor part when a collision is detected.  The minor part is then iterated to try to locate a matching or free bucket.

This is considerably easier to do and reason about when everything is a power of two.  Then, modulus is a masking operation, and divide is a shift, either of which can be done in one cycle flat.

AFAIK, however, the main CPU cost of the hash function in Cake is not the hash itself, but the packet dissection required to obtain the data it operates on.  This is something a profile would shed more light on.

 - Jonathan Morton