Skip to content

speed of ecdf #964

Closed
Closed

Description

@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?

Activity

  1. devmotion commented on Oct 9, 2025

    @devmotion
    Member

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

    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].

  2. andferrari commented on Oct 9, 2025

    @andferrari
    Author

    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.
  3. devmotion commented on Oct 9, 2025

    @devmotion
    Member

    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.
  4. devmotion commented on Oct 10, 2025

    @devmotion
    Member

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

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

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions