[fpc-devel] Modernising Pascal
Sebastian.Kaliszewski at softax.pl
Fri Feb 25 16:30:25 CET 2005
On Friday 25 February 2005 15:18, Eric Grange wrote:
> > No worse that normal memory allocation, if GC is implemented properly.
> Actually, that's incorrect, manual memory allocation has a constant
> complexity cost if done properly (each alloc/free has a constant CPU
> cost, whatever the amount of objects allocated or their size, just don't
> use old fashioned linked-lists memory managers),
1. This is not "entirely true" (the cost is at best logarithmic on the
number of objects or your allocator has terrible fragmentation)
2. You have to initialise your allocated data anyway.
3. In real life often you have virtual memory system underneath and there is
no guarantee whatosoever.
> while theoretically-
> best-case-GC still isn't constant time
GC allocation (in case of compacting collecotr) is constant time trivially,
all the cost is in compacting which is linear.
> (and practical ones are more
> like O(n²)),
Huh? If anything tracing is (trivially) O(m) where m is number of pointers
of memory and in all but few contrived examples m<n (where n is amount of
allocated memory). Then most object die young so they are traced once. When
you amortise the costs you'll see that tracing is allmost constant per
Then you can go for non tracing GC, use your "nearly" consttime
alloc/dealloc and all the overhead is tracing (which is also nearly
consttime per object)
> GC memory allocation and heap compaction patterns are quite
> cache unfriendly and will require partial or total freezes while they
compacting GC allocation is rather more cache friendly than non GC one.
Compacting Collection is not cache friendly though.
More information about the fpc-devel