[Issue 15553] New: topN very inefficient [slower than sort, even for topN(0)] but should be O(n)

[via Digitalmars-d-bugs]

https://issues.dlang.org/show_bug.cgi?id=15553

          Issue ID: 15553
           Summary: topN very inefficient [slower than sort, even for
                    topN(0)] but should be O(n)
           Product: D
           Version: D2
          Hardware: x86
                OS: Mac OS X
            Status: NEW
          Severity: blocker
          Priority: P1
         Component: phobos
          Assignee: nobody at puremagic.com
          Reporter: timothee.cour2 at gmail.com

It's a serious bug because people are either generating slow code with topN or
are using sort instead of topN (as in
http://jackstouffer.com/blog/nd_slice.html)


----
module tests.bench_topn;

/+
testing:
test_sort, test_topn, test_topn_zeroth, test_max

$ldc_X -O3 -inline -release -boundscheck=off -mcpu=native -L=-L$dmd_build_D
-I=$phobos_D -of=/tmp/benchmark_ndslice $code/tests/bench_topn.d
/tmp/benchmark_ndslice
[640, 1248, 731, 146]

$dmd_069_X -O -inline -release -noboundscheck $code/tests/bench_topn.d
-of/tmp/benchmark_ndslice
/benchmark_ndslice
[746, 2357, 1440, 281]

=> topN slower than sort, and even topN(0) is slower than sort (but should be
same speed as max)
+/

import std.algorithm;
import std.random;

void test_sort(T)(T a) {
  a.sort();
}

void test_topn(T)(T a) {
  a.topN(a.length / 2);
}

// should be roughly as fast as test_max
void test_topn_zeroth(T)(T a) {
  a.topN(0);
}

void test_max(T)(T a) {
  static int counter;
  counter = a.reduce!max;
}

void fun() {
  alias T = ubyte;

  int n = 100;
  auto a = new T[n];
  foreach (ref ai; a)
    ai = cast(T)(uniform(0, T.max));

  auto iter = 1000000;
  import std.datetime;
  import std.stdio;
  import std.conv : to;
  import std.array;

  iter.benchmark!({ test_sort(a.dup); }, { test_topn(a.dup); }, {
test_topn_zeroth(a.dup); }, { test_max(a.dup); })[].map!(a =>
a.to!Duration.total!`msecs`).array.writeln;
}

void main() {
  fun;
}
----

--