dvanhorn @ λ-calcul.us

Based on the presentation of functional vectors in Conchon and Filliâtre, ML Workshop 2007, which in turn is based on Baker, CACM 1978.

The library provides functional vectors in two flavors: thread-safe, type disjoint, and structurally equal; or fast(er).

PLaneT Package Repository : PLaneT > dvanhorn > fector.plt

Here’s a comparison of both flavors against the random-access lists in the RaList library, the random-access lists in the Purely Functional Data Structures library, Racket’s hash tables, and a simple implementation representing vectors of X as functions in (Nat -> X). The benchmark and numbers are from Jay McCarthy and on github.


% rk bench-fvector.rkt
fec:fast: cpu: 6.45 real: 6.5 gc: 0.0 (averaged over 20 runs)
fec:slow: cpu: 8.2 real: 8.249999999999998 gc: 0.0 (averaged over 20 runs)
ralist: cpu: 18.549999999999997 real: 18.949999999999996 gc: 0.0
(averaged over 20 runs)
sbal: cpu: 19.700000000000003 real: 21.15 gc: 0.25 (averaged over 20 runs)
hasheq: cpu: 47.95000000000001 real: 48.4 gc: 2.9499999999999993
(averaged over 20 runs)
fvec: cpu: 114.45 real: 118.64999999999999 gc: 0.0 (averaged over 20 runs)
Normalized:
fec:fast: cpu: 1.00 real: 1.00 gc: inf (averaged over 20 runs)
fec:slow: cpu: 1.27 real: 1.27 gc: inf (averaged over 20 runs)
ralist: cpu: 2.88 real: 2.92 gc: inf (averaged over 20 runs)
sbal: cpu: 3.05 real: 3.25 gc: inf (averaged over 20 runs)
hasheq: cpu: 7.43 real: 7.45 gc: inf (averaged over 20 runs)
fvec: cpu: 17.74 real: 18.25 gc: inf (averaged over 20 runs)