speed of ecdf

[andferrari]

ecdf uses a sortperm to sort the vector of samples given in X

ord = sortperm(X)
ECDF(X[ord], isempty(weights) ? weights : Weights(weights[ord]))

But sortperm(X) is much slower than sort(X).
Why not use a simple sort?

[devmotion]

It seems you're referring to the use of sortperm in

StatsBase.jl/src/empirical.jl

Lines 60 to 61 in 92d1674

	ord = sortperm(X)
	ECDF(X[ord], isempty(weights) ? weights : Weights(weights[ord]))

?

If weights are present (ie not empty), then sortperm is needed since the weights have to permuted in the same way as the samples.

However, if weights are not present (ie if isempty(weights)), it seems one could just use sort if that is more performant [I haven't done any benchmarking].

[andferrari]

Thank you for your answer. Here is a short benchmark:

julia> x = randn(10_000_000);

julia> @benchmark sortperm(x)
BenchmarkTools.Trial: 10 samples with 1 evaluation per sample.
 Range (min … max):  509.166 ms … 580.831 ms  ┊ GC (min … max): 0.07% … 11.35%
 Time  (median):     514.216 ms               ┊ GC (median):    0.07%
 Time  (mean ± σ):   523.034 ms ±  21.743 ms  ┊ GC (mean ± σ):  1.44% ±  3.55%

  ▁█ █▁ ▁          ▁▁                                         ▁  
  ██▁██▁█▁▁▁▁▁▁▁▁▁▁██▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁█ ▁
  509 ms           Histogram: frequency by time          581 ms <

 Memory estimate: 114.45 MiB, allocs estimate: 6.

julia> @benchmark sort(x)
BenchmarkTools.Trial: 57 samples with 1 evaluation per sample.
 Range (min … max):  86.369 ms … 149.330 ms  ┊ GC (min … max): 0.34% … 41.55%
 Time  (median):     87.259 ms               ┊ GC (median):    0.34%
 Time  (mean ± σ):   88.534 ms ±   8.272 ms  ┊ GC (mean ± σ):  1.65% ±  5.51%

     ▂▂▁█▂                                                      
  ▃▅▆██████▆▆▁▅▃▁▃▁▁▁▁▁▃▁▁▁▁▁▁▃▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▃ ▁
  86.4 ms         Histogram: frequency by time         94.4 ms <

 Memory estimate: 114.47 MiB, allocs estimate: 12.

[devmotion]

It seems I can reproduce this, on Julia 1.12 I get

julia> using BenchmarkTools

julia> x = randn(10_000_000);

julia> @benchmark sortperm($x)
BenchmarkTools.Trial: 7 samples with 1 evaluation per sample.
 Range (min … max):  685.402 ms … 775.997 ms  ┊ GC (min … max): 0.04% … 11.19%
 Time  (median):     690.798 ms               ┊ GC (median):    0.25%
 Time  (mean ± σ):   718.565 ms ±  41.807 ms  ┊ GC (mean ± σ):  3.52% ±  5.34%

  █▁ ▁                          ▁                            ▁▁
  ██▁█▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁█▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁██ ▁
  685 ms           Histogram: frequency by time          776 ms <

 Memory estimate: 189.38 MiB, allocs estimate: 8.

julia> @benchmark sort($x)
BenchmarkTools.Trial: 35 samples with 1 evaluation per sample.
 Range (min … max):  129.740 ms … 231.416 ms  ┊ GC (min … max):  0.00% … 39.97%
 Time  (median):     130.685 ms               ┊ GC (median):     0.49%
 Time  (mean ± σ):   146.942 ms ±  32.265 ms  ┊ GC (mean ± σ):  10.78% ± 14.57%

  █
  █▃▃▃▁▄▃▁▃▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▃▃▁▁▃▁▁▃▁▁▁▁▁▃ ▁
  130 ms           Histogram: frequency by time          231 ms <

 Memory estimate: 189.39 MiB, allocs estimate: 14.

[devmotion]

I opened a PR to improve performance in the unweighted case: #965