A simpler and 5x faster alternative to HashMap in Rust, which doesn't use hashing and doesn't use heap

Related tags

Learning Resources rust performance data-structures hashmap fast-map-matching
Overview

cargo crates.io codecov Hits-of-Code Lines of code License docs.rs

At least 5x faster alternative of HashMap, for very small maps. It is also faster than FxHashMap, hashbrown, ArrayMap, and nohash-hasher. The smaller the map, the higher the performance. When the map contains more than 50 keys, it is better to use the standard HashMap, since the performance of micromap::Map may start to degrade.

The only important restriction is that both key and value must implement the Copy trait.

WELCOME: Not all functions that a user expects to have in a map are implemented. I will appreciate if you contribute by implementing these missing functions.

Here is how you use it:

use micromap::Map;
let mut m : Map<u64, &str, 10> = Map::new(); // allocation on stack
m.insert(1, "foo");
m.insert(2, "bar");
assert_eq!(2, m.len());

Pay attention, here the map is created with an extra generic argument 10. This is the total size of the map, which is allocated on stack when ::new() is called. Unlike HashMap, the Map doesn't use heap at all. If more than ten keys will be added to the map, it will panic.

Read the API documentation. The struct micromap::Map is designed as closely similar to std::collections::HashMap as possible.

How to Contribute

First, install Rust and then:

$ cargo test -vv

If everything goes well, fork repository, make changes, send us a pull request. We will review your changes and apply them to the master branch shortly, provided they don't violate our quality standards. To avoid frustration, before sending us your pull request please run cargo test again. Also, run cargo fmt and cargo clippy.

Comments
  • Update Rust crate serde to 1.0.160

    Update Rust crate serde to 1.0.160

    Mend Renovate

    This PR contains the following updates:

    | Package | Type | Update | Change | |---|---|---|---| | serde (source) | dependencies | patch | 1.0.159 -> 1.0.160 |

    Release Notes

    serde-rs/serde

    v1.0.160

    Compare Source

    Configuration

    📅 Schedule: Branch creation - At any time (no schedule defined), Automerge - At any time (no schedule defined).

    🚦 Automerge: Disabled by config. Please merge this manually once you are satisfied.

    ♻ Rebasing: Whenever PR becomes conflicted, or you tick the rebase/retry checkbox.

    🔕 Ignore: Close this PR and you won't be reminded about this update again.

    • [ ] If you want to rebase/retry this PR, check this box

    This PR has been generated by Mend Renovate. View repository job log here.

    opened by renovate[bot] 2
  • Using swap deletion to maintain 'packed' array

    Using swap deletion to maintain 'packed' array

    The current implementation requires to loop over empty slots. The code could be simpler - and depending on the use case faster - if the last pair would be moved to the empty slot on deletion and empty slots would never occur in the range 0..self.next.

    For instance the implementation of len(&self) would reduce to self.next (therefore I would suggest renaming next to len if this adjustment would be made).

    enhancement 
    opened by WiebeCnossen 1
  • Optimize loops by exploiting invariant self.next <= N

    Optimize loops by exploiting invariant self.next <= N

    As self.next <= N always holds, the construction

    for i in 0..N {
  if self.next <= i { break; }

    can always be written as

    for i in 0..self.next {
    bug 
    opened by WiebeCnossen 0
  • benchmark with a graph

    benchmark with a graph

    Let's create a new GitHub Action workflow, which will (on every new tag):

    • checkout the repo
    • create a number of similar Rust CLI scripts in src/bin
    • each script will do exactly the same manipulations with a map
    • each script will use different implementations of the map (HashMap, Micromap, etc.)
    • collect the performance results into a .csv file
    • using gnuplot render a graph in SVG
    • add the results summary and a graph to README.md
    • submit a pull request
    enhancement 
    opened by yegor256 0
  • get rid of the Copy trait for K and V

    get rid of the Copy trait for K and V

    Somehow Vec and HashMap work with keys and values that don't implement Copy. We should do the same. I'm not sure exactly how this can be done, but it should be possible.

    bug 
    opened by yegor256 2
  • serde dependency should be optional

    serde dependency should be optional

    Serde dependency is not really necessary for the functionality of the crate, only adding serialization capabilities. A common practice is to make it an optional dependency (see, for example, gram-rs here and here)

    bug 
    opened by DCNick3 1
  • Map::eq() is not working as expected

    Map::eq() is not working as expected

    This test fails:

    let mut m1: Map<u8, i32, 10> = Map::new();
m1.insert(1, 42);
let mut m2: Map<u8, i32, 10> = Map::new();
m2.insert(1, 42);
assert!(m1.eq(&m2));

    I believe, it must pass. Let's fix.

    bug 
    opened by yegor256 0
Releases(0.0.4)

  • 0.0.4(Apr 17, 2023)

    See #7, release log:

    • 72b332e500335d58c76bff1a78af204ee84917c1 by @yegor256: #7 contains_key by ref
    • 605a3543468438dfce031d401cb68cb717cda60e by @yegor256: #7 clear()
    • af297648f523acdb6ff73f182aea38358e90b4ff by @yegor256: #7 optim
    • f749d654b858ad0746ac05d45ebb184e77ec1ec4 by @yegor256: #7 get by ref
    • 9dc39b46aa40dd93d5d00de3c1e42ebfb16b89b5 by @yegor256: #6 debug and display for map

    Released by Rultor 1.74.7, see build log

    Source code(tar.gz)
    Source code(zip)

  • 0.0.3(Apr 17, 2023)

    See #5, release log:

    • ac1c61464b182fef4043732586a69ef953e903d5 by @yegor256: #5 doc
    • 9945c1a491f52489ca4621e90ce9d4602f82d2aa by @yegor256: #5 remove K by ref
    • 920eb9792e6fba866ce8271fc73da3a744acfad0 by @yegor256: #5 MaybeUninit
    • 88570fcfe8aa7c2cda23fb907e7fb615559ee044 by @yegor256: #5 iterators
    • 5e0af3d15d4aee47ef58ab1b8d0897dee2f0f1c6 by @yegor256: #5 Map.next
    • 3a7f80206e7aca32d14dddf01500e6d55499b422 by @yegor256: #5 Copy trait
    • 3c4d1c3fefc3d1025df9916ba2a125302345b3de by @yegor256: #5 Copy trait
    • 8d0a274bc52f18082934cafbabe56c9ab4408eb7 by @yegor256: #4 test moved
    • 3b041dd9c1b0ecbcab2f620c0bfd5c0d37610bb9 by @yegor256: #4 more tests
    • 5a7d7130d81c2351a6453ccd71a02a0c881e178e by @yegor256: #4 doc
    • 8280198fb897e0209b97b1172318b012abe2a09c by @yegor256: #4 more tests

    Released by Rultor 1.74.7, see build log

    Source code(tar.gz)
    Source code(zip)

  • 0.0.2(Apr 16, 2023)

    See #4, release log:

    • 1dab298390337d80e15d0494b2377d39e22f5318 by @yegor256: #4 rename
    • 118fbf084eae4153cec0760366d6313cd2535f39 by @yegor256: #3 doc
    • b1e3ecd803fcd8fcfd7ada8584321835ab7b064a by @yegor256: Merge pull request #1 from yeg...

    Released by Rultor 1.74.7, see build log

    Source code(tar.gz)
    Source code(zip)

  • 0.0.1(Apr 16, 2023)

    See #3, release log:

    • 0aada40c908c2611d29c7fb0e4758dca5990a4c7 by @yegor256: #3 creds
    • 87ff5270fc3067d78efafe93b208bc34d5603481 by @yegor256: #3 more ops in the test
    • 15d28863f09c162a08e2fa9e6e149551ccf10da3 by @yegor256: #3 clippy
    • b24e6c754cdf49300efbce0c329a697a078edb5d by @yegor256: #3 doc
    • 55b97eb1dd3de3f1e033c82f4df03840ed1eb2e1 by @yegor256: #3 doc
    • 6de719a3e1d21f794d826da9298766240c51b066 by @yegor256: #3 links
    • 1a1603c16e5b8c639452e355cf387e84586c6f33 by @yegor256: #3 gha
    • d4434effb4f544b2eb5ab76d7f80292d9d4130be by @yegor256: #3 links
    • 9537b46e0273b99e1dc55004eb9b951044871acd by @yegor256: #3 doc
    • b971c09055b8585a265f0c09ed3bb0c122a5d3e1 by @yegor256: #3 typos
    • f10183825ed8ecfb2b61c8f87b89b42870f9506d by @yegor256: start

    Released by Rultor 1.74.7, see build log

    Source code(tar.gz)
    Source code(zip)
Owner
Yegor Bugayenko
Author of "Elegant Objects" book series (buy them on Amazon); architect of @objectionary; founder of @zerocracy; creator of @zold-io
Yegor Bugayenko
GitHub https://crates.io/crates/micromap
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
An inline SIMD accelerated hashmap designed for small amount of data.

Small-Map An inline SIMD accelerated hashmap designed for small amount of data. Usage use small_map::SmallMap; // Don't worry about the 16 here. // Wh

ihc童鞋@提不起劲 49 Nov 14, 2023
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

Sprite 6 Feb 9, 2022
A typemap for a set of known types optionally without heap allocation, and supporting iterating by traits

fixed_typemap docs.rs GitHub Sponsors Implements typemaps that support a lot of extra funcctionality using procedural macros. docs.rs has a lot more t

Austin Hicks 2 Dec 27, 2021
A heap allocated runtime for deeply recursive algorithms.

Reblessive A heap allocated runtime for deeply recursive algorithms. Turn your cursed recursive algorithm into a blessed heap allocated structure whic

Mees Delzenne 4 Feb 27, 2024
📈 The fastest map possible in Rust, where keys are integers and the capacity is fixed (faster than Vec!)

It is an alternative on-heap implementation of a map with keys of type usize and a fixed capacity. It works much faster than a standard HashMap becaus

Yegor Bugayenko 6 Apr 26, 2023
A faster Arc.

Trc Trc is a performant heap-allocated smart pointer for Rust that implements thread reference counting. Trc stands for: Thread Reference Counted. Trc

Eric Buehler 19 Jul 12, 2023
Code for blog post "{n} times faster than C, where n = 128"

Code for {n} times faster than C, where n = 128 Actually, n = 290 ?? Benchmark Setup Rust version: rustc 1.70.0 (90c541806 2023-05-31) Run test: cargo

Thomas Ip 9 Jul 24, 2023
Secure mTLS and gRPC backed runtime daemon. Alternative to systemd. Written in Rust.

Auraed A runtime daemon written in Rust. Designed to run as pid 1 mTLS backed gRPC API over unix domain socket Run executables Run containers Run virt

Aurae Runtime 57 Dec 22, 2022
An alternative broken buggy Nix implementation in Rust + Java (for evaluation)

An alternative broken buggy Nix implementation in Rust + Java (for evaluation)

Moritz Hedtke 1 Feb 12, 2022
A peer-reviewed collection of articles/talks/repos which teach concise, idiomatic Rust.

This repository collects resources for writing clean, idiomatic Rust code. Please bring your own. ?? Idiomatic coding means following the conventions

Matthias 4.2k Dec 30, 2022
Cogo is a high-performance library for programming stackful coroutines with which you can easily develop and maintain massive concurrent programs.

Cogo is a high-performance library for programming stackful coroutines with which you can easily develop and maintain massive concurrent programs.

co-rs 47 Nov 17, 2022
Stack-based programming language which emulates the look and feel of the 60s

Cauchemar Cauchemar is a stack-based programming language inspired by FORTH but more arcane. Emulates the look and feel of a programming language from

Yuki Langley 4 Dec 29, 2022
A Matrix bot which can generate "This Week in X" like blog posts

hebbot A Matrix bot which can help to generate periodic / recurrent summary blog posts (also known as "This Week in X"). The bot was inspired by twim-

Häcker Felix 43 Dec 17, 2022
An embedded key-value storage for learning purpose, which is based on the idea of SSTable / LSM-tree.

Nouzdb An embedded key-value storage for learning purpose, which is based on the idea of SSTable / LSM-tree. Plan Implement a memtable. Implement the

Nouzan 1 Dec 5, 2021
ArbOS operating system, to run at Layer 2 on Arbitrum chains. Also a compiler for Mini, the language in which ArbOS is written.

ArbOS and Mini compiler ArbOS is the "operating system" that runs at Layer 2 on an Arbitrum chain, to manage the chain's operation, maintain security,

Offchain Labs 88 Nov 6, 2022
A typed map which can make sure item exist.

Certain Map A typed map which can make sure item exist. What Problem Does It Solve In Rust, we often use Service abstraction for modular structure des

ihc童鞋@提不起劲 27 Jun 26, 2023
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