performance regression in hash(::Perm) in Julia 0.7

[kalmarek]

this was probably introduced during transition to julia-0.7:

julia> versioninfo()
Julia Version 0.6.4
Commit 9d11f62bcb (2018-07-09 19:09 UTC)
Platform Info:
  OS: Linux (x86_64-pc-linux-gnu)
  CPU: Intel(R) Core(TM) i5-6200U CPU @ 2.30GHz
  WORD_SIZE: 64
  BLAS: libopenblas (USE64BITINT DYNAMIC_ARCH NO_AFFINITY Haswell MAX_THREADS=16)
  LAPACK: libopenblas64_
  LIBM: libopenlibm
  LLVM: libLLVM-3.9.1 (ORCJIT, skylake)

julia> function test(n)
             res = UInt(0)
             for p in Generic.elements!(PermGroup(n))
               res = hash(p, res)
             end
             return res
             end
test (generic function with 1 method)

julia> @time test(5)
  0.108565 seconds (34.74 k allocations: 1.877 MiB)
0x0f2cd8ba75f36698

julia> @time test(5)
  0.000009 seconds (10 allocations: 528 bytes)
0x0f2cd8ba75f36698

julia> @time test(6)
  0.000319 seconds (10 allocations: 528 bytes)
0xdedb7b56542cbe1a

julia> @time test(10)
  0.346696 seconds (10 allocations: 592 bytes)
0xeba1b46577ab914c

julia> versioninfo()
Julia Version 1.0.3
Commit 099e826241 (2018-12-18 01:34 UTC)
Platform Info:
  OS: Linux (x86_64-pc-linux-gnu)
  CPU: Intel(R) Core(TM) i5-6200U CPU @ 2.30GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-6.0.0 (ORCJIT, skylake)
Environment:
  JULIA_NUM_THREADS = 2

julia> function test(n)
             res = UInt(0)
             for p in Generic.elements!(PermGroup(n))
               res = hash(p, res)
             end
             return res
             end
test (generic function with 1 method)

julia> @time test(5)
  0.145024 seconds (236.19 k allocations: 11.687 MiB, 4.45% gc time)
0x3a8569f5ec15165c

julia> @time test(5)
  0.000046 seconds (129 allocations: 4.234 KiB)
0x3a8569f5ec15165c

julia> @time test(6)
  0.000185 seconds (729 allocations: 22.984 KiB)
0x1b1548da152f74a8

julia> @time test(10)
  1.058082 seconds (3.63 M allocations: 110.743 MiB, 1.27% gc time)
0x009115240712e5c5

[thofma]

The allocations are fixed in #248, but the runtime regression persists. I am currently building latest julia to see if the regression is fixed there.

[kalmarek]

indeed:

julia> using AbstractAlgebra
[ Info: Recompiling stale cache file /home/kalmar/.julia/compiled/v1.1/AbstractAlgebra/b8V2b.ji for AbstractAlgebra [c3fe647b-3220-5bb0-a1ea-a7954cac585d]

julia> function test(n)
             res = UInt(0)
             for p in Generic.elements!(PermGroup(n))
               res = hash(p, res)
             end
             return res
             end
test (generic function with 1 method)

julia> @time test(5)
  0.147882 seconds (242.94 k allocations: 11.902 MiB, 5.39% gc time)
0x3a8569f5ec15165c

julia> @time test(5)
  0.000026 seconds (10 allocations: 528 bytes)
0x3a8569f5ec15165c

julia> @time test(6)
  0.000150 seconds (10 allocations: 528 bytes)
0x1b1548da152f74a8

julia> @time test(10)
  0.961476 seconds (10 allocations: 592 bytes)
0x009115240712e5c5

julia> versioninfo()
Julia Version 1.1.0
Commit 80516ca202 (2019-01-21 21:24 UTC)
Platform Info:
  OS: Linux (x86_64-pc-linux-gnu)
  CPU: Intel(R) Core(TM) i5-6200U CPU @ 2.30GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-6.0.1 (ORCJIT, skylake)
Environment:
  JULIA_NUM_THREADS = 2

thanks for looking into this; I opened it more for a reminder for myself, but i'm rather busy with other stuff

[thofma]

It is not fixed on

julia> versioninfo()
Julia Version 1.2.0-DEV.221
Commit 8fa0645ef1 (2019-01-28 01:13 UTC)
Platform Info:
  OS: Linux (x86_64-linux-gnu)
  CPU: Intel(R) Core(TM) i7-7700 CPU @ 3.60GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-6.0.1 (ORCJIT, skylake)

[rfourquet]

So almost all the time spent in the loop seems to come from hash itself, not the iteration on elements!.
I don't have a Julia 0.6 available, but there has been a lot of discussions (which I followed distantly) in the transition 0.6 -> 0.7 on hashing arrays, one reason being that hashing Vector and UnitRange should be consistent. My guess is that as a result it became quite slower. And when you look at the code for hash(::AbstractArray, ::UInt), there seems to be a lot of overhead compared to what we need here to hash a permutation.

I'm changing the title of the issue accordingly, feel free to revert if you disagree.

[thofma]

It is very scary that hash(Vector{UInt}) is 5x slower then necessary. I have used Dict with keys of type Vector{Int} or Vector{UInt} a lot recently. This could explain why it was not as fast as I had hoped. Thanks!

[kalmarek]

yeah, with the new version of hash we have

julia> @time test(10)
  0.276211 seconds (5 allocations: 416 bytes)
0x8fef8d8d2a72885b

old hash:

julia> @time test(10)
  1.016941 seconds (5 allocations: 416 bytes)
0x009115240712e5c5

many thanks @rfourquet, I forgot about this issue!