RE: Are new sequences really O(1)?

On 27 May 2005 21:02, Marcin 'Qrczak' Kowalczyk wrote:

[moved from libraries to glasgow-haskell-users]

Ross Paterson writes:

...

GCs that happen during this process will be more expensive, as they have to scan the stack. I suspect that GC costs are swamping everything else for large n.

I just tweaked the implementation GC in my compiler of my language, so that minor collection doesn't scan the whole stack, but only the part up to the deepest point where the stack pointer has been since the previous collection. Deeper regions contain only old pointers so they don't need to be scanned (I have only two generations).

A program which builds a list of length 270,000 non-tail-recursively, which in a strict language leads to proportional usage of the stack, and performs on average 4kB of temporary allocations for each element, so there are 9,000 GCs in total with the young heap of 128 kB, runs 10 times faster after the change. GC takes 5% of the time instead of 88%.

Nice trick. Unfortunately the same assumptions don't hold for GHC's garbage collector - objects are aged in the youngest generation, so it is usually at least two GCs before an object is promoted. We could still do the same trick, but instead we'd have to find maximum stack depth at which all objects below are in an older generation. Incedentally, how do you mark the stack depth? Overwrite a return address with a special one, and keep the real one around in a known place? Cheers, Simon