[fpc-devel] Modernising Pascal

[Sebastian Kaliszewski]

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 
object.

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
> happen.

compacting GC allocation is rather more cache friendly than non GC one. 
Compacting Collection is not cache friendly though.

>
> Eric

rgds

-- 
Sebastian Kaliszewski