[New-bugs-announce] [issue45080] functools._HashedSeq implements __hash__ but not __eq__

Leopold Talirz report at bugs.python.org
Wed Sep 1 12:54:27 EDT 2021


New submission from Leopold Talirz <leopold.talirz at epfl.ch>:

Disclaimer: this is my first issue on the python bug tracker. Please feel free to close this issue and redirect this to a specific mailing list, if more appropriate.


The implementation of `functools._HashedSeq` [1] does not include an implementation of `__eq__` that takes advantage of the hash:
```
class _HashedSeq(list):
    """ This class guarantees that hash() will be called no more than once
        per element.  This is important because the lru_cache() will hash
        the key multiple times on a cache miss.
    """

    __slots__ = 'hashvalue'

    def __init__(self, tup, hash=hash):
        self[:] = tup
        self.hashvalue = hash(tup)

    def __hash__(self):
        return self.hashvalue
```
As far as I can tell, the `_HashedSeq` object is used as a key for looking up values in the python dictionary that holds the LRU cache, and this lookup mechanism relies on `__eq__` over `__hash__` (besides shortcuts for objects with the same id, etc.).

This can cause potentially expensive `__eq__` calls on the arguments of the cached function and I wonder whether this is intended?

Here is a short example code to demonstrate this:
```
from functools import _HashedSeq

class CompList(list):
    """Hashable list (please forgive)"""
    def __eq__(self, other):
        print("equality comparison")
        return super().__eq__(other)
    def __hash__(self):
        return hash(tuple(self))

args1=CompList((1,2,3))  # represents function arguments passed to lru_cache
args2=CompList((1,2,3))  # identical content but different object


hs1=_HashedSeq( (args1,))
hs2=_HashedSeq( (args2,))

hs1 == hs2  # True, prints "equality comparison"

d={}
d[hs1] = "cached"
d[hs2] # "cached", prints "equality comparison"

```

Adding the following to the implementation of `_HashedSeq` gets rid of the calls to `__eq__`:
```
    def __eq__(self, other):
        return self.hashvalue == other.hashvalue
```
Happy to open a PR for this.

I'm certainly a bit out of my depth here, so apologies if that is all intended behavior.


[1] https://github.com/python/cpython/blob/679cb4781ea370c3b3ce40d3334dc404d7e9d92b/Lib/functools.py#L432-L446

----------
components: Library (Lib)
messages: 400858
nosy: leopold.talirz
priority: normal
severity: normal
status: open
title: functools._HashedSeq implements __hash__ but not __eq__
type: behavior
versions: Python 3.10, Python 3.9

_______________________________________
Python tracker <report at bugs.python.org>
<https://bugs.python.org/issue45080>
_______________________________________


More information about the New-bugs-announce mailing list