A fork of Cliff Click's High Scale Library. Improved with bug fixes and a real build system.

Overview

High Scale Lib

This is Boundary's fork of Cliff Click's high scale lib. We will be maintaining this fork with bug fixes, improvements and versioned builds in maven central.

To use high scale lib from ivy declare the dependency in ivy.xml:

<dependency
  org="com.boundary"
  name="high-scale-lib"
  rev="1.0.3" />

From maven simply add the dependency to the dependencies element:

<dependency>
  <groupId>com.boundary</groupId>
  <artifactId>high-scale-lib</artifactId>
  <version>1.0.6</version>
</dependency>

Original README

IF YOU ARE LOOKING for the drop-in replacement for java.util.Hashtable, it's in the lib directory, lib/java_util_hashtable.jar. It needs to be in your bootclasspath. Example:

java -Xbootclasspath/p:lib/java_util_hashtable.jar my_java_app_goes_here

A collection of Concurrent and Highly Scalable Utilities. These are intended as direct replacements for the java.util.* or java.util.concurrent.* collections but with better performance when many CPUs are using the collection concurrently. Single-threaded performance may be slightly lower.

The direct replacements match the API - but not all behaviors are covered by the API, and so they may not work for your program. In particular, the replacement for java.util.Hashtable is NOT synchronized (that is the point!), although it is multi-threaded safe. If you rely on the undocumented synchronization behavior of the JDK Hashtable, your program may not work. Similarly, the iteration order is different between this version and the JDK version (this exact issue broke the SpecJBB benchmark when the iteration order was changed slightly (via using a slightly different hash function) between JDK rev's).

If you want to drop-in the non-blocking versions of Hashtable, HashMap or ConcurrentHashMap, you'll need to alter your bootclasspath - these classes come directly from your JDK and so are found via the System loader before any class-path hacks can be done.

To replace the JDK implementation of Hashtable with a non-blocking version of Hashtable, add java_util_hashtable.jar to your java launch line:

java -Xbootclasspath/p:lib/java_util_hashtable.jar my_app_goes_here

Similarly for ConcurrentHashMap, add java_util_concurrent_chm.jar:

java -Xbootclasspath/p:lib/java_util_concurrent_chm.jar my_app_goes_here

The other utilities do not have direct JDK replacements; you need to call them out directly and place high_scale_lib.jar in your classpath:

  • NonBlockingHashMap - Fast, concurrent, lock-free HashMap. Linear scaling to 768 CPUs.
  • NonBlockingHashMapLong - Same as above, but using primitive 'long' keys
  • NonBlockingHashSet - A Set version of NBHM
  • NonBlockingSetInt - A fast fully concurrent BitVector
  • Counter - A simple counter that scales linearly even when extremely hot. Most simple counters are either unsynchronized (hence drop counts, generally really badly beyond 2 cpus), or are normally lock'd (hence bottleneck in the 5-10 cpu range), or might use Atomic's (hence bottleneck in the 25-50 cpu range). This version scales linearly to 768 CPUs.

Cliff Click

Comments
  • Publish artifact to maven central

    Publish artifact to maven central

    Hi, we would like to use this library in apache cassanda but we've hit a snag when trying to build from our .pom file

    Would it be possible for you to publish this library to maven central?

    see https://issues.apache.org/jira/browse/CASSANDRA-7128 for reference.

    opened by tjake 3
  • Add NonBlockingHashSetLong and fix bug.

    Add NonBlockingHashSetLong and fix bug.

    Add NonBlockingHashSetLong (with additional improvements to avoid auto-boxing). Fix a bug in retainAll() in NonBlockingSetInt (wasn't properly returning the 'modified' value. Added a test to verify the behavior of retainAll().

    opened by pkwarren 0
  • Avoid additional auto-boxing in NonBlockingSetInt.

    Avoid additional auto-boxing in NonBlockingSetInt.

    Overloads addAll(), removeAll(), containsAll(), retainAll(), hashCode(), and toString() to avoid auto-boxing. Fixes some miscellaneous JavaDoc issues and other small code changes.

    opened by pkwarren 0
  • Add a LongIterator interface to favor primitives.

    Add a LongIterator interface to favor primitives.

    The current IteratorLong class is a nested class in NonBlockingHashMapLong, which means to iterate over the keys without auto boxing the casting can get awkward. This adds an interface LongIterator which the returned iterator from keySet().iterator() can be cast to safely. This also cleans up the Maven POM file and adds a simple test for the iterator.

    opened by pkwarren 0
  • Adjust cache line size

    Adjust cache line size

    A cache line size is 64 byes on modern CPUs. But the code appears to assume a size of 32 bytes. I adjusted two constants to increase the padding between counters.

    opened by suranap 0
  • high-scale-lib  don't include the license file

    high-scale-lib don't include the license file

    Not available LICENSE file in source directory structure Please. Added license and copyright notice. the fedora pakaging guideline is very strictly precise about this problem https://fedoraproject.org/wiki/Packaging:LicensingGuidelines?rd=Packaging/LicensingGuidelines#License_Text Thanks in advance Regards

    opened by puntogil 0
  • Source files without license headers

    Source files without license headers

    The following source files are without license headers. Please, confirm the licensing of code and/or content/s, with adding license headers https://fedoraproject.org/wiki/Packaging:LicensingGuidelines?rd=Packaging/LicensingGuidelines#License_Clarification

    src/main/java/com/boundary/BitPrint.java src/main/java/com/boundary/high_scale_lib/NonBlockingHashSetLong.java

    opened by puntogil 1
  • LICENSE file is missing

    LICENSE file is missing

    Original software is Public Domain, pom.xml file here contains information package is MIT licensed. It creates confusion about correct license and LICENSE file with proper content may make uncertainity lower.

    Licensing information in README usually helps too.

    opened by vlna 2
  • Always leads to OutOfMemoryError when we use large scalar random keys

    Always leads to OutOfMemoryError when we use large scalar random keys

            Map<Long, Object> map = new NonBlockingHashMap<Long, Object>();
            for (long i = 0;;i++) {
                map.put(i, i);
                map.remove(i);
            }
    
    Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
        at org.cliffc.high_scale_lib.NonBlockingHashMap$CHM.resize(NonBlockingHashMap.java:863)
        at org.cliffc.high_scale_lib.NonBlockingHashMap$CHM.access$3(NonBlockingHashMap.java:794)
        at org.cliffc.high_scale_lib.NonBlockingHashMap.putIfMatch(NonBlockingHashMap.java:649)
        at org.cliffc.high_scale_lib.NonBlockingHashMap.putIfMatch(NonBlockingHashMap.java:354)
        at org.cliffc.high_scale_lib.NonBlockingHashMap.put(NonBlockingHashMap.java:313)
    

    It is really serious bug because this make it unusable in many cases.

    Same issue was addressed at

    1. https://sourceforge.net/p/high-scale-lib/bugs/14/
    2. http://jsr166-concurrency.10961.n7.nabble.com/Unexpected-memory-usage-in-NonBlockingHashHashMap-td9913.html

    In the README file please add some notices about its limitation .

    opened by xfeep 0
  • add test and correct logic for failed replace on never used slot

    add test and correct logic for failed replace on never used slot

    Happened to check in on this fork, and realized I have an old bug fix kicking around (Jan 2013). Figured I should create a PR for it. I think everything here is pretty self explanatory.

    opened by chrisdennis 0
  • Typo in get_impl?

    Typo in get_impl?

    I believe there is a typo in get_impl here: https://github.com/boundary/high-scale-lib/blob/master/src/main/java/org/cliffc/high_scale_lib/NonBlockingHashMap.java#L540

    The line should instead read K == TOMBSTONE.

    You'll note that key is what the user passed in, and users should never try to retrieve a TOMBSTONE. In fact, I think Java's type safety prevents them from even getting a reference to the TOMBSTONE.

    This typo can effect the safety and efficiency of the get operation as the hash table is no longer linearizable. A write, that is then marked with a TOMBSTONE and copied to the new table will be set to TOMBSTONE. If the copying and the get race, the copy could see a null and return the null, even though it should instead begin looking in the next table. It's a small race, but it's there.

    It's also less efficient to reprobe up to reprobe_limit on larger tables, but what's a few extra cycles among friends ;-).

    opened by rescrv 5
Owner
BMC TrueSight Pulse (formerly Boundary)
BMC TrueSight Pulse (formerly Boundary)
A high performance caching library for Java

Caffeine is a high performance, near optimal caching library. For more details, see our user's guide and browse the API docs for the latest release. C

Ben Manes 13k Jan 5, 2023
Table-Computing (Simplified as TC) is a distributed light weighted, high performance and low latency stream processing and data analysis framework. Milliseconds latency and 10+ times faster than Flink for complicated use cases.

Table-Computing Welcome to the Table-Computing GitHub. Table-Computing (Simplified as TC) is a distributed light weighted, high performance and low la

Alibaba 34 Oct 14, 2022
SWE5003 - Achitecting Real Time Systems for Data Processing - Code Base

ARTS2022 SWE5003 - Achitecting Real Time Systems for Data Processing (ISS NUS Offering) - Code Base This module is part of the ISS MTech Graduate Cert

Suria R Asai 5 Apr 2, 2022
High Performance data structures and utility methods for Java

Agrona Agrona provides a library of data structures and utility methods that are a common need when building high-performance applications in Java. Ma

Real Logic 2.5k Jan 5, 2023
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
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
Simple Binary Encoding (SBE) - High Performance Message Codec

Simple Binary Encoding (SBE) SBE is an OSI layer 6 presentation for encoding and decoding binary application messages for low-latency financial applic

Real Logic 2.8k Dec 28, 2022
A Java library for quickly and efficiently parsing and writing UUIDs

fast-uuid fast-uuid is a Java library for quickly and efficiently parsing and writing UUIDs. It yields the most dramatic performance gains when compar

Jon Chambers 142 Jan 1, 2023
LWJGL is a Java library that enables cross-platform access to popular native APIs useful in the development of graphics (OpenGL, Vulkan), audio (OpenAL), parallel computing (OpenCL, CUDA) and XR (OpenVR, LibOVR) applications.

LWJGL - Lightweight Java Game Library 3 LWJGL (https://www.lwjgl.org) is a Java library that enables cross-platform access to popular native APIs usef

Lightweight Java Game Library 4k Dec 29, 2022
A modern I/O library for Android, Kotlin, and Java.

Okio See the project website for documentation and APIs. Okio is a library that complements java.io and java.nio to make it much easier to access, sto

Square 8.2k Dec 31, 2022
RxJava – Reactive Extensions for the JVM – a library for composing asynchronous and event-based programs using observable sequences for the Java VM.

RxJava: Reactive Extensions for the JVM RxJava is a Java VM implementation of Reactive Extensions: a library for composing asynchronous and event-base

ReactiveX 46.7k Dec 30, 2022
Jalgorithm is an open-source Java library which has implemented various algorithms and data structure

We loved Java and algorithms, so We made Jalgorithm ❤ Jalgorithm is an open-source Java library which has implemented various algorithms and data stru

Muhammad Karbalaee 35 Dec 15, 2022
A Primitive Collection library that reduces memory usage and improves performance

Primitive-Collections This is a Simple Primitive Collections Library i started as a hobby Project. It is based on Java's Collection Library and FastUt

Speiger 26 Dec 25, 2022
Java port of a concurrent trie hash map implementation from the Scala collections library

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

null 147 Oct 31, 2022
Java library for the HyperLogLog algorithm

java-hll A Java implementation of HyperLogLog whose goal is to be storage-compatible with other similar offerings from Aggregate Knowledge. NOTE: This

Aggregate Knowledge (a Neustar service) 296 Dec 30, 2022
A simple integer compression library in Java

JavaFastPFOR: A simple integer compression library in Java License This code is released under the Apache License Version 2.0 http://www.apache.org/li

Daniel Lemire 487 Dec 30, 2022
Library for creating In-memory circular buffers that use direct ByteBuffers to minimize GC overhead

Overview This project aims at creating a simple efficient building block for "Big Data" libraries, applications and frameworks; thing that can be used

Tatu Saloranta 132 Jul 28, 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
Reactive Streams Utilities - Future standard utilities library for Reactive Streams.

Reactive Streams Utilities This is an exploration of what a utilities library for Reactive Streams in the JDK might look like. Glossary: A short gloss

Lightbend 61 May 27, 2021