mpm + datastructure   151

A Scalable, Portable, and Memory-Efficient Lock-Free FIFO Queue
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 
19 hours ago by mpm
EBtree - Design for a Scheduler and Use (Almost) Everywhere
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
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
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
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 
6 weeks ago by mpm
Black-box Concurrent Data Structures for NUMA Architectures
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
Exploring the basics of computer science, every Monday, for a year.
datastructure  algorithm 
october 2017 by mpm
Modern B-Tree Techniques
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 
october 2017 by mpm
diiskhash
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 
july 2017 by mpm
BwTree
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
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
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
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
std::bitset with constexpr implementations plus additional features.
c++  datastructure 
december 2016 by mpm
Skip Lists: Done Right
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
An experiment with modern C++, suffix trees, and Ukkonen's algorithm for suffix tree construction
c++  datastructure 
december 2016 by mpm
immer
immer is a library of persistent and immutable data structures written in C++.
c++  datastructure  concurrency 
november 2016 by mpm
Bloofi
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
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
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
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
libcuckoo provides a high-performance, compact hash table that allows multiple concurrent reader and writer threads
c++  concurrency  datastructure 
november 2015 by mpm
SmoothieMap
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
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
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
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
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
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
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
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
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
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 
december 2014 by mpm
streaming-papers
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
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
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 
august 2014 by mpm
STX B+ Tree
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
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
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
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
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 
june 2014 by mpm
The Bw-Tree: A B-tree for New Hardware Platforms
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
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
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
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
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
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
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
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
ArrayTrie<V>
A Trie String lookup data structure.
java  datastructure 
january 2013 by mpm
ArrayTernaryTrie<V>
A Ternary Trie String lookup data structure. This Trie is of a fixed size and cannot grow
java  datastructure 
january 2013 by mpm
GapList
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
a height balanced binary tree with a static structure
datastructure 
january 2013 by mpm
sparsehash
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
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
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
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
meangirls
Convergent Replicated Data Types
datastructure  consistency  base 
may 2012 by mpm
A survey of B-tree locking techniques
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
+ 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 
march 2012 by mpm
Single-Producer/Single-Consumer Queue
Unbounded single-producer/single-consumer node-based queue
datastructure  non-blocking 
march 2012 by mpm
Boxwood: Abstractions as the Foundation for Storage Infrastructure
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
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
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
This erlang-based storage engine implements a structure somewhat like LSM-trees (Log-Structured Merge Trees)
erlang  storage  datastructure 
january 2012 by mpm
lockfreeskiptree
Drop-in replacement for java.util.concurrent.ConcurrentSkipList[Map|Set]
java  concurrency  datastructure 
january 2012 by mpm
javaewah
A compressed alternative to the Java BitSet class
java  datastructure 
january 2012 by mpm
« earlier      
per page:    204080120160

Copy this bookmark:



description:


tags: