The problem with the D GC

[Sean Kelly]

Frits van Bommel wrote:
> Sean Kelly wrote:
>> Assuming this is a multithreaded app, you have to pay for two mutex 
>> locks for every concat operation.  So an expression like:
>>
>> a = b ~ c ~ d;
>>
>> would result in six locks of the mutex protecting the GC to perform 
>> allocations (I think anyway--I don't believe chained concats have 
>> special handling).  I think this would also result in two discarded 
>> temporary buffers for the GC to clean up later.  And since the Phobos 
>> GC scans all such blocks by default...
> 
> Chained concats *do* have special handling. See 
> phobos/internal/arraycat.d, _d_arraycatn() (first function in the file, 
> can't miss it).
> This function takes element size and number of arrays, followed by 
> C-style vararg arrays.
> And yes, it only allocates once :).

Oh good :)  I knew about the varargs but hadn't given the code a close 
enough look to be sure.

> By the way, how do you figure six locks? At two locks per concat, that 
> code only has two concats so even without above special handling 
> wouldn't it still only lock four times?

I miscounted :p  It would have been four without the special handling.

> Also: Why two locks per concat at all? A concat only requires one 
> allocation, so does a single alloc require two locks?
> (I haven't looked much into the GC code, so this is just curiosity)

The code in internal/gc/gc.d first checks the size of the array to see 
if a realloc is necessary, then it performs the realloc.  So worst case 
you're stuck with two locks per operation.  However, this may not be the 
case in the arraycat routines.  It's been a while since I've looked at them.

>> My patch will address the scanning issue, but it won't address the 
>> mutex issue--there's really no easy way to avoid that one.
> 
> What exactly do you mean by "the mutex issue"? Is using mutexes at all 
> the problem, or is it locking them too often per operation (i.e. more 
> than once per alloc)?

Too often per operation.  So given the vararg stuff you mentioned above, 
this isn't an issue IMO.  As it is, locks should only be acquired if the 
app is multithreaded, so this cost is only incurred if it's necessary. 
I think Phobos might actually lock in a few instances where it isn't 
strictly necessary, but I can't recall for certain.

> If you don't want to use them at all, I think the closest you'd get 
> would involve implementing thread-local heaps.
> But that would still require a mutex if you want to allow deleting an 
> object from a different thread than it was allocated in...

No it wouldn't--give each per-thread heap a lock-free free list.  But 
per-thread heaps for a GC are somewhat complicated.  I think you'd have 
to implement something like a read/write lock where the "writer" is 
actually the thread that wants to collect.


Sean