memoryview: equality-hash invariant

[skrah]

BPO	15814
Nosy	@loewis, @birkenfeld, @mdickinson, @ncoghlan, @abalkin, @pitrou, @vstinner, @tiran, @skrah, @meadori
Files	issue15814-doc.diff issue15814-2.diff

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = 'https://github.com/skrah'
closed_at = <Date 2012-11-02.17:25:55.915>
created_at = <Date 2012-08-29.17:07:08.653>
labels = ['type-bug']
title = 'memoryview: equality-hash invariant'
updated_at = <Date 2012-11-02.17:25:55.914>
user = 'https://github.com/skrah'

bugs.python.org fields:

activity = <Date 2012-11-02.17:25:55.914>
actor = 'skrah'
assignee = 'skrah'
closed = True
closed_date = <Date 2012-11-02.17:25:55.915>
closer = 'skrah'
components = []
creation = <Date 2012-08-29.17:07:08.653>
creator = 'skrah'
dependencies = []
files = ['27058', '27085']
hgrepos = []
issue_num = 15814
keywords = ['patch']
message_count = 51.0
messages = ['169398', '169403', '169404', '169408', '169409', '169411', '169415', '169416', '169417', '169425', '169440', '169450', '169451', '169497', '169498', '169499', '169508', '169510', '169515', '169622', '169626', '169627', '169633', '169636', '169638', '169641', '169642', '169643', '169644', '169645', '169648', '169654', '169655', '169657', '169659', '169682', '169693', '169694', '169700', '169754', '169755', '169757', '169760', '169800', '169801', '170051', '170052', '170092', '173201', '173203', '174542']
nosy_count = 15.0
nosy_names = ['loewis', 'georg.brandl', 'mark.dickinson', 'ncoghlan', 'belopolsky', 'pitrou', 'vstinner', 'christian.heimes', 'Arfrever', 'skrah', 'meador.inge', 'Alexander.Belopolsky', 'BreamoreBoy', 'python-dev', 'Dag.Sverre.Seljebotn']
pr_nums = []
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'behavior'
url = 'https://bugs.python.org/issue15814'
versions = ['Python 3.4']

[skrah]

The new PEP-3118 equality definition from bpo-15573 that is based
on element-wise comparisons breaks the equality-hash invariant:

>>> from _testbuffer import ndarray
>>> x = ndarray([1,2,3], shape=[3], format='f')
>>> y = ndarray([1,2,3], shape=[3], format='B')
>>> a = memoryview(x)
>>> b = memoryview(y)
>>> a == b
True
>>> hash(a) == hash(b)
False
>>>

[loewis]

I think the proper solution is to make memoryview objects unhashable. Any other approach will have flaws of some kind.

[pitrou]

I think the proper solution is to make memoryview objects unhashable.

Disagreed. If memoryviews are to be bytes-like objects they should be
hashable (at least when readonly).

Any other approach will have flaws of some kind.

Not more so than equality between memoryviews.

[loewis]

Am 29.08.12 20:01, schrieb Antoine Pitrou:

> I think the proper solution is to make memoryview objects unhashable.

Disagreed. If memoryviews are to be bytes-like objects they should be
hashable (at least when readonly).

So what specific hash algorithm do you propose?

> Any other approach will have flaws of some kind.

Not more so than equality between memoryviews.

Well, memoryviews now have a definition of equality as discussed in
bpo-15573. You may disagree whether it's a useful definition, but I
don't believe it has actual flaws (in the sense that it is incorrect
or inconsistent).

My claim is that any hash definition for memoryviews will have a
*fundamental* flaw, failing to provide the basic property
that A==B must imply hash(A)==hash(B), making it actually work
incorrectly (when used for its primary application, namely keys
in dictionaries).

[pitrou]

Am 29.08.12 20:01, schrieb Antoine Pitrou:
>> I think the proper solution is to make memoryview objects unhashable.
>
> Disagreed. If memoryviews are to be bytes-like objects they should be
> hashable (at least when readonly).

So what specific hash algorithm do you propose?

The current algorithm works well in conjunction with bytes objects.

My claim is that any hash definition for memoryviews will have a
*fundamental* flaw, failing to provide the basic property
that A==B must imply hash(A)==hash(B), making it actually work
incorrectly

Why is there such a fundamental flaw?

[loewis]

Am 29.08.12 21:06, schrieb Antoine Pitrou:

> So what specific hash algorithm do you propose?

The current algorithm works well in conjunction with bytes objects.

That's about the only type if works for.

> My claim is that any hash definition for memoryviews will have a
> *fundamental* flaw, failing to provide the basic property
> that A==B must imply hash(A)==hash(B), making it actually work
> incorrectly

Why is there such a fundamental flaw?

The current algorithm is flawed as described in Stefan's original
message: two objects compare equal, yet hash different. That means
that if you use them as dictionary keys, you may end up with two
different values for the "same" key, depending on the size of the
dictionary (as the modulo operation in the dictionary still may
map the different hashes to the same dictionary slot).

In general, since memoryview(obj)==obj, it would be necessary that
hash(memoryview(obj))==hash(obj). However, since memoryview cannot
know what hashing algorithm obj uses, it cannot compute the hash
value with the same algorithm.

IOW, hashing is mutually exclusive with comparison with the
underlying object, unless you know what the hash algorithm
of the underlying object is.

So restricting tp_hash to memoryview objects where the underlying
object is the bytes type would work.

[skrah]

Martin v. L??wis <report@bugs.python.org> wrote:

In general, since memoryview(obj)==obj, it would be necessary that
hash(memoryview(obj))==hash(obj). However, since memoryview cannot
know what hashing algorithm obj uses, it cannot compute the hash
value with the same algorithm.

In the memoryview-hash thread on python-dev [1] this objection was
addressed by demanding from exporters that they all use:

hash(x) == hash(x.tobytes())

Since the previous equality concept was also based on
x.tobytes() == y.tobytes(), this wasn't a problem.

The new equality definition and any possible new hash definition should
probably also be part of the buffer API documentation, since they
aren't memoryview specific.

[1] http://mail.python.org/pipermail/python-dev/2011-November/114459.html

[skrah]

And since memory_richcompare() and any potentially compatible hash function
are quite tricky to implement by now, perhaps the generally useful parts
could be exposed as PyBuffer_RichCompareBool() and PyBuffer_Hash().

[loewis]

Am 29.08.12 22:04, schrieb Stefan Krah:

In the memoryview-hash thread on python-dev [1] this objection was
addressed by demanding from exporters that they all use:

hash(x) == hash(x.tobytes())

Since the previous equality concept was also based on
x.tobytes() == y.tobytes(), this wasn't a problem.

In the light of this requirement, it's even more difficult to ask
people that they change their hashing, since some exporters may already
comply with that original request.

The new equality definition and any possible new hash definition should
probably also be part of the buffer API documentation, since they
aren't memoryview specific.

That's not true: they *are* memoryview-specific. The notion of equality
is entirely one of memoryview objects, not of buffers.

I still maintain that specifying hashing for memoryviews under the
new equality definition is just not feasible, and that we should give
up on it (except perhaps supporting the hashing of bytes views).
I also question whether it is useful to hash arbitrarily-shaped
read-only buffers (along with questioning whether people will actually
*have* arbitrarily-shaped read-only buffers).

Stefan: please do propose a semantics also along with proposing interfaces.

[ncoghlan]

My perspective is that hashing a memoryview only makes sense when the memoryview is read-only and "m == m.tobytes()" (i.e. it's a C contiguous 1D view of bytes, either because that's what the original object exported as a buffer or because the view has been cast that way)

So, I think we should document that restriction in What's New and the memoryview docs for 3.3.0, and actually enforce it in 3.3.1 by raising ValueError from hash(m) when the assumption of a 1D C contiguous bytes view is violated (the "read-only" restriction is already enforced).

In previous versions, this constraint didn't need to be explicitly enforced, since memoryview basically treated *everything* as a 1D C contiguous view of bytes.

[skrah]

Martin v. L??wis <report@bugs.python.org> wrote:

> hash(x) == hash(x.tobytes())
In the light of this requirement, it's even more difficult to ask
people that they change their hashing, since some exporters may already
comply with that original request.

I don't think so. memoryview.__hash__() is new in 3.3 and the requirement
is not documented at all in the general PEP-3118 sections.

[Adding Stefan Behnel to nosy, since Cython is pretty quick to pick up
new features.]

> The new equality definition and any possible new hash definition should
> probably also be part of the buffer API documentation, since they
> aren't memoryview specific.

That's not true: they *are* memoryview-specific. The notion of equality
is entirely one of memoryview objects, not of buffers.

Could you name a part of the equality definition that is memoryview-specific?

I still maintain that specifying hashing for memoryviews under the
new equality definition is just not feasible, and that we should give
up on it (except perhaps supporting the hashing of bytes views).
I also question whether it is useful to hash arbitrarily-shaped
read-only buffers (along with questioning whether people will actually
*have* arbitrarily-shaped read-only buffers).

Useful, perhaps. I don't know if it is worth the effort though. We
could restrict hashing to contiguous bytes views in 3.3.1.

[skrah]

Here's a doc patch restricting the hash to formats 'B', 'b' and 'c'.
I think non-contiguous views are fine: both __eq__() and tobytes()
handle these, so the equality-hash invariant is preserved.

[loewis]

Am 30.08.12 11:24, schrieb Stefan Krah:
>>> The new equality definition and any possible new hash definition should
>>> probably also be part of the buffer API documentation, since they
>>> aren't memoryview specific.
>>
>> That's not true: they *are* memoryview-specific. The notion of equality
>> is entirely one of memoryview objects, not of buffers.
>
> Could you name a part of the equality definition that is memoryview-specific?

As literally spelled out, it starts with "a memoryview and a PEP-3118
exporter". But I was actually thinking of the implementation...

In any case, I'm skeptical that this is a useful extension to the buffer
interface. You would imply "two exporters are equal iff their exported
buffers are equal". I think this is asking too much.