Strange behaviour with tuples as keys in dictionary

49 views
Skip to first unread message

Michael Hull

unread,
Jan 2, 2017, 7:45:29 AM1/2/17
to brython
Hi Everyone,
Happy New Year!
Thanks for the continued work on Brython, it is great. Your time on the project is appreciated.

I have been using it in a project, and have come across some unexpected behaviour with keys for dictionary:
Here is a minimum working example:

<html>
<head>
<script type="text/javascript"
</script>
<!--
<script type="text/javascript"
</script>
-->

<script type="text/python">
from browser import document, alert, window

def pyEntry():

print( hash( (1,3) ) )
print( hash( (-1,3) ) )
print( hash( (1,-3) ) )
print( hash( (-1,-3) ) )

d = {}
d[ (1,3) ] = None
d[ (-1,3) ] = None
d[ (1,-3) ] = None
d[ (-1,-3) ] = None

#d[ "JLKJ" ] = 2
print("Hello")
print( d )
window.pyEntry = pyEntry
</script>

<script>
function jsEntry() {
brython(1);
window.pyEntry()
}
</script>



</head>
<body onload="jsEntry()">
</body>
</html>

Gives the following output:

brython.js:4896 219750520

brython.js:4896 -219750522

brython.js:4896 -219750522

brython.js:4896 219750520

brython.js:4896 Eq: False

brython.js:4896 Hello

brython.js:4896 {(-1, -3): None, (1, -3): None}

I am not familiar with Python dictionary implementations, but I think its hashing with open addressing
It looks like the hashes for different tuples are the same. (I think this is allowed)
It looks like they compare for equality correctly.
Perhaps there is something wrong with the dictionary lookup implementation, that there is not a check for equality, as well as the hash??

Should I file a bug-report somewhere?

Best wishes,


Mike

Pierre Quentel

unread,
Jan 2, 2017, 3:49:05 PM1/2/17
to brython
Thanks for the report. Normally bugs are reported on the Github site, but it's ok to report them in this group too.

There was a bug in the tuple hash implementation. I modified it, using a custom version of the c_mul function used in the CPython implementation. I'm not sure it's 100% accurate but it fixes the bug you report.

Michael Hull

unread,
Jan 3, 2017, 8:10:28 AM1/3/17
to brython
Thanks for getting back for quickly and fixing the bug Pierre.

I just wonder, is the dictionary implementation correct though -- even if hashes compare equally, I think the dictionary should still look at the test for equality as well?
(I mean even with colliding hashes, since the equals function does the right the the dictionary should still have 4 entries?)

Best wishes,


Mike

Pierre Quentel

unread,
Jan 5, 2017, 4:54:12 PM1/5/17
to brython


Le mardi 3 janvier 2017 14:10:28 UTC+1, Michael Hull a écrit :
Thanks for getting back for quickly and fixing the bug Pierre.

I just wonder, is the dictionary implementation correct though -- even if hashes compare equally, I think the dictionary should still look at the test for equality as well?
(I mean even with colliding hashes, since the equals function does the right the the dictionary should still have 4 entries?)

Best wishes,


Mike

I must admit I didn't know about this, and the current Brython implementation only relies on hash.
Can you open an issue in the tracker ? I don't promise it will be on top of the priorities, the issues with colliding hashes should be rare in real world situations.

Michael Hull

unread,
Jan 9, 2017, 4:36:23 AM1/9/17
to bry...@googlegroups.com
HI Pierre,
Yes I will, I will also try and look at the Brython implementation if I get a few minutes :)

Best wishes, and once again, thankyou for your work on such a great project.

Mike
]


--
You received this message because you are subscribed to a topic in the Google Groups "brython" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/brython/DGZQGX_OcHw/unsubscribe.
To unsubscribe from this group and all its topics, send an email to brython+unsubscribe@googlegroups.com.
To post to this group, send email to bry...@googlegroups.com.
 To view this discussion on the web visit https://groups.google.com/d/msgid/brython/35cc10e3-f985-4921-90e2-b4ffe9eff26e%40googlegroups.com.

For more options, visit https://groups.google.com/d/optout.

Reply all
Reply to author
Forward
0 new messages