Giter Club home page Giter Club logo

ordnung's Introduction

Ordnung

Fast, vector-based map implementation that preserves insertion order.

  • Map is implemented as a binary tree over a Vec for storage, with only two extra words per entry for book-keeping on 64-bit architectures.
  • A fast hash function with good random distribution is used to balance the tree. Ordnung makes no guarantees that the tree will be perfectly balanced, but key lookup should be approaching O(log n) in most cases.
  • Tree traversal is always breadth-first and happens over a single continuous block of memory, which makes it cache friendly.
  • Iterating over all entries is always O(n), same as Vec<(K, V)>.
  • Removing a value uses a sentinel and is ~O(log n).
  • There are no buckets, so there is no need to re-bucket things when growing the map.

When should you use this?

  • You need to preserve insertion order of the map.
  • Iterating over the map is very performance sensitive.
  • Your average map has fewer than 100 entries.
  • You have no a priori knowledge about the final size of the map when you start creating it.

Benchmarks

  • All charts show time in ns, smaller is better.
  • All blue bars are std HashMap (SwissTable) with different hashing algorithms.
  • All benchmarks were compiled with -C target-cpu=native to take advantage of aHash.

Map construction

While insertion in Ordnung is getting progressively slower as the size of the map grows, growing a HashMap is also getting progressively slower due to re-bucketing costs.

Map construction benchmark

Map construction with preallocated memory

With preallocated memory, Ordnung is still faster for a small number of entries.

Map construction benchmark with preallocated memory

Average time to find value by key

As the size of the map doubles, Ordnung incurs a roughly constant jump in cost due to its ~O(log n) nature, however it still remains competitive with fast HashMaps.

Map find benchmark

License

This code is distributed under the terms of both the MIT license and the Apache License (Version 2.0), choose whatever works for you.

See LICENSE-APACHE and LICENSE-MIT for details.

ordnung's People

Contributors

maciejhirsz avatar licenser avatar

Watchers

James Cloos avatar

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    ๐Ÿ–– Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. ๐Ÿ“Š๐Ÿ“ˆ๐ŸŽ‰

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google โค๏ธ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.