<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Fri, Dec 30, 2016 at 3:54 PM, Christian Heimes <span dir="ltr"><<a href="mailto:christian@python.org" target="_blank">christian@python.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Hi,<br>
<br>
I'm the author of PEP 456 (SipHash24) and one of the maintainers of the<br>
hashlib module.<br>
<br>
Before we come up with a new API or recipe, I would like to understand<br>
the problem first. Why does the initial op consider hash(large_tuple) a<br>
performance issue? If you have an object with lots of members that<br>
affect both __hash__ and __eq__, then __hash__ is really least of your<br>
concern. The hash has to be computed just once and then will stay the<br>
same over the life time of the object. Once computed the hash can be<br>
cached.<br>
<br>
On the other hand __eq__ is at least called once for every successful<br>
hash lookup. On the worst case it is called n-1 for a dict of size n for<br>
a match *and* a hashmap miss. Every __eq__ call has to compare between 1<br>
and m member attributes. For a dict with 1,000 elements with 1,000<br>
members each, that's just 1,000 hash computations with roughly 8 bB<br>
memory allocation but almost a million comparisons in worst case.<br>
<br>
A hasher objects adds further overhead, e.g. object allocation, creation<br>
of a bound methods for each call etc. It's also less CPU cache friendly<br>
than the linear data structure of a tuple.</blockquote><div><br></div><div><br></div><div>Thanks for joining the discussion, great to have your input.</div><div><br>In the use cases I described, the objects' members are ordered. So in the unlikely event that two objects hash to the same value but are unequal, the __eq__ call should be cheap, because they probably differ in length or on their first member, and can skip further comparison. After a successful hash lookup of an object that's already in a set or dict, a successful identity check avoids an expensive equality check. Perhaps I misunderstood?</div><div><br></div><div>Here is some example code:</div><div><br></div><div>class FrozenOrderedCollection:</div><div>    ...</div><div><div>    def __eq__(self, other):</div><div>        if not isinstance(other, FrozenOrderedCollection):</div><div>            return NotImplemented</div><div>        if len(self) != len(other):</div><div>            return False</div><div>        return all(i == j for (i, j) in zip(self, other))</div><div><br></div></div><div><div>    def __hash__(self):</div><div>        if hasattr(self, '_hashval'):</div><div>            return self._hashval</div><div>        hash_initial = hash(self.__class__)</div><div>        self._hashval = reduce(lambda h, i: hash((h, i)), self, hash_initial)<br></div><div>        return self._hashval</div></div><div><br></div><div><br></div><div><br></div><div>Is it the case that internally, the code is mostly there to compute the hash of such an object in incremental fashion, and it's just a matter of figuring out the right API to expose it?</div><div><br></div><div>If creating an arbitrarily large tuple, passing that to hash(), and then throwing it away really is the best practice, then perhaps that should be explicitly documented, since I think many would find that counterintuitive?</div><div><br></div><div>@Stephen J. Turnbull, thank you for your input -- still digesting, but very interesting.</div><div><br></div><div>Thanks again to everyone for the helpful discussion.</div></div></div></div>