lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]


One note:  I was challenged personally on this list to discuss the issue, a few others are challenged. It's clear that someone is on the wrong side for the correct answer to this challenge.
I assert it is not me (and I'm given enough proofs).

Being in error is not dramatic: challenging someone for his errors is not a personal attack. Remember: "Errare humanum est", and errors can occur from anyone (qualified or not) in any programming project (there are tons of bugs discovered late, most of them are unvoluntary, they just were unnoticed because of an initial unchecked assumption when writing code, or because this was still not a design goal matching the immediate need and the initial usages).

What matters is that these bugs get fixed when they are demonstrated and the atittude of "official" maintainers of published code (that many Lua programmers will want to use without constantly checking everything in the Lua engine they just install "as is"):

I propose a very simple fix (use a true prime constant multiplier, that cannot break anything and certainly not performance) and some improvement (changing the rotation to 3 bits instead of 2, and adding the unit before multiplying by a constant, instead of after the multiplication) to increase the performance of tables, make them much less vulnerable to wellknown attacks, and make them usable with less frequent "slow worst cases" in many practical cases in Lua applications. I have also proposed (like Knuth did) to not use any Mersenne prime (Knuth suggested Mersenne numbers as a possible but still poor choice only good for very small tables, he recommanded and published stronger primes for common hash word sizes, that can work for all hash tables with any size lower than or equal to one of these common hash word sizes).


Le mer. 27 mai 2020 à 11:09, Francisco Olarte <folarte@peoplecall.com> a écrit :
Philippe:

On Tue, May 26, 2020 at 11:30 PM Philippe Verdy <verdyp@gmail.com> wrote:
> So now you can confirm that the factor 129 is not suitable as is is not prime (divisible by 3) even if it's a Mersenne number (=2^7+1).

To be strict, Mersenne numbers are -1, that +1 is an extension you
have put without proof.

Anyway, what can I confirm 129 is not suitable for?

> But the current implementation still uses it as the factor: (h<<5)+(h>>2) is the same as (h<<7 + h)>>>2 = (h*128+h)>>>2 = (h*129)>>>2; this way of writing it with the sum of shifts in two directions avoids discarding 2 high bits with (h<<7)

So, you affirm it is the same only to prove it is not the same in the
same sentence?

...
> Knuth designated good multipliers for several wordsizes. You deliberately ignored it just like you deliberately chose to ignore the primality requiement of the factor: this is a proof that you've not understood the Knuth algorithm and how and why it really works as a good (but still fast) hash.

.... This "you deliberately" seems to indicate you are not replying to
me, although you are doing it in ( top posted as usual, something
smells rotten in Denmark ) response which quotes me.

> So in this piece of code,

Yep, you are totally loosing direction. No piece of code, no context.
I think this should be addressed to the PUC people or some other real
implementer. Cutting it short now.

FOS.