4 ms·

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 no

• yakubin 4y ago
  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.