Is this function pure?

[Bill Baxter]

Nathan Reed wrote:
> Bill Baxter wrote:
>> On the other hand the support for concurrency may consist of little 
>> more than a global mutex.  That means that the performance benefits of 
>> launching multiple threads might not be so great since they'll all 
>> just end up in a queued waiting for their turn to malloc.
>>
>> I have no idea what they do in practice though.  Do typical malloc 
>> systems actually allow simultaneous allocations in multiple threads?
>>
>> --bb
> 
> On a multicore system the allocator might conceivably have a heap for 
> each core or something like that.
> 
> However, even if this is not the case, allocation in a garbage-collected 
> language is very quick and the mutex would only need to be held for the 
> duration of the allocation.

I've heard this claim a couple of times recently (allocation is fast in 
GC languages).  I don't think it's true, though, at least not of D. 
Maybe it's a distortion of the the claim that *overall*, memory 
management in a GC language can be faster than explicit management.  But 
that's not because allocations are cheaper.  It's because you don't have 
to keep deleting things one by one as they go out of scope.  Instead, a 
bunch of out-of-scope objects all get reclaimed together during a GC 
sweep.  But the GC sweep takes place when you do an allocation, so in 
addition to the normal work necessary to do an allocation (finding a 
contiguous block of free memory that's big enough) you also have to do a 
full mark-sweep of all reachable memory.  I don't see how 
mark+sweep+allocate can be faster than just allocate.

[Rereading that now, though, it doesn't make much sense to me -- if 
there's a big gain to be had just by not explicitly freeing memory until 
the next allocation attempt, then regular malloc implementations could 
do that too, queuing up the free() requests until the next malloc call.]

The 'fast allocation' claim may be true of generational GCs or other 
fancy GCs, but D currently has a mark&sweep type.

Sean and other folks more in the know about GC -- please feel free to 
correct me on any of this.

--bb