VAST: Re: 2.4.X inode cache bug

Quim K Holland <[e-mail]> wrote:
> Then maybe the attached patch is what you want?  This also replaces
> `+' on the next line with `^' to avoid slanted distribution.

Thanks. The use of + in a hash-formula is usually all right, though. It's
XOR with carry propagation; when there's some pattern or cycicity to
the value being hashed, carry propagation is even a desired quality. And
due to being a common operation, it's usually at least as fast as XOR.
Ofcourse, the sum of multiple random values tends to normalize (ie. the
distribution is normal-distribution) but since the upper bits are
discarded, this isn't a big problem.

For a really fast version of this hash-function, I would just sum up the
upper 32 bits of the inode with the lower 32 bits, and then again the
upper 16 bits of he result with lower 16 bits, using carry. Then take as
many lower bits as needed. Usually hash-table sizes should be prime
numbers, but I predict through profiling would show modulo-operation
to take more time than scanning the bucket in typical cases.

If cache-affinity was desired, one should be familiar with the
associativity rules on target platform, however the practical effect is
normally to just reduce the effective hash-taable size.

 -Donwulff