Linear structures: position, contiguity and the operation that pays

Unit two showed that the machine under the bound decides between equal operation counts. This unit turns to the smallest decision a model leaves open: how a linear sequence is stored, and what an operation on it may cost. The choice is usually offered as a menu of two entries, a contiguous block or a chain of nodes, as though the operations' names settled it. The names do not settle it. A queue, a string, an editing history and a cursor are each defined by the operations the interface performs often and by the latency it promises. The same word hides a different structure in each. The choice between contiguous and linked storage, and between an amortised and a real-time guarantee, is a claim about the operations an interface will perform often.

An operation's name is not a cost, and contiguity is a claim about use

Aho, Hopcroft and Ullman (1983) present the abstract data type as the working unit: a set of operations with a stated behaviour, separated from the representation that implements it. Their lists, stacks and queues appear in a linked and a contiguous form, with the choice left to the application. The type states what an operation does, not how often it is called. Two implementations can therefore satisfy one interface at different costs, and the interface alone cannot rank them.

Boehm, Atkinson and Plass (1995) make the argument at one familiar type. The conventional string suits only applications with specific and unusual performance requirements, because an edit that changes a length can force a copy of the rest. Their ropes represent text as a balanced tree of fragments. Concatenation and splitting are then cheap, and an edit touches one branch. The word string names an interface, not a layout: edited text is better served by the tree, bulk reads by the block.

Brodnik, Carlsson, Demaine, Munro and Sedgewick (1999) make the same point about the growable list. Doubling a full array concedes an amortised cost and slack of unused capacity. They give structures for a resizable array that support access to any position and perform every operation in constant time. The extra space beyond the elements is O(sqrt n), within a constant factor of optimal.

A rope shows where the contiguous string pays. Inserting one character into a block of n characters copies the tail. The cost therefore grows with the distance from the end of the edit. The rope splits the tree at the edit point and joins a new fragment in its place. The same edit touches one path of logarithmic depth and leaves the untouched fragments shared.

The operation set decides the structure, and one structure can serve several interfaces

Kaplan and Tarjan (1999) give a purely functional deque with catenation. In it, push, pop, inject, eject and catenation each run in worst-case constant time.

A second operation the name does not anticipate is the user's position in the sequence. Huet (1997) describes the zipper, a tree with a focused subtree. Its focus moves left, right, up or down while the context needed to reassemble the tree travels alongside. A structure without a focus answers a different question.

The undo history is where the names mislead. A linear undo is a stack, and the name suggests a history is one. Berlage (1994) shows a linear undo is insufficient, and he gives selective undo, which copies an isolated command into the current state when that is meaningful. Myers and Kosbie (1996) build the idea into a toolkit. They give command objects single undo, multiple undo, and a selective undo that reverses any previous operation and repeats it on new objects. A person who works slowly, or with a switch or voice input, builds a longer and more interleaved history, and a selective undo spares them unwinding work that was never wrong.

Hinze and Paterson (2006) give the unit's clearest case of a structure chosen by the operation set rather than named for it. Their 2-3 finger trees are a persistent sequence, with access to the ends in amortised constant time and splitting logarithmic in the size of the smaller piece. A general split lets one structure serve as a sequence, a priority queue, a search tree and a priority search queue.

Amortised or real-time: what the promise covers

Tarjan (1985) supplies the measure the decision turns on. Amortisation averages a structure's cost over a sequence of operations. Amortised running time is a realistic and robust measure for which tight bounds can be proved.

Hood and Melville (1981) show the promise can be tightened. Their queue operates in real time, with a worst-case constant bound rather than an amortised one. It runs in a pure functional language, and it makes the deferred work incremental. The two cases are the same structure under two accounting schemes, and the interface's deadline decides which account is acceptable.

Okasaki (1998) adds the condition under which the amortised account survives at all. The accounting behind an amortised bound does not carry over to persistent structures. A persisted version may be queried in an order the analysis did not anticipate, and the deferred operation may then be repeated, though redesigns such as banker's queues restore the bound. Whether the bound is good enough depends on whether the interface's versions persist.

Hood and Melville (1981) show that the two accounts can describe one structure. A queue built from two lists, one for the front and one for the back, is amortised constant per operation. A single dequeue that has to reverse the back list costs time proportional to its length. Their version keeps the same two lists and schedules that reversal a few elements at a time. No operation then pays the whole reversal, and each runs in worst-case constant time.

Contested question: is an amortised bound good enough for an interface?

The literature divides over the guarantee an interface should demand. The first position treats the sequence as the unit of use. Tarjan (1985) gives amortised running time as a realistic measure, and the structures that ship rest on it. Brodnik and colleagues (1999) prove constant-time operations for the resizable array, and Hinze and Paterson (2006) prove amortised constant-time access at the ends of the finger tree. On this reading the averaged bound describes the session.

The second position treats the per-operation latency as what the interface promises. Hood and Melville (1981) and Kaplan and Tarjan (1999) build real-time structures with worst-case constant operations, because an individual operation may fall on a deadline. Okasaki (1998) shows the amortised bound is not even stable once versions persist, so an interface that can revisit an old state has no amortised guarantee to lean on.

A second disagreement cuts beneath the first. Once a structure is shared, being fast is not the whole requirement. Herlihy and Wing (1990) define linearizability, the condition that each concurrent operation appears to take effect at a single instant between its invocation and its response. They prove it composable, and a bound about one thread says nothing about overlapping operations. Michael and Scott (1996) give a non-blocking queue and a two-lock queue. On a 12-node SGI Challenge multiprocessor the non-blocking queue beat the best known alternatives. Prakash and Knister (1994) show the history has the same problem. Users reverse their own changes, and conflicts between concurrent operations must be handled explicitly, so it is not a stack over a shared document.

A study of one shape would settle the disagreement. It would take a single interface and record the workload its operations impose. It would report the per-operation latency distribution rather than the mean, under persistence and under concurrency, comparing a real-time structure with its amortised twin. No source here reports that tail.

The two sides rest on proofs of different objects. Tarjan (1985) proves an amortised bound over a sequence, and Hood and Melville (1981) and Kaplan and Tarjan (1999) prove worst-case constant operations for one. Neither reports a latency distribution, so the real-time side is a construction rather than a measured advantage. The strongest objection is that a per-operation guarantee costs space and code that most interfaces never recover, so it can be a tax the workload does not need. While the dispute is open, a designer names whether versions persist and whether an operation shares a deadline, then chooses the account.

Where the argument is heading

The named work points towards structures that keep a strong per-operation promise while carrying many operations. Kaplan and Tarjan (1999) removed the logarithmic cost of catenation and made the deque real-time and purely functional. Hinze and Paterson (2006) reduced a family of interfaces to one structure, and Okasaki (1998) made amortised bounds survive persistence. On the shared side, Herlihy and Wing (1990) and Michael and Scott (1996) set the correctness condition and the contention measurement. The argument still open is the one this unit has run through the canon: the operation mix is the design input, and it is rarely measured.

The sources this unit rests on

• Aho, A. V., Hopcroft, J. E. and Ullman, J. D. (1983). Data Structures and Algorithms. Addison-Wesley. https://archive.org/details/datastructuresal00ahoa Aho, Hopcroft and Ullman present lists, stacks and queues as abstract data types with implementations and analyses, separating an operation's behaviour from the representation that realises it. It is a textbook, and that separation makes the unit's argument possible.
• Berlage, T. (1994). A selective undo mechanism for graphical user interfaces based on command objects. ACM Transactions on Computer-Human Interaction. doi:10.1145/196699.196721 Berlage argues that linear undo is insufficient, since a past action may have no sensible interpretation in the present state, and gives a selective undo that copies an isolated command into the current state. It shows a history need not be a stack.
• Boehm, H., Atkinson, R. and Plass, M. (1995). Ropes: An alternative to strings. Software: Practice and Experience. doi:10.1002/spe.4380251203 Boehm, Atkinson and Plass compare the conventional contiguous string with ropes, a balanced tree of text fragments in which concatenation and splitting are cheap and an edit touches one branch. It separates the word string from the layout of an array of characters.
• Brodnik, A., Carlsson, S., Demaine, E. D., Munro, J. I. and Sedgewick, R. (1999). Resizable Arrays in Optimal Time and Space. Lecture Notes in Computer Science. doi:10.1007/3-540-48447-7_4 Brodnik, Carlsson, Demaine, Munro and Sedgewick give structures for a resizable array with access to any position and constant time per operation, using extra space of O(sqrt n). It corrects the belief that doubling forces a space penalty.
• Herlihy, M. P. and Wing, J. M. (1990). Linearizability: a correctness condition for concurrent objects. ACM Transactions on Programming Languages and Systems. doi:10.1145/78969.78972 Herlihy and Wing define linearizability, the condition that each concurrent operation appears to take effect at a single instant between its invocation and its response, and prove it composable. It names what correct means once operations overlap.
• Hinze, R. and Paterson, R. (2006). Finger trees: a simple general-purpose data structure. Journal of Functional Programming. doi:10.1017/s0956796805005769 Hinze and Paterson introduce 2-3 finger trees, a persistent sequence with amortised constant access at the ends and splitting logarithmic in the smaller piece. A general split lets one structure serve as a sequence, a priority queue and a search tree.
• Hood, R. and Melville, R. (1981). Real-time queue operations in pure LISP. Information Processing Letters. doi:10.1016/0020-0190(81)90030-2 Hood and Melville give a queue whose operations run in real time, a worst-case constant bound rather than an amortised one, by making the deferred work incremental. It shows an amortised guarantee can become a per-operation promise.
• Huet, G. (1997). The Zipper. Journal of Functional Programming. doi:10.1017/s0956796897002864 Huet describes the zipper, a tree with a focused subtree whose focus can be moved left, right, up or down while the context needed to reassemble the tree travels alongside. It is the standard cursor over a recursive structure.
• Kaplan, H. and Tarjan, R. E. (1999). Purely functional, real-time deques with catenation. Journal of the ACM. doi:10.1145/324133.324139 Kaplan and Tarjan give a purely functional deque with catenation in which push, pop, inject, eject and catenation each run in worst-case constant time. It is the unit's worked case for an interface with two live ends.
• Michael, M. M. and Scott, M. L. (1996). Simple, fast, and practical non-blocking and blocking concurrent queue algorithms. Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing - PODC '96. doi:10.1145/248052.248106 Michael and Scott give a non-blocking queue and a two-lock queue in which one enqueue and one dequeue proceed concurrently. On a 12-node SGI Challenge the non-blocking queue beat the alternatives, so a linear structure's design changes when threads share it.
• Myers, B. A. and Kosbie, D. S. (1996). Reusable hierarchical command objects. Proceedings of the SIGCHI conference on Human factors in computing systems common ground - CHI '96. doi:10.1145/238386.238526 Myers and Kosbie build reusable hierarchical command objects into the Amulet toolkit, giving them single undo, multiple undo and a selective undo that reverses any previous operation and repeats it on new objects. It shows the history's structure follows the interface's operations.
• Okasaki, C. (1998). Purely Functional Data Structures. doi:10.1017/cbo9780511530104 Okasaki shows that amortised bounds derived by the usual accounting methods do not carry over to persistent structures, because a persisted version may be queried in an unanticipated order and the deferred operation repeated. Redesigns such as banker's queues restore the bound.
• Prakash, A. and Knister, M. J. (1994). A framework for undoing actions in collaborative systems. ACM Transactions on Computer-Human Interaction. doi:10.1145/198425.198427 Prakash and Knister set out a framework in which each user can reverse their own changes individually, with conflicts between concurrent operations handled explicitly, incorporated into a group text editor. It shows multi-actor undo is not a stack.
• Tarjan, R. E. (1985). Amortized Computational Complexity. SIAM Journal on Algebraic Discrete Methods. doi:10.1137/0606031 Tarjan surveys amortisation, averaging a structure's cost over a sequence of operations, and argues that amortised running time is a realistic measure for which tight bounds can be proved. It is the measure the unit's contested question tests.