Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Imperative and functional finite map implementations, head to head
OCaml
tree: e4606f57ac

Fetching latest commit…

Cannot retrieve the latest commit at this time

Failed to load latest commit information.
corpora
.gitignore
OMakefile
OMakeroot
README
benchmark.ml
fasthashtbl.ml
hashtbl_hval.ml
hashtbl_hval.mli
hashtbl_mod.ml
hashtbl_mod.mli
size.ml
size.mli
ternary.ml
ternary.mli
trie_map.ml
trie_map.mli
trie_map_mod.ml

README

Several finite map implementations in OCaml, head to head.

Functional
----------

Trie_map: TST with coalesced constructor for nodes with and without values
Trie_map_mod: TST with different constructors for leaves and inner nodes with
              a value
Ternary: TST with separate constructor for nodes with and without values
         but no leaf constructor

Imperative
----------

Fasthashtbl: hash table with open addressing and double hashing
Hashtbl: the hash table from INRIA's stdlib (external chaining)
Hashtbl_mod: Hashtbl with more aggressive resizing (lower load factor)
Hashtbl_hval: Hashtbl_mod with caching of the hash value

Requirements
============
* OMake
* OCaml (any version should do)

Compiling and running
=====================

$ omake

$ ./benchmark -help

  -n N    Number of iterations (default: 3)
  -s      Show structure sizes.
  -help   Display this list of options
  --help  Display this list of options

$ ./benchmark -n 10
String set size: 98568
Target array 1: 217625
Target array 2: 86016

Fasthashtbl:
 ints
  add                                    0.18055s  (1205378 / sec)
 struct size: 11124672
  find (constant w/ overhead)            0.02775s  (36040042 / sec)
  find (constant, no overhead)           0.02312s  (43250748 / sec)
...


Something went wrong with that request. Please try again.