An inline SIMD accelerated hashmap designed for small amount of data.

Overview

Small-Map

Crates.io

An inline SIMD accelerated hashmap designed for small amount of data.

Usage

use small_map::SmallMap;
// Don't worry about the 16 here.
// When the size grows, it will automatically switch to heap impl.
type MySmallMap<K, V> = SmallMap<16, K, V>;

let mut map = MySmallMap::new();
map.insert(1_u8, 2_u8);
assert_eq!(*map.get(&1).unwrap(), 2);

Usually you can use this map for short lifetime and small key/values, for example, http or RPC headers.

You can use it like other normal hashmaps without worrying about its size.

Performance

The performance of SmallMap depends on the capacity, Key/Value size and operation scenario.

It is recommended to set the size to 16(or 32) because with SSE2 it can search 16 items within a single instruction. It is only recommended to use SmallMap for small Key/Values, such as numbers and strings.

benchmark result

Here is a benchmark result with size 16 and u8 key/value. This benchmark was conducted on an Intel Xeon.

Note

Comparing to HashBrown, it saves 25%~43% CPU in test scenario; and comparing to std HashMap, it saves 25%~54% CPU in test scenario.

How it Works

Like SmallVec, for HashMap with a small amount of data, inlining the data can avoid heap allocation overhead and improve performance.

SmallMap inlines a fixed-size sequential structure, and refers to the design of swisstable to additionally store the hash of the data in Group units, and uses SIMD to accelerate the search.

When the data capacity exceeds the inline capacity, the data will be transferred to HashMap implemented by hashbrown.

Credit

Hashbrown is heavily referenced to and copied by this project, and is a very elegant and efficient implementation.

You might also like...
Stack heap flexible string designed to improve performance for Rust

flexible-string A stack heap flexible string designed to improve performance. FlexibleString was first implemented in spdlog-rs crate, which improved

A set of Zero Knowledge modules, written in Rust and designed to be used in other system programming environments.

Zerokit A set of Zero Knowledge modules, written in Rust and designed to be used in other system programming environments. Initial scope Focus on RLN

The utility is designed to check the availability of peers and automatically update them in the Yggdrasil configuration file, as well as using the admin API - addPeer method.

Yggrasil network peers checker / updater The utility is designed to check the availability of peers and automatically update them in the Yggdrasil con

An actors library for Rust and Tokio designed to work with async / await message handlers out of the box.

Akt An actors framework for Rust and Tokio. It is heavily inspired by Actix and right now it has very similar look and feel. The main difference is th

The Fast Vector Similarity Library is designed to provide efficient computation of various similarity measures between vectors.
The Fast Vector Similarity Library is designed to provide efficient computation of various similarity measures between vectors.

Fast Vector Similarity Library Introduction The Fast Vector Similarity Library is designed to provide efficient computation of various similarity meas

CloudLLM is a Rust library designed to seamlessly bridge applications with remote Language Learning Models (LLMs) across various platforms.
CloudLLM is a Rust library designed to seamlessly bridge applications with remote Language Learning Models (LLMs) across various platforms.

CloudLLM CloudLLM is a Rust library designed to seamlessly bridge applications with remote Language Learning Models (LLMs) across various platforms. W

TodoX is a sophisticated Rust-based application designed to facilitate seamless todo management.

Rust Todo List App is a command-line tool written in Rust that allows users to manage their tasks efficiently. Whether you need to add, mark as done, edit, or clear tasks from your todo list, this app provides essential functionalities to streamline your task management process. Additionally, I have integrated sqlite3 using the rusqlite crate. The database stores the data and will persist indefinitely until you manually delete it.

:crab: Small exercises to get you used to reading and writing Rust code!
:crab: Small exercises to get you used to reading and writing Rust code!

rustlings 🦀 ❤️ Greetings and welcome to rustlings. This project contains small exercises to get you used to reading and writing Rust code. This inclu

Fegeya Elitebuild, small, powerful build system. Written in Rust.
Fegeya Elitebuild, small, powerful build system. Written in Rust.

Fegeya Elitebuild Small, powerful, work-in-progress build system. Written in Rust. Features: No functions (all are built-ins) All variables are global

Owner
ihc童鞋@提不起劲
ihc童鞋@提不起劲
memchr vs stringzilla - up to 7x throughput difference between two SIMD-accelerated substring search libraries in Rust

memchr vs stringzilla Rust Substring Search Benchmarks Substring search is one of the most common operations in text processing, and one of the slowes

Ash Vardanian 38 Mar 5, 2024
A HashMap/Vector hybrid: efficient, ordered key-value data storage in Rust.

hashvec A HashVec is a hash map / dictionary whose key-value pairs are stored (and can be iterated over) in a fixed order, by default the order in whi

Skye Terran 2 May 16, 2022
A lock-free, partially wait-free, eventually consistent, concurrent hashmap.

A lock-free, partially wait-free, eventually consistent, concurrent hashmap. This map implementation allows reads to always be wait-free on certain pl

Ian Smith 216 Nov 18, 2022
A simpler and 5x faster alternative to HashMap in Rust, which doesn't use hashing and doesn't use heap

At least 5x faster alternative of HashMap, for very small maps. It is also faster than FxHashMap, hashbrown, ArrayMap, and nohash-hasher. The smaller

Yegor Bugayenko 12 Apr 19, 2023
Support SIMD low-memory overhead and high-performance adaptive radix tree.

Artful Artful is an adaptive radix tree library for Rust. At a high-level, it's like a BTreeMap. It is based on the implementation of paper, see The A

future 3 Sep 7, 2022
Rust library for hardware accelerated drawing of 2D shapes, images, and text, with an easy to use API.

Speedy2D Hardware-accelerated drawing of shapes, images, and text, with an easy to use API. Speedy2D aims to be: The simplest Rust API for creating a

null 223 Dec 26, 2022
A special rope, designed to work with any data type that is not String

AnyRope AnyRope is an arbitrary data type rope for Rust, designed for similar operations that a rope would do, but targeted at data types that are not

ahoyiski 27 Mar 22, 2023
An expression based data notation, aimed at transpiling itself to any cascaded data notation.

Lala An expression oriented data notation, aimed at transpiling itself to any cascaded data notation. Lala is separated into three components: Nana, L

null 37 Mar 9, 2022
Mote is a systems-programming language designed to be practical, performant, and simple.

Mote NOTE: this following lists the goals for what Mote is supposed to be. It does not promise that any of the features here will be accomplished or a

The Mote Programming Language 14 Jul 28, 2021
Portable linked-list allocator designed for baremetal systems

Palloc Portable linked-list allocator for embedded / baremetal systems. Using the crate Include this in the [dependencies] section of Cargo.toml pallo

Pietro 3 Jan 11, 2022