Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Regression: hash([1,2,[3]]) throws on 0.7 #26011

Closed
chethega opened this issue Feb 12, 2018 · 1 comment
Closed

Regression: hash([1,2,[3]]) throws on 0.7 #26011

chethega opened this issue Feb 12, 2018 · 1 comment
Assignees
@nalimilan
Labels
domain:arrays [a, r, r, a, y, s] domain:hashing kind:bug Indicates an unexpected problem or unintended behavior kind:regression Regression in behavior compared to a previous version

Comments

@chethega
Copy link
Contributor 

versioninfo()
#Julia Version 0.7.0-DEV.3943
#Commit dcc39f4d8d* (2018-02-09 22:47 UTC)

hash([1,2,[3]])

ERROR: MethodError: no method matching widen(::Type{Array{Int64,1}})
Closest candidates are:
  widen(::Type{T}) where T at operators.jl:729
  widen(::T) where T at operators.jl:728
  widen(::Type{Int32}) at int.jl:629
  ...
Stacktrace:
 [1] widen at ./operators.jl:729 [inlined]
 [2] widen(::Array{Int64,1}) at ./operators.jl:728
 [3] hash(::Array{Any,1}, ::UInt64) at ./abstractarray.jl:2007
 [4] hash(::Array{Any,1}) at ./hashing.jl:18
 [5] top-level scope

Works fine on Julia Version 0.6.2 Commit d386e40 (2017-12-13 18:08 UTC).
@StefanKarpinski StefanKarpinski added domain:arrays [a, r, r, a, y, s] kind:bug Indicates an unexpected problem or unintended behavior labels Feb 12, 2018
@nalimilan
Copy link
Member

#25822 is one way of fixing this.

@JeffBezanson JeffBezanson added the kind:regression Regression in behavior compared to a previous version label Feb 14, 2018
@JeffBezanson JeffBezanson added this to the 1.0.x milestone Apr 16, 2018
@chethega chethega mentioned this issue Jun 29, 2018
Closed
@nalimilan nalimilan mentioned this issue Jun 30, 2018
Merged
mbauman added a commit that referenced this issue Jul 26, 2018
@mbauman
Add tests
0e97f65 
Fixes #27865 and fixes #26011.
KristofferC pushed a commit that referenced this issue Feb 11, 2019
@mbauman @KristofferC
Simpler array hashing (#26022)
351af92 
    Goal: Hash approximately log(N) entries with a higher density of hashed elements
    weighted towards the end and special consideration for repeated values. Colliding
    hashes will often subsequently be compared by equality -- and equality between arrays
    works elementwise forwards and is short-circuiting. This means that a collision
    between arrays that differ by elements at the beginning is cheaper than one where the
    difference is towards the end. Furthermore, blindly choosing log(N) entries from a
    sparse array will likely only choose the same element repeatedly (zero in this case).

    To achieve this, we work backwards, starting by hashing the last element of the
    array. After hashing each element, we skip the next `fibskip` elements, where
    `fibskip` is pulled from the Fibonacci sequence -- Fibonacci was chosen as a simple
    ~O(log(N)) algorithm that ensures we don't hit a common divisor of a dimension and
    only end up hashing one slice of the array (as might happen with powers of two).
    Finally, we find the next distinct value from the one we just hashed.

Fixes #27865 and fixes #26011.

Fixes #26034
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@nalimilan nalimilan

Labels
domain:arrays [a, r, r, a, y, s] domain:hashing kind:bug Indicates an unexpected problem or unintended behavior kind:regression Regression in behavior compared to a previous version
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
4 participants
@StefanKarpinski @JeffBezanson @nalimilan @chethega