hetero-dict

Fast heterogeneous data structures

Latest on Hackage:0.1.1.0

This package is not currently in any snapshots. If you're interested in using it, we recommend adding it to Stackage Nightly. Doing so will make builds more reliable, and allow stackage.org to host generated Haddocks.

MIT licensed by Hirotomo Moriwaki, Winterland
Maintained by drkoster@qq.com

hetero-dict: fast heterogeneous data structures

Hackage Travis-CI

This package provide two flavor fast and easy to use heterogeneous data structures:

  1. Dict which use boxed array, it's read-only with O(1) get.

  2. DynDict which use linked-list(see module document for details).

Features simple api, good performance and good error message, Show and From/ToJSON instances are provided.

Example

> :set -XDataKinds -XQuasiQuotes
> :m + Data.Hetero.Dict
> let d = mkDict . add [key|foo|] 12 . add [key|bar|] "baz" $ emptyStore
> :t d
d :: Num v => Dict '["foo" ':= v, "bar" ':= [Char]]
> get [key|foo|] d
12
> get [key|bar|] d
"baz"
> get [key|qux|] d
 • Couldn't match type ‘'Index i1’ with ‘'NotFoundKey "qux"’
 ...
> :set -XDataKinds -XQuasiQuotes
> :m + Data.Hetero.DynDict
> let d =  add [key|foo|] 12 . add [key|bar|] "baz" $ empty
> get [key|foo|] d
12
> get [key|bar|] d
"baz"
> let d' = set [key|foo|] 13 d
> get [key|foo|] d'
13

Benchmark

We use hvect and vinyl as references.

benchmarking n = 3/Index Dict
time                 8.656 ns   (8.396 ns .. 9.040 ns)
                     0.987 R²   (0.964 R² .. 0.999 R²)
mean                 8.784 ns   (8.503 ns .. 9.318 ns)
std dev              1.322 ns   (767.5 ps .. 2.059 ns)
variance introduced by outliers: 97% (severely inflated)

benchmarking n = 3/Index DynDict
time                 6.400 ns   (6.340 ns .. 6.467 ns)
                     0.999 R²   (0.999 R² .. 1.000 R²)
mean                 6.394 ns   (6.348 ns .. 6.454 ns)
std dev              183.8 ps   (153.3 ps .. 230.6 ps)
variance introduced by outliers: 49% (moderately inflated)

benchmarking n = 3/Index HVect
time                 14.12 ns   (13.99 ns .. 14.25 ns)
                     0.999 R²   (0.999 R² .. 1.000 R²)
mean                 14.09 ns   (13.95 ns .. 14.25 ns)
std dev              520.1 ps   (445.4 ps .. 608.7 ps)
variance introduced by outliers: 60% (severely inflated)

benchmarking n = 3/Index Vinyl
time                 6.735 ns   (6.635 ns .. 6.849 ns)
                     0.999 R²   (0.998 R² .. 1.000 R²)
mean                 6.706 ns   (6.656 ns .. 6.763 ns)
std dev              186.4 ps   (142.7 ps .. 252.2 ps)
variance introduced by outliers: 47% (moderately inflated)

benchmarking n = 15/Index Dict
time                 9.482 ns   (9.395 ns .. 9.564 ns)
                     0.999 R²   (0.999 R² .. 1.000 R²)
mean                 9.460 ns   (9.387 ns .. 9.529 ns)
std dev              252.6 ps   (212.2 ps .. 328.3 ps)
variance introduced by outliers: 44% (moderately inflated)

benchmarking n = 15/Index DynDict
time                 10.66 ns   (10.47 ns .. 10.94 ns)
                     0.998 R²   (0.996 R² .. 1.000 R²)
mean                 10.52 ns   (10.43 ns .. 10.65 ns)
std dev              389.0 ps   (286.7 ps .. 575.8 ps)
variance introduced by outliers: 61% (severely inflated)

benchmarking n = 15/Index HVect
time                 14.35 ns   (14.24 ns .. 14.46 ns)
                     0.999 R²   (0.999 R² .. 1.000 R²)
mean                 14.35 ns   (14.20 ns .. 14.51 ns)
std dev              513.6 ps   (395.2 ps .. 693.4 ps)
variance introduced by outliers: 59% (severely inflated)

benchmarking n = 15/Index Vinyl
time                 11.62 ns   (11.47 ns .. 11.75 ns)
                     0.999 R²   (0.999 R² .. 0.999 R²)
mean                 11.63 ns   (11.52 ns .. 11.74 ns)
std dev              373.0 ps   (314.5 ps .. 452.0 ps)
variance introduced by outliers: 54% (severely inflated)

benchmarking n = 15/Modify DynDict
time                 10.30 ns   (10.13 ns .. 10.50 ns)
                     0.998 R²   (0.997 R² .. 0.999 R²)
mean                 10.26 ns   (10.18 ns .. 10.38 ns)
std dev              335.2 ps   (260.3 ps .. 427.1 ps)
variance introduced by outliers: 55% (severely inflated)

benchmarking n = 15/Modify Vinyl
time                 11.74 ns   (11.60 ns .. 11.86 ns)
                     0.999 R²   (0.999 R² .. 0.999 R²)
mean                 11.67 ns   (11.55 ns .. 11.79 ns)
std dev              398.9 ps   (330.5 ps .. 487.9 ps)
variance introduced by outliers: 56% (severely inflated)

Changes

Revision history for hetero-dict

0.1.1.0 -- 2016-05-31

  • Change DynDict's implementation to linked-list.

  • add From/ToJSON instance to DynDict.

0.1.0.1 -- 2016-05-31

  • fix DynDict's Show instance.

0.1.0.0 -- 2016-05-31

  • First version. extract from web-routing, drop GHC 7.6 support.
comments powered byDisqus