Skip to content

sortperm on small inputs is slower on 1.9 than 1.8 #47811

Open

Description

It's about a 2x regression for smaller than 256 elements.

julia> for i in 1:12
           n = 2^i
           print(lpad(n, 4)); @btime sortperm(x) setup=(x=rand($n));
       end
   2  228.013 ns (2 allocations: 96 bytes)  =>    2  503.767 ns (4 allocations: 128 bytes)
   4  237.002 ns (2 allocations: 112 bytes) =>    4  521.963 ns (4 allocations: 144 bytes)
   8  260.322 ns (2 allocations: 144 bytes) =>    8  550.038 ns (4 allocations: 176 bytes)
  16  326.942 ns (2 allocations: 208 bytes) =>   16  742.277 ns (5 allocations: 432 bytes)
  32  481.206 ns (2 allocations: 352 bytes) =>   32  1.200 μs (5 allocations: 720 bytes)
  64  850.224 ns (2 allocations: 592 bytes) =>   64  2.091 μs (5 allocations: 1.17 KiB)
 128  2.159 μs (2 allocations: 1.08 KiB)    =>  128  4.026 μs (5 allocations: 2.17 KiB)
 256  5.409 μs (2 allocations: 2.14 KiB)    =>  256  8.060 μs (5 allocations: 4.30 KiB)
 512  17.091 μs (2 allocations: 4.14 KiB)   =>  512  15.894 μs (5 allocations: 8.30 KiB)
1024  44.933 μs (2 allocations: 8.14 KiB)   => 1024  33.661 μs (5 allocations: 16.30 KiB)
2048  99.723 μs (2 allocations: 16.14 KiB)  => 2048  71.643 μs (5 allocations: 32.30 KiB)
4096  220.581 μs (3 allocations: 32.06 KiB) => 4096  154.905 μs (7 allocations: 64.14 KiB)

julia> VERSION
v"1.8.3" => v"1.10.0-DEV.91"
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Assignees

No one assigned

    Labels

    performanceMust go fasterregressionRegression in behavior compared to a previous versionsortingPut things in order

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions