**mpm + datastructure**
151

A Scalable, Portable, and Memory-Efficient Lock-Free FIFO Queue

19 hours ago by mpm

We present a new lock-free multiple-producer and multiple-consumer (MPMC) FIFO queue design which is scalable and, unlike existing high-performant queues, very memory efficient. Moreover, the design is ABA safe and does not require any external memory allocators or safe memory reclamation techniques, typically needed by other scalable designs. In fact, this queue itself can be leveraged for object allocation and reclamation, as in data pools. We use FAA (fetch-and-add), a specialized and more scalable than CAS (compare-and-set) instruction, on the most contended hot spots of the algorithm. However, unlike prior attempts with FAA, our queue is both lock-free and linearizable.

We propose a general approach, SCQ, for bounded queues. This approach can easily be extended to support unbounded FIFO queues which can store an arbitrary number of elements. SCQ is portable across virtually all existing architectures and flexible enough for a wide variety of uses. We measure the performance of our algorithm on the x86-64 and PowerPC architectures. Our evaluation validates that our queue has exceptional memory efficiency compared to other algorithms and its performance is often comparable to, or exceeding that of state-of-the-art scalable algorithms.

non-blocking
datastructure
We propose a general approach, SCQ, for bounded queues. This approach can easily be extended to support unbounded FIFO queues which can store an arbitrary number of elements. SCQ is portable across virtually all existing architectures and flexible enough for a wide variety of uses. We measure the performance of our algorithm on the x86-64 and PowerPC architectures. Our evaluation validates that our queue has exceptional memory efficiency compared to other algorithms and its performance is often comparable to, or exceeding that of state-of-the-art scalable algorithms.

19 hours ago by mpm

EBtree - Design for a Scheduler and Use (Almost) Everywhere

8 days ago by mpm

Andjelko Iharos explores the goals, design and the choices behind the implementations of EBtree, and how they produce a very fast and versatile data storage for many of HAProxys advanced features. EBtree is a different take on the ubiquitous tree data structure, and has been helping HAProxy, a high performance open source software load balancer, to keep up with demands for over a decade.

datastructure
concurrency
8 days ago by mpm

Hash table tradeoffs: CPU, memory, and variability

8 days ago by mpm

In this post, I describe a tri-factor model which I find more useful in the analysis of hash table algorithms and discuss several state-of-the-art algorithms in the context of this model.

datastructure
memory
performance
8 days ago by mpm

cbuffer

22 days ago by mpm

A circular buffer written in C using Posix calls to create a contiguously mapped memory space.

datastructure
memory
22 days ago by mpm

The Adaptive Priority Queue with Elimination and Combining

6 weeks ago by mpm

Priority queues are fundamental abstract data structures, often used to manage limited resources in parallel programming. Several proposed parallel priority queue implementations are based on skiplists, harnessing the potential for parallelism of the add() operations. In addition, methods such as Flat Combining have been proposed to reduce contention by batching together multiple operations to be executed by a single thread. While this technique can decrease lock-switching overhead and the number of pointer changes required by the removeMin() operations in the priority queue, it can also create a sequential bottleneck and limit parallelism, especially for non-conflicting add() operations.

In this paper, we describe a novel priority queue design, harnessing the scalability of parallel insertions in conjunction with the efficiency of batched removals. Moreover, we present a new elimination algorithm suitable for a priority queue, which further increases concurrency on balanced workloads with similar numbers of add() and removeMin() operations. We implement and evaluate our design using a variety of techniques including locking, atomic operations, hardware transactional memory, as well as employing adaptive heuristics given the workload.

non-blocking
datastructure
In this paper, we describe a novel priority queue design, harnessing the scalability of parallel insertions in conjunction with the efficiency of batched removals. Moreover, we present a new elimination algorithm suitable for a priority queue, which further increases concurrency on balanced workloads with similar numbers of add() and removeMin() operations. We implement and evaluate our design using a variety of techniques including locking, atomic operations, hardware transactional memory, as well as employing adaptive heuristics given the workload.

6 weeks ago by mpm

Black-box Concurrent Data Structures for NUMA Architectures

6 weeks ago by mpm

High-performance servers are non-uniform memory access (NUMA) machines. To fully leverage these machines, programmers need efficient concurrent data structures that are aware of the NUMA performance artifacts. We propose Node Replication (NR), a black-box approach to obtaining such data structures. NR takes an arbitrary sequential data structure and automatically transforms it into a NUMA-aware concurrent data structure satisfying linearizability. Using NR requires no expertise in concurrent data structure design, and the result is free of concurrency bugs. NR draws ideas from two disciplines: shared-memory algorithms and distributed systems. Briefly, NR implements a NUMA-aware shared log, and then uses the log to replicate data structures consistently across NUMA nodes. NR is best suited for contended data structures, where it can outperform lock-free algorithms by 3.1x, and lock-based solutions by 30x. To show the benefits of NR to a real application, we apply NR to the data structures of Redis, an in-memory storage system. The result outperforms other methods by up to 14x. The cost of NR is additional memory for its log and replicas.

concurrency
datastructure
memory
6 weeks ago by mpm

Concurrent Robin Hood Hashing

december 2018 by mpm

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.

non-blocking
datastructure
december 2018 by mpm

Beating hash tables with trees? The ART-ful radix trie

november 2018 by mpm

There must be more efficient ways to store a set of pointers, indexed by a fixed size set of keys (the trie’s alphabet). Indeed, there are - several of them, in fact, distinguished by the number of children the node actually has, not just how many it might potentially have.

datastructure
november 2018 by mpm

Paper Notes: Cache Craftiness for Fast Multicore Key-Value Storage

october 2018 by mpm

This paper proposes an efficient tree data structure that relies on splitting variable length keys into a variable number of fixed-length keys called slices. As you go down the tree, you compare the first slice of each key, then the second, then the third and so on, but each comparision has constant cost.

datastructure
october 2018 by mpm

Elastic Binary Trees

september 2018 by mpm

In computer science, an elastic binary tree (or EB tree or EBtree) is a binary search tree specially optimized to very frequently store, retrieve and delete discrete integer or binary data without having to deal with memory allocation. It is particularly well suited for operating system schedulers where fast time-ordering and priority-ordering are strong requirements.

datastructure
september 2018 by mpm

The FuzzyLog: Partially Ordered Shared Log

august 2018 by mpm

The FuzzyLog is a partially ordered shared log. Unlike traditional SMR systems, such as Paxos or Tango, which store all events in a single total order, the FuzzyLog allows the storage and update of partially ordered histories. This relaxation of ordering contraints enables richer application semantics around consistency guarentees, data partitioning and log-playback, while retaining the ease-of-programming of the shared-log model.

consistency
storage
database
datastructure
august 2018 by mpm

Functional Data Structures

june 2018 by mpm

This flânerie is a stroll through intermediate data structures and their associated algorithms, from the point of view of functional programming.

functional
datastructure
june 2018 by mpm

Algorithms Behind Modern Storage Systems

june 2018 by mpm

This article takes a closer look at two storage system design approaches used in a majority of modern databases—read-optimized B-trees and write-optimized LSM (log-structured merge)-trees—and describes their use cases and tradeoffs.

storage
datastructure
june 2018 by mpm

Cache-tries: concurrent lock-free hash tries with constant-time operations

march 2018 by mpm

Concurrent non-blocking hash tries have good cache locality, and horizontally scalable operations. However, operations on most existing concurrent hash tries run in O(log n) time. In this paper, we show that the concurrent hash trie operations can run in expected constant time. We present a novel lock-free concurrent hash trie design that exerts less pressure on the memory allocator. This hash trie is augmented with a quiescently consistent cache, which permits the basic operations to run in expected O(1) time. We show a statistical analysis for the constant-time bound, which, to the best of our knowledge, is the first such proof for hash tries. We also prove the safety, lock-freedom and linearizability properties. On typical workloads, our implementation demonstrates up to 5X performance improvements with respect to the previous hash trie variants.

concurrency
datastructure
march 2018 by mpm

Concurrent Tries with Efficient Non-blocking Snapshots

january 2018 by mpm

We describe a non-blocking concurrent hash trie based on shared-memory single-word compare-and-swap instructions. The hash trie supports standard mutable lock-free operations such as insertion, removal, lookup and their conditional variants. To ensure space-efficiency, removal operations compress the trie when necessary.

non-blocking
datastructure
january 2018 by mpm

An Adaptive Packed-Memory Array

january 2018 by mpm

The packed-memory array (PMA) is a data structure that maintains a dynamic set of N elements in sorted order in a Θ(N)-sized array. The idea is to intersperse Θ(N) empty spaces or gaps among the elements so that only a small number of elements need to be shifted around on an insert or delete. Because the elements are stored physically in sorted order in memory or on disk, the PMA can be used to support extremely efficient range queries. Specifically, the cost to scan L consecutive elements is O(1+L/B) memory transfers.

datastructure
memory
january 2018 by mpm

hat-trie

december 2017 by mpm

The library provides an efficient and compact way to store a set or a map of strings by compressing the common prefixes. It also allows to search for keys that match a prefix.

c++
datastructure
december 2017 by mpm

hopscotch-map

november 2017 by mpm

The hopscotch-map library is a C++ implementation of a fast hash map and hash set using open-addressing and hopscotch hashing to resolve collisions. It is a cache-friendly data structure offering better performances than std::unordered_map in most cases and is closely similar to google::dense_hash_map while using less memory and providing more functionalities.

datastructure
c++
november 2017 by mpm

Gap Buffers

october 2017 by mpm

A gap buffer is a simple extension of the array of strings which can improve inserts and deletes, when they are clustered in the same location.

datastructure
october 2017 by mpm

I Wrote The Fastest Hashtable

october 2017 by mpm

The trick is to use Robin Hood hashing with an upper limit on the number of probes. If an element has to be more than X positions away from its ideal position, you grow the table and hope that with a bigger table every element can be close to where it wants to be. Turns out that this works really well. X can be relatively small which allows some nice optimizations for the inner loop of a hashtable lookup.

datastructure
performance
october 2017 by mpm

basecs

october 2017 by mpm

Exploring the basics of computer science, every Monday, for a year.

datastructure
algorithm
october 2017 by mpm

Modern B-Tree Techniques

october 2017 by mpm

Invented about 40 years ago and called ubiquitous less than 10 years later, B-tree indexes have been used in a wide variety of computing systems from handheld devices to mainframes and server farms. Over the years, many techniques have been added to the basic design in order to improve efficiency or to add functionality. Examples include

separation of updates to structure or contents, utility operations such as non-logged yet transactional index creation, and robust query processing such as graceful degradation during index-to-index navigation.

database
datastructure
storage
separation of updates to structure or contents, utility operations such as non-logged yet transactional index creation, and robust query processing such as graceful degradation during index-to-index navigation.

october 2017 by mpm

diiskhash

july 2017 by mpm

A simple disk-based hash table (i.e., persistent hash table).

It is a hashtable implemented on memory-mapped disk, so that it can be loaded with a single mmap() system call and used in memory directly (being as fast as an in-memory hashtable once it is loaded from disk).

storage
database
memory
datastructure
c++
python
It is a hashtable implemented on memory-mapped disk, so that it can be loaded with a single mmap() system call and used in memory directly (being as fast as an in-memory hashtable once it is loaded from disk).

july 2017 by mpm

BwTree

march 2017 by mpm

BwTree is a general purpose, concurrent and lock-free B+-Tree index. It allows for multiple threads modifying and/or querying the tree concurrently without corrupting the tree or giving inconsistent results. However, BwTree only guarantees atomicity of operations, and is not a concurrency control agent. If both atomicity and isolation is required, an extra concurrency control layer must be implemented

datastructure
non-blocking
concurrency
march 2017 by mpm

Nonblocking Concurrent Data Structures with Condition Synchronization

february 2017 by mpm

We use the term dual data structure to describe a concurrent object implementation that may hold both data and reservations (registered requests). By reasoning separately about a request, its successful follow-up, and the period in-between, we obtain meaningful definitions of nonblocking dual data structures. As concrete examples, we present lock-free dualstacks and dualqueues, and experimentally compare their performance with that of lock-based and nonblocking alternatives.

concurrency
datastructure
non-blocking
february 2017 by mpm

plf::colony

january 2017 by mpm

A colony is the highest-performance C++ template-based data container for high-modification scenarios with unordered data

c++
datastructure
january 2017 by mpm

Finger Trees

january 2017 by mpm

We present 2-3 finger trees, a functional representation of persistent sequences supporting access to the ends in amortized constant time, and concatenation and splitting in time logarithmic in the size of the smaller piece

functional
datastructure
january 2017 by mpm

bitset2

december 2016 by mpm

std::bitset with constexpr implementations plus additional features.

c++
datastructure
december 2016 by mpm

Skip Lists: Done Right

december 2016 by mpm

In the past five years, people have become increasingly sceptical of skip lists’ performance, due to their poor cache behavior when compared to e.g. B-trees, but fear not, a good implementation of skip lists can easily outperform B-trees while being implementable in only a couple of hundred lines

datastructure
december 2016 by mpm

murrayc-suffix-tree

december 2016 by mpm

An experiment with modern C++, suffix trees, and Ukkonen's algorithm for suffix tree construction

c++
datastructure
december 2016 by mpm

immer

november 2016 by mpm

immer is a library of persistent and immutable data structures written in C++.

c++
datastructure
concurrency
november 2016 by mpm

Bloofi

march 2016 by mpm

we effectively have a multidimensional Bloom filter problem: given an element, we wish to receive a list of candidate sets where the element might be. To solve this problem, we consider 3 alternatives. Firstly, we can naively check many Bloom filters. Secondly, we propose to organize the Bloom filters in a hierarchical index structure akin to a B+ tree, that we call Bloofi. Finally, we propose another data structure that packs the Bloom filters in such a way as to exploit bit-level parallelism, which we call Flat-Bloofi. Our theoretical and experimental results show that Bloofi and Flat-Bloofi provide scalable and efficient solutions alternatives to search through a large number of Bloom filters.

datastructure
march 2016 by mpm

libtwiddle

february 2016 by mpm

libtwiddle is a data structure library aiming for speed on modern Linux x86-64 systems. The following data structures are implemented: bitmaps (dense & RLE); Bloom filters (standard & active-active); HyperLogLog; MinHash

c++
datastructure
february 2016 by mpm

A Probing Hash Table Framework

february 2016 by mpm

What if we allow for keys to be moved/copied around as the hash table grows? If we relax the requirement that we never move key/value pairs after insertion, we now open the door for implementing a hash table using open addressing. Here, the table is stored as a single huge array containing either a key/value pair or nothing

datastructure
february 2016 by mpm

Split-Ordered Lists: Lock-Free Extensible Hash Tables

december 2015 by mpm

We present the first lock-free implementation of an extensible hash table running on current architectures. Our algorithm provides concurrent insert, delete, and find operations with an expected O(1) cost. It consists of very simple code, easily implementable using only load, store, and compareand-swap operations. The new mathematical structure at the core of our algorithm is recursive splitordering, a way of ordering elements in a linked list so that they can be repeatedly “split ” using a single compare-and-swap operation. Metaphorically speaking, our algorithm differs from prior known algorithms in that extensibility is derived by “moving the buckets among the items ” rather than “the items among the buckets. ” Though lock-free algorithms are expected to work best in multiprogrammed environments, empirical tests we conducted on a large shared memory multiprocessor show that even in non-multiprogrammed environments, the new algorithm performs as well as the most efficient known lock-based resizable hash-table algorithm, and in high load cases it significantly outperforms it.

datastructure
c++
memory
non-blocking
december 2015 by mpm

libcuckoo

november 2015 by mpm

libcuckoo provides a high-performance, compact hash table that allows multiple concurrent reader and writer threads

c++
concurrency
datastructure
november 2015 by mpm

SmoothieMap

november 2015 by mpm

SmoothieMap is a java.util.Map implementation with worst write (put(k, v)) operation latencies more than 100 times smaller than in ordinary hash table implementations like java.util.HashMap

java
datastructure
memory
november 2015 by mpm

libart

october 2015 by mpm

This library provides a C99 implementation of the Adaptive Radix Tree or ART. The ART operates similar to a traditional radix tree but avoids the wasted space of internal nodes by changing the node size. It makes use of 4 node sizes (4, 16, 48, 256), and can guarentee that the overhead is no more than 52 bytes per key, though in practice it is much lower

datastructure
october 2015 by mpm

qp trie

october 2015 by mpm

A qp trie is like a crit-bit trie (aka patricia trie) except each branch is indexed by a quadbit (a nibble) at a time instead of one bit. The array of sub-tries at a branch node is compressed using the popcount trick to omit unused branches. Based on a few benchmarks, qp tries have about 1/3 less memory overhead of crit-bit tries, 1.3 words vs 2 words of overhead per item; the average depth of a qp trie is about half that of a crit-bit trie; and the overall speed of qp tries is about 10% faster....

datastructure
october 2015 by mpm

sdsl-lite

september 2015 by mpm

The Succinct Data Structure Library (SDSL) is a powerful and flexible C++11 library implementing succinct data structures. In total, the library contains the highlights of 40 research publications. Succinct data structures can represent an object (such as a bitvector or a tree) in space close the information-theoretic lower bound of the object while supporting operations of the original object efficiently. The theoretical time complexity of an operation performed on the classical data structure ...

c++
datastructure
september 2015 by mpm

The Adaptive Priority Queue with Elimination and Combining

april 2015 by mpm

Priority queues are fundamental abstract data structures, often used to manage limited resources in parallel programming. Several proposed parallel priority queue implementations are based on skiplists, harnessing the potential for parallelism of the add() operations. In addition, methods such as Flat Combining have been proposed to reduce contention by batching together multiple operations to be executed by a single thread. While this technique can decrease lock-switching overhead and the number of pointer changes required by the removeMin() operations in the priority queue, it can also create a sequential bottleneck and limit parallelism, especially for non-conflicting add() operations. In this paper, we describe a novel priority queue design, harnessing the scalability of parallel insertions in conjunction with the efficiency of batched removals. Moreover, we present a new elimination algorithm suitable for a priority queue, which further increases concurrency on balanced workloads with similar numbers of add() and removeMin() operations. We implement and evaluate our design using a variety of techniques including locking, atomic operations, hardware transactional memory, as well as employing adaptive heuristics given the workload.

concurrency
datastructure
april 2015 by mpm

ASCYLIB

april 2015 by mpm

ASCYLIB is a concurrent-search data-structure (CSDS) library. It contains over 30 implementations of linked lists, hash tables, skip lists, and binary search trees (BST). ASCYLIB contains sequential, lock-based, and lock-free implementations for each data structure.

concurrency
datastructure
april 2015 by mpm

Andersson Trees

march 2015 by mpm

Andersson trees are simple and easy to implement balanced binary search trees that are based on the foundations of red black trees. Consequently, Andersson trees have similar performance and structuring properties as red black trees without the difficult implementation. Red black trees are an abstraction of the symmetric binary B-tree, which is a clever abstraction of a B-tree of order 4. Andersson trees are a simplification of the symmetric binary B-tree that use a B-tree of order 3 to remove s...

datastructure
march 2015 by mpm

pahole

february 2015 by mpm

pahole shows data structure layouts encoded in debugging information formats, DWARF and CTF being supported. This is useful for, among other things: optimizing important data structures by reducing its size, figuring out what is the field sitting at an offset from the start of a data structure, investigating ABI changes and more generally understanding a new codebase you have to work with

datastructure
memory
february 2015 by mpm

concurrent-trees

december 2014 by mpm

This project provides concurrent Radix Trees and concurrent Suffix Trees for Java.

java
concurrency
datastructure
december 2014 by mpm

A Practical Concurrent Binary Search Tree

december 2014 by mpm

We propose a concurrent relaxed balance AVL tree algorithm that is fast, scales well, and tolerates contention. It is based on optimistic techniques adapted from software transactional memory, but

takes advantage of specific knowledge of the the algorithm to reduce overheads and avoid unnecessary retries. We extend our algorithm with a fast linearizable clone operation, which can be used for consistent iteration of the tree. Experimental evidence shows that our algorithm outperforms a highly tuned concurrent skip list for many access patterns, with an average of 39% higher singlethreaded throughput and 32% higher multi-threaded throughput over a range of contention levels and operation mixes.

concurrency
datastructure
takes advantage of specific knowledge of the the algorithm to reduce overheads and avoid unnecessary retries. We extend our algorithm with a fast linearizable clone operation, which can be used for consistent iteration of the tree. Experimental evidence shows that our algorithm outperforms a highly tuned concurrent skip list for many access patterns, with an average of 39% higher singlethreaded throughput and 32% higher multi-threaded throughput over a range of contention levels and operation mixes.

december 2014 by mpm

streaming-papers

november 2014 by mpm

A curated collection of papers on streaming algorithms

algorithm
stream
statistics
datastructure
november 2014 by mpm

Frugal Streaming for Estimating Quantiles:One (or two) memory suffices

november 2014 by mpm

Modern applications require processing streams of data for estimating statistical quantities such as quantiles with small amount of memory. In many such applications, in fact, one needs to compute such statistical quantities for each of a large number of groups, which additionally restricts the amount of memory available for the stream for any particular group. We address this challenge and introduce frugal streaming, that is algorithms that work with tiny -- typically, sub-streaming -- amount of memory per group. We design a frugal algorithm that uses only one unit of memory per group to compute a quantile for each group. For stochastic streams where data items are drawn from a distribution independently, we analyze and show that the algorithm finds an approximation to the quantile rapidly and remains stably close to it. We also propose an extension of this algorithm that uses two units of memory per group. We show with extensive experiments with real world data from HTTP trace and Twitter that our frugal algorithms are comparable to existing streaming algorithms for estimating any quantile, but these existing algorithms use far more space per group and are unrealistic in frugal applications; further, the two memory frugal algorithm converges significantly faster than the one memory algorithm.

statistics
datastructure
november 2014 by mpm

Algorithmic Complexity

august 2014 by mpm

If you a software developer, you know how difficult it can be studying for finals in school, technical interviews, or just refreshing yourself on fundamental algorithms and data structures.

AlgorithmicComplexity.com aims to be a good resource for anyone in this position.

algorithm
datastructure
AlgorithmicComplexity.com aims to be a good resource for anyone in this position.

august 2014 by mpm

STX B+ Tree

august 2014 by mpm

The STX B+ Tree package is a set of C++ template classes implementing a B+ tree key/data container in main memory. The classes are designed as drop-in replacements of the STL containers set, map, multiset and multimap and follow their interfaces very closely. By packing multiple value pairs into each node of the tree the B+ tree reduces heap fragmentation and utilizes cache-line effectsbetter than the standard red-black binary tree

c++
datastructure
august 2014 by mpm

Implementing a Key-Value Store – Part 6: Open-Addressing Hash Tables

july 2014 by mpm

In this article, I will compare several open-addressing hash tables: Linear Probing, Hopscotch hashing, and Robin Hood hashing. I have already done some work on this topic, and in this article I want to gather data for more metrics in order to decide which hash table I will use for my key-value store.

datastructure
performance
io
july 2014 by mpm

Efficient Lock-free Binary Search Trees

june 2014 by mpm

In this paper we present a novel algorithm for concurrent lock-free internal binary search trees (BST) and implement a Set abstract data type (ADT) based on that. We show that in the presented lock-free BST algorithm the amortized step complexity of each set operation - Add, Remove and Contains - is O(H(n)+c), where, H(n) is the height of BST with n number of nodes and c is the contention during the execution. Our algorithm adapts to contention measures according to read-write load. If the situation is read-heavy, the operations avoid helping pending concurrent Remove operations during traversal, and, adapt to interval contention. However, for write-heavy situations we let an operation help pending Remove, even though it is not obstructed, and so adapt to tighter point contention. It uses single-word compare-and-swap {CAS} operations. We show that our algorithm has improved disjoint-access-parallelism compared to similar existing algorithms. We prove that the presented algorithm is linearizable. To the best of our knowledge this is the first algorithm for any concurrent tree data structure in which the modify operations are performed with an additive term of contention measure.

concurrency
datastructure
june 2014 by mpm

PTLQueue : a scalable bounded-capacity MPMC queue

june 2014 by mpm

A fast and scalable multiple-producer multiple-consumer (MPSC) concurrent queue called PTLQueue. The queue has bounded capacity and is implemented via a circular array.

concurrency
datastructure
june 2014 by mpm

Open Data Structures

june 2014 by mpm

Open Data Structures covers the implementation and analysis of data structures for sequences (lists), queues, priority queues, unordered dictionaries, ordered dictionaries, and graphs.

Data structures presented in the book include stacks, queues, deques, and lists implemented as arrays and linked-lists; space-efficient implementations of lists; skip lists; hash tables and hash codes; binary search trees including treaps, scapegoat trees, and red-black trees; integer searching structures including binary tries, x-fast tries, and y-fast tries; heaps, including implicit binary heaps and randomized meldable heaps; graphs, including adjacency matrix and ajacency list representations; and B-trees.

book
datastructure
Data structures presented in the book include stacks, queues, deques, and lists implemented as arrays and linked-lists; space-efficient implementations of lists; skip lists; hash tables and hash codes; binary search trees including treaps, scapegoat trees, and red-black trees; integer searching structures including binary tries, x-fast tries, and y-fast tries; heaps, including implicit binary heaps and randomized meldable heaps; graphs, including adjacency matrix and ajacency list representations; and B-trees.

june 2014 by mpm

The Bw-Tree: A B-tree for New Hardware Platforms

april 2014 by mpm

The emergence of new hardware and platforms has led to reconsideration of how data management systems are designed. However, certain basic functions such as key indexed access to records remain essential. While we exploit the common architectural layering of prior systems, we make radically new design decisions about each layer. Our new form of B-tree, called the Bw-tree achieves its very high performance via a latch-free approach that effectively exploits the processor caches of modern multi-core chips. Our storage manager uses a unique form of log structuring that blurs the distinction between a page and a record store and works well with flash storage.

datastructure
memory
storage
april 2014 by mpm

nedtries

october 2013 by mpm

So what if I told you that for the very common case of a pointer sized key lookup that the standard assumptions are wrong? What if there was an algorithm which provides one of the big advantages of ordered indexation which is close fit finds, except it has nearly O(1) complexity rather than O(log N) and is therefore 100% faster? What if, in fact, this algorithm is a good 20% faster than the typical O(1) hash table implementation for medium sized collections and is no slower even at 10,000 items?

datastructure
memory
october 2013 by mpm

Non-blocking Patricia Tries with Replace Operations

march 2013 by mpm

This paper presents a non-blocking Patricia trie implementation for an asynchronous shared-memory system using Compare&Swap

datastructure
non-blocking
march 2013 by mpm

Systems Programming: Coping with Parallelism

february 2013 by mpm

Creating operating system components and subsystcms in today's large processors generally requires dealing with more than one CPU operating in parallel against a shared memory. While "applications" are typically shielded from the effects of parallelism, components and subsystems ususally are designed in such a way that some level of understanding is required. This paper concentrates on the pitfalls awaiting the proprammer in a parallel (or even a multiprogramming) environment when shared data structures (control blocks) are referenced and altercd by muitipie processes (tasks). The focus is on the IBM Systemi 370 architecture because of its multiple CPU architecture and the powerful "compare and swap" instruction. The paper reviews some architectural groundrules that a parallel programmer must understand, presents problems that must often be solved in a parallel environment, then describes solutions such as usage of compare and swap, locks, and single-process schemes. Kernels of code are used to illustrate problems and solutions

concurrency
datastructure
non-blocking
february 2013 by mpm

A Lock-Free Algorithm for Concurrent Bags

february 2013 by mpm

A lock-free bag data structure supporting unordered buffering is presented in this paper. The algorithm supports multiple producers and multiple consumers, as well as dynamic collection sizes. To handle concurrency efficiently, the algorithm was designed to thrive for disjoint-access-parallelism for the supported semantics. Therefore, the algorithm exploits a distributed design combined with novel techniques for handling concurrent modifications of linked lists using double marks, detection of total emptiness, and efficient memory management with hazard pointer handover. Experiments on a 24-way multi-core platform show significantly better performance for the new algorithm compared to previous algorithms of relevance.

concurrency
datastructure
non-blocking
february 2013 by mpm

A Scalable Lock-free Stack Algorithm

february 2013 by mpm

The literature describes two high performance concurrent stack algorithms based on combining funnels and elimination trees. Unfortunately, the funnels are linearizable but blocking, and the elimination trees are non-blocking but not linearizable. Neither is used in practice since they perform well only at exceptionally high loads. The literature also describes a simple lock-free linearizable stack algorithm that works at low loads but does not scale as the load increases. The question of designing a stack algorithm that is non-blocking, linearizable, and scales well throughout the concurrency range, has thus remained open. This paper presents such a concurrent stack algorithm. It is based on the following simple observation: that a single elimination array used as a backoff scheme for a simple lock-free stack is lock-free, linearizable, and scalable. As our empirical results show, the resulting eliminationbackoff stack performs as well as the simple stack at low loads, and increasingly outperforms all other methods (lock-based and non-blocking) as concurrency increases. We believe its simplicity and scalability make it a viable practical alternative to existing constructions for implementing concurrent stacks.

concurrency
datastructure
non-blocking
february 2013 by mpm

FastFlow Queue

february 2013 by mpm

FastFlow is a parallel programming framework for multicore platforms, which uses hybrid single-producer/single-consumer queues as a base underlying component for inter-thread communication

concurrency
datastructure
non-blocking
february 2013 by mpm

C++ B-tree

february 2013 by mpm

C++ B-tree is a template library that implements ordered in-memory containers based on a B-tree data structure. Similar to the STL map, set, multimap, and multiset templates, this library provides btree_map, btree_set, btree_multimap, and btree_multiset

c++
datastructure
february 2013 by mpm

ArrayTernaryTrie<V>

january 2013 by mpm

A Ternary Trie String lookup data structure. This Trie is of a fixed size and cannot grow

java
datastructure
january 2013 by mpm

GapList

january 2013 by mpm

This article introduces GapList, an implementation which strives for combining the strengths of both ArrayList and LinkedList. We will show how it is implemented to offer efficient random access to elements by index (as ArrayList does) and at the same time efficient adding and removing elements to and from head and tail of the list (as LinkedList does).

java
datastructure
january 2013 by mpm

Segment Trees

january 2013 by mpm

a height balanced binary tree with a static structure

datastructure
january 2013 by mpm

sparsehash

november 2012 by mpm

An extremely memory-efficient hash_map implementation. 2 bits/entry overhead! The SparseHash library contains several hash-map implementations, including implementations that optimize for space or speed

c++
datastructure
november 2012 by mpm

SSTable and Log Structured Storage: LevelDB

july 2012 by mpm

SSTable is a simple abstraction to efficiently store large numbers of key-value pairs while optimizing for high throughput, sequential read/write workloads

database
datastructure
io
storage
july 2012 by mpm

Count-Min Sketch

june 2012 by mpm

The Count-Min sketch is a simple technique to summarize large amounts of frequency data. It was introduced in 2003, and since then has inspired many applications, extensions and variations. This sitelet collects and explains this work on the Count-Min, or CM, sketch

probability
datastructure
june 2012 by mpm

A comprehensive study of Convergent and Commutative Replicated Data Types

may 2012 by mpm

Eventual consistency aims to ensure that replicas of some mutable shared object converge without foreground synchronisation. Previous approaches to eventual consistency are ad-hoc and error-prone. We study a principled approach: to base the design of shared data types on some simple formal conditions that are sufficient to guarantee eventual consistency. We call these types Convergent or Commutative Replicated Data Types (CRDTs)

distributed
datastructure
consistency
base
may 2012 by mpm

A survey of B-tree locking techniques

april 2012 by mpm

The purpose of this survey is to clarify, simplify, and structure the topic of concurrency control in B-trees by dividing it into two sub-topics and exploring each of them in depth.

concurrency
datastructure
april 2012 by mpm

Non-intrusive MPSC node-based queue

march 2012 by mpm

+ Waitfree and fast producers. One XCHG is maximum what one can get with multi-producer non-distributed queue.

+ Extremely fast consumer. On fast-path it's atomic-free, XCHG executed per node batch, in order to grab 'last item'.

+ No need for node order reversion. So pop operation is always O(1).

+ ABA-free.

+ No need for PDR. That is, one can use this algorithm out-of-the-box. No need for thread registration/deregistration, periodic activity, deferred garbage etc.

datastructure
non-blocking
+ Extremely fast consumer. On fast-path it's atomic-free, XCHG executed per node batch, in order to grab 'last item'.

+ No need for node order reversion. So pop operation is always O(1).

+ ABA-free.

+ No need for PDR. That is, one can use this algorithm out-of-the-box. No need for thread registration/deregistration, periodic activity, deferred garbage etc.

march 2012 by mpm

Single-Producer/Single-Consumer Queue

march 2012 by mpm

Unbounded single-producer/single-consumer node-based queue

datastructure
non-blocking
march 2012 by mpm

Boxwood: Abstractions as the Foundation for Storage Infrastructure

march 2012 by mpm

We have built a system called Boxwood to explore the feasibility and utility of providing high-level abstractions or data structures as the fundamental storage infrastructure

distributed
consensus
datastructure
storage
fault-tolerance
march 2012 by mpm

Heavy Hitter Detection with Sketches

february 2012 by mpm

A sketch is generally defined as a data structure that summarizes streaming data, and supports certain queries on the stream. It maintains sufficient statistics to answer those queries

statistics
datastructure
february 2012 by mpm

Ctrie

february 2012 by mpm

A concurrent hash-trie or Ctrie is a concurrent thread-safe lock-free implementation of a hash array mapped trie. It is used to implement the concurrent map abstraction. It has particularly scalable concurrent insert and remove operations and is memory-efficient. It is the first known concurrent data-structure that supports O(1), atomic, lock-free snapshots

concurrency
datastructure
non-blocking
february 2012 by mpm

lsm_btree

january 2012 by mpm

This erlang-based storage engine implements a structure somewhat like LSM-trees (Log-Structured Merge Trees)

erlang
storage
datastructure
january 2012 by mpm

lockfreeskiptree

january 2012 by mpm

Drop-in replacement for java.util.concurrent.ConcurrentSkipList[Map|Set]

java
concurrency
datastructure
january 2012 by mpm

**related tags**

Copy this bookmark: