Who Owns the Contents of a Doubly-Linked List?

Remark that the design of WebPage leaves the removal of a vertex from the graph rather challenging. To keep our representation consistent, all web pages referring to the one being removed must be updated. Unfortunately, our design does not natually give us a whole view of the graph. Since there is no obvious root nor any guarantee that the graph is connected, there is no obvious way to collect the set of vertices contained in the graph. We can fix this issue by storing all vertices in one collection but this approach introduces a new problem: we must guarantee that elements inserted in the links of a WebPage are also present in this collection. Another complication is that updating the outgoing edges of all the web pages is expensive. We can fix this issue by adding backward links in each web page but again, doing so introduces new structural invariants to maintain. The resulting program is shown in Listing 2. Significant complexity has been added to maintain the graph’s invariants, making the whole data structure much more difficult to modify correctly. In particular, instances of WebPage are now responsible for updating the values of other objects to maintain structural invariants, which arguably breaks the abstraction principle.

One may opt to redesign remove and addLink as methods of WebGraph to better encapsulate them. Interestingly, doing so evidences the fact that these two operations notionally act on the whole graph rather than on a single vertex – unlike, e.g., modifying the topic of a web page. It also simplifies interactions with the data structure and leaves its interface easier to discover. In Listing 2, it seems arbitrary and needlessly asymmetric that one must call a method of WebGraph to insert a page and then call a method of WebPage to remove one. Pushing this observation further, one may wonder whether the relation between webpages ought to be stored in a WebGraph rather than spread in instances of WebPage, as doing so would better encapsulate the maintenance of the graph’s structural invariants. If one is willing to adopt this change, the constraints of full ownership become sensible as they acknowledge the whole/part relationship relating a web graph to the web pages that it uniquely owns.

Recognizing whole/part relationships is an important step in the design of a data structure as it tells us what constitutes the notional value of an instance and thus its meaning. In turn, this concept lets us properly characterize essential operations such as equality, copying, or hashing, and distance ourselves from the cumbersome and error-prone distinction between referential and structural – a.k.a shallow and deep – properties. Two web graphs are equal if and only if they contain equal web pages having the same relationnships. Likewise, copying a web graph means copying its pages and the relation between those.

Notional values cannot be identified automatically in general because they depend on the abstract meaning one ascribes to a particular set of bits. In other words, only the author of a type can determine the notional values of its instances. Nonetheless, choosing representations that expose whole/part relationships helps since clearly the parts of a whole belong to the latter’s value. In most systems supporting value types, including Swift, this information can be leveraged to synthesize structural operations like equlity and copying.

The widespread use of first-class references muddies the difference between whole/part and peer relationships, captured in UML as the distinction between composition and association [4], respectively. Moreover, aliasing invites a litany of issues due to unintended mutation through shared mutable state [8]. These downsides highlights the benefits of full ownership but one question remains: how is one supposed to represent peer relationships?

A possible solution is shown in Listing 3. The keyword struct introduces a value type in Swift and the keyword mutating marks methods of value types that can modify their receiver. This program satisfies the constraints of full ownership: web pages do not reference each others and they can be uniquely owned by a web graph. It goes even one step further and dispenses with first-class references altogether, using only value types. The peer relationships are expressed with two tables, keyed by the URLs of the web pages involved. These URLs act as unique identifiers, thereby filling one of the two roles first-class references have. That is sufficient to represent relationships: links and backlinks do not require knowledge about the contents of a web page; only about their existence.

The second role of first-class references, namely the ability to confer access to the referred value, is fulfilled by using an URL as a key to index the pages of a graph. For example, the expression g.pages["https://x.abc"] denotes the value of a web page assumed to be contained in g. One may object that this approach could suffer from the misuse of a URL, e.g., by calling addLink on a page contained in a different graph. Note however that such a danger was already present in Listing 2.

Requiring that accesses to the web pages go through the graph has two advantages. It allows structural invariants to be upheld directly in the graph’s methods, thus improving encapsulation, and it also ensures that no operation can modify the graph’s value behind one’s back. This guarantee can be used to fend againt data races in a concurrent setting and to reason locally about the implementation of a data structure in general. In Listing 3, for example, we know in remove that if links is assigned at p, then so is backlinks.¹¹1That is assuming the fields of WebGraph are not modified directly, which can be enforced with traditional access control mechanisms [5, Chapter 6].

One may wonder whether working with this representation is at all practical. We can look at classical graph algorithms to answer affirmatively. A graph is almost ubiquitously defined formally as a pair $⟨V,E⟩$ where $V$ is a set of vertices and $E\subseteq V\times V$ is a relation. Algorithms on graphs are therefore typically described according to this particular presentation, which happens to match the implementation shown in Listing 3 much more closely than the one shown in Listing 2. We have implemented two classical graph algorithms to confirm this observation. Our code, which is provided as a companion material, is almost a word-for-word translation of textbook descriptions, suggesting that the absence of first-class references does not raise implementation challenges. We also come back to the performance of the value-based approach in Section 4.

We have implemented Tarjan’s strongly connected components algorithm [12] and Dijkstra’s shortest path algorithm [3, Chapter 24] on the two representations of a web graph discussed in Section 2. Figure 1(a) reports the time taken to identify all strongly connected components in randomly generated graphs of various sizes. Figure 1(b) reports the time taken to compute the shortests path to all the pages available from a randomly selected origin. In both figures, running times for the reference-based and value-based implementations are shown in blue (left) and green (right), respectively. The y-axis uses a logarithmic scale.

The results show no noticeable difference between the two graph implementations, suggesting that representing peer relationship separately, without first-class references, does not negatively impact performance. Interestingly, remark that the costs to access hashtable contents do not introduce a prohibitive overhead compared to dereferencing, despite our use of strings as keys. A more careful choice of identities – e.g., using integers to avoid the cost of hashing character strings – would likely improve on performance at the cost of some convenience and ease of implementation.

We have examined two implementations of doubly-linked lists. The first uses unrestricted first-class references to store forward and backward links in each node, as in traditional approaches. The second represents forward and backward links as offsets into an array, as discussed in Section 3.

Four operations were considered. Figure 2(a) reports the time taken to append new elements at the end of a list. Figure 2(b) reports the time taken to traverse a list. Figure 2(c) reports the time taken to remove elements at random positions until the list is empty. Figure 2(d) reports the time taken to traverse a list after having removed half of its contents at random. In all four cases the the lists were filled with random integers. Running times for the reference-based and value-based implementations are shown in blue (left) and green (right), respectively. The y-axis uses a logarithmic scale.

The results show that the value-based approach significantly outperforms its reference-based counterpart, by one order of magnitude. The biggest contributor of this difference is cache locality. In the value-based representation, the contents of the list are stored in contiguous memory locations. As a consequence, the data related to the successor of a node $n$ is likely available in the CPU’s cache after $n$ has been accessed, especially if all elements have been appended to the end of the list, as it is the case in Figure 2(b). This advantage persists even in Figure 2(d), after the removals of elements create “holes” in the array.

Another contributor to the overhead is the atomic exclusivity check Swift’s runtime performs before mutating an object, which protects the program from data races in concurrent settings. The cost of this check appears clearly in Figure 2(c). It comes in addition to the overhead caused by the indirections necessary to access the predecessor and successor of the removed node, whose links must be updated after a removal.

Finally, Figure 2(a) shows that allocating individual pieces of memory for each node is considerably slower than appending new nodes at the end of a resizeable array. On large inputs, this operation effectively has a constant time complexity and, unlike individual allocations, does not involve system calls unless the array has to be resized. Note however that Swift’s runtime is not particularly optimized for allocating large numbers of small objects. Hence, systems placing heavier emphasis on this aspect will likely yield better results.

Overall, these benchmarks reveal that notionally self-referential data structure can be implemented quite efficiently within the constraints of full ownership.