A bug in my code

[bearophile]

Jarrett Billingsley:

> They're both pretty inefficient.  Adding a root or range is pretty
> fast, it might have to resize its internal array.  But removing a root
> or range requires the linear traversal of the internal list of roots
> or ranges as well as copying every root/range after it down a slot,
> which is all very slow, as downs has found out

I have just read some of the relevant code:

for (size_t i = nranges; i--;) {
  if (ranges[i].pbot == pbot) {
    nranges--;
    cstring.memmove(ranges+i, ranges+i+1, (nranges-i) * ranges[0].sizeof);
    return;
  }
}

it's written in D, but it looks like C because I presume that you can't rely on the GC (to use a more efficient associative array (of or better a set) of Range structs) inside the code that implements the GC itself :-)
Even with that, if ranges are few, the slowdown is little.

The addRange() function doesn't seem to control if a given Range is already present, so it appends it again and again, I think. This may be okay, because if two sources define a Range as source for roots, then they both independently will take care of removing them, but the GC itself may slow down, because it looks from the  same starting points twice. So an associative Range->counter seems a better data structure, where the removeRange actually removes a range only of its counter goes to zero.

In that code I have also understood why Sergey Gromov has added 1 to the second pointer given to addRange():

/// Search a range of memory values and mark any pointers into the GC pool.
void mark(void *pbot, void *ptop) {
    void **p1 = cast(void **)pbot;
    void **p2 = cast(void **)ptop;
    uint changes = 0;
    for (; p1 < p2; p1++) {
...

It's an interval open to the right, indeed.


>(and patched, though it's not in the official GC yet).

Months ago a very gentle person has created a patch for the GC just for me, to reduce a lot a performance problem I have found, but I think that patch too is waiting still.
Where can I find the patch by downs (mostly to take a look)?
I presume the Tango GC doesn't suffer such performance problem.

Bye,
bearophile