Log in

Previous Entry | Next Entry

Stupid RCU Tricks: An Early-1970s Example

Up to now, I have been calling out Kung's and Lehman's classic 1980 “Concurrent Manipulation of Binary Search Trees” as the oldest mention of something vaguely resembling RCU.

However, while looking into the history of reference counting, I found Weizenbaum's postively antique 1963 “Symmetric List Processor (SLIP)”, which describes a list-processing library, written in FORTRAN, no less. One of its features was storage reclamation based on reference counting, in which newly reclaimed list items are added to the end of SLIP's list of available space.

And, on page 413 of his 1973 “The Art of Computer Programming: Fundamental Algorithms”, none other than Donald Knuth points out that this add-at-end implementation means that “incorrect programs run correctly for awhile”. Here, “incorrect programs” is presumably referring to readers traversing SLIP lists while failing to increment the needed SLIP reference counters.

So it is that the earliest known mention of RCU-based algorithms dismisses them all as buggy. And rightfully so, given that SLIP has no notion of anything like a grace period. Thus, Kung and Lehman remain the first known implementers of something vaguely resembling RCU—but no longer the first mention!


Jul. 11th, 2016 04:50 am (UTC)
Cool !!
Good find Paul :)