Bug 2181 – Constant-time std.gc.removeRange

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

Created attachment 260 GC patch for constant-time removeRange

addRange and removeRange are now log(n) since this pull request was merged: https://github.com/D-Programming-Language/druntime/pull/788/ I think we can close this.