A Web-based News Reader
| Subject | Feature Req.+Patch: O(1) removeRange | ||||||||||||||||||||||||
| From | downs <default_357-line@yahoo.de> | ||||||||||||||||||||||||
| Date | Wed, 25 Jun 2008 18:10:16 +0200 | ||||||||||||||||||||||||
| Newsgroups | digitalmars.D | ||||||||||||||||||||||||
| Attachment(s) | phobos_gc_constant_time_removeRange.patch | ||||||||||||||||||||||||
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 | |||||||||||||||||||||||||
diff -Nur --exclude aaA.d --exclude math.d dgcc/d/phobos/internal/gc/gc.d gcc-4.2.4/gcc/d/phobos/internal/gc/gc.d --- dgcc/d/phobos/internal/gc/gc.d 2008-03-07 16:55:56.000000000 +0100 +++ gcc-4.2.4/gcc/d/phobos/internal/gc/gc.d 2008-06-25 17:42:38.000000000 +0200 @@ -56,8 +56,11 @@ void addRoot(void *p) { _gc.addRoot(p); } void removeRoot(void *p) { _gc.removeRoot(p); } -void addRange(void *pbot, void *ptop) { _gc.addRange(pbot, ptop); } +void addRange(void *pbot, void *ptop, size_t* target = null) { + _gc.addRange(pbot, ptop, target); +} void removeRange(void *pbot) { _gc.removeRange(pbot); } +void removeRange(size_t index) { _gc.removeRange(index); } void fullCollect() { _gc.fullCollect(); } void fullCollectNoStack() { _gc.fullCollectNoStack(); } void genCollect() { _gc.genCollect(); } diff -Nur --exclude aaA.d --exclude math.d dgcc/d/phobos/internal/gc/gcx.d gcc-4.2.4/gcc/d/phobos/internal/gc/gcx.d --- dgcc/d/phobos/internal/gc/gcx.d 2008-06-18 19:36:26.000000000 +0200 +++ gcc-4.2.4/gcc/d/phobos/internal/gc/gcx.d 2008-06-25 18:00:39.000000000 +0200 @@ -343,6 +343,7 @@ // // // + import std.stdio: writefln; private void *mallocNoSync(size_t size) { assert(size != 0); @@ -353,6 +354,7 @@ //debug(PRINTF) printf("GC::malloc(size = %d, gcx = %p)\n", size, gcx); assert(gcx); //debug(PRINTF) printf("gcx.self = %x, pthread_self() = %x\n", gcx.self, pthread_self()); + //writefln("malloc: pre buckets: ", gcx.bucket); size += SENTINEL_EXTRA; // Compute size bin @@ -404,6 +406,7 @@ // Return next item from free list gcx.bucket[bin] = (cast(List *)p).next; + auto test = *gcx.bucket[bin]; // trigger segv early cstring.memset(p + size, 0, binsize[bin] - size); //debug(PRINTF) printf("\tmalloc => %x\n", p); debug (MEMSTOMP) cstring.memset(p, 0xF0, size); @@ -722,7 +725,8 @@ List *list = cast(List *)p; debug (MEMSTOMP) cstring.memset(p, 0xF2, binsize[bin]); - + + if (auto p = gcx.bucket[bin]) auto test = *p; // test list.next = gcx.bucket[bin]; gcx.bucket[bin] = list; } @@ -966,7 +970,7 @@ /** * add range to scan for roots */ - void addRange(void *pbot, void *ptop) + void addRange(void *pbot, void *ptop, size_t* target = null) { if (!pbot || !ptop) { @@ -976,11 +980,11 @@ //debug(PRINTF) printf("+GC.addRange(pbot = x%x, ptop = x%x)\n", pbot, ptop); if (!thread_needLock()) { - gcx.addRange(pbot, ptop); + gcx.addRange(pbot, ptop, target); } else synchronized (gcLock) { - gcx.addRange(pbot, ptop); + gcx.addRange(pbot, ptop, target); } //debug(PRINTF) printf("-GC.addRange()\n"); } @@ -1006,6 +1010,20 @@ } } + /** + * remove range with index + */ + void removeRange(size_t index) + { + if (!thread_needLock()) + { + gcx.removeRange(index); + } + else synchronized (gcLock) + { + gcx.removeRange(index); + } + } /** * do full garbage collection @@ -1211,6 +1229,7 @@ struct Range { + size_t* target; void *pbot; void *ptop; } @@ -1417,7 +1436,7 @@ /** * */ - void addRange(void *pbot, void *ptop) + void addRange(void *pbot, void *ptop, size_t* target = null) { debug(THREADINVARIANT) { debug(PRINTF) printf("Thread %x ", pthread_self()); } debug(PRINTF) printf("%x.Gcx::addRange(%x, %x), nranges = %d\n", this, pbot, ptop, nranges); @@ -1438,7 +1457,8 @@ } ranges[nranges].pbot = pbot; ranges[nranges].ptop = ptop; - nranges++; + ranges[nranges].target = target; + nranges ++; } @@ -1453,8 +1473,9 @@ { if (ranges[i].pbot == pbot) { - nranges--; - cstring.memmove(ranges + i, ranges + i + 1, (nranges - i) * ranges[0].sizeof); + /*nranges--; + cstring.memmove(ranges + i, ranges + i + 1, (nranges - i) * ranges[0].sizeof);*/ + removeRange(i); return; } } @@ -1466,6 +1487,17 @@ //assert(zero); } + void removeRange(size_t index) { + if (index !< nranges) + throw new Exception("removeRange: No such index!"); + if (index < nranges - 1) { + ranges[index] = ranges[nranges - 1]; + if (ranges[index].target) + *ranges[index].target = index; + } + nranges--; + } + /** * Find Pool that pointer is in. diff -Nur --exclude aaA.d --exclude math.d dgcc/d/phobos/std/gc.d gcc-4.2.4/gcc/d/phobos/std/gc.d --- dgcc/d/phobos/std/gc.d 2007-10-16 21:02:09.000000000 +0200 +++ gcc-4.2.4/gcc/d/phobos/std/gc.d 2008-06-25 17:50:43.000000000 +0200 @@ -52,12 +52,13 @@ /** * Add range to scan for roots. */ -void addRange(void *pbot, void *ptop); // add range to scan for roots +void addRange(void *pbot, void *ptop, size_t* target = null); /** * Remove range. */ void removeRange(void *pbot); // remove range +void removeRange(size_t index); // remove range by index /** * Mark a gc allocated block of memory as possibly containing pointers. | |||||||||||||||||||||||||
| |||||||||||||||||||||||||
Feature Req.+Patch: O(1) removeRange (Current message)
