Decision Trees for Analyzing Influences on the Accuracy of Indoor Localization Systems

1st Jakob Schyga
Institute for Technical Logistics

Hamburg University of Technology

Hamburg, Germany

2nd Swantje Plambeck
Institute of Embedded Systems

Hamburg University of Technology

Hamburg, Germany

3rd Johannes Hinckeldeyn
Institute for Technical Logistics

Hamburg University of Technology

Hamburg, Germany

4th Görschwin Fey
Institute of Embedded Systems

Hamburg University of Technology

Hamburg, Germany

5th Jochen Kreutzfeldt
Institute for Technical Logistics

Hamburg University of Technology

Hamburg, Germany

indoor localization, decision trees, influences, test and evaluation

§ INTRODUCTION

Knowing the position of an entity is essential for a multitude of applications such as equipment tracking in hospitals <cit.>, elderly people support <cit.>, augmented reality <cit.>, asset tracking in warehouses <cit.>, or autonomous mobile robots <cit.>. Indoor Localization Systems (ILS) enable the determination of an entity's position in indoor environments. In today's industry, ILS are of particular importance to meet the increasing demands for efficiency, transparency, flexibility, and safety.

ILS are highly heterogeneous and complex cyber-physical systems.  <cit.> present strategies for contour-based self-localization based on LiDAR, <cit.> present an experimental comparison of camera-based pose estimation with fiducial markers, and <cit.> present an approach for machine learning-based localization using visible light. All these examples show that the performance of ILS depends on a multitude of influences.

Figure <ref> presents an application-driven perspective on the performance of ILS under influences. A real-world application or application domain determines the environment and application processes. An ILS is deployed in this environment in a particular soft- and hardware configuration. The system's performance depends on the system configuration, the environment, and the processes that determine the movement of an entity to be localized. To enable an application, the system performance must be higher than required by the application. Performance requirements are derived by analyzing the application processes.

Application-Driven Perspective on ILS Performance

Test and Evaluation (T&E) of ILS serves system developers and users to determine and compare system performance, understand system behavior, optimize the system or environment configuration, and find a suitable system for an application. The absolute accuracy of a localization estimate is considered the key performance criterion of a localization system. Since ILS are heterogeneous and complex cyber-physical systems, the position accuracy can depend on various influencing factors.

ILS are commonly tested and evaluated in benchmarking studies <cit.>, indoor localization competitions <cit.>, and in system development <cit.>. However, systematic analysis of influencing factors is rare. To achieve meaningful test and evaluation results, the application-driven perspective as presented in Figure <ref> must be taken into account.

In this work, we propose a strategy for the analysis of influences on the absolute position accuracy of ILS using decision trees. For the analysis of the T&E results, decision trees are learned in combination with application-related and technology-related categorization. The benefits of decision trees are rooted in their simple structure and intuitive interpretability.
Related research is presented in Section <ref>. Section <ref> describes the strategy for identifying influencing factors, determining the system's accuracy, and learning decision trees. The proposed strategy is applied to an Ultra-Wideband (UWB)-based and a Light Detection and Ranging (LiDAR)-based ILS, as presented in Section <ref> under consideration of an industrial application. In Section <ref>, the usefulness of a decision tree-based analysis is evaluated for several typical problems in the practical use of localization systems. In addition, limitations are discussed. Finally, we provide conclusions in Section <ref>.

§ RELATED WORK

Approaches for T&E can be divided into system vs. component-testing, black-box vs. white-box (or grey-box) testing, or building-wide vs. laboratory testing <cit.>. Influences can be considered for the experiment design and/or for analysis. In system-level testing, influences are commonly considered by designing the system set-up, the choice of the building, and the entity-type appropriately for the localization system and application under consideration. For example, <cit.> test ILS for miners in an underground mine and <cit.> for Automated Guided Vehicles (AGVs) in warehouses. Occasionally, individual influences are examined. For example, <cit.> analyze the influence of image noise on the accuracy of a visual Simultaneous  Localization and Mapping (vSLAM) algorithm, while <cit.> examine influences on the received signal strength for Wi-Fi-based localization. For comparison, results are commonly visualized by cumulative distribution functions or boxplots <cit.>.
However, determining the magnitude of various influencing factors on the accuracy of an ILS is rare.

Methodologies for T&E of indoor localization systems on a system-level exist and can be applied to systematize the process of test and evaluation. As for the consideration of influences, the EvAAL Framework only requires the building, the path, and the entity to be localized to represent the considered application <cit.>, while the ISO/IEC 18305 <cit.> additionally suggests to include particularly challenging experiments for the system under test. The T&E 4iLoc Framework <cit.> proposes a procedure to systematically define application-driven influencing factors and transpose them into an experiment in a semi-controlled test environment such as a test hall. Finally, the EVARILOS Benchmarking Handbook <cit.> proposes the systematic analysis of influences from changes in the environment, mobility, amount of radio-frequency nodes, or radio interference to a reference scenario individually. Hence, the EVARILOS Benchmarking Handbook <cit.> is the only methodology, that directly includes methods to analyze influencing factors. However, the determination of such sensitivity values comes with the following limitations:

* influences are only considered as a comparison to a reference scenario,

* dependencies between influencing factors are not considered,

* non-linear dependencies are neglected.

Therefore, sensitivity values are not suitable for describing a system's accuracy under various complex influences. An integrative approach for the application-driven determination and analysis of influences does not yet exist.

§ LEARNING DECISION TREES ON INFLUENCES TO THE POSITION ACCURACY

In the following, we propose a strategy for application-driven T&E of indoor localization systems to determine the position accuracy under different influencing factors. The problem solved by this strategy is to decide which localization performance is achievable under given influencing factors. Due to their simple structure and intuitive interpretability, we use decision trees to represent the T&E results. A decision tree is a graph-based representation of a decision function. Given a set of influences, the decision tree decides which localization performance is achieved. Figure <ref> depicts the three steps of the proposed strategy:

A. Performance metrics of the system under test are determined for each experiment together with an associated set of influencing factors.

B. The resulting performance metrics for each experiment are categorized.

C. The influencing factors labeled with performance classes are used to learn a decision tree.

Proposed Strategy for Learning Decision Trees

§.§ Test and Evaluation

In step A of Figure <ref>, performance metrics are collected from experiments under several different scenarios.

To ensure repeatability of results for the complex experiment scenario, the T&E 4iLoc Framework <cit.> is utilized as methodology.

With the T&E 4iLoc Framework <cit.>, test and evaluation works as follows. An application or application domain defines a scenario. A scenario specifies influencing factors for an experiment, such as the type of entity to be localized, the lighting conditions, and static or dynamic objects in the environment. The experiment is set up according to the scenario and an entity to be localized is equipped with the localization and a reference system for continuous localization. The coordinate systems are aligned by applying the Umeyama-Alignment <cit.>. The experiment is then executed by sequentially passing a number of predefined evaluation poses. Finally, by comparing the ground truth position with the system's location estimate at the evaluation poses, various accuracy metrics are computed.

The accuracy metrics are associated with the influencing factors of the scenario. We repeat each experiment several times to investigate the significance of the influencing factors.
The average of the performance metrics over all experiments from the same scenario is finally used for the further analysis steps.

§.§ Output Categorization

The representation in decision trees, discussed in the next subsection, requires categorization of the performance metric. The first possibility is an application-related categorization where boundaries are defined manually by setting performance classes based on requirements of an application.

If the specific application or requirements are not known or not relevant, automatic clustering can provide reasonable performance classes. Automatically generated clusters are more related to the capabilities of the system and thus represent a technology-related categorization. The k-nearest neighbor (kNN) clustering method is proposed as a well-established approach. When clustering with kNN, the number of clusters must be determined a priori. The elbow criterion is used to find the best tradeoff between clustering accuracy and overfitting, while the clustering inaccuracy in the case of kNN is measured by the sum of squared distances of the data points and their cluster center <cit.>.

§.§ Decision Tree Learning

A decision tree allows the systematic analysis of various features for a single output metric. Here, we use the performance metric as the output while the influencing factors represent the input features.
To learn a decision tree, labeled feature vectors are required. Here, this is the set of influences of a T&E scenario associated with the respective performance class. During the learning process, individual decisions are chosen so that all feature vectors leading to the same leaf have the same categorical label in the learning set. Knowing a feature vector, we can follow the decision steps from the entry node (called root) to an output category (encoded in the leafs) to obtain the category corresponding to the given feature vector.

§ EXPERIMENTS AND RESULTS

In this section, the proposed strategy to learn decision trees for the analysis of the system performance of ILS under influences is applied to an empirical case-study. To obtain a realistic experiment setup, influencing factors, and output categorization, an application must be considered. The application of Autonomous Mobile Robots (AMRs) is chosen, because AMRs require knowledge of their position for various tasks such as navigation, obstacle avoidance, material handling, or goods picking. UWB and LiDAR are common technologies for locating AMRs in warehouses <cit.>. We present the procedure from the determination of influencing factors to learned decision trees in the following for an UWB-based ILS (LOCU <cit.>, SICK AG) and a LiDAR-based ILS. The LiDAR ILS consists of a multilayer LiDAR scanner (microScan3 <cit.>), a control unit (SIM1000 <cit.>), and a localization software (LiDAR-LOC <cit.>) from SICK AG.

§.§ Experimental Setup and Factors of Influence

In the following, the experimental setup, parameters, and technologies are introduced. First, an overview of the test environment is given. Afterwards, details on the two ILS, namely LiDAR and UWB, are given together with their influencing factors that exist in the test environment.

§.§.§ Test Environment and Experiment Setup

The experiments are  carried out at a test facility at the TUHH Institute for Technical Logistics. The facility contains various objects such as racks, load carriers, and industrial vehicles and thus represents a typical warehouse environment. A high-precision optical motion capture system provides localization data that serves as a position reference for accuracy evaluation and robot control <cit.>. The collected performance measure, thus, is the euclidian distance between the location estimate of an ILS and the actual position provided by the reference system. The TurtleBot2 robot platform is equipped with the localization devices to be used as the entity to be localized (Figure <ref>).

Experimental Setup: (a) TurtleBot2 equipped with LiDAR Sensor, UWB Tag, and Reflectors for the Motion Capture System. (b) Aisle Environment at the Institute for Technical Logistics. (c) Recorded Contour Map of the Aisle Environment. The Experiment Path, the Position of the LiDAR Reflectors, and the UWB Anchors are marked.

§.§.§ LiDAR ILS and Influencing Factors

The LiDAR ILS computes the sensor's position via map matching. The distance of the sensor to objects in the environment is determined by the emission and detection of laser impulses. The position of the sensor is then determined by comparing the scan points with a previously recorded map of the environment applying a particle filter, supported by the data collected from an Inertial Measurement Unit (IMU). The influencing factors and parameter values are summarized in Table <ref> on the left. Reflectors can be used as reference points to improve localization accuracy. Besides the presence of reflectors, the quality of the pre-recorded map, the dynamics of surrounding entities, and the Field of View (FoV) are considered application-driven influencing factors. In the experiments, the FoV is limited to either $270^{\circ}$ or $180^{\circ}$.  A person walking in front of the robot at a distance of 1.5 to 2.5m emulates dynamics. To account for map quality as an influencing factor, two environments are set up - the empty test area (Empty) and an area with logistic objects representing a warehouse aisle (Aisle). A map is recorded for each of the environment configurations. Figure <ref> shows the robot in the Aisle environment, while Figure <ref> shows a recorded map in the same environment. In addition, the planned path, the positions of the LiDAR reflectors and UWB anchors are marked. The pairwise combination of the environments and maps results in four configurations. We quantify the map quality by recording an additional map during an exemplary experiment execution for each environment and comparing it with the original maps using a point cloud matching algorithm based on Iterative Closest Point (ICP) registration with a prior global registration step using the implementation in the python library Open3D <cit.>. Table <ref> presents the results of this process as a value between 0 and 1 for each of the four configurations, where 1 represents a perfect match.

2c|LiDAR      2cUWB

Factors      Values     Factors      Values

Dynamics     yes, no     Dynamics     yes, no

Reflector     on, off     EKF     on, off

FoV     [$180^{\circ}$, $270^{\circ}$]     Environment     empty, aisle

Map quality     [t][0.54, 0.81,
0.84, 0.99]

Parameter Values for Considered Influencing Factors

Map     Empty     Aisle

Empty     0.84     0.54

Aisle     0.81     0.99

Map Quality

§.§.§ UWB ILS and Influencing Factors

The UWB ILS is based on the time-difference-of-arrival method. Localization systems based on radio-frequency signals are generally prone to None-Line-of-Sight (NLoS) errors. The Aisle environment leads to realistic NLoS for the UWB ILS. Therefore, the environment is considered as an influencing factor. Dynamics are likewise considered for the LiDAR and the UWB ILS. Finally, the system can be configured to filter the position using an Extended Kalman Filter (EKF).

§.§ Experiment Execution

Combining the parameter values from Table <ref> results in 32 possible scenarios for the LiDAR and eight scenarios for the UWB ILS. To evaluate the repeatability of an experiment and reduce noise effects, three experiments are performed for each scenario, resulting in a total of 120 experiments. The localization systems are synchronized with the reference system via Precision Time Protocol (PTP) <cit.> and aligned prior to the experiments.
For each experiment, the system and the environment are configured according to the scenario. The localization and reference data are then continuously recorded as the robot successively traverses 33 evaluation poses at an average speed of 0.3 m/s. The resulting path describes the shape of two rectangles as shown in Figure <ref>, with the start and end point in the center.

§.§ Accuracy Evaluation

Comparison of experiments: (a): UWB, LiDAR, and reference trajectories for a single experiment. (b): Cumulative distribution function for comparison of experiments and scenarios.

The code provided with the T&E 4iLoc Framework <cit.> is used to compute the accuracy metrics for each experiment. Figure <ref> shows the recorded trajectories of the UWB ILS, the LiDAR ILS, and the reference system for an exemplary experiment. Figure <ref> shows the cumulative distribution functions for six experiments from two scenarios for the LiDAR ILS. Comparing the experiments for one scenario indicates good repeatability, because their cumulative error frequencies are very similar, while the comparison of the scenarios indicates the significance of influences. The 95%-percentile of the horizontal position error ($h_{95}$) at the evaluation poses is further considered as the performance metric. The median of the position error is an alternative, more robust metric, but high percentiles are more relevant for end-users and thus support an application-driven scenario. The mean value of the percentiles is used from the three experiments for each scenario.

§.§ Output Categorization

As described earlier, the categorization of the output can be either application-related or technology-related. Application-related categorization is favorable to determine the suitability of an ILS or its configuration for a specific application. Different processes of an application may require different localization accuracy. For the considered application of AMRs for warehouses, we define four performance classes for different processes with requirements for the 95%-percentile of the horizontal position error. To enable the automated picking of goods, we require an accuracy of less then 0.05m (performance class A), while 0.1m is sufficient for material handling (performance class B). Tracking the absolute position of assets (performance class C) requires 0.5m and global navigation 1m (performance class D).

For technology-related categorization, automatic clustering via kNN is used together with the elbow criterion to determine the number of clusters.
For the data considered, the optimal number of clusters is five. Table <ref> shows the clusters resulting from kNN for five clusters along with the results of application-related categorization.

Performance Class      Requirements in [m]     Process

Application-Related Categorization
(Based on Process Requirements)

A      $ h_{95} <$ 0.05     Goods Picking

B      0.05 $\leq h_{95} <$ 0.1     Material Handling

C      0.1 $\leq h_{95} <$ 0.5     Asset Tracking

D      0.5 $\leq h_{95} <$ 1     Navigation

Technology-Related Categorization
(Based on System Capabilities)

I     $ h_{95}<$ 0.056     -

II      0.056 $\leq h_{95} <$ 0.209     -

III      0.209 $\leq h_{95} <$ 0.394     -

IV      0.493 $\leq h_{95} <$ 0.493     -

V      $ h_{95} \geq  $ 0.493     -

Performance Classes and Accuracy Requirements

Figure <ref> shows the 40 data points, i.e., the 95%-precentiles of the horizontal position error for each scenario with the application-related and the technology-related performance classes. Intuitively, the automatic clustering provides reasonable categories. With the exception of one data point, the data points of performance classes A and B correspond to classes I and II, and the data points for performance class D correspond to class V. For technology-related categorization, the data points of performance class C are split into class III and IV.

Data Points, combined for UWB (purple) and LiDAR ILS (green) with Application and Technology-Related Categorization

§.§ Decision Trees

Decision Tree for Application-Related Performance Classes

Decision Tree for Technology-Related Performance Classes

The python package scikit-learn <cit.> is used to learn the decision trees for the combined data set of the UWB and LiDAR ILS. We present the resulting decision trees for application-related and technology-related categorization in Figure <ref> and Figure <ref>.
Each leaf contains at least one data point. Since we use the average of three experiments, we have only one data point per feature vector. Therefore, there are no contradicting outcomes.
For continuous data such as map quality or the FoV, the midpoint of the parameter values is chosen as the decision boundary, i.e., 0.676 and 225$^\circ$, respectively. The scenario is specified more and more following the tree-decisions from top to bottom. If an influence is not considered following a path from the root to a leaf of the tree, this influence is not relevant for the performance class represented by the leaf, i.e., all specifications for this influence result in an identical performance class.

We first consider the application-related decision tree from Figure <ref>.
The root node decides the type of system. For the UWB ILS, either performance class C or D are achievable, whereby the type of environment and the EKF support are relevant influences. Hence, the dynamics are not considered relevant, when deciding on a performance class. To achieve performance class C and thus meet the defined requirements for asset tracking, there are two options. Either the environment is Empty (i.e., optimal LoS), or for the Aisle environment the EKF support must be switched on. Following the branch of the LiDAR ILS, either performance class A or performance class B is reached, whereby all parameters are basically relevant. If the map quality is greater than 0.676, performance class B is only reached if the FoV is below 225$^\circ$, reflector support is switched off, and the map quality remains below 0.914. On the other hand, if the map quality is less than 0.676, performance class A is reached only if the FoV is greater than 225$^\circ$, reflector support is on, and there are no dynamics induced.

The structure of the technology-related decision tree from Figure <ref> is similar to the application-related decision tree, which is an intuitive result considering the intersections of performance classes from Figure <ref>. On the LiDAR side, the only difference is that the dynamics are not relevant for any decision. This can be explained by the division of data points into categories presented earlier. There is one data point that belongs to performance class I and B, which results from the scenario 'ILS: LiDAR,  Map Quality: 0.54, FoV: 270$^\circ$, Reflector: on, Dynamics: yes'. When dynamics is on, the accuracy is reduced. However, for the technology-related categorization, this does not result in a worse performance class. On the UWB branch side, a new performance class is introduced, which leads to additional relevant features for determining scenarios from that performance class. If the Aisle environment is chosen and EKF support is enabled, the induced dynamics is a decisive criterion. When the dynamics is turned off, the system performs better and performance class III is reached.

§ OPPORTUNITIES AND LIMITATIONS OF ANALYZING DECISION TREES

We introduced a new analysis based on the combination of a clearly determined T&E process combined with meaningful output categorization (application- or technology-related) and the visualization using decision trees. In the following, we present opportunities and limitations of analyzing decision trees that represent influences on the accuracy of ILS according to our proposed strategy.

§.§ Opportunities

The decision tree representation automatically prepares and provides the experimental results in a simple structure that is intuitively interpreted by a human.

Increasing reproducibility and comparability for benchmarking ILS
Ideally, the test environment can be abstracted by various influencing factors. When benchmarking ILS, the influencing factors on the system performance are often not clearly stated. By reporting the performance metrics not just as a single number, but by presenting the results with influences in the form of decision trees, the reproducibility and comparability of benchmarking results is increased.

Understanding the impact of influencing factors on system performance
Both users and system providers can use a decision tree to decide which influencing factors are relevant under which conditions. Looking at the application-related decision tree from Figure <ref>, if the map quality for the LiDAR ILS is greater than 0.676 and the FoV is greater than 225$^\circ$, performance class A is achieved regardless of the reflector support.

Finding a suitable system for a given application
If the requirements for an application including its environment are known, decision trees can be used to find the optimal system. In the given example, the process of picking goods would require the LiDAR ILS, while the UWB ILS would be sufficient for navigation.

Optimizing the system or environment configuration to meet application requirements
In the event that the application requirements are not met by an ILS under given influences, the system and environment configuration can be optimized to reach a scenario that results in a satisfactory system performance. For example, for the scenario  'ILS: LiDAR,  Map Quality: 0.54, FoV: 270$^\circ$, Reflector: off, Dynamics: no', the use of reflectors would result in a change from performance class B to performance class A, enabling the process of good picking.

§.§ Limitations

Influences can be challenging to control, quantify/categorize, or generalize. For example, the influence of the recorded map on the accuracy of a LiDAR ILS can hardly be generalized by a single metric such as the suggested map quality value. Furthermore, continuous feature values in particular should be viewed with caution. For example, a FoV of 5$^\circ$ or a map quality of 0.1 could probably not end up in performance class A, as suggested by the decision trees in Figure <ref> and Figure <ref>. In the presented case-study, no data is provided with FoV less than 180$^\circ$ or a map quality of less than 0.54. Other approaches for analyzing influencing factors, such as a factor analysis <cit.>, eventually, yield more accurate results for these cases. However, by using decision tree learning, we can model even non-linear dependencies and categorical influences. In addition, only few influencing factors were examined so far.  Further influences could be investigated, but it should be noted that the condition of testing the scenarios in all constellations leads to an exponential increase in the number of experiments.

In this case study, we collected data in a certain test hall under various restrictions, such as the used robot or path. For the potential of the analysis of influences with decision trees to unfold, it ultimately comes down to the quality of the collected data. To reliably enable the presented opportunities in practice, the T&E data must represent the real world. Ideally, the experiments and influences reflect reality. In addition, the experiments should produce the same results when repeated multiple times in the same or a different test environment. Designing system-level experiments and defining influences that provide repeatable results that are relevant in real-world applications is a major challenge.

§ CONCLUSIONS

In this work, a strategy for determining the position accuracy of ILS under application-related influences and the representation of the data in decision trees was presented. In a first step, the absolute position accuracy has to be determined by empirical test and evaluation. The T&E 4iLoc framework is used as methodology for test and evaluation.. The framework provides a systematic way to determine performance metrics for application-dependent test scenarios consisting of various influencing factors. Next, the performance metrics from several experiments under different influences are categorized into performance classes. This can either be done application-related based on application requirements, or technology-related, based on automatic clustering. For automatic clustering, we propose the kNN algorithm in combination with an elbow criterion. Finally, the experiments associated with the influencing factors are labelled with the performance classes and decision trees are learned.

The strategy was successfully demonstrated by empirical experiments. The horizontal position accuracy ($h_{95}$) of a UWB and a LiDAR ILS was determined considering the  application of AMRs in warehouses for a total of 120 experiments under different influences. The application is considered to define application-driven influencing factors and application-related output categorization. The decision trees provide a simple and intuitively interpretable overview of the systems's performance, depending on the influences. Furthermore, the opportunities of analyzing decision trees for benchmarking ILS, identifying a suitable system, optimizing the configuration, and understanding the impact of influencing factors are presented. The opportunities of analyzing the decision trees in practice ultimately depend on the quality of the T&E results. Nonetheless, our proposed strategy provides a simple way to generate decision trees as an intuitive, comprehensible and meaningful representation of the influences on the position accuracy of ILS.

§ ACKNOWLEDGMENT

This work is supported by the TUHH $I^3$ Projects funding. Special thanks go to the 3D_Log project team.


Maynooth University Department of Computer Science, Maynooth,
Irelandrob.kelly@cs.nuim.iehttps://orcid.org/0000-0001-8266-2961 Maynooth
University Department of Computer Science and Hamilton Institute, Maynooth,
Irelandbarak@cs.nuim.iehttps://orcid.org/0000-0003-0521-4553 Maynooth
University Department of Computer Science, Maynooth,
Irelandpmaguire@cs.nuim.iehttps://orcid.org/0000-0002-8993-8403 Robert Kelly,
Barak A. Pearlmutter, and Phil MaguireFunded by the Government of Ireland
Postgraduate Scholarship.

###### Acknowledgements.

I want to thank William Leiserson for his invaluable help with reviewing and
feedback. I also want to thank Nir Shavit for extensive access to hardware for
running the benchmarks.Jiannong Cao, Faith Ellen, Luis Rodrigues, and Bernardo
Ferreira 4 22nd International Conference on Principles of Distributed Systems
(OPODIS 2018) OPODIS 2018 OPODIS 2018 December 17–19, 2018 Hong Kong, China
122 0

# Concurrent Robin Hood Hashing

Robert Kelly  ,  Barak A. Pearlmutter  and  Phil Maguire

###### Abstract.

In this paper we examine the issues involved in adding concurrency to the
Robin Hood hash table algorithm. We present a non-blocking obstruction-free
K-CAS Robin Hood algorithm which requires only a single word compare-and-swap
primitive, thus making it highly portable. The implementation maintains the
attractive properties of the original Robin Hood structure, such as a low
expected probe length, capability to operate effectively under a high load
factor and good cache locality, all of which are essential for high
performance on modern computer architectures. We compare our data-structures
to various other lock-free and concurrent algorithms, as well as a simple
hardware transactional variant, and show that our implementation performs
better across a number of contexts.

###### Key words and phrases:

concurrency, Robin Hood Hashing, data-structures, hash tables, non-blocking

###### 1991 Mathematics Subject Classification:

[500]Theory of computation Concurrent algorithms

###### category:

##  1\. Introduction

Concurrent data-structures allow multiple threads to operate on them without
risk of data corruption, as well as providing guarantees of correctness for
concurrent operations. Lock-free data-structures are a class of concurrent
data-structures that have specific properties relating to system or thread
progress guarantees. The programming of portable and practical lock-free data-
structures is becoming ever more practical, with the addition of mainstream
language support for atomic variables, and a well defined thread memory model
(see [5], [28]).

Concurrent algorithms can be separated into two major classes, namely blocking
and non-blocking, with both featuring further partitions based on the specific
progress guarantees within those classes [20]. Blocking algorithms have well
documented issues when it comes to their use. They are susceptible to
deadlock, priority inversion, convoying, and a lack of composability with
respect to multiple operations on data-structures. A lock-free, or non-
blocking, algorithm has none of these problems. Such algorithms suffer,
however, from their own set of challenges relating to memory management ([1],
[2], [26], [14], [9]), correctness ([22], [24], [3]) and potentially
lackluster performance as the system is flooded with contention under heavy
write load. As hardware manufacturers resort to expanding processor core
counts for enhanced performance [34], non-blocking data-structures are coming
to the fore, providing more robust progress guarantees and tolerance to the
suspension of threads. For end consumers to realise the full performance of
their system, algorithms must efficiently exploit as many cores as possible.

Hash tables are one of the major building blocks in software applications,
providing efficient implementations for the abstract data types of maps and
sets. These data-structures are highly versatile, making them an active area
of research in concurrency (e.g. [25], [20], [21], [8], [27], [30], [32]).
Hash tables are associative data-structures that contain a pool of keys and
associated values [10], lending themselves to efficient implementations. In
general, they feature the methods Add, Remove, and Contains, each of which is
bound by $\mathcal{O}(1)$ computational complexity while requiring
$\mathcal{O}(n)$ space [10]. Hash table algorithms achieve this performance by
calculating an index, called a hash, from each key, and use this to
efficiently find the relevant entry in the pool of keys, normally an array.
Unlike comparative structures, which store keys in a sorted order and binary
search through the space, hash tables rely on the hash function to distribute
the keys across the space. Ideally, the hash function generates a unique index
for each key. In reality, however, the keys often have the same hash, creating
what is known as a collision. A primary focus of research in hash tables is
how to efficiently deal with these collisions.

Hash tables can be divided into two major design variants, namely open-
addressing and closed-addressing (i.e. separate-chaining). Open addressing
stores the key and value pairings in different buckets in the table, either
through a pointer or directly in the internal array itself, with a single item
allowed per bucket. When a hash collision takes place (when another entry has
taken the desired bucket), a new bucket is selected via some collision
resolution algorithm. Separate chaining, on the other hand, stores a pointer
to a list of values at that bucket, containing all the key and value pairings
that collided on that bucket.

Robin Hood Hashing [7] is an open-addressing hash table method in which
entries in the table are moved around so that the variance of the distances to
their original bucket is minimised. Insertion is a multi-stage process,
potentially moving multiple items throughout the table. The general goal is to
find an empty bucket, or another entry that is less ‘deserving’ of its bucket
than the current item being inserted or moved. If an empty bucket is found, it
is taken. If another less deserving entry has been identified, then it’s
swapped with the current entry and ‘kicked’ further down the line, with this
process repeating until an empty bucket is found. The serial version of Robin
Hood is well suited to modern computer architecture. As CPU utilisation
effectively becomes a function of the memory bottleneck [11], algorithms that
use the CPU cache more efficiently can enhance performance for memory bounded
tasks. For instance, Robin Hood Hashing has a very low expected probe count,
allowing reads to be culled early even though the algorithm uses linear
probing. Low probe counts mean fewer cache misses, performing very well on
modern architectures. As it stands, these attractive properties have been
maintained in our concurrent versions. Our concurrent solution manages to
achieve non-blocking progress with physical deletion and all of the
aforementioned benefits of the serial algorithm. We use an algorithmically
optimised K-CAS [4] implementation along with a timestamp mechanism to handle
bulk relocations while maintaining correctness.

In Section 2 we review the current landscape of concurrent and lock-free hash
tables, and the original Robin Hood algorithm. Section 3 outlines the
structure of our algorithms and the various challenges encountered in adding
concurrency, while Section 4 discusses the performance of these algorithms
relative to competitors.

##  2\. Background

###  2.1. Prior Work

A number of concurrent open-addressing hash table algorithms have been
proposed. Purcell and Harris [30] presented a lock-free open-addressing hash
table where per-bucket upper bounds are stored in conjunction with the keys,
thus allowing searches to be culled early. Nielson and Karlsson [27] built
upon the work of Purcell and Harris with a Lock-Free Linear Probing hash
table, simplifying the earlier algorithm, reducing the number of bucket states
required, and removing the word normally required. Herlihy, Shavit, and
Tzafrir [21] presented Hopscotch Hashing, a concurrent hash table algorithm
with outstanding performance. This algorithm allows searches, insertions, and
removals to skip over irrelevant items, and is also cache aware in its
reordering of entries present in the table. While Hopscotch’s insertions and
deletions are blocking, the mutating operations are sharded over multiple
locks.

Like open-addressing, separate-chaining can be implemented in many different
forms. Michael [25] presented a lock-free hash table, with each bucket
containing a slightly modified Harris linked list [16]. Shalev and Shavit [32]
presented a particularly succinct implementation of using a linked list as a
hash table, indexing into it from an array of node pointers. In this case, the
list can grow forever, so long as pointers to new entry points are added to
prevent the probe length from growing out of control. The table can be
automatically resized, as only the entry point array of pointers need be
extended. Laborder, Feldman, and Dechev [13] presented their Wait-Free Hash
Table, whereby a key collision at a bucket leads the bucket to be expanded
into another sub-table until a point is reached such that all collisions are
resolved.

###  2.2. Original Robin Hood

Robin Hood Hashing was first proposed by Celis [7] in 1986. Though remaining
relatively obscure, it has recently gained recognition via the new programming
language Rust [35], which has adopted Robin Hood as its standard hash table
algorithm. Robin Hood is an open-addressing hash table algorithm that employs
linear probing for finding items and for finding spaces for new entries. Robin
Hood does exactly what it says on the tin: it steals from the rich and gives
to the poor. Here, “rich” refers to items that got lucky during the hashing
process, by finding a free bucket close to their original bucket. In other
words, these “rich” items have a low Distance From their expected Bucket (this
distance is referred to as DFB for short) and a low expected probe count
before being found. In contrast, being “poor” means hashing to a bucket that
has been heavily saturated beforehand, and thus has a high number of items to
step over before finding a free bucket. “Poor” items thus have a higher DFB,
and a high expected probe count before being found.

Figure 1. An example Robin Hood insertion where V is inserted into X’s bucket.
Each step of the insertion is numbered.

Robin Hood solves this inequality during insertion by moving existing entries
around the table. In other words, when the item being relocated has a larger
DFB than the item currently being examined, these items are swapped, and the
search continues for an empty bucket. Once an empty bucket is found, the
relocated item is inserted, and the process terminates. Figure 1 shows an
example Robin Hood insertion. In all examples the subscripts represent the DFB
of each entry. Step 1 shows the table initially containing X, Y, Z, and W,
each with a DFB of 0, 1, 1, and 1 respectively. Step 2 shows that V is to be
inserted where X currently resides. Step 3 shows how V doesn’t kick out X, as
they’re equal in DFB; the same is true for Y in step 4. Step 5 shows the swap
between V and Z, as V is now further away than Z (DFB of 2, compared to 1). Z
linear probes further down the table in step 6, and in step 7 swaps with W.
Finally, in step 8 W lands in the empty bucket at the end, and the insertion
process finishes. In summary, V is swapped with Z, Z is swapped with W, and,
finally, W is placed in the empty bucket at the end. Figure 2 shows a
comparison of the Robin Hood insertion and the same insertion using the Linear
Probing collision resolution. As can be seen, the entry V ends up far further
away using Linear Probing than using Robin Hood.

Figure 2. Comparison of Robin Hood to Linear Probing for insertion of V.

The outcome of this shuffling is a reduced average variance in DFB (i.e.
reduced probe lengths). Not only does reduced variance make for more
predictable and uniform performance, it also allows searches to be culled
early, without having to find an empty bucket, which is typically the
requirement for calling off a linear probing search. As soon as the item being
examined during the search has a lower DFB than the current probing DFB the
search can be called off, with the knowledge that it will be unsuccessful: the
item being searched for cannot possibly be present in the table, as it would
already have kicked out any items with a lower DFB than itself. Figure 3 shows
an example Robin Hood search operation. The key U is being queried, probing
the table as far as the bucket containing Z before terminating. The linear
probing is shown in steps 1 to 3, while termination happens at step 4.
Termination is possible as U is 3 buckets away from its original bucket,
whereas Z is only 2, meaning U can’t possibly be in the table. The reasoning
is that if U was being inserted it would have displaced Z for having a higher
DFB than itself; therefore, it cannot possibly be in the table. A similar
search taking place using linear probing would have to keep searching until an
empty bucket is found, resulting in far more probes at higher load factors,
and higher amounts of cache misses too. We refer to this search mechanism as
the Robin Hood invariant. Violating this invariant leads to a corrupted table,
potentially losing items in the table. These factors enable Robin Hood to
support a higher load factor, given that the expected search is only 2.6 probe
counts on average for successful searches, and $\mathcal{O}(ln(n))$ for
unsuccessful searches [7].

Figure 3. Example Robin Hood search, querying the table for the entry U.

Deletion in Robin Hood is more complicated than in linear probing. In linear
probing one can simply tombstone a bucket, as it does not matter what entry
was there before. However, in Robin Hood the DFB of the entry matters, as
subsequent searches employ this metric to determine if the entry being queried
is contained in the table. The solution to this is to either logically mark
the entry as deleted, or shift back every entry in front of it until some
criterion is met. Logical deletion is unacceptable, as it causes the table to
fill up and lose its efficiency, resulting in unnecessary resizes. Backward
shifting effectively undoes the insertion of the entry we wish to delete from
the table. An example of this is given in Figure 4. Since the removing thread
cannot tell which entries the item to be deleted originally displaced to get
there (assuming they aren’t at their ideal bucket), we must shift back all
items. The shifting is continued until we find an empty bucket or an item in
its ideal bucket. Step 1 shows the initial table, step 2 shows the “nulling”
of Y. Steps 3, 4, and 5 show a backward shifting of entries within the table.
Step 6 shows the termination of the shifting, as an empty bucket is ahead of
W.

Figure 4. Example Robin Hood deletion. Entry in question is Y.

###  2.3. K-CAS

K-CAS or, multi-word-compare-and-swap, is an extended version of CAS,
supporting multiple compare-and-swap operations on many distinct memory
locations, all of which either succeed or else fail together. Our algorithm
employs a modified version of the K-CAS originally proposed by Harris, Kaiser
and Pratt [17]. The K-CAS algorithm does come at a small cost, reserving an
additional 0-2 bits for each word being manipulated by the algorithm. These
reserved bits are needed to store run-time type information that allows
descriptors to be distinguished from normal values. The standard K-CAS
interface provides two functions for basic reading and writing,
K_CAS_READ(loc: T*) -> T and K_CAS_WRITE(loc: T*, T val) -> void, and a
mechanism for adding addresses and their values to a descriptor. The rationale
for needing dedicated read and write functions is that the values being
operated on have specific bits reserved to indicate an ongoing K-CAS
operation. Both the read and write functions help any pending K-CAS operation
installed at that particular memory location.

Traditional K-CAS implementations require a memory reclaimer system, as each
descriptor must be fresh to avoid the ABA problem [29] . However, the specific
K-CAS implementation we use, developed by Arbel-Raviv and Brown [4], employs
descriptor reuse, thereby eliminating the need for a freshly allocated
descriptor for each operation. Given that this implementation does not require
a memory allocation per K-CAS operation, or a reclaimer, its performance is
substantially improved. This enhancement makes K-CAS a feasible concurrency
primitive and, as we show, allows it to outperform the best lock-based hash
table algorithms.

##  3\. Algorithm

###  3.1. Challenges For Concurrent Robin Hood

The primary challenge in making Robin Hood concurrent is, unsurprisingly, the
modifying operations on the table. Both Add and Remove can modify large parts
of the table, with Add potentially performing a global table reorganisation,
and Remove potentially shifting back many entries. These problems defeat naive
solutions such as sharded locks, as Add could potentially grab all of them,
leading to no concurrency. Another issue is that of deadlock; insertions at
two different points in the table might grab the locks in a cyclic manner,
leading to deadlock. For example, the table could have 8 locks with 8 ongoing
insertions in 8 different locations. Initially, each insertion will grab one
lock corresponding to the original location. If all insertions relocate an
entry to another lock section, deadlock occurs. To achieve a truly concurrent
implementation of Robin Hood we need an efficient mechanism to update large
disparate parts of the underlying table. For this there are two options. The
first is K-CAS, which became feasible from a performance standpoint thanks to
the work of Arbel-Raviv and Brown [4]. The second choice is hardware
transactional memory, which we use to provide efficient speculative lock-
elision [31].

###  3.2. Overview

K-CAS is a natural choice for relocation-based hash table algorithms. It
prohibits a number of issues that typical concurrent algorithms run into, for
example, examining whether invariants hold during some intermediate operation
or state. K-CAS behaves like an expressively weaker transactional memory [19],
but unlike hardware transactional memory [37], it has well defined progress
guarantees. Another reason for using K-CAS is that keys can be stored directly
in the table, thus improving cache locality. The entry relocations initiated
by modifications are summarised into a K-CAS descriptor instead of relying on
in-place modifications of the table featuring entry relocation information.
Threads cannot see a K-CAS operation partially completed. Nevertheless,
special considerations need to be made for operations when reading the table,
as they can experience inconsistent views if applied naively.

Since entries can be moved around during concurrent reads, they could
inadvertently miss a key due to some ongoing relocation operation. For
example, when Contains uses the Robin Hood invariant to terminate a search
early, there is a race with a concurrent Remove which could have shifted that
particular entry in question back through the table, behind the reader,
leading to an incorrect result. This happens when Remove is called on an
unrelated entry located in the vicinity of the entry being queried. An example
of this phenomenon is illustrated in Figure 5. Here the entry V is being
queried while at the same time entry Y is being removed. When the reader gets
to the bucket containing V, the remover executes its K-CAS operation, shifting
a number of entries, including V, backwards. The searcher then checks the
bucket after the shift and sees Z, terminates the search, and falsely declares
V as not present in the table.

Figure 5. The problem of concurrent searches and removals. The searcher is
trying to find V while entry Y is being removed

Our solution to avoiding this race is to associate each part of the table with
a timestamp, updated upon every relocation. Figure 6 shows the correspondence
of timestamps to physical buckets in the table. A timestamp can be mapped onto
several buckets in the table. The mapping of the timestamps is identical to
how locks are sharded in blocking hash tables like Hopscotch Hashing [21].
When a reader is checking for the presence of a particular key, the reader
remembers the timestamps encountered during its search. If the key is found
and read atomically, then the search can finish. However, if they key isn’t
found the reader must check the values of those timestamps after the search
has completed. If a discrepancy is found, the search is restarted, otherwise
we know for certain the key isn’t in the table. When Remove is executing, it
increments the timestamp every time it shifts an entry, and similarly for the
Add method.

Figure 6. An illustration of how the timestamps are sharded across multiple
entries.

###  3.3. Algorithm Methods

We now outline our algorithm with annotations of code presented in Figures 7,
8, and 9, which highlight and explain important parts and what they do. The
algorithmic code has been simplified in two areas. The first simplification
involves timestamps: the code provided doesn’t check if a timestamp has
already been added to the list, nor does it check the number of entries per
timestamp. The second simplification involves Remove when shuffling elements
back. In both cases the code is long but simple, so we have excluded it for
the sake of clarity.

  *
fn Contains(key: K) -> bool {
start_bucket: u64 = hash(key) % size;
retry:
timestamps: List<u64> = [];
for(i = start_bucket, cur_dist = 0;; cur_dist++, i++) {
i %= size;
// Add the timestamp for that specific index.
timestamps.append(read_timestamp(i));
cur_key: K = K_CAS_load(&table[i]);
if(cur_key == Nil) { goto timestamp_check; }
if(cur_key == key) { return true; }
distance: u64 = calc_dist(cur_key, i); // Robin Hood Invariant
if (distance < cur_dist) { goto timestamp_check; }
}
timestamp_check:
// Compare every timestamp.
for(i = start_bucket, idx = 0; idx < timestamps.size(); i++, idx++) {
i %= size;
if(list[idx] != read_timestamp(i)) { goto retry; }
}
return false; // No key
}

Figure 7. Pseudo-code for Contains

A - Contains

All line numbers refer to Figure 7. At the beginning of the Contains method, a
timestamp list is created. Line 8 adds the timestamp for that bucket to the
list of timestamps. Line 9 loads a candidate key from the table; if it’s a Nil
key, then the search is culled and the timestamps are checked. Line 11 handles
a matching key, returning true. Lines 12 - 13 handle the case where the
distance of the key is too far away from its original bucket to be present in
the table. Lines 17 - 19 check if the timestamp for the particular key has
changed since the beginning of the operation, requiring the entire Contains
method to be retried, as a key could have been missed.

  *
fn Add(key: K) -> bool {
start_bucket: u64 = hash(key) % size;
retry:
active_key: K = key;
descriptor: K_CAS_Desc = create_descriptor();
for(i = start_bucket, active_dist = 0;; i++, active_dist++) {
i %= size;
cur_timestamp = read_timestamp(i);
cur_key: K = K_CAS_load(&table[i]);
if(cur_key == Nil) {
descriptor.add(&table[i], Nil, active_key);
res: bool = K_CAS(descriptor); // Attempt to K-CAS operations
if(!res) { goto retry; }
return true;
}
if(cur_key == key) { return false; }
distance: u64 = calc_dist(cur_key, i); // Robin Hood Invariant
if (distance < active_dist) {
descriptor.add(&table[i], cur_key, active_key); // Swap keys
// Increment the timestamp within the descriptor.
add_timestamp_increment(i, cur_timestamp);
// Swap active key and kick this key down the table
active_key = cur_key;
active_dist = distance;
}
}
}

Figure 8. Pseudo-code for Add

B - Add

All line numbers refer to Figure 8. Add is quite similar to the serial
version. Lines 4 - 5 keep track of the entry currently being relocated via the
active key, initially setting the variable to the key being inserted. Add also
keeps track of the last timestamp bucket it has incremented. This is hidden
behind a helper function called add_timestamp_increment. Timestamps are
incremented to prevent a concurrently running Add or Remove from interfering
with the correctness of the method. Lines 10 - 14 attempt to insert the key
currently being relocated into a Nil bucket, retrying the whole Add operation
on failure. Line 16 returns false upon a key match, as the entry is already in
the set. Lines 17 - 24 check if an entry needs to be relocated, replacing it
with the entry currently being relocated in the thread’s K-CAS descriptor.

  *
fn Remove(key: K) -> bool {
start_bucket: u64 = hash(key) % size;
retry:
timestamps: List<u64> = [];
descriptor: K_CAS_Desc = create_descriptor();
for(i = start_bucket, cur_dist = 0;; cur_dist++, i++) {
i %= size;
// Add the timestamp for that specific index.
timestamps.append(read_timestamp(i));
cur_key: K = K_CAS_load(&table[i]);
if(cur_key == Nil) { goto timestamp_check; }
if(cur_key == key) {
// Shuffle items down until a Nil key or dist(key) == 0
shuffle_items(i, cur_key);
res: bool = K_CAS(descriptor);
if(!res) { goto retry; }
return true;
}
distance: u64 = calc_dist(cur_key, i); // Robin Hood Invariant
if (distance < cur_dist) { goto timestamp_check; }
}
timestamp_check:
// Compare every timestamp.
for(i = start_bucket, idx = 0; idx < timestamps.size(); i++, idx++) {
i %= size;
if(list[idx] != read_timestamp(i)) { goto retry; }
}
return false;
}

Figure 9. Pseudo-code for Remove

C - Remove

All line numbers refer to Figure 9. Remove is a combination of Contains and
Add. First, Remove tries to find the key. If the key isn’t found then, as per
Contains, timestamps are checked in case a concurrent Remove or Add has
relocated the key during its search. If a key is found, then the process of
deletion begins. Lines 12 - 17 constitute the deletion process. The function
shuffle_items linearly shuffles items back until a Nil key is found, or else
an entry with a DFB of 0 is found. As mentioned earlier, the function is
simple, though expansive, so we exclude it. Each linear shuffle is put into
the K-CAS descriptor, with line 15 performing the K-CAS operation. The
ultimate outcome of this operation is the physical deletion of the entry.
Lines 19 - 20 check for the Robin Hood invariant, terminating the search and
checking timestamps if the criterion is met. Like Contains, Remove will
restart if there is a discrepancy in the timestamps. Lines 24 - 26 check the
timestamps of each bucket read.

###  3.4. Proof Of Correctness

The proof of correctness is relatively simple and informal. K-CAS [17] is
itself linearisable [22], and K-CAS encodes all relocations and timestamp
increments to the data structure in its descriptors. An invocation of K-CAS
essentially turns each modification operation on the table into a transaction.
Every Add or Remove call that results in relocations increments a timestamp
via the K-CAS operation; if any reading thread was to examine the table’s
contents during a relocation, the reader could compare before and after
timestamps so as to ensure that no entry was moved during the search.
Furthermore, because each reader also helps the K-CAS operation, reading the
timestamp will result in one of three outcomes. Either the reader will read a
new timestamp value, the same timestamp, or else help the operation complete
an ongoing K-CAS operation by reading the new timestamp if the operation
succeeds or the old one if it fails. Readers need only ensure that the
timestamps haven’t changed since their initial reading. Since Remove can exit
in two ways, it has two different linearisation points. The linearisation
point of Add, and the first code path of Remove are at line 12 in Figure 8 and
line 15 in Figure 9, where the K-CAS is successfully called. Contains and the
second exit point of Remove linearise at the point of reading their last
timestamp from their search on lines 8 and 9 respectively.

###  3.5. Progress

The progress of each operation is parameterised by the progress of the K-CAS
operation. If the K-CAS operation is blocking, then all method calls on the
hash table are blocking. However if we have a lock-free implementation of
K-CAS, then the following classifications for each method occur. Calls to
Contains are obstruction-free [18], as other concurrent operations can cause a
relevant timestamp to change, thus forcing the method to restart. Threads
calling Contains can starve but they are not blocked if another thread dies.
Add has the same progress guarantees as Contains and for the same reasons,
other modifying operations can modify relevant timestamps forcing the method
to fail and restart. Timestamps are not guaranteed to correspond to the
entries the method wants to examine, they are coarse and each timestamp
corresponds to a number of entries. Remove must first find the entry it wishes
to remove, effectively running the same code as Contains and thus having the
same classification. Afterwards, once found, the deletion and subsequent
shuffling of that entry is also obstruction-free since other irrelevant
operations with the same timestamp can interfere with its progress. In
summary, lock-free K-CAS calls to Contains, Add, and Remove are obstruction-
free.

##  4\. Performance, Results, and Discussion

In this section we detail the performance and implementation of our
algorithms. All of our code is made freely available online [23]. This
includes K-CAS Robin Hood, the hardware transactional [19] variant of Robin
Hood Hashing with lock-elision [31], the implementation of alternative
competing algorithms (either coded by us or obtained via online sources), and
benchmarking code which allows readers to replicate our results.

###  4.1. Experimental Setup

For our experiments we opted to use a set of microbenchmarks which stressed
the hash table under various capacities and workloads. Our benchmarks were run
on a 4 CPU machine, with each CPU (Intel® Xeon® CPU E7-8890 v3) featuring 18
cores with 36 hardware threads and 512 GiB RAM. The machine was running Ubuntu
14.04 with kernel version 3.13.0-141. Each thread was pinned to a specific
core during testing. When scaling the number of threads, care was taken to pin
the thread to a new core, avoiding HyperThreading™ until necessary. Once all
non HyperThreading™ cores on each CPU were exhausted, HyperThreading™ was
employed thereafter. The rational for this scheduling choice is that
algorithms which employ hardware transactional memory are disproportionately
penalised by HyperThreading™ and some mainstream operating systems, such as
OpenBSD, disable HyperThreading™. As a result we shed light on how our
algorithms would scale on those systems. NUMA memory effects were controlled
by specifying where each thread could allocate using the numactl command,
allocating on the RAM banks closest to the running CPUs as they came into use.

The algorithms used in the experiments are as follows: K-CAS Robin Hood,
Transactional Lock-Elision Robin Hood Hashing, Hopscotch Hashing [21], a Lock-
Free Linear Probing hash table described by Nielsen and Karlsson [27], and
Michael’s lock-free hash table [25].

A number of workload configurations were used in graphing the results. Four
load factors of 20%, 40%, 60%, and 80% were chosen, along with two update
workload configurations, namely 10% and 20%, referred to herein as “light” and
“heavy”. Both of the workload configurations were tried at the specified load
factors, and both were used for comparing the different Robin Hood Hashing
algorithms against each other, and against competitors. We sized the tables at
$2^{23}$ to ensure that they wouldn’t fit into the cache, thereby exposing
each algorithm’s effective cache use. The key space was equal to the size of
the table, and was filled to the specified load factors. The scalable JeMalloc
[12] allocator was used in the experiments and no memory reclamation system
was used in algorithms that traditionally require one.

Figure 10. Single-core performance of the hash tables relative to K-CAS Robin
Hood.

The testing process was carried out as follows: Each thread calls a random
method with a random argument from some predefined method and key
distribution. All threads are synchronised before execution on the data
structure, and for a specified amount of time rather than a specific number of
iterations. Each thread counts the number of operations it performed on the
structure during the benchmark. The total amount of operations per microsecond
for all threads is then graphed. Each experiment was run five times for 10
seconds each, and the average of each result was computed and plotted. All of
our algorithms were written in C++11, and compiled with g++ 4.8.4 with O3
level of optimisation. Cache misses were collected via PAPI [36].

###  4.2. Discussion and results

In order to gain an understanding of general operation overhead, we measured
single-core performance. The performance is measured against K-CAS Robin Hood.
In Figure 10 we see that Hopscotch Hashing, Maged Michael’s Separate Chaining,
and Lock-Free Linear Probing are significantly slower than the other
algorithms. The reason for this is two-fold. First, the issue of cache
efficiency arises: Lock-Free Linear Probing and separate chaining use dynamic
memory allocation, meaning that a pointer dereference is needed for every
bucket access. While Hopscotch Hashing does not use dynamically allocated
memory, it does put more pressure on the cache by storing the original hash of
a key inside the table. However it should be noted that it doesn’t put as much
pressure on the cache as K-CAS Robin Hood, as per Table 1. The second issue is
the amount of work carried out for every operation: Hopscotch Hashing is the
most complicated, executing more code and performing more operations.
Transactional Robin Hood has higher performance than K-CAS Robin Hood as it
does not require to consult the K-CAS descriptor and timestamps.

| Configurations (Load factor w/ Updates)
---|---
| Hash
---
Tables
| 20%
---
w/
10%
| 20%
---
w/
20%
| 40%
---
w/
10%
| 40%
---
w/
20%
| 60%
---
w/
10%
| 60%
---
w/
20%
| 80%
---
w/
10%
| 80%
---
w/
20%
Hopscotch Hashing | 88% | 82% | 70% | 71% | 64% | 68% | 59% | 65%
Lock-Free LP | 185% | 207% | 227% | 240% | 294% | 305% | 430% | 453%
Maged Michael | 109% | 105% | 95% | 95% | 89% | 93% | 85% | 91%
Transactional RH | 86% | 85% | 82% | 78% | 89% | 86% | 93% | 90%
Table 1. Cache misses relative to K-CAS Robin Hood single-core.

The cache results can be seen in Table 1 as a percentage relative to K-CAS
Robin Hood for a single-core. These cache statistics were measured over the
course of the entire execution of the benchmark for each table and for each
configuration. Hopscotch Hashing fairs very well as it is able to skip over
irrelevant entries. Lock-Free Linear Probing uses dynamic memory and thus puts
enormous pressure on the cache. Another downside is as the table fills up over
time with tombstones, it forces operations to take roughly the same amount of
time regardless of load factor. This phenomenon is called contamination [15].
Maged Michael [25] fairs reasonably well even though it uses dynamic memory.
Very few buckets have more than a single node meaning few extra nodes are
needed. Transactional Lock-Elision Robin Hood performs better as it does not
need to consult an extra timestamp array or any extra K-CAS descriptor, which
would require an extra level of indirection.

As is clear from the multi-core results in Figure 11, 12 the K-CAS Robin Hood
Hashing algorithm either scales better than or is competitive with its
opposition. Across all graphs there are two significant dips in performance.
The first is at 18 threads, where threads are pinned to a different CPU
socket. The use of another socket requires inter-socket communication and NUMA
effects, reducing overall performance. The second is when increasing from 72
to 81 threads, which is the point where HyperThreading™ kicks in. This kink is
particularly pronounced for the transactional Robin Hood variant, which never
recovers after that point. Both of these effects become most pronounced when a
significant write load is placed on the tables.

Figure 11. Cumulative operations per microsecond for the hash tables at 20%
and 40% load factors at two update rates. (Higher is better)

Each of the workloads highlights the particular performance characteristics of
each hash table. The update-light (10% writes) workload shows K-CAS Robin Hood
dominating the competition across all thread counts and load factors. The
update-heavy (20% writes) workload has two distinct outcomes predicated on the
table load factor. The lower load factor shows K-CAS Robin Hood is slightly
beaten out by the Transactional Robin Hood variant until the 72 thread mark,
wherein it drops off entirely. K-CAS Robin Hood also edges out Hopscotch
Hashing throughout most of the update-heavy workload until the very upper end
of the thread count, where it is slightly outclassed. However, at higher load
factors K-CAS Robin Hood demonstrates similar relative performance to the
lower load factor benchmarks but maintains its lead over Hopscotch Hashing.
All workloads show the gap between K-CAS Robin Hood and Hopscotch begins to
narrow once HyperThreading™ kicks in. As mentioned earlier, in every
configuration the transactional variant of Robin Hood scales very well until
72 threads, after which HyperThreading™ causes a huge kink in performance, and
the algorithm never recovers. Maged Michael scales well in the tested
workloads, however the gradient of the line isn’t steep enough to challenge
K-CAS Robin Hood or Hopscotch Hashing. Lock-Free Linear Probing does the worst
of all, ending up at the same end point as Transactional Robin Hood.

Figure 12. Cumulative operations per microsecond the hash tables at 60% and
80% load factors at two update rates. (Higher is better)

###  4.3. Future Work

An issue we don’t deal with is resize, specifically, when to resize the table
and how to do it. Lock-free resize methods have been discussed in the
literature ([8], [32]). To the best of our knowledge there has not yet been a
formally published generic hash table resize method. Another item for future
work is a combination of lock-free K-CAS and transactional [19] memory, such
as the algorithm presented by Trevor Brown [6] for lock-free trees. A similar
exploration for Robin Hood and other the hash tables benchmarked would be of
interest. Work done by Siakavaras et el. [33] shows that naive application of
hardware transactional systems to data-structures typically perform poorly and
require algorithm modifications to operate efficiently. Future work aimed at
determining the optimal modifications for Robin Hood might elevate its
performance for hardware transactional memory.

##  5\. Conclusion

We have presented an obstruction-free Robin Hood Hashing algorithm which
achieves superior performance relative to other concurrent algorithms with
similar capabilities, and a hardware transaction variant which demonstrates
best in class performance. These results establish that the Robin Hood
algorithm is algorithmically suited to concurrency. Our experiments have shown
that it scales strongly at all thread counts. Unlike linear probing, the
algorithm can scale effectively to significantly higher load factors. It is
very simple in nature, relying primarily on an efficient K-CAS, as well as
being highly portable, using only single word compare-and-swap instructions,
with no memory reclaimer required. Our results improve upon the state of the
art in the field which is more than 10 years old.

## References

  * [1] D. Alistarh, W. Leiserson, A. Matveev, and N. Shavit.  Threadscan: Automatic and scalable memory reclamation.  In SPAA, 2015.
  * [2] D. Alistarh, W. Leiserson, A. Matveev, and N. Shavit.  Forkscan: Conservative memory reclamation for modern operating systems.  In EuroSys, 2017.
  * [3] A. Amighi, S. Blom, and M. Huisman.  Vercors: A layered approach to practical verification of concurrent software.  In 24th Euromicro International Conference on Parallel, Distributed, and Network-Based Processing, PDP, 2016.
  * [4] M. Arbel-Raviv and T. Brown.  Reuse, don’t recycle: Transforming lock-free algorithms that throw away descriptors.  In DISC, 2017.
  * [5] M. Batty.  The c11 and c++11 concurrency model.  http://www.cl.cam.ac.uk/~mjb220/thesis/thesis.pdf.  Accessed: 2017-05-04.
  * [6] T. Brown.  A template for implementing fast lock-free trees using htm.  In PODC, 2017.
  * [7] P. Celis.  Robin Hood Hashing.  PhD thesis, University of Waterloo, Waterloo, Ont., Canada, Canada, 1986\.
  * [8] C. Click.  Lock-free/wait-free hash table.  http://web.stanford.edu/class/ee380/Abstracts/070221_LockFreeHash.pdf.  Accessed: 2017-05-04.
  * [9] N. Cohen and E. Petrank.  Efficient memory management for lock-free data structures with optimistic access.  In Proceedings of the 27th ACM symposium on Parallelism in Algorithms and Architectures, pages 254–263. ACM, 2015.
  * [10] T. Cormen, C. Stein, R. Rivest, and C. Leiserson.  Introduction to Algorithms.  McGraw-Hill Higher Education, 2nd edition, 2001.
  * [11] U. Drepper.  What Every Programmer Should Know About Memory, 2007.
  * [12] J. Evans.  Jemalloc, Retrieved 2018-08-06.  Available at https://github.com/jemalloc/jemalloc.
  * [13] S. Feldman, P. LaBorde, and D. Dechev.  A wait-free multi-word compare-and-swap operation.  International Journal of Parallel Programming, 43(4):572–596, Aug 2015.
  * [14] K. Fraser.  Practical lock-freedom.  Technical report, University of Cambridge, Computer Laboratory, 2004.
  * [15] G. Gonnet and R. Baeza-Yates.  Handbook of Algorithms and Data Structures: In Pascal and C (2Nd Ed.).  Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1991.
  * [16] T. Harris.  A pragmatic implementation of non-blocking linked-lists.  In Proceedings of the 15th International Conference on Distributed Computing, DISC, 2001.
  * [17] T. Harris, K. Fraser, and I. Pratt.  A practical multi-word compare-and-swap operation.  In Proceedings of the 16th International Conference on Distributed Computing, DISC ’02, pages 265–279, London, UK, UK, 2002. Springer-Verlag.
  * [18] M. Herlihy, V. Luchangco, and M. Moir.  Obstruction-free synchronization: Double-ended queues as an example.  In Proceedings of the 23rd International Conference on Distributed Computing Systems, ICDCS ’03. IEEE Computer Society, 2003.
  * [19] M. Herlihy and J. Moss.  Transactional memory: Architectural support for lock-free data structures.  In Proceedings of the 20th Annual International Symposium on Computer Architecture, ISCA ’93. ACM, 1993.
  * [20] M. Herlihy and N. Shavit.  The Art of Multiprocessor Programming.  Morgan Kaufmann, 1 edition, March 2008.
  * [21] M. Herlihy, N. Shavit, and M. Tzafrir.  Hopscotch Hashing.  In DISC ’08: Proceedings of the 22nd international symposium on Distributed Computing, pages 350–364, Berlin, Heidelberg, 2008. Springer-Verlag.  doi:10.1007/978-3-540-87779-0\\_24.
  * [22] M. Herlihy and J. Wing.  Linearizability: A correctness condition for concurrent objects.  ACM Trans. Program. Lang. Syst., 12(3):463–492, July 1990.
  * [23] R. Kelly.  Source code for lock-free robin hood benchmark.  https://github.com/DaKellyFella/concurrent-robin-hood-hashing.  Accessed: 2018-11-14.
  * [24] K. Rustan M. Leino and Peter Müller.  A Basis for Verifying Multi-threaded Programs, pages 378–393.  Springer Berlin Heidelberg, Berlin, Heidelberg, 2009.
  * [25] M. Michael.  High performance dynamic lock-free hash tables and list-based sets.  In Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, SPAA. ACM, 2002.
  * [26] M. Michael.  Hazard pointers: Safe memory reclamation for lock-free objects.  IEEE Trans. Parallel Distrib. Syst., 15(6):491–504, June 2004.
  * [27] J. Nielsen and S. Karlsson.  A scalable lock-free hash table with open addressing.  SIGPLAN Not., 51(8):33:1–33:2, February 2016.
  * [28] D. Lea P. William, S. Adve.  Jsr 133: Javatm memory model and thread specification revision.  https://www.jcp.org/en/jsr/detail?id=133.  Accessed: 2017-05-04.
  * [29] A. Padegs.  System/370 extended architecture: Design considerations.  IBM Journal of Research and Development, 27(3):198–205, 1983.
  * [30] C. Purcell and T. Harris.  Non-blocking Hashtables with Open Addressing, pages 108–121.  Springer Berlin Heidelberg, Berlin, Heidelberg, 2005.
  * [31] R. Rajwar and J. Goodman.  Speculative lock elision: Enabling highly concurrent multithreaded execution.  In Proceedings of the 34th annual ACM/IEEE international symposium on Microarchitecture, pages 294–305. IEEE Computer Society, 2001.
  * [32] O. Shalev and N. Shavit.  Split-Ordered Lists: Lock-Free Extensible Hash Tables.  In Proceedings of the 22nd Annual ACM Symposium on Principles of Distributed Computing (PODC), 2003.
  * [33] D. Siakavaras, K. Nikas, G. Goumas, and N. Koziris.  Massively concurrent red-black trees with hardware transactional memory.  In 2016 24th Euromicro International Conference on Parallel, Distributed, and Network-Based Processing (PDP), 2016.
  * [34] H. Sutter.  The Free Lunch Is Over: A Fundamental Turn Toward Concurrency in Software.  Dr. Dobb’s Journal, 30(3), 2005.
  * [35] Rust Core Team.  Rust collections hash table.  https://doc.rust-lang.org/std/collections/struct.HashMap.html.  Accessed: 2017-05-07.
  * [36] D. Terpstra, H. Jagode, H. You, and J. Dongarra.  Collecting performance data with papi-c.  In Tools for High Performance Computing 2009, pages 157–173, Berlin, Heidelberg, 2010. Springer Berlin Heidelberg.
  * [37] R. Yoo, C. Hughes, K. Lai, and R. Rajwar.  Performance evaluation of intel; transactional synchronization extensions for high-performance computing.  In Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis, SC. ACM, 2013.