On Thu, 28 Apr 2011 11:11:41 -0400, Alexander <[email protected]> wrote:
On 28.04.2011 16:52, Steven Schveighoffer wrote:
delete() is 99% of the cases O(1) operation (thanks to free lists),
Not exactly, it still needs to update the metadata for the block, which
involves a binary search (O(lgn)) + you have to take the global lock,
which means you could be making your multi-threaded application worse
than a single-threaded one.
Well, I was assuming that metadata is attached to the block - there is
no need to search. Of course, it depends on implementation.
This is not how it's implemented. The metadata is kept in a separate page
from the memory itself.
OTOH, when there are deletes performed in a bunch (+ time to scan the
data for references), it could really take time. Taking a lock, IMHO, is
a bit less expensive comparing to pausing all threads. But I may be
wrong...
The point is, you only do it once in a while. If you delete objects 100
times a second, and the GC runs only every 10 seconds, then you have to
consider the cost of pausing all threads and running a collection cycle
against 10,000 times taking the lock.
IMO, the GC runs too often in D, but we can improve that metric.
The point is that it runs infrequently enough to avoid hindering
performance.
Then there is another catch lurking around - the less frequently it
runs, the more objects will be collected, so performance is hindered
even more.
Not really. The more objects there are to collect, the less scanning
needs to be done. You only process blocks that have references to them.
There is also a certain amount of overhead that runs regardless of how
many objects are ready to be collected.
D's GC is pretty horrible at performance, so there are definitely
improvements yet to be seen there (David recently fixed some really bad
ones, the next version of dmd
should be much faster at allocation).
Is it possible to adapt (or use directly) Boehm's GC? Just an idea...
Yes, the GC is swappable. You need to re-compile the runtime with a
different GC, all the hooks are movable. In fact, there's a GC stub that
just calls C malloc for all allocations.
As mentioned, RT applications and OS kernels would need a specialized
runtime, D does not support that with the current GC/runtime. This
does not mean that you would be using delete for those, you'd probably
use a specialized runtime function using
that specialized runtime.
Right, but using "delete" is a bit more "natural". IMHO, of course :)
For some, free might be more "natural" :) I think you can find another
term to free data that is not a keyword easily enough.
Additionally, memory management hooks supported by the compiler are
faster than any other solution (templates & co).
Absolutely untrue. Runtime hooks cannot be inlined for instance.
Unless compiler *knows* that there are hooks. Some believe that
compiler must not handle anything specifically, but, to be really
effective, this is difficult to avoid. Intrinsic functions are very
useful.
The compiler cannot possibly make any assumptions about how memory
management is done. It must dutifully call the runtime function, or else
you could not implement interesting things in the GC.
Having a dedicated keyword makes it seem sanctioned and promoted by the
language, when in fact, it should almost never be used.
D has some features which are discouraged anyway (like pointers &
co.), but - D is a tool, and I believe that decision how to use a tool
should be left to the user, that's all :)
But delete doesn't allow you to do things that you can't already do
otherwise. Delete is not going away without replacing it with an
equivalent functionality. Pointers and casting are a necessary evil for
optimizing code and forcing things in the type system. There is no way to
implement pointers and casting in the runtime.
-Steve
