<div dir="ltr"><br><br><div class="gmail_quote"><div dir="ltr">Le dim. 25 nov. 2018 à 22:21, Eliot Miranda <<a href="mailto:eliot.miranda@gmail.com">eliot.miranda@gmail.com</a>> a écrit :<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="auto">Hi Luciano,<div dir="ltr"><br>On Nov 24, 2018, at 9:06 PM, Luciano Notarfrancesco <<a href="mailto:luchiano@gmail.com" target="_blank">luchiano@gmail.com</a>> wrote:<br><br></div><blockquote type="cite"><div dir="ltr"><div dir="ltr">Hi Eliot!<br><div><br><div class="gmail_quote"><div dir="ltr">On Sat, Nov 24, 2018 at 9:18 PM Eliot Miranda <<a href="mailto:eliot.miranda@gmail.com" target="_blank">eliot.miranda@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><br><div class="gmail_quote"><div dir="ltr">On Sat, Nov 24, 2018 at 7:40 AM Luciano Notarfrancesco <<a href="mailto:luchiano@gmail.com" target="_blank">luchiano@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><br><div class="gmail_quote"><div>Yes! I had this problem blow in my face a couple of years ago, and Juan agreed to include the change in Cuis to make SmallIntegers NOT their own hash.</div></div></div></blockquote><div><br></div><div>This seems to be a basic error.  The idea of a hash function is to produce a well-distributed set of integers for some set of values.  Since the SmallIntegers are themselves perfectly distributed (each unique SmallInteger is a unique value), it is impossible to produce a better distributed hash function than  the integers themselves. For some application it may indeed be possible to produce a better distributed set of hashes for the integers; for example an application which considers only powers of two could use the log base 2 to produce a smaller and better distributed set fo values modulo N than the integers themselves.  But in general the integers are definitionally well-distributed.  In fact, unless one has a perfect hash function one is in danger of producing a less well-distributed set of values from a hash function than the SmallIntegers themselves.</div><div><br></div></div></div></blockquote><div><br></div><div>The problem I see is that sequences of SmallIntegers that we humans tend add to hashed collections are not usually uniformly distributed. Hopefully they have some meaning, and thus some patterns to them, most of the time they don't look random, and thus if they are their own hash the performance of hashed collections will most likely suffer.</div></div></div></div></div></blockquote><div><br></div>As I said, god specific cases where the distribution of interludes used fits some pattern, there is PluggableDictionary and <span style="background-color:rgba(255,255,255,0)">PluggableSet.  In cases where integers are randomly or evenly distributed one cannot improve on integers being their own hashes, so KISS, and use the available alternatives.</span><div><br></div></div></blockquote><div>Hi Eliot,</div><div>my bet is as Luciano: set of integers with uniform distribution is the least probable in my experience: it's just noise. Every other data of interest will show different patterns.<br></div><div>So I'm not sure that forcing usage of Pluggable* is that simple, for preserving theoretical property that we don't encounter...</div><div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="auto"><div><blockquote type="cite"><div dir="ltr"><div dir="ltr"><div><div class="gmail_quote"><div><br></div><div>I found this problem when profiling my code. I guess some people might assume that Sets or Dictionaries are fast and use them with SmallIntegers without much care, and never discover that their code could be orders of magnitude faster. So, another option might be to modify scanFor: to randomize the hash of the argument (for example sending an additional hashMultiply). This is because scanFor: is assuming the arguments of successive calls will have uniformly distributed hashes:</div><div>    start := anObject hash \\ array size + 1.<br></div><div>the algorithm needs 'start' to be uniformly distributed between 1 and array size, and in the case of SmallIntegers current hash this is very unlikely and lookups degenerate in linear searches.</div></div></div></div></div></blockquote><div><br></div>Whether it is likely or unlikely depends on the specific set of integers.  Any hash function can suffer from the same issue; and if a hash function produces fewer values than its input set then that hash function may make things worse.  Hence it makes sense to keep things simple and be aware of alternatives for specific situations.</div><div><br></div></div></blockquote><div><br></div><div>But that is the case for any other hash. What is important is the length of hash bits compared to the size of the Set.</div><div>If hashMultiply result in too short hashes, then we get a problem for Set of any other objects...<br></div><div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="auto"><div><blockquote type="cite"><div dir="ltr"><div dir="ltr"><div><div class="gmail_quote"><div><br></div><div>Also, any cryptographic hash will do great in pretty much ALL use cases. Finding a sequence of integers that produces non-uniform hashes is very hard,</div></div></div></div></div></blockquote><div><br></div>Since one takes the result of the hash modulo N I think this statement is false.  It depends on the hash table size and the specific set of integers one is hashing.</div><div><br></div></div></blockquote><div>Hmm number theory, let's see... Hmm, that's really a question for Luciano or Andres ;)<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="auto"><div><blockquote type="cite"><div dir="ltr"><div dir="ltr"><div><div class="gmail_quote"><div> and is equivalent to breaking the cryptographic hash and make it unusable for cryptography. This is a sort of silver bullet, I seem to remember that Java does this now, but I think it is overkill and something like hashMultiply is enough (plus, it is cheaper).</div><br></div><div class="gmail_quote">My 2 maos,</div><div class="gmail_quote">Luciano<br></div></div></div>
</div></blockquote><blockquote type="cite"><div dir="ltr"><span></span><br></div></blockquote></div></div><br>
</blockquote></div></div>