Linus with some good observations on garbage collection

Andrei Alexandrescu SeeWebsiteForEmail at erdani.org
Sun Apr 24 19:32:32 PDT 2011


On 04/24/2011 07:10 PM, Timon Gehr wrote:
> Andrei Alexandrescu wrote:
>> I am sorry, you simply have no case - each and every argument you put
>> forth has no strength or is just wrong. We could spend time on debating
>> each, but I suspect that would do little toward convincing you of what
>> is after all a simple fact, but one with many subtle facets. It might
>> not a good use of our time to further engage in a diatribe on this. The
>> delete keyword will go, as will class-specific new and delete.
>>
>>
>> Andrei
>
> Ok, lets stop. Custom allocators and delete should probably be removed from D:

Thank you for agreeing.

> Some of my facts:
> * freelist is faster if most allocation and deallocation concentrates on only one
> class. (see attachment) I think this is also the reason it increases DMDs speed.
> Token and Scope are quite obvious bottlenecks..

I agree. There are two other things that I don't agree with:

1. This particular point does nothing to help the original argument, 
which was to keep the delete keyword (and in particular class 
allocators) in the D programming language.

2. Freelists are not all smiles - have their big problems too. When 
deciding to go with freelist the implementer must also decide on a 
strategy for releasing that memory back to the backend allocator on some 
schedule. Choosing a "good" schedule is already a full-blown problem 
that is best left to the the specialists implementing the backend 
allocator. My colleagues discovered with horror that unless the 
environment variable GLIBCXX_FORCE_NEW was defined, the STL node-based 
containers would _never_ give back memory once allocated.

Memory allocation is difficult, and for any allocator some workloads 
exist that makes it worse than all others. Nevertheless, recent 
developments in general-purpose memory allocators (e.g. the 
Low-Fragmentation Heap on Windows and a slew of allocators on Unix 
including ptmalloc, tcmalloc, jemalloc, and others) have shown that it's 
best to just use a good general-purpose allocator instead of fiddling 
with custom allocation.

> * such bottlenecks will most of the time only be detected when development is
> almost finished. (Almost never for library code, so I don't get why STL uses
> custom allocators at all.)
> * premature optimization is evil (see STL custom allocators)
> * late optimization: it is easy if there are custom allocators. In C++ it is even
> trivial. Nice design. Still no clue why STL is abusing it.
> * that form of custom allocators does not play nicely with Ds Garbage collector
> though, because it changes the semantics of 'new', ergo builtin custom allocators
> should probably indeed be removed from D.
> * this makes this form of optimization painful in D without custom allocators.
> This is what I was instinctively scared about. Fact is: it is also painful with
> them, because you don't get the 'delete's for free as in C++. I was somewhat
> inconsiderate on this.
> * it is possible that hinting the GC is only about twice as bad (again, see
> attachment).

OK.

Allow me to add a speculation here. I believe that one mistake that both 
class-level new/delete and STL allocators have done was to associate 
allocators with types. That just seems to force the proverbial square 
peg through the round hole. General-purpose allocators just focus on 
size classes and do awfully well. In addition, they do that in an 
integrated, non-modular way (as work on HeapLayers has shown, 
modularizing allocators is difficult and not very intuitive).

> And some notes:
> * the fact that you think all my points were worthless or wrong implies that you
> either did not read all of them or have not considered them yourself when making
> your decision. I think that is scary.

Well I think I owe you an apology. It is very difficult to use limited 
time resources to convince someone of rather subtle matters, 
particularly if the discussion starts not with a question (e.g. "In 
light of what I said, I wonder whether removing delete is the right way 
to go."), but with an assertion. At that point I need to make a sort of 
a cold estimate - do I have a reasonable chance of convincing someone of 
something within a reasonable time frame? It's difficult to make and 
convey that decision without seeming impolite, although please believe 
me being curt pains me as much as anyone.

To make matters more difficult, I'm not an expert in memory allocation 
and garbage collection. Probably I'm just at the point I can recognise 
good work when I see it. Yet, after a book chapter on memory allocation, 
a couple of articles written on memory allocation, a course I'm teaching 
on memory allocation, and a good amount of work on STL's interaction 
with jemalloc while at Facebook - I must admit I've become a bit jaded 
and as such less sanguine about arguing my points.

> * There are many ways in which I am always right. The most dominant being that any
> sufficiently smart guy with a PhD in rocket science would totally agree with all
> my statements. No pun/offense intended.

Not sure how you mean that. I mean, nobody here is discussing your 
competence on any personal trait of yours, and in particular I'm not 
keen of drawing any sweeping conclusion from any one discussion. You may 
as well know better than everybody about allocation, but so far you 
didn't seem to have found the right words to convey that. The simple 
fact is that here all anybody knows about you is what you write. And 
what you wrote failed to produce (now by your own admission as far as I 
can understand) a viable case for keeping the delete operator and 
class-level allocators in the D programming language.

> * this discussion would have been a waste of your time, had it not been public.
>
> Thanks for discussing. It was helpful.

I hope that's not in jest :o).


Andrei


More information about the Digitalmars-d mailing list