# Adjusted objects: an efficient and principled approach to scalable programming

Boubacar Kane, Pierre Sutra

► To cite this version:

Boubacar Kane, Pierre Sutra. Adjusted objects: an efficient and principled approach to scalable programming. MIDDLEWARE 2025 - 26th ACM/IFIP International Middleware Conference, Dec 2025, Nashville (Tennessee), United States. pp.215-227, 10.1145/3721462.3730953. hal-05472538

HAL Id: hal-05472538

https://hal.science/hal-05472538v1

Submitted on 6 Feb 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
<figure><img src="image_2.png" /></figure>

Latest updates: https://dl.acm.org/doi/10.1145/3721462.3730953

RESEARCH-ARTICLE

# Adjusted Objects: An Efficient and Principled Approach to Scalable Programming

BOUBACAR KANE, Telecom SudParis, Evry, Ile-de-France, France

PIERRE SUTRA, Telecom SudParis, Evry, Ile-de-France, France

Open Access Support provided by:

Telecom SudParis

<figure><img src="image_3.png" /></figure>
# Adjusted Objects: An Efficient and Principled Approach to Scalable Programming

Boubacar Kane

Telecom SudParis, Inria Saclay
Institut Polytechnique de Paris
Palaiseau, France
boubacar.kane@telecom-sudparis.eu

## Abstract

Parallel programs require software support to coordinate access to shared data. For this purpose, modern programming languages provide strongly-consistent shared objects. To account for their many usages, these objects offer a large API. However, in practice, each program calls only a small subset of the interface. Leveraging such an observation, we propose to tailor a shared object for a specific usage. We call this principle *adjusted objects*. Adjusted objects already exist in the wild. This paper provides their first systematic study. We explain how everyday programmers already adjust common shared objects (such as queues, maps, and counters) for better performance. We present the formal foundations of adjusted objects using a new tool to characterize scalability, the indistinguishability graph. Leveraging this study, we introduce a library named DEGO to inject adjusted objects in a Java program. In micro-benchmarks, objects from the DEGO library improve the performance of standard JDK shared objects by up to two orders of magnitude. We also evaluate DEGO with a Retwis-like benchmark modeled after a social network application. On a modern server-class machine, DEGO boosts by up to 1.7x the performance of the benchmark.

## CCS Concepts

* **Computing methodologies** → **Concurrent algorithms**; *Theory of computation* → **Concurrency**; • **Software and its engineering** → **Software system structures**.

## Keywords

Design, Performance, Theory, Scalability, Multicore, Software interfaces

**ACM Reference Format:**

Boubacar Kane and Pierre Sutra. 2025. Adjusted Objects: An Efficient and Principled Approach to Scalable Programming. In *26th ACM Middleware Conference (Middleware '25), December 15–19, 2025, Nashville, TN, USA*. ACM, New York, NY, USA, 13 pages. https://doi.org/10.1145/3721462.3730953

<figure><img src="image_4.png" /></figure>

This work is licensed under a Creative Commons Attribution 4.0 International License.
Middleware '25, Nashville, TN, USA

© 2025 Copyright held by the owner/author(s).

ACM ISBN 979-8-4007-1554-9/25/12

https://doi.org/10.1145/3721462.3730953

Pierre Sutra

Telecom SudParis, Inria Saclay
Institut Polytechnique de Paris
Palaiseau, France
pierre.sutra@telecom-sudparis.eu

## 1 Introduction

*Context.* Over the past 20 years, the clock rate of processors has almost stalled. From the 1 GHz landmark at the turn of the 2000s, current processors just tick at a few GHz. Nevertheless, Moore's law is well alive and the industry is able to always pack more transistors into the same square inch of silicon. Manycore systems have 10s to 100s of hardware threads. They are now common place in modern IT infrastructures, ranging from servers to small devices. To harvest this computing power, programmers write parallel programs. Ideally, these programs should be scalable, that is their performance improves linearly with the number of cores.

Getting right parallelism in an application is notoriously difficult. To help programmers in this task, programming languages and libraries provide shared objects. A plethora of objects is available, from primitive data types (such as long, integer, reference), collections (set, map, list, queue), to complex synchronization mechanisms (compare-and-swap, lock, semaphore, monitor, barrier, transactions). In most cases, these shared objects are strongly consistent. This means that the interleaving of concurrent calls to the methods of an object is equivalent to a sequential execution. Strong consistency allows the programmer to understand a shared object from its sequential specification. This greatly simplifies the reasoning about correctness.

*Motivation.* Typically, a shared object provides a wide interface with complex capabilities. This accounts for the many usages the object has across the spectrum of applications. Understanding how this interface is used in practice may provide hints to improve the object.

A first observation is that an application rarely uses the interface of a shared object in full. To assess this point, we have delved into the usage of the *java.util.concurrent* library in several prominent open-source projects. Figure 1 reports on our findings for *AtomicLong*. In Figure 1(left), we can notice that (i) projects only use a handful of the available methods, (ii) some methods are used much more frequently than others, and (iii) certain groups of methods are employed specifically altogether. Additionally, the return value of a method is not always used. We illustrate this point in Figure 1(right). For Apache Cassandra, this figure indicates if a class makes use of the return value, or not. In many cases, the response of the method call is just ignored.

Another key observation is that if the specification is not used in full, it might be possible to implement a better version of the object. Some expert programmers have already leveraged this insight to write objects ad-hoc to their use cases. These implementations boost the performance of a program with improved scalability
<figure><img src="image_5.png" /><figcaption>Figure 1: Usage of `AtomicLong` across different open-source Java projects: (left) lists the methods that are called. (right) indicates if the returned value of a method is used (+), or not (×) in Apache Cassandra.</figcaption></figure>

thanks to reduced hardware contention. For instance, Listing 1 shows an extract of the Conccurentli project at Linkedin [25]. In this library, the programmers have implemented a specific version of `AtomicReference`. Here, as the reference is written at most once (line 15), it is possible to buffer its value in the CPU cache for better efficiency (lines 6-7). Other real-life examples of ad-hoc objects include counters [23] and queues [2, 36].

*Objective & Contributions.* In this paper, we propose to tailor a shared object for a specific use. We call this principle *adjusted objects*. As pointed above, adjusted objects already exist in the wild. This paper presents the first systematic study of them. In detail, we claim the following contributions:

* We present the formal foundations of adjusted objects. First, we introduce a new characterization of the scalability of a shared object: the indistinguishability graph. In a nutshell, the denser this graph is the more scalable the object is. Adjusting an object is interpreted as adding more edges to the graph.

* Based on this characterization, we then propose DEGO a library of adjusted objects for Java. DEGO includes different adjusted objects for primitive data types, collection, and synchronization mechanisms. These objects are mirroring the shared objects found in the Java Development Kit (JDK). They offer an efficient implementation tailored to a specific usage.

* We evaluate the performance benefits of DEGO across a range of micro-benchmarks. In these benchmarks, DEGO improves the performance of the standard JDK objects by up to two orders of magnitude. We also evaluate DEGO with a Retwis-like [31] benchmark modeled after a social network application. On a modern server-class machine, DEGO boosts by up to 1.7x the performance of the benchmark.

* We also report on the usage of shared objects across 50 projects of the Apache Software foundation. Our study assesses that these objects (i) account for a small part of a code base, (ii) they are central to an application, and (iii) as underlined above, each program uses only a fraction of an object's interface.

*Outline.* §2 introduces our system model and definitions. In §3, we present the indistinguishability graph and detail how this notion

```java
public class AtomicWriteOnceReference<T> {
    private T _cachedObj = null;
    private volatile T _obj = null;
    public T get() {
        if (_cachedObj != null) return _cachedObj;
        _cachedObj = _obj;
        return _cachedObj;
    }
    public boolean trySet(T value) {
        if (!trySet(value))
            throw new IllegalStateException("already_set");
        return true;
    }
    public boolean trySet(T value) {
        if (get() != null) return false;
        if (!UPDATER.compareAndSet(this, null, value))
            return false;
        _cachedObj = value;
        return true;
    }
    /*...*/
}
```

<caption>Listing 1: Extract from the Concurrentli library</caption>

helps to measure scalability. Based on such graphs, §4 principles the notion of adjusted object. The DEGO library is described in §5. §6 details our evaluation campaign. We survey related work in §7 before closing in §8. Due to space constraints, the proofs are deferred to the long version of this paper [19].

## 2 System Model

We assume the standard shared memory model of computation. In this model, a set of $n \ge 2$ threads communicate using shared objects. Each object abides by a sequential specification, or *data type*. For an object *O*, *O.T* denotes its data type. The base objects of the shared memory model are registers to which threads read and write. The memory also offers common synchronization primitives, such as *compare-and-swap* and *test-and-set*, to update a register. Registers are used to implement higher-level objects (such as maps, queues, and trees). We restrict our attention to wait-free linearizable deterministic objects. Wait-freedom guarantees that every call to the interface eventually returns. Linearizability ensures that the interleaving of concurrent calls is equivalent to a sequential execution that preserves real time.

Some objects may have restricted use. They can be one-shot, that is each thread calling them at most once—in contrast with
long-lived objects. Another restriction is what part of the interface is available to which thread. For instance, single-writer multiple-readers (SWMR) registers are common in literature [14]. To model this, we consider that each object *O* has an *access permission map* *O*.m that defines operations a thread can execute. Every operation defined by the data type *O*.T is executable by at least one thread.

Threads may access a common register when they call a shared object. If this happens and the register is updated, we call it a conflict. In detail, operations *c* and *d* called by two distinct threads *conflict* when they access a common register that one of them updates. Operations *c* and *d* *update conflict* when they both update a common register [34]. Conversely, an operation is *invisible* when it never updates a register accessed by some other operation [4]. An operation is *conflict-free* when it never conflicts with any other operation. When no two operations conflict, the implementation is *conflict-free*. In such a situation, shared data is read-only. In the case where threads do not access a common register, the implementation is disjoint-access parallel [16].

An implementation *scales* when its performance grows with the number of threads. In practice, several parameters influence scalability, such as the size and locality of the working set. When the workload is parallel-enough, the key factor is the conflict rate. On modern hardware, an implementation scales when conflicts are rare [8]. Hence, it is paramount to understand when such an implementation is feasible.

## 3 Scalability

To principle adjusted objects, we need a good indicator of scalability. Because it captures the synchronization power, the consensus number is a potential candidate in this task. Unfortunately, it is well-known that this is not the case. We start this section by recalling such a result (§3.1). To fill the gap, we then propose a new metric, the indistinguishability graph (§3.2). The indistinguishability graph is built from the sequential data type of a shared object. We explain how scalability is closely related to the density of this graph (§3.3).

### 3.1 On the consensus number

In distributed computing, a central object is consensus. Its interface exposes a single operation: *propose(v)*, where *v* is some input value. Threads that call *propose()* all return (aka. *agree on*) one of the input values.

Given a data type *T*, the maximal number of threads that may agree using objects of type *T* and read/write operations on registers is called the consensus number of *T* [12]. We write $CN(T)$ the consensus number of *T*, and $CN_k$ all the shared objects with consensus number *k*. We will say that an operation *c* of *T* has consensus power when *T* restricted to just operation *c* has a consensus number greater than 1.

Objects like queues permit to reach consensus among several threads. Registers alone are too weak to solve a distributed agreement. They belong to $CN_1$.

A *m*-valued max-register stores up to $log(m)$ values. Updating its content demands $O(min(n, log(m)))$ read/write operations on the registers [3]. Differently, reading a snapshot object requires $\Omega(n)$ such steps [10]. Hence, despite these two objects are in $CN_1$, they

<figure><img src="image_6.png" /></figure>

x_1 = abc
x_4 = bca
x_2 = acb
x_5 = cab
x_3 = bac
x_6 = cba

= {a, b}
= {a}
= {b}
= {a, b c}

<caption>**Figure 2: From left to right, the indistinguishability graph** $\mathcal{G}(\{a, b, c\})$ **for a reference** (a = set(1), b = set(2), c = get()), **a set** (a = add(1), b = add(1), c = contains(1)), **and a counter** (a = inc(1), b = inc(3), c = inc(5)).</caption>

scale differently. This explains why the consensus number is a poor indicator of scalability.

### 3.2 Indistinguishability graph

This section introduces the indistinguishability graph. Such a graph is built from the data type of the shared object. We later explain how scalability and the density of the indistinguishability graph are related.

**Definition.** Consider an object of type *T*, a state *s*, and a bag (a set with possible repetitions) *B* of operations. For some permutation *x* of *B*, the response of *c* ∈ *B* from *s* is the return value of *c* after applying *x* until *c* from state *s*. Two permutations *x* and *x'* are *indistinguishable* from *s* for *c*, denoted $x \stackrel{\sim}{\sim}^s x'$, when (i) *c* obtains the same response in both permutations, and (ii) there exists a common state *s'* attainable after *c* in both *x* and *x'*. Hereafter, when *c* and *s* are clear from the context, we omit them (*x* ~ *x'*).

A convenient way to represent relation ~ is through an *indistinguishability graph*. Given *B* and *s*, the nodes of this graph $\mathcal{G}_T(B, s)$ corresponds to all the permutations of *B*. There exists an edge (*x*, *x'*), labeled with *C* in $\mathcal{G}_T(B, s)$ if and only if *x* and *x'* are indistinguishable from *s* for all the operations *c* ∈ *C*. The label is considered *strong* if applying *x* from *s* results in the same state as applying *x'*.

The *indistinguishability class* of *x* is the transitive closure of *x* by relation ~. It is written $[x]^B$. This corresponds to the connected component *x* belongs to in $\mathcal{G}_T(B, s)$. When *B* and *s* are clear from the context, we just write $[x]$. An operation *c* is *labeling* in $\mathcal{G}_T(B, s)$ when it is a label of all the edges. In this case, there is one indistinguishability class. When *c* is a strong label of all the edges, it is *strongly labeling*.

These notions extend naturally to shared objects. In detail, let *O* be an object of type *T*. The indistinguishability graphs of *O* are the graphs $\mathcal{G}_T(B, s)$ such that *s* is a state of *O*, and *B* complies with the access permission map *O*.m (that is, each thread *p* is mapped to a
unique operation $c_p$ in $B$ with $c_p \in O.m[p])$. The indistinguishability graphs of $O$ are written $\Gamma_O$.

**Examples.** Figure 2 illustrates the indistinguishability graph of three common objects: a reference, a set, and a counter. There are three operations {a, b, c}, applied from the initial state. The formal specification of these objects and operations appear in Table 1 (first column).

In total, there are $3! = 6$ nodes in the indistinguishability graph. For a reference (left side of Figure 2), the graph is complete because *set* does not return anything. Hence all edges have (at least) the default label $l = \{a, b\}$. When the same *set* is immediately preceding *get*, it returns the same response. Thus, *c* labels the edges $(x_1, x_4)$, $(x_2, x_3)$, and $(x_5, x_6)$.

For a set object, $c = contains(1)$ is labeling when it is not the first operation. Indeed, in such cases it always returns true. Moreover, when the *add(1)* operations are in the same order, their responses do not change. In those cases, a and b are labeling. Whatever the permutation is, the set always ends up in the same final state. Hence all labels are strong in this example.

The rightmost figure illustrates three increments of 1, 3, and 5 applied to a counter. Each increment returns the state of the counter after it is applied. Thus, if we permute the first two operations, the last operation will return the same value.

In Figure 2, all the graphs are connected. As a consequence, there is a single indistinguishability class. In general, there are at most $|B|$ indistinguishability classes. This comes from the fact that if $x[0] = y[0]$ then $[x] = [y]$.

**Relation with consensus.** When among $k = |B|$ operation, a data type $T$ has the power to distinguish up to $l$ classes, we say that $T$ is $\mathcal{D}(k, l)$. For instance, an increment-only counter is $\mathcal{D}(2, 2)$ but only $\mathcal{D}(3, 1)$, as the third operation cannot distinguish how the preceding ones are ordered (see Figure 2). This is also the case with a set. In these examples, key is the transition to $\mathcal{D}(k, 1)$. Below, we establish that when such a transition exists and $T$ is readable, that is any thread may retrieve the latest state of the object, $k$ is the consensus number of $T$.

**Theorem 1.** Consider a readable data type $T$. Then, $CN(T) = \max \{k : \exists l \ge 2. T \in \mathcal{D}(k, l)\} \cup \{1\}$

### 3.3 Predicting scalability

We now connect the scalability of a shared object $O$ to the shape of its indistinguishability graphs $\Gamma_O$. First, we provide necessary and sufficient conditions on those graphs for a conflict-free implementation of $O$ to exist. Then, we turn our attention to updates conflicts and invisible operations.

**Conflict freedom.** For starters, we investigate one-shot objects, that is objects callable at most once per thread. Recall from §2 that an implementation is conflict-free when no two operations access the same register, with one of them updating it. We can establish the following result.

**Proposition 1.** Assume that object $O$ is one shot. There exists a conflict-free implementation of $O$ if and only if $B$ is labeling in every $\mathcal{G}_T(B, s)$ of $\Gamma_O$.

In [8], the authors introduce the SIM-commutativity rule. The rule indicates when an interval of a concurrent execution can be implemented in a conflict-free manner. This corresponds to the sufficient part of Proposition 1: it happens when all operations $B$ in the interval are labeling in $\mathcal{G}_T(B, s)$, where $s$ is the state of the object before the interval. Proposition 1 proves that it is also necessary for deterministic objects. This result extends to the case of long-lived objects as detailed below.

**Proposition 2.** A conflict-free implementation of $O$ exists if and only if $B$ is strongly labeling in every $\mathcal{G}_T(B, s)$ of $\Gamma_O$ with $|B| = 2$.

The above condition demands that any two operations of different threads commute. This may happen when they access different shards, or *segments*, in a large object. For instance, in a key-value store, a thread can be in charge of a particular key range of the store.

In Listing 1, the *AtomicWriteOnceReference* class does not satisfy the premises of Proposition 2 when $B = \{set, get\}$. Nonetheless, this data type scales in practice (see §6). One observation is that its indistinguishability graph is dense. Indeed, permuting operations before (or after) the first *set* does not change their return values, nor the state of the object. Our next results further delve into the relation between the shape of the indistinguishability graphs and scalability.

**Update conflicts.** Scalability relates to the existence of conflicts among operations. Roughly speaking, a conflict is necessary when two operations impact each other. To track this, we introduce a moverness semantic [21, 26].

Consider an indistinguishability graph $\mathcal{G}_T(B, s)$ and a permutation $x = c_1...c_{m \ge 2}$ of $B$. An operation $c_i$ left-moves in $x$ when $c_i$ strongly labels the edge $(x, x')$ in $\mathcal{G}_T(B, s)$, with $x' = c_1...c_i c_{i-1}...c_m$. By extension, the operation left-moves in $\mathcal{G}_T(B, s)$ when it left-moves in all permutations of $B$. If it left-moves in all the indistinguishability graphs of the object, we say that the operation is a *left-mover*.

Blind writes, that is writes whose return value is null, are potential left-movers. For instance, consider a set object. If *add* is blind (object $S_2$ in Table 1), it left-moves with prior *add* operations. Another example is *offer* for a queue (object $Q_1$ in Table 1). When the queue is not empty, this operation left-moves with *poll*. Hence, if at most one thread invokes *offer*, the operation is likely to left-move. This is an example of adjusted object and §5 covers it in detail. The proposition below states that left-movers can be implemented efficiently.

**Proposition 3.** Operation *c* is implementable without update conflicts if *c* left-moves in every $\mathcal{G}_T(B, s)$ of $\Gamma_O$. Such an implementation exists only if *c* has no consensus power.

**Invisible operations.** Right-movers are another type of operations implementable in an efficient manner. Such operations do not change the result of an adjacent operation when their positions are swapped. More precisely, $c_i$ right-moves in $x = c_1...c_{i-1} c_i...c_m$ when $c_{i-1}$ strongly labels the edge $(x, x')$ in $\mathcal{G}_T(B, s)$, where $x' = c_1...c_i c_{i-1}...c_m$. Notice that $c_i$ right-moves in $x$ if and only if $c_{i-1}$ left-moves in $x'$. Right-movers are defined similarly to left-movers.

Because they have no side effects, reads are typical right-movers. However, they are not the only one. This is also likely to happen when updates are blind. The result below proves that right-movers are implementable in an invisible manner.
<table><caption>Table 1: Adjusted versions of common data types in Hoare logic. We note s the state of the object, s' the state after the operation is applied, and r the return value. If left unspecified, the state is unchanged and the return value is empty (⊥).</caption><thead><tr><th></th><th></th><th></th><th></th><th></th><th></th></tr></thead><tbody><tr><td>Counter</td><td>[true] rmw(f, x) [s' = f(s, x) ∧ r = s']<br>[true] inc() [s' = s + 1 ∧ r = s']<br>[true] get() [r = s]<br>[true] reset() [s' = 0]</td><td>C<sub>1</sub></td><td>[true] rmw(f, x) [true]<br>[true] inc() [s' = s + 1 ∧ r = s']<br>[true] get() [r = s]<br>[false] reset() [s' = 0]</td><td>C<sub>2</sub></td><td>C<sub>3</sub></td></tr><tr><td>Set</td><td>[true] add(x) [s' = s ∪ {x} ∧ r = x ∉ s]<br>[true] remove(x) [s' = s \ {x} ∧ r = x ∈ s]<br>[true] contains(x) [r = x ∈ s]</td><td>S<sub>1</sub></td><td>[true] add(x) [s' = s ∪ {x}]<br>[true] remove(x) [s' = s \ {x}]<br>[true] contains(x) [r = x ∈ s]</td><td>S<sub>2</sub></td><td>S<sub>3</sub></td></tr><tr><td>Queue</td><td>[true] offer(x) [s' = s ∘ x]<br>[true] poll() [if |s| = 0 then r = ⊥ else r =<br>head(s) ∧ s' = s \ {head(s)}]<br>[true] contains(x) [r = x ∈ s]</td><td>Q<sub>1</sub></td><td></td><td></td><td></td></tr><tr><td>Reference</td><td>[x ∈ Addr] set(x) [s' = x]<br>[true] get() [r = s]</td><td>R<sub>1</sub></td><td>[x ∈ Addr ∧ s = ⊥] set(x) [s' = x]<br>[true] get() [r = s]</td><td>R<sub>2</sub></td><td></td></tr><tr><td>Map</td><td>[true] put(k, v) [s'[k] = v ∧ r = s[k]]<br>[true] remove(k) [s'[k] = ⊥ ∧ r = s[k]]<br>[true] contains(k) [r = (s[k] ≠ ⊥)]</td><td>M<sub>1</sub></td><td>[true] put(k, v) [s'[k] = v]<br>[true] remove(k) [s'[k] = ⊥]<br>[true] contains(k) [r = (s[k] ≠ ⊥)]</td><td>M<sub>2</sub></td><td></td></tr></tbody></table>

**Proposition 4.** If c right-moves in every $\mathcal{GT}(B, s)$ of $\Gamma_O$, then there is an implementation of c in which it is invisible.

## 3.4 How to use the indistinguishability graph?

Programmers can leverage the indistinguishability graph to write better concurrent code.

For instance, Theorem 1 states that if the indistinguishability graph is not connected and the object is readable, then it has a consensus number higher than 1. As a consequence, any implementation requires internally some form of synchronization [13].

The graph also helps with comparing shared objects. As an example, consider that we have the choice between objects *O* and *O'*. We can use the indistinguishability graph to decide: if the indistinguishability graphs of *O* include the ones of *O'*, then it is likely that *O* scales better. For instance, this happens when we compare *AtomicWriteOnceReference* (presented in Listing 1) with *AtomicReference* from the JDK.

Building upon such observations, the next logical step is to adjust an object to a specific usage in a given piece of code. We further delve into this idea in the next section.

## 4 Adjusted Objects

Adjusted objects are objects tailored for a specific use in a program. They are more scalable than their vanilla counterparts because they have denser indistinguishability graphs. Below, we define adjusted objects and establish this result. We also introduce a methodology to adjust an object by controlling how threads access it and/or altering its interface.

### 4.1 Principles

**Definition.** In many situations, access to a shared object is not symmetrical. A base example is a single-writer multi-reader (SWMR) register. A unique thread (the writer) may invoke operation *write* on the register. The other threads are readers and can only call *read*. Another common situation is a queue with one producer and one consumer. The producer (resp., consumer) only invokes *offer* (resp., *poll*). In such cases, the object is adjusted appropriately. In detail, recall that we write *O.m* the access permission map of a shared

object *O*. With this adjustment, *O.m* is restricted to how the threads use operations in the specific use case. For instance, a SWMR register has a single thread *w*, the writer, with *write* ∈ *O.m*[*w*]. Every other thread *p* satisfies *O.m*[*p*] = {read}.

A second adjustment is to alter the interface. For instance, as shown in Figure 1, the return value of a call can be ignored in part of a program. Another situation is when the interface is not used in full, but narrowed to a handful of operations. All these modifications are captured with subtyping.

To formally define adjusted objects, we follow the work of Liskov and Wing [27] that introduces types and subtypes. Recall that a data type *S* is a subtype of *T* when it satisfies the following two conditions: there is an abstraction function that maps a state of *S* to a state of *T* which maintains state invariants; and *S* preserves the operations of *T*. We say that *S* is a *narrow* subtype of *T* if *S* is a subtype of *T* and *T* implements only the operations *S* defines. Based on this, we define the notion of adjusted object as follows.

**Definition 1.** Let *O* and *O'* be shared objects. *O* adjusts *O'* when *O'*. *T* is a narrow subtype of *O*. *T* and *O*. *m* ⊆ *O'*. *m*.

**Examples.** To illustrate this principle, consider a reference object, as commonly found in programming languages. Its state consists of one variable *s*, initially set to null (⊥). The interface offers two operations: *get* returns the value of *s*, and *set(x)* changes *s* to *x*, provided *x* is an address. We can adjust this object by requiring that it is write-once. In which case, we add the precondition *v* = ⊥ to *set*, as detailed in Table 1. This table also presents several adjusted versions of common data types. For each data type, its operations are specified in Hoare logic [15]. The reference object corresponds to *R*<sub>1</sub>, while its adjusted counterpart is *R*<sub>2</sub> (fourth row in Table 1).

Another approach to adjust the reference is to have at most one thread that call *set* (single writer). In this case, the access permission map of the object is changed appropriately.

**Benefits.** When *O* adjusts *O'*, *O'* is at least as strong as *O*. This is a consequence of subtyping Formally,

**Proposition 5.** Consider that object *O* adjusts object *O'*. Every distributed task that is solvable with *O* (and registers) is also solvable with *O'*.
As expected, the converse proposition does not hold. We illustrate this with Table 1. In this table, $S_2$ adjusts $S_1$ by nullifying the return values of *add* and *remove*. Using Theorem 1, one can observe that $S_2$ is in $CN_1$. On the contrary, it is easy to see that the write operations of $S_1$ both have consensus power.

From what precedes, adjusting an object may reduce the amount of conflicts necessary to implement it. As a consequence, this should *boost scalability*. This key property is established below. It shows that adjusting an object increases the number of edges in the indistinguishability graphs.

**Proposition 6.** Assume that *O* adjusts *O'*. Let *s* be a common state and *B* be a bag of operations such that *B* complies with both *O*.*m* and *O'*.*m*. Then, $G_{O' \cdot T}(B, s) \subseteq G_{O \cdot T}(B, s)$.

Adjusting an object open opportunities for better scalability. In the next section, we present a methodology to achieve this. Later, we use this methodology in the construction of DEGO, an efficient library of adjusted objects for Java.

## 4.2 Methodology

Adjusting an object involves either altering its sequential specification, or restricting access to it. Figure 3 depicts examples of both techniques. In this figure, a shared object is a pair (X, Y), where X is a data type from Table 1 and Y the permission map. ALL stands for the default permissions, when threads access the full interface. Below, we explain the various adjustments in this figure.

Deleting an operation ($\stackrel{d}{\rightarrow}$) adjusts an object. For instance, this happens with *reset* for the counter object. In $C_2$, the precondition is set to *false*. We obtain the same result when the postcondition is voided. This is illustrated with the read-modify-write operation (*rmw*). In both cases, the operation is labeling in the indistinguishability graph as it fails silently.

Another approach is a stronger precondition ($\stackrel{p}{\rightarrow}$). As noted earlier, this occurs with $R_2$ which is write once in Table 1. The rationale is the same as for a deletion: Suppose that *d* has a stronger precondition than *c* and *c*'s precondition is satisfied in a permutation *x*, while *d* is not. Then, *d* fails silently in *x* which increases its likelihood to be labeling.

A third option is to have a weaker postcondition. For instance, voiding the return value of a write makes it blind. In Table 1, this happens with operation *add* in $S_2$ ($\stackrel{\rightarrow}{\}$). This alteration densifies the indistinguishability graph, increasing the moverness of other operations (see §3.3).

One can also restrict how an object is accessed. For instance, writes can be commuting ($\stackrel{c}{\rightarrow}$). In Figure 3, ($S_3$, CWMR), requires that all write operations, namely *add* and *remove*, commute when executed by distinct threads. Consequently, permutations in the indistinguishability graph that only differ in the way they are ordering these operations are connected.

Operations may also be asymmetric, that is some threads are allowed to only call certain operations ($\stackrel{m}{\rightarrow}$). Objects can be single-writer multi-reader (SWMR), or multi-writer single-reader (MWSR). Writers may also only issue commuting operations (CWMR and CWSR) on the object. All of this densifies the object's indistinguishability graphs.

<figure><img src="image_7.png" /><figcaption>**Figure 3: We combine subtyping ($\stackrel{p}{\rightarrow}$, $\stackrel{r}{\rightarrow}$) and restrictions of access ($\stackrel{d}{\rightarrow}$, $\stackrel{c}{\rightarrow}$, $\stackrel{m}{\rightarrow}$) to adjust an object.**</figcaption></figure>

As seen in Figure 3, several adjustments can be combined. In the most general case, they form an acyclic directed graph.

# 5 The DEGO Library

This section presents a library of adjusted objects for the Java language called DEGO.

## 5.1 Overview

The DEGO library provides drop-in replacements for the package `java.util.concurrent` of the JDK—hereafter, abbreviated in JUC. It contains ~11,000 SLOC [18]. DEGO includes collections (e.g., set, list) and maps, as well as other base objects (e.g., reference). Access permissions are the ones listed earlier: ALL, SWMR, MWSR, CWMR and CWSR. For an object, DEGO does not implement all the access permissions. Instead, it provides hooks and useful abstractions to this end. One such abstraction is a segmentation that we cover below.

## 5.2 Segmentation

Adjusted objects that are multi-writer collections are built with *segmentations*. A segmentation is a (dynamic or static) array of objects. Each object in the array is SWMR and own by one thread; it is called a *segment*. A segmentation allows to efficiently implement an adjusted object for which writes are commuting (that is, either CWMR or CWSR). For instance, consider the adjusted object ($C_3$, CWSR) at the bottom of Figure 3. In this case, each segment stores a counter. When it executes *inc*, a thread updates its segment appropriately. To read the counter, a thread sums up all entries. (Notice that if *inc* are unitary, such a read is linearizable.)

Different forms of segmentation are available in DEGO. In the case of a *BaseSegmentation*, the mapping between threads and segments is static. It is implemented using an instance of the class *CopyOnWriteArray* and a *ThreadLocal* variable. Consequently, to execute a read, e.g., when iterating over the collection, the thread needs to traverse all segments. This makes the *BaseSegmentation* interesting in workloads where the object is predominantly accessed through writing.

Two other types of segmentation also exist: *HashSegmentation* and *ExtendedSegmentation*. With these types, each data item added to a segmentation carries an information to identify the segment where it is stored. In *HashSegmentation*, an item is stored in the segment corresponding to its hash code. In the case of *ExtendedSegmentation*, when an item is inserted for the first
time, it retains the segment where it was stored. This is implemented using a dedicated field in the item. These two segmentations eliminate the need to iterate over all segments for a lookup.

The next section explains how each segment is implemented. It also covers other adjusted objects in the library.

## 5.3 Implementation details

To construct adjusted objects, we rely on the *VarHandle* mechanics. *VarHandles* are introduced in JEP 193. They permit to manipulate a Java variable while controlling its consistency at fine grain. There are four models: *Plain*, *Opaque*, *Release/Acquire*, and *Volatile*, ordered from the weakest to the strongest.

*Plain* offers minimal guarantees as operations may be re-ordered. This model corresponds to the vanilla Java memory model. *Opaque* ensures that operations on a single variable form a partial order, with writes totally ordered, thereby guaranteeing eventual consistency. It also guarantees that the bits from multiple writes do not interleave (for writes larger than a single memory word). The *Release/Acquire* model ensures causality. For instance, if a thread *p* changes a variable *a* then raises a flag using `setRelease`, a thread *q* must see what happened to *a* if it sees the flag raised with `getAcquire`. This model is typically used in situations where only one thread can write to a variable, while others read it. Operation in *Volatile* mode are linearizable. In DEGO, *VarHandles* are used in various SWMR constructions. Below, we detail a hash table and a skip list.

To construct an SWMR object, we start from a sequential code taken, e.g., from the JDK. This code is then extended to support concurrent readers. For instance, when a new entry is added to an instance of `SWMRHashMap`, if its key is already there, it is updated with `setVolatile`. Otherwise, a new node is created and inserted atomically in the appropriate bin. Upon a call to `resize`, nodes cannot be re-ordered on the fly due to potential readers. Instead, they are de-duplicated and inserted into the new binned array backing the hash table.

For `SWMRSkipListMap`, a new node *n* is added as follows: At each level, *n*.next is set to *m*, where *m* is the smallest higher node than *n*. Then, the *next* pointer of the node preceding *m* is changed to *n* using `setRelease`. The last level uses `setVolatile` to ensure that the insertion is globally visible.

Our library also includes a multi-producer single-consumer queue. This queue is implemented without compare-and-swap when invoking *poll*. Instead, the thread moves the head of the queue appropriately. The *offer* operation is identical to the one in the JDK (that is, in `ConcurrentLinkedQueue`).

Write-once shared objects are common in applications. For references, we use the `ConcurrentLI` implementation (Listing 1). For other objects, DEGO uses a RCU-like mechanism, using a full copy of the object and swapping the reference atomically with `setVolatile`.

Notice that in DEGO, read operations over adjusted objects are as consistent as in JUC. In particular, iterating over a collection provides the same weak guarantees.

## 6 Evaluation

This section analyzes the use of shared objects in practice. Then, it evaluates the adjusted objects of the DEGO library using micro-benchmarks and a social network application.

<figure><img src="image_8.png" /></figure>

<figure><img src="image_9.png" /><figcaption>**Figure 4:** Number of declarations of shared objects in the ASF projects: (top) on average over time, and (bot) in the 20 most modified files for the latest version of each project.</figcaption></figure>

### 6.1 How shared objects are used?

We analyze the usage of shared objects in parallel Java programs. To this end, we mined 50 prominent projects from the *Apache Software Foundation* (ASF). Our study covers the following four data types: `ConcurrentLinkedQueue`, `ConcurrentSkipListSet`, as well as `AtomicLong` and `ConcurrentHashMap`.

First, we examine the number of declarations and their proportions within each project. Figure 4(top) depicts the results for `ConcurrentHashMap`. Our findings are similar for the other data types. Overall, we observe a gradual increase in the number of declarations. On average, this represents less than 1% of the total declarations in a project (second y-axis of the figure). Nonetheless, relative to the number of lines of code, this reflects a 25% growth over ten years.

Although shared objects are used parsimoniously, they may still be pivotal in a code base. To evaluate this, we analyze for each ASF project the 20 most modified files over the past ten years. For each file, we check if it uses objects from the `java.util.concurrent` library or not. The results are reported in Figure 4 bot).

In Figure 4 bot), the x-axis represents the 50 projects. Each row corresponds to the 20 most modified files in a project. Files using (at least) one shared object are in blue, while the others are in orange. Color intensity reflects the frequency of modifications, with darker shades indicating more commits. As illustrated in the figure, nearly half of the most modified files involve `java.util.concurrent` objects. This underlines that despite their low declaration count, these objects are central to program development.

We now study the extent to which the interface is used. For this, we analyze the methods called, the classes in which these calls occur, and whether the return values are used.
<figure><img src="image_10.png" /><figcaption>Figure 5: Most used methods in the ASF projects.</figcaption></figure>

Figure 5 illustrates the usages we found for the aforementioned shared objects. For clarity, only methods representing more than 10% of the total calls are reported. The other methods are grouped into the category *others*. The number in bracket indicates how many methods are in this category.

In Figure 5, we observe that only a fraction of the interface of each object is used, with some of the methods being called much more frequently than others. In detail, out of the 134 different methods available in `AtomicLong`, just 3 of them account for 66.5% of the calls. Similarly, from the 92 different methods in `ConcurrentHashMap`, only 3 account for 57.5% of the usage. This is equal to 66.3% and 72.3% for the classes `ConcurrentLinkedQueue` and `ConcurrentSkipListSet`, respectively.

Figure 1(right) depicts the usage of `AtomicLong` in Apache Cassandra. The y-axis lists the methods used in this project. For each method, the figure indicates whether the return value is used (+) or not (X). Some methods tend to be invoked together, such as `get` and `increment And Get`. For `AtomicLong`, the two most frequently used methods are called together in 29.5% of the classes. This value changes to 40% and 45.2% with `ConcurrentSkipListSet` and `ConcurrentHashMap`, respectively. In addition, we notice that in many cases (e.g., for `increment And Get` and `add And Get`), these calls do not use the return values. Similar observations can be drawn with other programs and for the other data types.

All in all, our study reveals that there are opportunities to adjust a shared object for a specific usage in a program.

## Takeaway #1

Shared objects are rare (<1%) but critical, with 25% growth in a decade. Each program has a limited use of an object's interface.

## 6.2 Micro-benchmarks

We now evaluate the objects proposed in the DEGO library using micro-benchmarks.

**Settings.** The evaluation uses a machine with 362GB of DRAM and 4 Intel Xeon Gold 6230 CPUs, each having 40 (hyperthreaded) cores. The machine runs Linux 6.1.0-18-amd64 and Java 22-oracle (OpenJDK). Benchmarks that execute with 40 threads (or below) are run on a single socket.

For DEGO, we evaluate the following objects: `QueueMASP` which is a multi-producer single-consumer linked queue (`Q1`, `MWSR`); `CounterIncrementOnly`, which corresponds to (`C3`, `CWSR`); we implement (`M1`, `CWMR`) using an extended segmentation called `ExtendedSegmentedHashMap`; the same segmentation is used in an efficient `skipList map` (`ExtendedSegmentedSkipListMap`); and `AtomicWriteOnceReference` is the class presented in Listing 1. These adjusted objects are compared against their counterparts in the JDK. Such objects are found in the `java.util.concurrent` package, or JUC hereafter.

**Methodology.** We run each benchmark for 60 s after a 30 s warm-up phase. Each reported value is an average over 30 tests. An operation (method call) executes 1,000 times and the measure is then averaged.

For data structures (collections and maps), threads execute commuting updates. This corresponds to a common pattern where each request is routed to a particular thread (using, e.g., the hash of the data item). A data structure starts initially with 16K data items, and stores up to 32K possible values. Each item is generated randomly with a uniform distribution. Snapshot-like operations (such as iterators) are not tested. We also do not evaluate update operations that are composite (e.g., `putAll`).

First, we benchmark the adjusted objects in Table 1 under high-contention scenarios. This is equivalent to running `Synchrobench` [11] with the following parameters: `-u100-f1-l60000-s0-a0-i[16384]-r[32768]-W30-n30`. For each benchmark, we compute the throughput per thread. Since the results are per thread, an horizontal line indicates that the object scales perfectly. Conversely, a line that goes down quickly indicates poor scalability. If the line goes up, the object is hyper-scalable. This may happen due to benefit of sharing the CPU cache among hardware threads.

When multiple threads compete for access to the same object, one thread may be able to obtain a lock to utilize the object, while the others wait until the lock is available. This phenomenon can be observed by examining the `cycle_activity.stalls_total` event in the `perf` performance counter, which records the number of cycles during the execution of the program where at least one hardware thread is waiting.

We seek a correlation between throughput and the number of cycles with at least one thread waiting. To this end, we employ the *Pearson correlation coefficient*. The coefficient varies between -1 and 1 for two groups of values A and B. The closer the coefficient is to 1, the more it indicates that if A increases, B also increases linearly. Conversely, if the coefficient approaches -1, then as A increases, B decreases. A coefficient close to 0 signifies a lack of correlation.

**High contention.** Figure 6 compares DEGO versus JUC in a high-contention scenario. For maps, `put` is the unique operation called. For counters, threads repeatedly call `increment And Get`. The workload for queues is a producer-consumer: all the threads perform `offer`, but one that executes just `poll`. For references, threads call continuously `get`, once the object is initialized.
<figure><img src="image_11.png" /><figcaption>Figure 6: Performance of the objects in DEGO versus their counterparts in java.util.concurrent under high contention.</figcaption></figure>

CounterIncrementOnly reduces by 80% the number of cycle_activity.stalls_total events wrt. AtomicLong. This is the main reason for its better performance. In this experiment, the Pearson coefficient is -0.93. Hence, as the number of cycle_activity.stalls_total events increases, the throughput decreases. This phenomenon is also observed for other objects, with an average Pearson coefficient of -0.88. When 80 threads access the object concurrently, CounterIncrementOnly is 350x faster than AtomicLong. JUC also includes a LongAdder class which employs an approach similar to ours to alleviate contention. Internally, LongAdder relies on Striped64 which uses weakCompare&Set for updates. Because there is a single owner per segment, CounterIncrementOnly exclusively relies on longs. This explains why its performance is slightly higher.

ExtendedSegmentedHashMap is up to 4.4x faster than its counterpart ConcurrentHashMap. This improvement is explained with cycle_activity.stalls_total events that are 23% fewer for the adjusted object. Similarly, the skip list map in DEGO is up to 1.7x faster than its JUC counterpart. This is also explained by the fact that threads are less stalled in the implementation.

AtomicReference employs a volatile variable which requires to use barriers. When a read is performed, two barriers are applied after the value contained in the variable is loaded: a LoadLoad barrier to ensure that the read is not reordered with reads performed after the barrier, and a LoadStore barrier to ensure that writes performed after the barrier are not ordered before the reads that happened before. A third StoreLoad barrier is used to guarantee that operations on the same volatile variable are not re-ordered. However, since this barrier is applied subsequent to a write, it is not needed in this benchmark.

As seen in Listing 1, the adjusted version maintains a copy of the reference. This eliminates the need to use a barrier when reading and brings a substantial performance improvement: 11.5x on average in Figure 6.

As noted in §5.3, our adjusted queue uses a simpler mechanism to update the head when a single thread executes poll operations. This explains why QueueMASP is an average 4.3x faster than ConcurrentLinkedQueue in Figure 6.

Mixed workloads. Figure 7 presents the performance of two maps: a hash table and a skip list. Here, updates are split evenly between

adds and removes. As previously, threads updates distinct items. Reads looks for a single item in the map.

The results in Figure 7 indicate that for both maps, adjusted or not, the throughput tends to decline with more updates. This is primarily due to contention as threads try to access the same memory resources on the machine. Overall, adjusted objects perform better. This comes from their internals which permit threads to access different memory locations, thereby reducing contention.

As pointed out earlier, cycle_activity.stalls_total reports thread activity. On average, ExtendedSegmentedHashMap exhibits 30% less cycles with one thread waiting than ConcurrentHashMap. With ExtendedSegmentedSkipListMap, the reduction is 11%.

When the update ratio increases, the performance gap between DEGO and JUC widens. For instance, with a hash table, DEGO is on average 2.5x faster with 25% updates, and up to 4.5x faster with 100% updates.

*Impact of the working set.* Figure 8 evaluates the hash tables when the working set changes. On the left of the figure, the working set is the same as in prior experiments. A map contains initially 16K data items, and there are 32K items in total. We double these numbers twice to see how performance changes (right of Figure 8).

Increasing the working set results in a growth of the binned array backing the hash table. Each time the size doubles, the values in the bins are re-balanced, to ensure fast access to the objects. As a consequence, contention on a given bin reduces. Contention also decreases due to a larger working set: the likelihood of two threads to have concurrently the same hash is smaller. All of this explains why the performance gap between the two implementations narrows with larger working sets.

## Takeaway #2

DEGO clearly outperforms JUC in high-contention scenarios and with mixed workloads. This is due to reduced cycle stalls and more parallel memory accesses. As the working set grows, contention decreases, narrowing the performance gap.

## 6.3 A social network application

This section evaluates the interest of DEGO for a modern application. More specifically, we consider a Retwis-like benchmark, a simplified
<figure><img src="image_12.png" /><figcaption>Figure 7: Varying the update ratio for a hash table (Unordered) and a skip list (Ordered).</figcaption></figure>

<figure><img src="image_13.png" /><figcaption>Figure 8: Performance of a hash table with various working sets (75% of updates)</figcaption></figure>

clone of Twitter. Our implementation is multithreaded and in Java. It covers around 1,500 SLOC.

*Overview.* Our code extends Retwis' logic [31]. The social network application maintains a set of users. Each user can write a message, follow/unfollow other users, and display her timeline (that is, the messages published by people she follows). Additionally, a user can also join/leave a group of interest, and update her profile. The application uses five data structures: `mapFollowers` associates to each user its followers; `mapFollowing` stores the users each user follows; and `mapTimelines` maintains the timeline of each user. `mapProfiles` maintains the profile of each user. `community` stores the users who joined the group of interest.

When a user is added to the system, the above data structures are updated appropriately. For the timeline, a queue is used. When a user tweets a message, the message is added to the timelines of her followers. To limit performance impact, the message is sent only to the first followers. Insertion in the other timelines is done asynchronously (not implemented). When reading the timeline, all the messages in the queue are fetched, and the last 50 messages are returned. Each thread is assigned a range of users with consistent hashing. The number of threads in the application is tunable.

We compare three versions of the application. The first version is based on JUC. The second one is disjoint-access parallel (DAP). This means that threads always access distinct objects. DAP provides an upper bound on the performance of a parallel implementation. The third version uses DEGO. Objects are adjusted as follows: `mapFollowers`, `mapFollowing` as well as `mapTimelines` are all CWMR. The queue used in the timeline is multi-producer single-consumer. The set implementing the interest group is CWMR.

*Dataset.* To build the social network graph, we follow the method in [32]. This results in a graph whose in-degree and out-degree distributions abide by a power law; as found in real-world social networks, e.g., Twitter [28]. In [32], the authors include an extra step to increase the average coefficient cluster of the graph. This step is omitted in our benchmark because it is too much time consuming at the scales we consider (for $10^6$ users, it would run for hundreds of days).

<table><caption>Table 2: Workload for the social network application.</caption><tr><td>Add a user</td><td>5%</td></tr><tr><td>Follow/unfollow a user</td><td>5%</td></tr><tr><td>Post a tweet</td><td>15%</td></tr><tr><td>Display the timeline</td><td>60%</td></tr><tr><td>Join/leave the interest group</td><td>5%</td></tr><tr><td>Update the profile</td><td>10%</td></tr></table>

*The benchmark.* The workload is modeled after actual usage in real-world social networks. Table 2 details the mix of operations. The benchmark runs 10 times during 20 s after a warm-up period of 5 s. The benchmark selects in advance users that do operations and the users they follow/unfollow. These two distributions are modeled after a power law to capture that some users are more active (or popular) than others. The distribution is tuned with a parameter $\alpha$. When $\alpha$ equals 1, it is biased and when it is close to 0 the distribution is uniform.

As the benchmark progresses, the social network changes. To maintain its invariants, when a user performs follow/unfollow, it immediately applies the converse operation. This second operation is not measured in the benchmark.

*Results.* Figure 9 shows the performance of the social network application. In this experiment, the parameter $\alpha$ is set to 1. We vary the number of users and the number of threads. Performance is reported relative to JUC. In this figure, DEGO is consistently faster than the baseline, except when a single thread runs the benchmark. More precisely, DEGO is between $0.89 \times$ and $1.7 \times$ of the baseline. The largest speed-up is obtained with $10^5$ users, when using 80 threads. This is close to the performance obtained with the DAP implementation (right of Figure 9).

Many factors influence performance, ranging from the CPU cache to the size of the working set. For DEGO, write amplification due to
<figure><img src="image_14.png" /><figcaption>**Figure 9:** Performance of the social network application relative to the baseline (JUC).</figcaption></figure>

<figure><img src="image_15.png" /><figcaption>**Figure 10:** Varying the user access distribution.</figcaption></figure>

additional metadata can lower benefits. In an early version of the implementation, the sets that store the followers and the people following a given user were both adjusted (because these are CWSR). However, the impact on memory was hindering any benefit from lower contention.

Figure 10 illustrates how the distribution law to pick users impacts performance. When the law is biased, high locality favors DEGO, as contention is the dominating performance factor. Conversely, when users are picked uniformly at random, the CPU cache is less efficient. Hence the performance gap with JUC is smaller. Contrarily to DAP, DEGO and JUC share data among threads. In this experiment, DEGO has a lower cache miss ratio than DAP’s–around 3 percentage points. This explains why it is slightly better.

**Takeaway #3**

DEGO outperforms JUC, achieving up to 1.7x speed-up with 80 threads. Its advantage comes from lower contention, although write amplification may reduce gains. Performance also depends on the workload distribution and its locality.

# 7 Related Work

Programming multicore hardware is notoriously difficult [35]. To simplify its use, some recent works propose to leverage commutativity. With Veracity [7], programmers write sequential code then anote the program to express conditions under which code fragments commute. In [8], the authors introduce the SIM-commutativity rule. A sequence *y* SIM-commutes in a sequential history *h* if for any subsequence *x* of *y*, the permutations of *x* are all equivalent. Clements et al. [8] show that if *y* SIM-commutes in *h* then there exists an implementation of *y* such that the steps of the threads when executing *y* are conflict free. Translated in our framework, the rule defines a sufficient condition for *y* to be strongly labeling in *G(y, s)*, where *s* is the state before entering *y*. The commuter tool in [8] checks a specification for non-commuting operations. This corresponds to verifying the sufficiency part in Proposition 2.

Some adjusted objects in DEGO rely internally on a segmentation. In the JDK, constructs such as the ones used in `LongAdder` and `ConcurrentHashMap`<fnref n="1" /> work similarly. However, they differ from ours in the sense that each segment is writable by multiple threads. (In a segmentation, a segment is `SWMR`.) Permitting this requires

complex concurrency-control mechanisms with a non-negligible performance cost.

Jayanti [17] proposes a hierarchy ($h_m^r$) to classify objects based on their consensus numbers. The hierarchy is robust when no collection of objects with consensus number *n* can be used to solve consensus in an (*n* + 1)-process distributed system. Several works explore the consensus hierarchy, for instance to find objects at each level [9], or to test its robustness [20]. In particular, Ruppert [30] studies two classes of objects: read-modify-write (RMW) and readable. The RMW class contains objects whose operations change the state of the object before returning the previous state. Readable types are objects for which there exists an operations that can read the state without changing it. He provides a characterization of the consensus number for objects in these classes. Theorem 1 (in §3) bears similarities with these results.

Many works explore the design of efficient shared objects and data structures We refer the reader to Herlihy and Shavit's book [14] for detailed examples. Sela and Petrank [33] propose an efficient construction to maintain the size of a data structure. The work in [5] shows that objects which provide strongly non-commuting operations at their interfaces are inherently non-scalable.

Weak consistency is a possible approach to improve parallel programs. Afek et al. [1] permit concurrent histories that are not legal (linearizable) but that are at a bounded distance from a legal history. Another relaxed model is IVL which allows objects to return values that are close to correct ones [29]. Some works change the level of consistency for operations upon request. For instance, this is the case with lazy replication [22] and RedBlue [24]. Anna [37] is a key-value store built atop CRDTs. Weak consistency has the potential to scale a program. On the other hand, it complexifies coding and does not permit to maintain certain application invariants.

# 8 Closing remarks

*Limitations.* In §3, we provide a characterization of scalability based on the indistinguishability graph. There are currently two issues with these results that we plan to address in a near future. First, as in [8], the existence of a universal construction with limited (or no) conflicts does not ensure that it is practical with current hardware. Second, reducing conflict may translate into write amplification. As noted in §6, this can deteriorate the CPU cache which in turn may void the benefits of lower contention.

<footnote n="1">¹prior to Java 8</footnote>
**Future work.** A next logical step is to generate indistinguishability graphs from the specification. This would guide programmers to choose and design objects for their applications. The results reported in Figures 1 and 5 were found with the help of scripts. They provide information about the methods called in a program and how their return values are used. Going further requires to find objects that bottleneck a program. In the present paper, this question is addressed using expertise. Automating this step demands to analyze the code at runtime with a profiler [6].

**Conclusion.** Adjusting an object combines subtyping and access restriction to its interface. As captured by the indistinguishability graph, this reduces conflicts among threads and makes the object potentially more scalable. Adjusted objects are already in the wild. This paper introduces their formal foundations. It also presents a library of adjusted objects for Java called DEGO. DEGO provides drop-in replacements for the standard concurrent objects from the JDK. In our evaluation, these adjusted objects can be up to two order of magnitude faster than the common ones.

## Acknowledgments

The authors thank the Middleware '25 reviewers for their valuable feedback. This work is supported by France 2030 Initiative under grant ANR-23-PECL-0004 (PEPR Cloud).

## References

[1] Yehuda Afek, Guy Korland, and Eitan Yanovsky. Quasi-linearizability: Relaxed consistency for improved concurrency. In Chenyang Lu, Toshimitsu Masuzawa, and Mohamed Mosbah, editors, *Principles of Distributed Systems*, OPODIS '10, pages 395-410, Berlin, Heidelberg, 2010. Springer Berlin Heidelberg. ISBN 978-3-642-17653-1.

[2] Andrey Gura Andrey Kuznetsov. Efficient deque with constant-time sizing. 2018. URL https://github.com/apache/ignite/blob/master/modules/core/src/main/java/ org/apache/ignite/util/deque/FastSizeDeque.java.

[3] James Aspnes, Hagit Attiya, and Keren Censor-Hillel. Polylogarithmic concurrent data structures from monotone circuits. *J. ACM*, 59(1), mar 2012. ISSN 0004-5411. doi: 10.1145/2108242.2108244. URL https://doi.org/10.1145/2108242.2108244.

[4] Hagit Attiya, Eshcar Hillel, and Alessia Milani. Inherent limitations on disjoint-access parallel implementations of transactional memory. In *Proceedings of the Twenty-First Annual Symposium on Parallelism in Algorithms and Architectures, SPAA '09*, page 69-78, New York, NY, USA, 2009. Association for Computing Machinery. ISBN 9781605586069. doi: 10.1145/1583991.1584015. URL https://doi.org/10.1145/1583991.1584015.

[5] Hagit Attiya, Rachid Guerraoui, Danny Hendler, Petr Kuznetsov, Maged M. Michael, and Martin Vechev. Laws of order: expensive synchronization in concurrent algorithms cannot be eliminated. In *Proceedings of the 38th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL '11*, page 487-498, New York, NY, USA, 2011. Association for Computing Machinery. ISBN 9781450304900. doi: 10.1145/1926385.1926442. URL https://doi.org/10.1145/1926385.1926442.

[6] Mohamed Said Mosli Bouksiaa, François Trahay, Alexis Lescouet, Gauthier Voron, Rémi Dulong, Amina Guermouche, Elisabeth Brunet, and Gaël Thomas. Using differential execution analysis to identify thread interference. *IEEE Trans. Parallel Distributed Syst.*, 30(12):2866-2878, 2019. doi: 10.1109/TPDS.2019.2927481. URL https://doi.org/10.1109/TPDS.2019.2927481.

[7] Adam Chen, Parisa Fathololumi, Eric Koskinen, and Jared Pincus. Veracity: declarative multicore programming with commutativity. *Proc. ACM Program. Lang.*, 6 (OOPSLA2), October 2022. doi: 10.1145/3563349. URL https://doi.org/10.1145/3563349.

[8] Austin T. Clements, M. Frans Kaashoek, Nickolai Zeldovich, Robert T. Morris, and Eddie Kohler. The scalable commutativity rule: Designing scalable software for multicore processors. *ACM Trans. Comput. Syst.*, 32(4), January 2015. ISSN 0734-2071. doi: 10.1145/2699681. URL https://doi.org/10.1145/2699681.

[9] Eli Daian, Giuliano Losa, Yehuda Afek, and Eli Gafni. A wealth of sub-consensus deterministic objects. In Ulrich Schmid and Josef Widder, editors, *32nd International Symposium on Distributed Computing, DISC 2018, New Orleans, LA, USA, October 15-19, 2018*, volume 121 of LIPIcs, pages 17:1-17:17. Schloss Dagstuhl -

Leibniz-Zentrum für Informatik. 2018. doi: 10.4230/LIPIcs.DISC.2018.17. URL https://doi.org/10.4230/LIPIcs.DISC.2018.17.

[10] Panagiota Fatourou, Faith Fich, and Eric Ruppert. A tight time lower bound for space-optimimal implementations of multi-writer snapshots. In *Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing*, STOC '03, page 259-268, New York, NY, USA, 2003. Association for Computing Machinery. ISBN 1581136749. doi: 10.1145/780542.780582. URL https://doi.org/10.1145/780542.780582.

[11] Vincent Gramoli. More than you ever wanted to know about synchronization: synchrobench, measuring the impact of the synchronization on concurrent algorithms. In *Proceedings of the 20th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming*, PPOPP '15, page 1-10, New York, NY, USA, 2015. Association for Computing Machinery. ISBN 9781450332057. doi: 10.1145/2688500.2688501. URL https://doi.org/10.1145/2688500.2688501.

[12] Maurice Herlihy. Wait-free synchronization. *ACM Trans. Program. Lang. Syst.*, 13(1):124-149, January 1991. ISSN 0164-0925. doi: 10.1145/114005.102808. URL http://doi.acm.org/10.1145/114005.102808.

[13] Maurice Herlihy. Asynchronous consensus impossibility. In *Encyclopedia of Algorithms*, pages 152-155. Springer, 2016. doi: 10.1007/978-1-4939-2864-4\_36. URL https://doi.org/10.1007/978-1-4939-2864-4\_36.

[14] Maurice Herlihy and Nir Shavit. *The art of multiprocessor programming*. Morgan Kaufmann, 2008. ISBN 978-0-12-370591-4.

[15] C. A. R. Hoare. An axiomatic basis for computer programming. *Commun. ACM*, 12(10):576-580, oct 1969. ISSN 0001-0782. doi: 10.1145/363235.363259. URL https://doi.org/10.1145/363235.363259.

[16] Amos Israeli and Lihu Rappoport. Disjoint-access-parallel implementations of strong shared memory primitives. In *Proceedings of the Thirteenth Annual ACM Symposium on Principles of Distributed Computing*, PODC '94, page 151-160, New York, NY, USA, 1994. Association for Computing Machinery. ISBN 0897916549. doi: 10.1145/197917.198079. URL https://doi.org/10.1145/197917.198079.

[17] Prasad Jayanti, King Tan, and Sam Toueg. Time and space lower bounds for non-blocking implementations (preliminary version). In *Proceedings of the Fifteenth Annual ACM Symposium on Principles of Distributed Computing*, PODC '96, page 257-266, New York, NY, USA, 1996. Association for Computing Machinery. ISBN 0897918002. doi: 10.1145/248052.248105. URL https://doi.org/10.1145/248052.248105.

[18] Boubacar Kane and Pierre Sutra. Dego. https://github.com/BoubacarKaneTSP/DEGO, 2025.

[19] Boubacar Kane and Pierre Sutra. Adjusted objects: An efficient and principled approach to scalable programming (extended version), 2025. URL https://arxiv.org/abs/2504.19495.

[20] Jon M. Kleinberg and Sendhil Mullainathan. Resource bounds and combinations of consensus objects. In Jim Anderson and Sam Toueg, editors, *Proceedings of the Twelfth Annual ACM Symposium on Principles of Distributed Computing*, Ithaca, New York, USA, August 15-18, 1993, pages 133-143. ACM, 1993. doi: 10.1145/164051.164069. URL https://doi.org/10.1145/164051.164069.

[21] Eric Koskinen, Matthew Parkinson, and Maurice Herlihy. Coarse-grained transactions. In *Proceedings of the 37th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages*, POPL '10, page 19-30, New York, NY, USA, 2010. Association for Computing Machinery. ISBN 9781605584799. doi: 10.1145/1706299.1706304. URL https://doi.org/10.1145/1706299.1706304.

[22] Rivka Ladin, Barbara Liskov, and Liuba Shrira. Lazy replication: exploiting the semantics of distributed services. In *Proceedings of the 4th Workshop on ACM SIGOPS European Workshop*, EW 4, page 1-6, New York, NY, USA, 1990. Association for Computing Machinery. ISBN 9781450373371. doi: 10.1145/504136.504138. URL https://doi.org/10.1145/504136.504138.

[23] Doug Lea. Longadder: Scalable atomic counter, 2014. URL https://github.com/openjdk/jdk/blob/master/src/java/base/share/classes/java/util/concurrent/atomic/LongAdder.java.

[24] Cheng Li, Daniel Porto, Allen Clement, Johannes Gehrke, Nuno Preguiça, and Rodrigo Rodrigues. Making geo-replicated systems fast as possible, consistent when necessary. In *Presented as part of the 10th USENIX Symposium on Operating Systems Design and Implementation (OSDI 12)*, pages 265-278, Hollywood, CA, 2012. USENIX. ISBN 978-1-931971-96-6. URL https://www.usenix.org/conference/osdi12/technical-sessions/presentation/li.

[25] LinkedIn. Concurrentli, 2018. URL https://github.com/linkedin/concurrentli.

[26] Richard J. Lipton. Reduction: a method of proving properties of parallel programs. *Commun. ACM*, 18(12):717-721, dec 1975. ISSN 0001-0782. doi: 10.1145/361227.361234. URL https://doi.org/10.1145/361227.361234.

[27] Barbara H. Liskov and Jeannette M. Wing. A behavioral notion of subtyping. *ACM Trans. Program. Lang. Syst.*, 16(6):1811-1841, November 1994. ISSN 0164-0925. doi: 10.1145/197320.197383. URL https://doi.org/10.1145/197320.197383.

[28] Seth A. Myers, Aneesh Sharma, Pankaj Gupta, and Jimmy Lin. Information network or social network? the structure of the twitter follow graph. In *Proceedings of the 23rd International Conference on World Wide Web, WWW '14 Companion*, page 493-498, New York, NY, USA, 2014. Association for Computing Machinery. ISBN 9781450327459. doi: 10.1145/2567948.2567939. URL https://doi.org/10.1145/2567948.2567939.
[29] Arik Rinberg and Idit Keidar. Intermediate value linearizability: A quantitative correctness criterion. *J. ACM*, 70(2), April 2023. ISSN 0004-5411. doi: 10.1145/3584699. URL https://doi.org/10.1145/3584699.

[30] Eric Ruppert. Determining consensus numbers. *SIAM J. Comput.*, 30(4):1156–1168, 2000. doi: 10.1137/S0097539797329439. URL https://doi.org/10.1137/S0097539797329439.

[31] Salvatore Sanfilippo. Retwis, 2009. URL https://github.com/antirez/retwis.

[32] Christoph Schweimer, Christine Gfrerer, Florian Lugstein, David Pape, Jan A. Velimsky, Robert Elsässer, and Bernhard C. Geiger. Generating simple directed social network graphs for information spreading. In *Proceedings of the ACM Web Conference 2022*, WWW ’22, page 1475–1485, New York, NY, USA, 2022. Association for Computing Machinery. ISBN 9781450390965. doi: 10.1145/3485447.3512194. URL https://doi.org/10.1145/3485447.3512194.

[33] Gal Sela and Erez Petrank. Concurrent size. *Proc. ACM Program. Lang.*, 6 (OOPSLA2), October 2022. doi: 10.1145/3563300. URL https://doi.org/10.1145/3563300.

[34] D. B. Terry, M. M. Theimer, Karin Petersen, A. J. Demers, M. J. Spreitzer, and C. H. Hauser. Managing update conflicts in bayou, a weakly connected replicated storage system. *SIGOPS Oper. Syst. Rev.*, 29(5):172–182, dec 1995. ISSN 0163-5980. doi: 10.1145/224057.224070. URL https://doi.org/10.1145/224057.224070.

[35] Uzi Vishkin. Is multicore hardware for general-purpose parallel processing broken? *Commun. ACM*, 57(4):35–39, April 2014. ISSN 0001-0782. doi: 10.1145/2580945. URL https://doi.org/10.1145/2580945.

[36] Nitsan Wakart. Efficient multi-producer, single-consumer queue, 2013. URL https://github.com/JCTools/JCTools/blob/master/jctools-core/src/main/java/ org/jctools/queues/MpscLinkedQueue.java.

[37] Chenggang Wu, Jose Faleiro, Yihan Lin, and Joseph Hellerstein. Anna: A kvs for any scale. In *2018 IEEE 34th International Conference on Data Engineering, ICDE '18*, pages 401–412, 2018. doi: 10.1109/ICDE.2018.00044.