• via Digitalmars-d-bugs (38/39) Jan 18 2016 https://issues.dlang.org/show_bug.cgi?id=15583

via Digitalmars-d-bugs <digitalmars-d-bugs puremagic.com> writes:

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

          Issue ID: 15583
           Summary: [REG] topN without uniform can show quadratic
                    performance
           Product: D
           Version: D2
          Hardware: All
                OS: All
            Status: NEW
          Severity: regression
          Priority: P1
         Component: dmd
          Assignee: nobody puremagic.com
          Reporter: gassa mail.ru

After Phobos pull #3921
(https://github.com/D-Programming-Language/phobos/pull/3921), topN is
deterministic.  As a result, it can now show quadratic performance on certain
pre-generated inputs. This violates the stronger complexity guarantee it
previously had, when quadratic performance was highly unlikely on a
pre-generated input.

Here goes the test which shows quadratic behavior for the new version:
http://dpaste.dzfl.pl/e4b3bc26c3cf
(dpaste kills the slow code before it completes the task)

My local timings with "-O -release -noboundscheck -inline":
building Element array: 4989 msecs
checking Element array: 5018 msecs
checking int array: 626 msecs

With "-debug -unittest":
building Element array: 8384 msecs
checking Element array: 8380 msecs
checking int array: 2987 msecs

If we change the length MAX_N to something observable, say, 50, the array is:
[0, 536870911, 2, 536870911, 4, 536870911, 6, 36, 8, 33, 10, 35, 12, 536870911,
14, 32, 16, 34, 18, 536870911, 536870911, 22, 23, 21, 20, 1, 3, 5, 7, 9, 11,
13, 15, 17, 19, 31, 30, 536870911, 29, 536870911, 28, 536870911, 27, 536870911,
26, 536870911, 25, 536870911, 24, 536870911]

From this forum post:

http://forum.dlang.org/post/uicjhjwghtulzffnutut forum.dlang.org

--