www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - [Issue 12245] New: BinaryHeap exhibits quadratic performance in debug mode

reply d-bugmail puremagic.com writes:
https://d.puremagic.com/issues/show_bug.cgi?id=12245

           Summary: BinaryHeap exhibits quadratic performance in debug
                    mode
           Product: D
           Version: D2
          Platform: All
        OS/Version: All
            Status: NEW
          Severity: normal
          Priority: P2
         Component: Phobos
        AssignedTo: nobody puremagic.com
        ReportedBy: sludwig outerproduct.org


--- Comment #0 from Sönke Ludwig <sludwig outerproduct.org> 2014-02-25 00:26:27
PST ---
BinaryHeap.insert, conditionalInsert and replaceFront all call assertValid, 
which goes through the complete heap to check for correct structure. This 
results in unusable performance in debug mode due to the quadratic run time. 
Arguably, such costly algorithm validation should be left for a unit test 
instead.

-- 
Configure issuemail: https://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Feb 25 2014
next sibling parent d-bugmail puremagic.com writes:
https://d.puremagic.com/issues/show_bug.cgi?id=12245


Ivan Kazmenko <gassa mail.ru> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |gassa mail.ru
           See Also|                            |https://d.puremagic.com/iss
                   |                            |ues/show_bug.cgi?id=12246


--- Comment #1 from Ivan Kazmenko <gassa mail.ru> 2014-02-25 01:05:26 PST ---
A similar issue with RedBlackTree container:

https://d.puremagic.com/issues/show_bug.cgi?id=12246

-- 
Configure issuemail: https://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Feb 25 2014
prev sibling next sibling parent d-bugmail puremagic.com writes:
https://d.puremagic.com/issues/show_bug.cgi?id=12245



--- Comment #2 from Ivan Kazmenko <gassa mail.ru> 2014-02-25 01:11:33 PST ---
I think implying "unittest => slow but checked containers" is not the way to
go, either.  Imagine a module making heavy use of containers and just wishing
to run the module's own unittests.  With such implication, there would be no
fast way to do that.  Or is there a way to import the generic container from
std.container without propagating the "-unittest" flag?  It's a generic after
all, so it can't be compiled separately, right?

A better way would be to (create and) mention a version flag needed for
container debugging in the documentation for the respective container.

-- 
Configure issuemail: https://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Feb 25 2014
prev sibling next sibling parent d-bugmail puremagic.com writes:
https://d.puremagic.com/issues/show_bug.cgi?id=12245


Peter Alexander <peter.alexander.au gmail.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |peter.alexander.au gmail.co
                   |                            |m


--- Comment #3 from Peter Alexander <peter.alexander.au gmail.com> 2014-03-02
08:38:05 PST ---
I have put them in debug(BinaryHeap)

https://github.com/D-Programming-Language/phobos/pull/1976

-- 
Configure issuemail: https://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Mar 02 2014
prev sibling next sibling parent d-bugmail puremagic.com writes:
https://d.puremagic.com/issues/show_bug.cgi?id=12245



--- Comment #4 from github-bugzilla puremagic.com 2014-03-02 08:39:32 PST ---
Commits pushed to master at https://github.com/D-Programming-Language/phobos

https://github.com/D-Programming-Language/phobos/commit/2a32a6382167627aab2318093a93b9987b0b8417
Fix Issue 12245 - BinaryHeap expensive in -debug

https://d.puremagic.com/issues/show_bug.cgi?id=12245

https://github.com/D-Programming-Language/phobos/commit/43d01952ac09ac451bb664c961e006d489c6f665
Merge pull request #1976 from Poita/bug12245

Fix Issue 12245 - BinaryHeap expensive in -debug

-- 
Configure issuemail: https://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Mar 02 2014
prev sibling parent d-bugmail puremagic.com writes:
https://d.puremagic.com/issues/show_bug.cgi?id=12245


Alex Rĝnne Petersen <alex lycus.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
                 CC|                            |alex lycus.org
         Resolution|                            |FIXED


-- 
Configure issuemail: https://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Mar 02 2014