22

I just realized that I have been assuming the answer to my question is "yes" but I don't have a good reason. I imagine that maybe there is a garbage collector that provably introduces only $O(1)$ worst-case slowdown. Is there a definitive reference I can cite? In my case I am working on a purely-functional data structure and I use Standard ML, if these details matter.

And perhaps this question would be even more relevant when applied to data structures specified in, say, Java? Maybe there is some relevant discussions in algorithms/data structure textbooks that use Java? (I know Sedgewick has a Java version, but I have access to the C version only.)

Neel Krishnaswami
  • 32,528
  • 1
  • 100
  • 165
Maverick Woo
  • 591
  • 6
  • 12

2 Answers2

17

Yes, gc is amortized constant time. Suppose you have an algorithm which runs for time $n$ with a peak working set of size $k$. Now, note that you can allocate at most $O(n)$ words during the execution of the program, and that the time cost of running a copying garbage collector is $O(k)$ (ie, the cost of a gc is proportional to the total amount of live data). So if you run the gc at most $O(n/k)$ times, then the total runtime cost is bounded by $O(n)$, which means that the amortized cost of the gc is constant. So if you have a Cheney-style collector, with each semispace being size $2k$, then it's easy to see that a full collection can't be invoked more than once every $n/k$ steps, since allocating $k$ words takes $O(k)$ time, and the working set never exceeds size $k$, which gives you the bound you want. This justifies ignoring gc issues.

However, one case where the presence or absence of gc is not ignorable is when writing lock-free data structures. Many modern lock-free data structures deliberately leak memory and rely on gc for correctness. This is because at a high level, the way they work is to copy some data, make a change to it, and try to atomically update it with a CAS instruction, and run this in a loop until the CAS succeeds. Adding deterministic deallocation to these algorithms makes them much more complex, and so people often don't bother (esp. since they are often targeted at Java-like environments).

EDIT: If you want non-amortized bounds, the Cheney collector won't do it -- it scans the whole live set each time it is invoked. The keyword to google for is "real-time garbage collection", and Djikstra et al. and Steele gave the first real time mark-and-sweep collectors, and Baker gave the first real time compacting gc. 

@article{dijkstra1978fly,
  title={{On-the-fly garbage collection: An exercise in cooperation}},
  author={Dijkstra, E.W. and Lamport, L. and Martin, A.J. and Scholten, C.S. and Steffens, E.F.M.},
  journal={Communications of the ACM},
  volume={21},
  number={11},
  pages={966--975},
  issn={0001-0782},
  year={1978},
  publisher={ACM}
}

@article{steele1975multiprocessing,
  title={{Multiprocessing compactifying garbage collection}},
  author={Steele Jr, G.L.},
  journal={Communications of the ACM},
  volume={18},
  number={9},
  pages={495--508},
  issn={0001-0782},
  year={1975},
  publisher={ACM}
}

@article{baker1978list,
  title={{List processing in real time on a serial computer}},
  author={Baker Jr, H.G.},
  journal={Communications of the ACM},
  volume={21},
  number={4},
  pages={280--294},
  issn={0001-0782},
  year={1978},
  publisher={ACM}
}
Neel Krishnaswami
  • 32,528
  • 1
  • 100
  • 165
  • Thanks to this lead, I just read about Cheney-style collector from Wikipedia. Can you confirm that a Cheney-style collector can dovetail with any algorithm that it collects, assuming the heap is sufficiently large? By dovetail, I mean such a collector can be executed incrementally in the background, one unit of work at a time. (More precisely, for some values of $a$ and $b$, after every $a$ instructions in the foreground algorithm, execute $b$ instructions in the background collector.) – Maverick Woo Nov 05 '10 at 15:13
  • 1
    "Yes, gc is amortized constant time". This is not true in general. You might argue that GC can be but they are not necessarily and real ones certainly are not. For example, the naive List.map in OCaml is actually quadratic complexity because stack depth is linear and the stack is traversed each time the nursery is evacuated. Same goes for major slices encountering large arrays of pointers. – J D Jan 30 '11 at 23:52
12

I'd say that you can ignore garbage collection. Interestingly, perhaps, all the work I've read on garbage collection fails to mention computational complexity. This is because the algorithms are $O(n)$ in the size of the heap, though typically they do not do a whole heap scan every time they are invoked.

The main problem with garbage collection is not the computational complexity, but unpredictability. This is most relevant when considering real-time systems. A lot of work on real-time garbage collection tries to address this issue. Others have simply given up. For example, the Real-time Specification for Java relies on programmer specified region which are allocated and deallocated programmatically with $O(1)$ cost, irrespective of their size.

The definitive garbage collection reference is:

  • Garbage Collection by Richard Jones and Rafael Lin

Ben Zorn did some work measuring actual costs of different garbage collection algorithms, though the following is more recent paper presents a much more comprehensive comparison:

For more see:

Dave Clarke
  • 16,666
  • 3
  • 60
  • 106