Hacker News Reader

Comment by yakubin | Hacker News Reader

What happens in your language when a linked list is freed? Doesn't running its destructor (or its equivalent) take a linear amount of time relative to the length of the list?

View on HN

The compiler uses arrays not linked lists. One of the big mistakes that other functional compilers make (IMHO) is that they use linked lists. It is a huge performance problem. There is a reason why high-performance software written in C++ and C always use arrays and not linked lists. Memory access patterns is the #1 thing to optimise for on modern CPUs.

So, as I understand it, you avoid pauses by avoiding data structures with long chains of pointers. The same will work equally well in a language with a GC. It's also not the case that reference-counting itself doesn't result in pauses itself, but that the user is responsible for using such data structures that they do not result in pauses. Which I think is the only way when you care about performance, no matter whether you use manual memory management, reference counting or a tracing GC, so that's by no means a criticism of you or your language, I think it's very sensible. But I think that describing it as a no-pause memory management mechanism is a mischaracterisation.

So according to your logic no pause GC is impossible? In that case my claim is that it works as fast as what an expert in C/C++ optimisations would hand craft the compiled code to do by carefully minimising allocs/frees. This is what AAA games do to minimise stuttering. You can achieve the same with GC languages like Java. However you then have to manually keep a pool of objects and manually “alloc/free” objects from that pool. That is what games written in GC languages do to avoid random GC pauses.

No-pause GC is possible, when we're talking about concurrent GCs, but it also shouldn't be mistaken for a "no-overhead GC". And reference-counting, as long as the actual reference counting isn't done in a separate thread as well, instead of blocking in a destructor, which triggers other destructors, is not a no-pause GC. It's true that application developer can avoid pauses even then, but that's a different claim.

From what I've been told, C++ games do another thing and just use arena allocators, which make allocations cheap (just an integer addition, provided you know a reasonable upper bound on the size of an arena, and if you don't, you may reserve a large piece of virtual memory, and commit it later in reasonably small, but also not too large chunks) and free-s even cheaper (either reset the integer, so that the arena can be reused, or a single syscall to unmap the whole arena in one go). That's a different strategy than making a lot of little allocs and frees, and then trying to minimize them by reusing objects, which is also quite hairy.

My guess is that this could be done concurrently and/or in parallel.

It still take time linear in length, but dead nodes are by definition stable so it does not really matter when you free them.

So just like with tracing GCs. You do have a pause, which you may avoid with parallelism, or smear out incrementally. If you do it in parallel, your reference counting needs to be atomic, which adds further overhead. You still need to perform all the reference counting operations for each element of the list, not just free them, because part of the list may be shared. E.g. in SML:

  fun replace_head_with_1 (_::xs) = 1::xs;
  val a = [2, 3, 4];
  val b = replace_head_with_1 a;

Now a and b share the tail.

And a linked list is only a simple demonstration of a chain of pointers. It occurs spontaneously outside of containers, when you just write e.g. classes which have objects of other classes as their fields. In Haskell that would be records, or just an algebraic data type. Or just closures.

Reply on news.ycombinator.com