www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Feature Req.+Patch: O(1) removeRange

reply downs <default_357-line yahoo.de> writes:
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit

When working with coroutines, the many removeRange calls can cause significant
slowdowns. This patch aims to address the problem.

It changes the Phobos GC's addRange to take an optional third parameter, a
pointer to a size_t.
If this pointer is non-null, its target will contain the current position of
the addedRange in the array of ranges.

When the array is reordered, for instance by removeRange, the moved ranges'
indexes are updated.

The size_t can be passed to removeRange for O(1) range removal.

Normal removeRange has been changed to call index-based removeRange instead, as
it is faster than memmove.

 --downs
Jun 25 2008
parent reply downs <default_357-line yahoo.de> writes:
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit

I forgot to remove some experimental stuff.

Sorry for that.
Jun 25 2008
parent reply downs <default_357-line yahoo.de> writes:
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit

And I found another bug. Due to the small size of the patch, I'm optimistic
that it's the last one.

(I forgot to set the target pointer in addRange)

Fixed patch attached.
Jun 25 2008
parent reply downs <default_357-line yahoo.de> writes:
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit

Aaaand another one!

This time, it's a race condition.

When two threads try to removeRange at the same time, the position of a Range
might change before the lock is engaged.

Fixed by passing the index by reference until inside the sync block.
Jun 25 2008
next sibling parent "Nick Sabalausky" <a a.a> writes:
"downs" <default_357-line yahoo.de> wrote in message 
news:g3tud7$h3r$1 digitalmars.com...
 Aaaand another one!

 This time, it's a race condition.

 When two threads try to removeRange at the same time, the position of a 
 Range might change before the lock is engaged.

 Fixed by passing the index by reference until inside the sync block.

"I am beginning to lose trust in my ability to code straight." Friends don't let friends drink and code ;)
Jun 25 2008
prev sibling next sibling parent "Jarrett Billingsley" <kb3ctd2 yahoo.com> writes:
"downs" <default_357-line yahoo.de> wrote in message 
news:g3tud7$h3r$1 digitalmars.com...
 Aaaand another one!

 This time, it's a race condition.

 When two threads try to removeRange at the same time, the position of a 
 Range might change before the lock is engaged.

 Fixed by passing the index by reference until inside the sync block.

Downs I think it's neat! /me supports downs' delicate ego.
Jun 25 2008
prev sibling parent Tom S <h3r3tic remove.mat.uni.torun.pl> writes:
downs wrote:
 Aaaand another one!
 (...)

These look pretty useful; Bump! // ++votes; -- Tomasz Stachowiak http://h3.team0xf.com/ h3/h3r3tic on #D freenode
Jun 28 2008