A collection of hash tables for parallel programming, including lock-free, wait-free tables.

Related tags

Data Structures data-structures hashmap concurrent-programming lock-free hashtable concurrent-data-structure wait-free
Overview

Hatrack

Hash tables for parallel programming

This project consisists of fast hash tables suitable for parallel programming, including multiple lock-free, wait-free hashtables.

If you're interested in understanding the different algorithms, see the README.md in the src/ directory.

If you're just interested in using the most efficient algorithms in your C applications, see below for instructions.

Overview

This project will install libhatrack.a, which exports high-level dictionary and set classes (hatrack_dict and hatrack_set), backed by two appropriate lower-level hash tables. Examples of using these classes are in the examples directory.

The lower-level hash tables can also be used directly; again, look at the src directory.

The hatrack_dict and hatrack_set implementations both support multiple simultaneous readers and multiple simultaneous writers.

You are responsible for all memory management for keys and items; our hash tables only worries about memory management for state internal to the table.

Installing

If you downloaded a release distro, you can simply do:

./configure
make
sudo make install

If you cloned the repo, then you'll first need to create the configure script and Makefile.in, using autotools:

aclocal
autoheader
autoconf
automake

If you want to run the test suite, first build it with:

make check

This will create an executable named test in the tests directory, which will run functionality and performance tests for all the different hash table implementations.

There are no library dependencies, beyond bits that are a part of the C11 standard (particularly stdatomic and pthreads). Parallel malloc implementations like jemalloc (http://jemalloc.net) or hoard (http://hoard.org) can be added via LD_PRELOAD, which may boost performance when there's significant concurancy, depending on the system malloc you're using... particularly with hatrack_set objects, which require more dynamic memory allocation than hatrack_dictionary objects do (this is due to sets requiring fully consistent views; see the README.md file in the src directory for more information).

Getting Started

Once you've built, you can just link against the library, and go. See the examples directory.

You might also like...
HashTableBenchmark - A simple cross-platform speed & memory-efficiency benchmark for the most common hash-table implementations in the C++ world

Hash-Tables Benchmarks This repository contains a bunch of extendable benchmarks mostly for following containers: std:unordered_map from STL. google::

Unum 9 Nov 20, 2022
Collection of all the LeetCode problem solutions using different programming languages.

LeetCode Solutions Collection of all the LeetCode problem solutions using different programming languages. To contribute, you can make a file for the

Jay Patel 34 Sep 2, 2022
A library of type safe sets over fixed size collections of types or values, including methods for accessing, modifying, visiting and iterating over those.

cpp_enum_set A library of type safe sets over fixed size collections of types or values, including methods for accessing, modifying, visiting and iter

Carl Dehlin 22 Jun 16, 2022
Tuplex is a parallel big data processing framework that runs data science pipelines written in Python at the speed of compiled code

Tuplex is a parallel big data processing framework that runs data science pipelines written in Python at the speed of compiled code. Tuplex has similar Python APIs to Apache Spark or Dask, but rather than invoking the Python interpreter, Tuplex generates optimized LLVM bytecode for the given pipeline and input data set.

Tuplex 791 Jan 4, 2023
Library of generic and type safe containers in pure C language (C99 or C11) for a wide collection of container (comparable to the C++ STL).
Library of generic and type safe containers in pure C language (C99 or C11) for a wide collection of container (comparable to the C++ STL).

M*LIB: Generic type-safe Container Library for C language Overview M*LIB (M star lib) is a C library enabling to use generic and type safe container i

PpHd 571 Jan 5, 2023
A collection of various algorithms to produce length-limited prefix codes

Introduction This is a collection of various algorithms to produce length-limited prefix codes. My library is written in plain C with tons of comments

Stephan Brumme 15 Nov 7, 2022
Algo-Tree is a collection of Algorithms and data structures which are fundamentals to efficient code and good software design. Creating and designing excellent algorithms is required for being an exemplary programmer. It contains solutions in various languages such as C++, Python and Java.
Algo-Tree is a collection of Algorithms and data structures which are fundamentals to efficient code and good software design. Creating and designing excellent algorithms is required for being an exemplary programmer. It contains solutions in various languages such as C++, Python and Java.

Algo-Tree 🌲 Algo-Tree is a collection of Algorithms and data structures which are fundamentals to efficient code and good software design. Creating a

Algo Phantoms 321 Dec 2, 2022
A collection of basic data structures syntaxes, useful for competitive coding and placement exams
A collection of basic data structures syntaxes, useful for competitive coding and placement exams

Data-Structures A collection of basic data structures syntaxes, useful for competitive coding and placement exams 1. Array 2. Matrix 3. Linked List Si

MAINAK CHAUDHURI 2 Aug 8, 2021
A collection of multiple types of lists used during pentesting, collected in one place. List types include usernames, passwords, combos, wordlist and may more..
A collection of multiple types of lists used during pentesting, collected in one place. List types include usernames, passwords, combos, wordlist and may more..

Access list is a collection of multiple types of lists used during pentesting, collected in one place, created by Undercode This list include a collec

UNDERCODE UTILITIES 10 Nov 21, 2022
Comments
  • Make core capq operations wait-free.

    Make core capq operations wait-free.

    I've changed the overall capq implementation, refactoring it to ensure that calls to top() are wait-free, so that one can use this abstraction to implement other wait-free algorithms.

    This actually simplified the algorithm and seems to have improved performance considerably as well.

    Note that it's still possible to use this abstraction in a way that destroys the progress guarantees. For example, I still provide a capq_dequeue operation built on top of top() plus compare-and-pop(), which is only lock-free (the operation mainly exists so that we can use the same code for testing capq as we do for other queues).

    opened by viega 0
  • Fast lock-free stack and flex-array.

    Fast lock-free stack and flex-array.

    I added a fast stack, that eliminates the head contention one sees with the traditional approach (favoring FAA over CAS). I originally had a complicated in-place compression algorithm to incrementally compress the stack, but it turned out the simpler migration strategy used on the hash tables is better in practice, and simpler.

    I will probably still do the little bit of work necessary to make the stack wait-free (at least optionally).

    Additionally, I added an initial fast, wait-free flexible array. It does bounds checking and can be resized up or down.

    The flexarray does NOT support push and pop the way C++ vectors do. I have an algorithm I need to implement that will allow for that, with the random access being almost as fast as flex array, and the push/pop being possible. When I get to that, it will be called a "vector", not a flexarray.

    The two separate constructions will be much faster on their own (especially the stack; there are reasons why the approach for this stack won't work in a vector), but if you need both in one data structure, I'll soon have you covered.

    opened by viega 0
Owner
null
GitHub
A fast hash map/hash table (whatever you want to call it) for the C programming language.

C HashMap A fast hash map/hash table (whatever you want to call it) for the C programming language. It can associate a key with a pointer or integer v

Mashpoe 74 Dec 27, 2022
C++ implementation of a fast hash map and hash set using hopscotch hashing

A C++ implementation of a fast hash map and hash set using hopscotch hashing The hopscotch-map library is a C++ implementation of a fast hash map and

Thibaut Goetghebuer-Planchon 578 Dec 23, 2022
C++ implementation of a fast hash map and hash set using robin hood hashing

A C++ implementation of a fast hash map and hash set using robin hood hashing The robin-map library is a C++ implementation of a fast hash map and has

Thibaut Goetghebuer-Planchon 878 Jan 2, 2023
Explore building a hash table with two different hash functions that balances chain length

hash-duo Explore building a hash table with two different hash functions that balances chain length. There is a really cool article called Don't Throw

Terence Parr 3 May 7, 2022
C++ hash map and hash set which preserve the order of insertion

C++ hash map and hash set which preserves the order of insertion The ordered-map library provides a hash map and a hash set which preserve the order o

Thibaut Goetghebuer-Planchon 381 Dec 2, 2022
A fast multi-producer, multi-consumer lock-free concurrent queue for C++11

moodycamel::ConcurrentQueue An industrial-strength lock-free queue for C++. Note: If all you need is a single-producer, single-consumer queue, I have

Cameron 7.4k Jan 2, 2023
Simple hash table implemented in C

Simple hash table written in C. To go with my article How to implement a hash table (in C). This is a learning exercise, not a battle-tested data stru

Ben Hoyt 86 Dec 10, 2022
simple hash table linear probing method can expand/reduce

hash table a simple c hash table implementation based on https://benhoyt.com/writings/hash-table-in-c/ project can store different data types (data al

Fabio Murer 1 Oct 3, 2021
A simple single header 64 and 32 bit hash function using only add, sub, ror, and xor.

K-HASH A simple single header 64 bit hash function using only add, sub, ror, and xor. This a just general-purpose hash function for like making hash m

null 70 Dec 27, 2022
Very Fast Non-Cryptographic Hash Function

KOMIHASH - Very Fast Hash Function Introduction The komihash() function available in the komihash.h file implements a very fast 64-bit hash function,

Aleksey Vaneev 94 Dec 12, 2022