A gulp of low latency Java

Last update: Oct 31, 2022

Overview

SmoothieMap

SmoothieMap is a Map implementation for Java with the lowest memory usage and absence of rehash latency spikes. Under the hood, it is a version of extendible hashing with 48-slot mini segments.

This project also includes a proof-of-concept implementation of SwissTable algorithm in Java: see SwissTable.java.

See this post for a more detailed introduction, performance and memory comparisons, etc.

Usage

Maven:

<dependency>
  <groupId>io.timeandspace</groupId>
  <artifactId>smoothie-map</artifactId>
  <version>2.0.2</version>
</dependency>

Then, in Java:

Map<String, String> myMap = SmoothieMap.<String, String>newBuilder().build();

See Javadocs.

Comments

java.lang.ClassNotFoundException: net.openhft.smoothie.Segment60

  @Bean(name = "mapInMemory")
    public Map<CharSequence, CharSequence> mapInMemory() {
        return new SmoothieMap<>(1_0000_0000L);
    }

。。。。。。 mapInMemory.put(lines[0], lines[1]); 。。。。。。 CharSequence value = mapInMemory.get((CharSequence) key);

org.springframework.beans.factory.BeanCreationException: Error creating bean with name 'initAction': Injection of resource dependencies failed; nested exception is org.springframework.beans.factory.BeanCreationException: Error creating bean with name 'mapInMemory' defined in class path resource [com/best/config/Config.class]: Instantiation of bean failed; nested exception is org.springframework.beans.factory.BeanDefinitionStoreException: Factory method [public java.util.Map com.best.config.Config.mapInMemory()] threw exception; nested exception is java.lang.RuntimeException: java.lang.ClassNotFoundException: net.openhft.smoothie.Segment60
    at org.springframework.context.annotation.CommonAnnotationBeanPostProcessor.postProcessPropertyValues(CommonAnnotationBeanPostProcessor.java:308)
    at org.springframework.beans.factory.support.AbstractAutowireCapableBeanFactory.populateBean(AbstractAutowireCapableBeanFactory.java:1185)
    at org.springframework.beans.factory.support.AbstractAutowireCapableBeanFactory.doCreateBean(AbstractAutowireCapableBeanFactory.java:537)
    at org.springframework.beans.factory.support.AbstractAutowireCapableBeanFactory.createBean(AbstractAutowireCapableBeanFactory.java:475)
    at org.springframework.beans.factory.support.AbstractBeanFactory$1.getObject(AbstractBeanFactory.java:304)
    at org.springframework.beans.factory.support.DefaultSingletonBeanRegistry.getSingleton(DefaultSingletonBeanRegistry.java:228)
    at org.springframework.beans.factory.support.AbstractBeanFactory.doGetBean(AbstractBeanFactory.java:300)
    at org.springframework.beans.factory.support.AbstractBeanFactory.getBean(AbstractBeanFactory.java:195)
    at org.springframework.beans.factory.support.DefaultListableBeanFactory.preInstantiateSingletons(DefaultListableBeanFactory.java:703)
    at org.springframework.context.support.AbstractApplicationContext.finishBeanFactoryInitialization(AbstractApplicationContext.java:760)
    at org.springframework.context.support.AbstractApplicationContext.refresh(AbstractApplicationContext.java:482)
    at org.springframework.boot.context.embedded.EmbeddedWebApplicationContext.refresh(EmbeddedWebApplicationContext.java:120)
    at org.springframework.boot.SpringApplication.refresh(SpringApplication.java:683)
    at org.springframework.boot.SpringApplication.run(SpringApplication.java:313)
    at org.springframework.boot.builder.SpringApplicationBuilder.run(SpringApplicationBuilder.java:142)
    at org.springframework.boot.context.web.SpringBootServletInitializer.createRootApplicationContext(SpringBootServletInitializer.java:89)
    at org.springframework.boot.context.web.SpringBootServletInitializer.onStartup(SpringBootServletInitializer.java:51)
    at org.springframework.web.SpringServletContainerInitializer.onStartup(SpringServletContainerInitializer.java:175)
    at org.apache.catalina.core.StandardContext.startInternal(StandardContext.java:5580)
    at org.apache.catalina.util.LifecycleBase.start(LifecycleBase.java:150)
    at org.apache.catalina.core.ContainerBase.addChildInternal(ContainerBase.java:901)
    at org.apache.catalina.core.ContainerBase.addChild(ContainerBase.java:877)
    at org.apache.catalina.core.StandardHost.addChild(StandardHost.java:652)
    at org.apache.catalina.startup.HostConfig.deployWAR(HostConfig.java:1095)
    at org.apache.catalina.startup.HostConfig$DeployWar.run(HostConfig.java:1957)
    at java.util.concurrent.Executors$RunnableAdapter.call(Executors.java:511)
    at java.util.concurrent.FutureTask.run(FutureTask.java:266)
    at java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1142)
    at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:617)
    at java.lang.Thread.run(Thread.java:745)

opened by qixiaobo 5

Calling clear() throws IllegalArgumentException

On calling clear() the below exception is thrown:

Exception in thread "main" java.lang.IllegalArgumentException
	at java.base/jdk.internal.misc.Unsafe.invalidInput(Unsafe.java:437)
	at java.base/jdk.internal.misc.Unsafe.checkPrimitiveArray(Unsafe.java:557)
	at java.base/jdk.internal.misc.Unsafe.checkPrimitivePointer(Unsafe.java:576)
	at java.base/jdk.internal.misc.Unsafe.setMemoryChecks(Unsafe.java:747)
	at java.base/jdk.internal.misc.Unsafe.setMemory(Unsafe.java:718)
	at jdk.unsupported/sun.misc.Unsafe.setMemory(Unsafe.java:527)
	at net.openhft.smoothie.Segment.clear(Segment.java:507)
	at net.openhft.smoothie.SmoothieMap.clear(SmoothieMap.java:1244)
	at Main.main(Main.java:11)

The below code can easily reproduce the issue. I am using OpenJDK 9.0.4.

import net.openhft.smoothie.SmoothieMap;

import java.util.Map;
import java.util.Optional;

public class Main {

    public static void main(String[] args) {
        Map<String, Optional<String>> map = new SmoothieMap<>(10);
        map.put("Hello", Optional.of("World!"));
        map.clear();
    }
}

Could someone please take a look into this?

opened by rishabh9 3

java.lang.ClassCastException: net.openhft.smoothie.Segment63 cannot be cast to net.openhft.smoothie.Segment

I am getting the following exception when I am running a unit test. Any ideas?

java.lang.ClassCastException: net.openhft.smoothie.Segment63 cannot be cast to net.openhft.smoothie.Segment at net.openhft.smoothie.SmoothieMap.makeSegment(SmoothieMap.java:589) at net.openhft.smoothie.SmoothieMap.initSegments(SmoothieMap.java:446) at net.openhft.smoothie.SmoothieMap.(SmoothieMap.java:429) at net.openhft.smoothie.SmoothieMap.(SmoothieMap.java:411)

opened by noahtaylor 3
ConcurrentModificationException on remove()
Experiencing rare CMEs on map.remove(object) with version 2.0.1 after upgrading from 1.3 The map is only within the scope of a single thread and is not being iterated.

I've added a shared lock for all put/remove/contains operations on the map but was still getting CME.

I'm making a large number of put, remove, and contains operations in a small time frame (thousands of calls in a few ms), which may be what's causing it.

Below is the exception. I'll pull up a snippet for reproducing this issue once I get the chance. The test cases I made was not able to reproduce this issue. I may have to create a subset of my original data set for this.

Using jdk1.8.0_231

Exception in thread "JavaFX Application Thread" java.util.ConcurrentModificationException at io.timeandspace.smoothie.SmoothieMap.checkModCountOrThrowCme(SmoothieMap.java:1242) at io.timeandspace.smoothie.SmoothieMap.tryShrink3(SmoothieMap.java:3771) at io.timeandspace.smoothie.SmoothieMap.tryShrink2(SmoothieMap.java:3674) at io.timeandspace.smoothie.SmoothieMap.tryShrink1(SmoothieMap.java:3632) at io.timeandspace.smoothie.SmoothieMap.removeAtSlot(SmoothieMap.java:3575) at io.timeandspace.smoothie.SmoothieMap.removeImpl(SmoothieMap.java:1935) at io.timeandspace.smoothie.SmoothieMap.remove(SmoothieMap.java:1389)
opened by itsdax 2
Keys collision by 30 lowest bits limitation

Hi,

I am just wondering whether or not the 30 lowest bit keys collision limitation is no-go for a real production usage? I cannot imagine that we deploy code which can anytime run into an illegal state exception without us having any chance to fix it. Whatever 'salt' we can add to key hash codes we still cannot guarantee that keys won't collide at 30 lowest bits. I understand that the probability is very low as the collision is limited to a single segment only but the Smoothie Map code has very explicit termination by throwing the illegal state exception.

Isn't there an option to somehow re-shake the data to get rid of the segment collision even with the put operation cost increase to O(N)?

Regards, Michal
wontfix

opened by frajt 1
squid:S1213 - The members of an interface declaration or class should…

This pull request is focused on resolving occurrence of Sonar rule squid:S1213 - The members of an interface declaration or class should appear in a pre-defined order. You can find more information about the issue here: https://dev.eclipse.org/sonar/rules/show/squid:S1213 Please let me know if you have any questions. George Kankava… appear in a pre-defined order

opened by georgekankava 1

JDK 16: AssertionError: expected: 8, actual: -12

Dependency:

        <dependency>
            <groupId>io.timeandspace</groupId>
            <artifactId>smoothie-map</artifactId>
            <version>2.0.2</version>
        </dependency>

Code:

import io.timeandspace.smoothie.SmoothieMap;

public class Main {

    public static void main(String[] args) {
        SmoothieMap.newBuilder().build();
    }

}

Command:

/Users/me/Library/Java/JavaVirtualMachines/openjdk-16.0.1/Contents/Home/bin/java --add-opens java.base/java.util=ALL-UNNAMED --add-opens java.base/java.lang=ALL-UNNAMED -Dfile.encoding=UTF-8 -classpath /Users/me/projects/HelloJava/target/classes:/Users/me/.m2/repository/io/timeandspace/smoothie-map/2.0.2/smoothie-map-2.0.2.jar:/Users/me/.m2/repository/io/timeandspace/jpsg-core/1.4/jpsg-core-1.4.jar:/Users/me/.m2/repository/org/checkerframework/checker-qual/2.11.1/checker-qual-2.11.1.jar Main

Error:

Exception in thread "main" java.lang.AssertionError: expected: 8, actual: -12
	at io.timeandspace.smoothie.Utils.verifyEqual(Utils.java:63)
	at io.timeandspace.smoothie.InterleavedSegments$FullCapacitySegment.<clinit>(InterleavedSegments.java:605)
	at io.timeandspace.smoothie.InterleavedSegments.allocateSegment(InterleavedSegments.java:2150)
	at io.timeandspace.smoothie.InterleavedSegments.allocateNewSegmentWithoutSettingBitSetAndSet(InterleavedSegments.java:2130)
	at io.timeandspace.smoothie.InterleavedSegments.createNewSegment(InterleavedSegments.java:2137)
	at io.timeandspace.smoothie.SmoothieMap.<clinit>(SmoothieMap.java:291)
	at Main.main(Main.java:6)

opened by itsdax 0

ConcurrentModificationException on get

[02:38:42] [Iris Generator 5/WARN]: java.util.ConcurrentModificationException
[02:38:42] [Iris Generator 5/WARN]: 	at io.timeandspace.smoothie.Utils.nonNullOrThrowCme(Utils.java:89)
[02:38:42] [Iris Generator 5/WARN]: 	at io.timeandspace.smoothie.InflatedSegmentQueryContext$Node.equals(InflatedSegmentQueryContext.java:792)
[02:38:42] [Iris Generator 5/WARN]: 	at java.util.HashMap$TreeNode.find(HashMap.java:1867)
[02:38:42] [Iris Generator 5/WARN]: 	at java.util.HashMap$TreeNode.find(HashMap.java:1877)
[02:38:42] [Iris Generator 5/WARN]: 	at java.util.HashMap$TreeNode.find(HashMap.java:1877)
[02:38:42] [Iris Generator 5/WARN]: 	at java.util.HashMap$TreeNode.getTreeNode(HashMap.java:1889)
[02:38:42] [Iris Generator 5/WARN]: 	at java.util.HashMap.getNode(HashMap.java:576)
[02:38:42] [Iris Generator 5/WARN]: 	at java.util.HashMap.get(HashMap.java:557)
[02:38:42] [Iris Generator 5/WARN]: 	at io.timeandspace.smoothie.InflatedSegmentQueryContext.get(InflatedSegmentQueryContext.java:226)
[02:38:42] [Iris Generator 5/WARN]: 	at io.timeandspace.smoothie.SmoothieMap$InflatedSegment.get(SmoothieMap.java:6093)
[02:38:42] [Iris Generator 5/WARN]: 	at io.timeandspace.smoothie.SmoothieMap.getInflated(SmoothieMap.java:1733)
[02:38:42] [Iris Generator 5/WARN]: 	at io.timeandspace.smoothie.SmoothieMap.get(SmoothieMap.java:1607)
[02:38:42] [Iris Generator 5/WARN]: 	at com.volmit.iris.object.IrisObject.place(IrisObject.java:517)

The last on the stack is simply invoking .get(KEY) within a for loop (keyset())

opened by cyberpwnn 0

Illegal reflectice access operation

I get the following error message when I start my application:

WARNING: An illegal reflective access operation has occurred
WARNING: Illegal reflective access by io.timeandspace.smoothie.ObjectSize (file:/home/user/.gradle/caches/modules-2/files-2.1/io.timeandspace/smoothie-map/2.0.2/e51889ef2e0a69f95e4203afc68c01a8b75a1380/smoothie-map-2.0.2.jar) to field java.util.HashMap.table
WARNING: Please consider reporting this to the maintainers of io.timeandspace.smoothie.ObjectSize
WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations
WARNING: All illegal access operations will be denied in a future release

I am using Java HotSpot(TM) 64-Bit Server VM, 14.0.1+7.

Application behaves correctly, but unfortunately this kind of error is not suppressible. Any way you could get rid of this?

opened by Tschigger 0

Releases(2.0.2)

2.0.2(Dec 29, 2019)
Fixed a bug in SmoothieMap shrinking logic (#8)

Download JAR: https://repo1.maven.org/maven2/io/timeandspace/smoothie-map/2.0.2/smoothie-map-2.0.2.jar
Source code(tar.gz)
Source code(zip)
2.0.1(Oct 9, 2019)

See the summary of changes in SmoothieMap 2 vs. SmoothieMap 1.x here.

Moved to io.timeandspace groupId, new SmoothieMapBuilider API.

Download JAR: https://repo1.maven.org/maven2/io/timeandspace/smoothie-map/2.0.1/smoothie-map-2.0.1.jar
Source code(tar.gz)
Source code(zip)
smoothie-map-1.3(Mar 31, 2016)
Replace source code generation with bytecode generation, add dependency to org.ow2.asm:asm

Download JAR: https://oss.sonatype.org/content/groups/public/net/openhft/smoothie-map/1.3/smoothie-map-1.3.jar
Source code(tar.gz)
Source code(zip)
smoothie-map-1.2(Mar 30, 2016)
Removed dependency to net.openhft:compiler

Improvements addressing runtime code generation in container and OSGi enviroments

Download JAR: https://oss.sonatype.org/content/groups/public/net/openhft/smoothie-map/1.2/smoothie-map-1.2.jar
Source code(tar.gz)
Source code(zip)
smoothie-map-1.1(Dec 2, 2015)
Fixed a bug

Reduced worst-case footprint of the data structure

Made com.intellij:annotations dependency optional

Download JAR: https://oss.sonatype.org/content/groups/public/net/openhft/smoothie-map/1.1/smoothie-map-1.1.jar
Source code(tar.gz)
Source code(zip)
smoothie-map-1.0(Sep 11, 2015)

Initial release with a single public class SmoothieMap (not synchronized Map implementation)

Download JAR: https://oss.sonatype.org/content/groups/public/net/openhft/smoothie-map/1.0/smoothie-map-1.0.jar
Source code(tar.gz)
Source code(zip)

Owner

GitHub

Lightning Memory Database (LMDB) for Java: a low latency, transactional, sorted, embedded, key-value store

LMDB for Java LMDB offers: Transactions (full ACID semantics) Ordered keys (enabling very fast cursor-based iteration) Memory-mapped files (enabling o

680 Dec 23, 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

2.5k Jan 5, 2023

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

71 Nov 2, 2022

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

13k Jan 5, 2023

Chronicle Bytes has a similar purpose to Java NIO's ByteBuffer with many extensions

Chronicle-Bytes Chronicle-Bytes Chronicle Bytes contains all the low level memory access wrappers. It is built on Chronicle Core’s direct memory and O

334 Jan 1, 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

161 Dec 30, 2022

An advanced, but easy to use, platform for writing functional applications in Java 8.

Getting Cyclops X (10) The latest version is cyclops:10.4.0 Stackoverflow tag cyclops-react Documentation (work in progress for Cyclops X) Integration

1.3k Dec 29, 2022

Eclipse Collections is a collections framework for Java with optimized data structures and a rich, functional and fluent API.

2.1k Dec 29, 2022

External-Memory Sorting in Java

Externalsortinginjava External-Memory Sorting in Java: useful to sort very large files using multiple cores and an external-memory algorithm. The vers

235 Dec 29, 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

142 Jan 1, 2023

Geohash utitlies in java

geo Java utility methods for geohashing. Status: production, available on Maven Central Maven site reports are here including javadoc. Add this to you

386 Jan 1, 2023

Hollow is a java library and toolset for disseminating in-memory datasets from a single producer to many consumers for high performance read-only access.

Hollow Hollow is a java library and toolset for disseminating in-memory datasets from a single producer to many consumers for high performance read-on

1.1k Dec 25, 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.

890 Dec 28, 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

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

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

487 Dec 30, 2022

jOOλ - The Missing Parts in Java 8 jOOλ improves the JDK libraries in areas where the Expert Group's focus was elsewhere. It adds tuple support, function support, and a lot of additional functionality around sequential Streams. The JDK 8's main efforts (default methods, lambdas, and the Stream API) were focused around maintaining backwards compatibility and implementing a functional API for parallelism.

jOOλ jOOλ is part of the jOOQ series (along with jOOQ, jOOX, jOOR, jOOU) providing some useful extensions to Java 8 lambdas. It contains these classes

2k Dec 31, 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

967 Nov 14, 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

1.4k Dec 30, 2022