www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - [Issue 2181] New: Constant-time std.gc.removeRange

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

           Summary: Constant-time std.gc.removeRange
           Product: D
           Version: 1.032
          Platform: All
        OS/Version: All
            Status: NEW
          Keywords: patch
          Severity: enhancement
          Priority: P2
         Component: Phobos
        AssignedTo: bugzilla digitalmars.com
        ReportedBy: default_357-line yahoo.de


When profiling my StackThreads benchmark, I discovered that removeRange was
taking up 90+% of my time.

Looking deeper, this seems to be because removeRange always scans the complete
array of ranges until it finds the correct one.

The proposed patch adds an optional size_t pointer to addRange, which points to
a variable intended to store the current index of the added range in the ranges
array. It is stored as a new field in the Range struct, and operations that
shuffle ranges around (like removeRange), update it.

Then, when removing a range, the pointer is passed to an overloaded removeRange
(in the form of a ref parameter, to prevent a race condition [see NG]). The
overloaded removeRange replaces the pointed-to index with the last index in the
array (updating its pointer), then reduces array size by one.

In my benchmark, this patch reduced time in removeRange to negligible, and
since it doesn't interact with the rest of Phobos, it shouldn't cause any
problems.

I thus request its inclusion into mainline Phobos 2. Since 1 is supposed to be
stable, I do not expect it to be included in Phobos1, although I will continue
to use it myself.

Thanks for any feedback,
 --feep


--
Jun 26 2008
parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=2181






Created an attachment (id=260)
 --> (http://d.puremagic.com/issues/attachment.cgi?id=260&action=view)
GC patch for constant-time removeRange


--
Jun 26 2008