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: nob...@puremagic.com Reporter: timothee.co...@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; } ---- --