Java port of a concurrent trie hash map implementation from the Scala collections library

Overview

About

This is a Java port of a concurrent trie hash map implementation from the Scala collections library. It is almost a line-by-line conversion from Scala to Java.

Idea + implementation techniques can be found in these reports written by Aleksandar Prokopec:

The original Scala implementation can be found here and is a part of scala.collection.concurrent:

Some of the tests and implementation details were borrowed from this project:

Implementation status :

  • The given implementation is complete and implements all features of the original Scala implementation including support for snapshots.
  • Wherever necessary, code was adapted to be more easily usable in Java, e.g. it returns Objects instead of Option as many methods of Scala's collections do.
  • This class implements all the ConcurrentMap & Iterator methods and passes all the tests. Can be used as a drop-in replacement for usual Java maps, including ConcurrentHashMap.

What is a concurrent trie hash map also known as ctrie?

ctrie is a lock-Free Concurrent Hash Array Mapped Trie.

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 supports O(1), atomic, lock-free snapshots which are used to implement linearizable lock-free size, iterator and clear operations. The cost of evaluating the (lazy) snapshot is distributed across subsequent updates, thus making snapshot evaluation horizontally scalable.

The original Scala-based implementation of the Ctrie is a part of the Scala standard library since the version 2.10.

More info about Ctries:

License

This library is licensed under the Apache 2.0 license.

Usage

Usage of this library is very simple. Simply import the class com.romix.scala.collection.concurrent.TrieMap and use it as a usual Map.

import com.romix.scala.collection.concurrent.TrieMap;

Map myMap = new TrieMap <Object, Object> ();
myMap.put("key", "value");

Building the library

Use a usual mvn clean install

Using the library with Maven projects

The prebuilt binaries of the library are available from Maven central. Please use the following dependency in your POM files:

	<dependency>
		<groupId>com.github.romix</groupId>
		<artifactId>java-concurrent-hash-trie-map</artifactId>
		<version>0.2.23</version>
	</dependency>

External dependencies

This library is self-contained. It does not depend on any additional libraries. In particular, it does not require the rather big Scala's standard library to be used.

Comments
  • Optimize the use of AtomicReferenceFieldUpdaters

    Optimize the use of AtomicReferenceFieldUpdaters

    Benchmarks indicate that instatiating the updaters takes ~92% of the CPU time required to initialize a TrieMap instance.

    TrieMap.inodeupdater is an unused per-object updater, which has its equivalent in INodeBase.updater.

    rtupd is an unused istance, so we can freely remove it, lowering the memory cost of a TrieMap just a tiny bit.

    Finally, we centralize the allocation of rootupdater -- instead of allocating it over and over again, we have a single instance which we share.

    Signed-off-by: Robert Varga [email protected]

    opened by rovarga 5
  • Use equal() instead of identity in readonly TNode

    Use equal() instead of identity in readonly TNode

    Instead of requiring a match on identity, use equal() to compare the stored and lookup keys. This fixes https://bugs.opendaylight.org/show_bug.cgi?id=6577.

    Signed-off-by: Robert Varga [email protected]

    opened by rovarga 2
  • Rework read-only tracking

    Rework read-only tracking

    This builds on top of pull request #14, and changes how read-only is tracked. Instead of tracking a reference, there is final boolean field which is checked before the static updater is touched.

    It should have the same (or slightly better) performance characteristics, that may or may not be true.

    opened by rovarga 2
  • V get (Object k) returns Some instead of V

    V get (Object k) returns Some instead of V

    We run into situations when subj. returns Some instance instead of V.

    I'm now working on isolated test case, but quick look suggest that there could be an obvious bug. Method 'get' performs lookuphc and return result just casting it to V. In the same time method 'lookup' performs the same call and checks whether the value is an Option or not.

    May be get should work the same as lookup?

    opened by CheatEx 2
  • Fix putIfAbsent / rec_insertif in case of an LNode and current node value is None (instead of null).

    Fix putIfAbsent / rec_insertif in case of an LNode and current node value is None (instead of null).

    This small code change fixes the handling of LNode "KEY_ABSENT" case when adding element to TrieMap. The problem is that getting current value from node (from it's internal ListMap) can never return null. It will return either Some or None. So the current check for null will not add element to node if that get will return None falsely assuming that element already exists. In the scala source version there is also only pattern match for None and Some.

    opened by mikesajak 1
  • Use java.util.concurrent.ThreadLocalRandom

    Use java.util.concurrent.ThreadLocalRandom

    Java 7 has introduced ThreadLocalRandom, which has been picked up by the Scala implementation. Mirror that decision here.

    Signed-off-by: Robert Varga [email protected]

    opened by rovarga 1
  • Remove Pair in favor of SimpleImmutableEntry

    Remove Pair in favor of SimpleImmutableEntry

    java.util.AbstractMap.SimpleImmutableEntry provides the same functionality as Pair. Remove Pair and adjust its users to use SimpleImmutableEntry instead.

    Signed-off-by: Robert Varga [email protected]

    opened by rovarga 1
  • Further improvements to serialization

    Further improvements to serialization

    The first patch eliminates the interim hashmap in the serialization path.

    The second patch makes the equality/hash functions final and reworks the serialization path to use default java serializer as much as possible (which will set the final fields for us).

    opened by rovarga 0
  • Detect attempts to modify read-only view

    Detect attempts to modify read-only view

    Adds explicit checks for read-only snapshot before attempting to perform a modification operation. As per ConcurrentMap/Iterator interface specification, throw an UnsupportedOperationException if such an attempt is made.

    Signed-off-by: Robert Varga [email protected]

    opened by rovarga 0
  • Fix constructor not passing down proper values

    Fix constructor not passing down proper values

    Internal constructor needs to pass down the arguments, so read-only snapshots are created properly. This allows serialization to work as expected. Also add serialVersionUID to fix some warnings.

    Signed-off-by: Robert Varga [email protected]

    opened by rovarga 0
  • Is this supposed to work? new TrieMap<>().clear();

    Is this supposed to work? new TrieMap<>().clear();

    On my machine this results to an infinite loop:

    /**
     *
     */
    public void testClear() {
        new TrieMap<>().clear();
    }
    

    2013-08-06 19:41:05 Full thread dump Java HotSpot(TM) 64-Bit Server VM (23.25-b01 mixed mode):

    "test-runner" prio=10 tid=0x00007f2d609d9800 nid=0x5cc7 runnable [0x00007f2d4f616000] java.lang.Thread.State: RUNNABLE at com.romix.scala.collection.concurrent.TrieMap.RDCSS_Complete(TrieMap.java:1115) at com.romix.scala.collection.concurrent.TrieMap.RDCSS_ROOT(TrieMap.java:1143) at com.romix.scala.collection.concurrent.TrieMap.clear(TrieMap.java:1285)

    2013-08-06 19:41:05 Full thread dump Java HotSpot(TM) 64-Bit Server VM (23.25-b01 mixed mode):

    "test-runner" prio=10 tid=0x00007f2d609d9800 nid=0x5cc7 runnable [0x00007f2d4f616000] java.lang.Thread.State: RUNNABLE at com.romix.scala.collection.concurrent.TrieMap.clear(TrieMap.java:1285) at org.gridgain.grid.lang.utils.GridTrieMapSelfTest.testClear(GridTrieMapSelfTest.java:96) at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method) at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:57) at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43) at java.lang.reflect.Method.invoke(Method.java:606)

    java -version java version "1.7.0_25" Java(TM) SE Runtime Environment (build 1.7.0_25-b15) Java HotSpot(TM) 64-Bit Server VM (build 23.25-b01, mixed mode)

    OS: ubuntu 12.04

    Yakov

    opened by yzhdanov 0
  • Bump junit from 4.9 to 4.13.1

    Bump junit from 4.9 to 4.13.1

    Bumps junit from 4.9 to 4.13.1.

    Release notes

    Sourced from junit's releases.

    JUnit 4.13.1

    Please refer to the release notes for details.

    JUnit 4.13

    Please refer to the release notes for details.

    JUnit 4.13 RC 2

    Please refer to the release notes for details.

    JUnit 4.13 RC 1

    Please refer to the release notes for details.

    JUnit 4.13 Beta 3

    Please refer to the release notes for details.

    JUnit 4.13 Beta 2

    Please refer to the release notes for details.

    JUnit 4.13 Beta 1

    Please refer to the release notes for details.

    JUnit 4.12

    Please refer to the release notes for details.

    JUnit 4.12 Beta 3

    Please refer to the release notes for details.

    JUnit 4.12 Beta 2

    No release notes provided.

    JUnit 4.12 Beta 1

    No release notes provided.

    JUnit 4.11

    No release notes provided.

    Changelog

    Sourced from junit's changelog.

    Summary of changes in version 4.13.1

    Rules

    Security fix: TemporaryFolder now limits access to temporary folders on Java 1.7 or later

    A local information disclosure vulnerability in TemporaryFolder has been fixed. See the published security advisory for details.

    Test Runners

    [Pull request #1669:](junit-team/junit#1669) Make FrameworkField constructor public

    Prior to this change, custom runners could make FrameworkMethod instances, but not FrameworkField instances. This small change allows for both now, because FrameworkField's constructor has been promoted from package-private to public.

    Commits
    • 1b683f4 [maven-release-plugin] prepare release r4.13.1
    • ce6ce3a Draft 4.13.1 release notes
    • c29dd82 Change version to 4.13.1-SNAPSHOT
    • 1d17486 Add a link to assertThrows in exception testing
    • 543905d Use separate line for annotation in Javadoc
    • 510e906 Add sub headlines to class Javadoc
    • 610155b Merge pull request from GHSA-269g-pwp5-87pp
    • b6cfd1e Explicitly wrap float parameter for consistency (#1671)
    • a5d205c Fix GitHub link in FAQ (#1672)
    • 3a5c6b4 Deprecated since jdk9 replacing constructor instance of Double and Float (#1660)
    • Additional commits viewable in compare view

    Dependabot compatibility score

    Dependabot will resolve any conflicts with this PR as long as you don't alter it yourself. You can also trigger a rebase manually by commenting @dependabot rebase.


    Dependabot commands and options

    You can trigger Dependabot actions by commenting on this PR:

    • @dependabot rebase will rebase this PR
    • @dependabot recreate will recreate this PR, overwriting any edits that have been made to it
    • @dependabot merge will merge this PR after your CI passes on it
    • @dependabot squash and merge will squash and merge this PR after your CI passes on it
    • @dependabot cancel merge will cancel a previously requested merge and block automerging
    • @dependabot reopen will reopen this PR if it is closed
    • @dependabot close will close this PR and stop Dependabot recreating it. You can achieve the same result by closing it manually
    • @dependabot ignore this major version will close this PR and stop Dependabot creating any more for this major version (unless you reopen the PR or upgrade to it yourself)
    • @dependabot ignore this minor version will close this PR and stop Dependabot creating any more for this minor version (unless you reopen the PR or upgrade to it yourself)
    • @dependabot ignore this dependency will close this PR and stop Dependabot creating any more for this dependency (unless you reopen the PR or upgrade to it yourself)
    • @dependabot use these labels will set the current labels as the default for future PRs for this repo and language
    • @dependabot use these reviewers will set the current reviewers as the default for future PRs for this repo and language
    • @dependabot use these assignees will set the current assignees as the default for future PRs for this repo and language
    • @dependabot use this milestone will set the current milestone as the default for future PRs for this repo and language

    You can disable automated security fix PRs for this repo from the Security Alerts page.

    dependencies 
    opened by dependabot[bot] 0
  • Comparision with high-scale-lib

    Comparision with high-scale-lib

    Was performance and memory footprint of this map implementation compared with NonBlockingHashMap from high-scale-lib? Seems like both of these projects aim to provide a non-blocking implementation of ConcurrentMap that could potentially replace ConcurrentHashMap in Java applications.

    opened by czyzby 0
Releases(java-concurrent-hash-trie-map-0.2.1)
Owner
null
Eclipse Collections is a collections framework for Java with optimized data structures and a rich, functional and fluent API.

English | 中文 | Deutsch | Español | Ελληνικά | Français | 日本語 | Norsk (bokmål) | Português-Brasil | Русский | हिंदी Eclipse Collections is a comprehens

Eclipse Foundation 2.1k Dec 29, 2022
Rolling hash functions in Java

Rolling hash functions in Java License: Apache 2.0 What is this? This is a set of Java classes implementing various recursive n-gram hashing technique

Daniel Lemire 73 Dec 14, 2022
An embedded database implemented in pure java based on bitcask which is a log-structured hash table for K/V Data.

Baka Db An embedded database implemented in pure java based on bitcask which is a log-structured hash table for K/V Data. Usage import cn.ryoii.baka.B

ryoii 3 Dec 20, 2021
Google Hash Code '22 Question

Answer for - Mentorship and Teamwork Google Hash Code '22 Question Credit goes to Google LLC - Hash Code '22 Work is so much more fun when we are part

Dilshan Karunarathne 4 Apr 12, 2022
A Persistent Java Collections Library

PCollections A Persistent Java Collections Library Overview PCollections serves as a persistent and immutable analogue of the Java Collections Framewo

harold cooper 708 Dec 28, 2022
High Performance Primitive Collections for Java

HPPC: High Performance Primitive Collections Collections of primitive types (maps, sets, stacks, lists) with open internals and an API twist (no java.

Carrot Search 890 Dec 28, 2022
Java Collections till the last breadcrumb of memory and performance

Koloboke A family of projects around collections in Java (so far). The Koloboke Collections API A carefully designed extension of the Java Collections

Roman Leventov 967 Nov 14, 2022
A java.util.HashMap compatible map that won't stall puts or gets when resizing

/* * Written by Gil Tene, based on Apache Harmony version of java.util.HashMap. */ PauselessHashMap: A java.util.HashMap compatible Map implementat

Gil Tene 145 Oct 19, 2022
A beginner's guide to Learn Java Collections Framework

Collections-Framework A beginner's guide to Learn Java Collections Framework Topics included: Collection Interface ArrayList Iterator Stack Queue and

Anuj Kumar Sharma 97 Dec 30, 2022
Persistent (immutable) collections for Java and Kotlin

What are Dexx Collections? Dexx Collections are a port of Scala's immutable, persistent collection classes to pure Java. Persistent in the context of

Andrew O'Malley 208 Sep 30, 2022
The Java collections framework provides a set of interfaces and classes to implement various data structures and algorithms.

Homework #14 Table of Contents General Info Technologies Used Project Status Contact General Information Homework contains topics: Sorting an ArrayLis

Mykhailo 1 Feb 12, 2022
fasttuple - Collections that are laid out adjacently in both on- and off-heap memory.

FastTuple Introduction There are lots of good things about working on the JVM, like a world class JIT, operating system threads, and a world class gar

BMC TrueSight Pulse (formerly Boundary) 137 Sep 30, 2022
Port of LevelDB to Java

LevelDB in Java This is a rewrite (port) of LevelDB in Java. This goal is to have a feature complete implementation that is within 10% of the performa

Dain Sundstrom 1.4k Dec 30, 2022
Bloofi: A java implementation of multidimensional Bloom filters

Bloofi: A java implementation of multidimensional Bloom filters Bloom filters are probabilistic data structures commonly used for approximate membersh

Daniel Lemire 71 Nov 2, 2022
High performance Java implementation of a Cuckoo filter - Apache Licensed

Cuckoo Filter For Java This library offers a similar interface to Guava's Bloom filters. In most cases it can be used interchangeably and has addition

Mark Gunlogson 161 Dec 30, 2022
A Java implementation of Transducers

transducers-java Transducers are composable algorithmic transformations. They are independent from the context of their input and output sources and s

null 117 Sep 29, 2022
Parquet-MR contains the java implementation of the Parquet format

Parquet MR Parquet-MR contains the java implementation of the Parquet format. Parquet is a columnar storage format for Hadoop; it provides efficient s

The Apache Software Foundation 1.8k Jan 5, 2023
Implementation of various string similarity and distance algorithms: Levenshtein, Jaro-winkler, n-Gram, Q-Gram, Jaccard index, Longest Common Subsequence edit distance, cosine similarity ...

java-string-similarity A library implementing different string similarity and distance measures. A dozen of algorithms (including Levenshtein edit dis

Thibault Debatty 2.5k Dec 29, 2022
Golang implementation of the Alaya protocol

Go PlatON Welcome to the PlatON-Go source code repository! This is an Ethereum-based、high-performance and high-security implementation of the PlatON p

null 23 Oct 14, 2022