Hector

hector is an OCaml library that offers vectors (also known as dynamic arrays, or resizeable arrays).

Installation and Usage

Type opam install hector.

In your dune file, add (libraries hector) to the description of your library or executable.

What is a Vector?

A vector is a data structure that holds a sequence of values. A vector is a mutable data structure: it can be updated. Like an array, it offers efficient random access functions, get and set. Furthermore, a vector can grow and shrink; elements can be pushed or popped at its right end.

The logical length of a vector is the length of the sequence.

Furthermore, a vector has a physical capacity. A vector's capacity is at least equal to its length, and can be greater than its length. Almost always, the capacity of a vector is the length of the data array where the vector's elements are stored. As an exception to the previous sentence, if a vector has logical length 0 then its data array can be empty, even if its capacity is nonzero.

Three Flavors of Vectors

Three main implementations of vectors are offered:

1. The module Hector.Poly offers polymorphic vectors: if elements have type 'a then a vector has type 'a vector. The signature of this module is Hector.POLYVECTOR.
2. The functor Hector.Mono.Make offers monomorphic vectors: the type of elements is fixed when this functor is applied to a module E, and a vector has type vector. The module produced by this functor has signature Hector.MONOVECTOR with type element = E.t.
3. The module Hector.Int offers integer vectors: the type of elements is int and a vector has type vector. The signature of this module is Hector.MONOVECTOR with type element = int. This module can be significantly faster than the equivalent module Hector.Mono.Make(Int).

For power users,

1. The functor Hector.Mono.OutOfArray offers monomorphic vectors. The user provides not only the type of elements, but also a set of basic operations on arrays of elements.

Words of Caution

hector's vectors are not thread-safe and do not include a protection against data races: concurrent accesses to a vector, where at least one thread attempts to modify the vector, are forbidden and can compromise memory safety (that is, they can cause a hard crash or silent memory corruption). Concurrent read accesses are safe. OCaml's Dynarray library also offers non-thread-safe vectors, and guarantees that data races cannot compromise memory safety, whereas hector does not.

hector's vectors do not include a protection against memory leaks. If a vector's capacity is greater than its length, then the logically empty slots in its data array contain stale values, which in the eyes of the garbage collector are reachable. This problem can be avoided by explicitly calling reset or fit_capacity. In contrast, OCaml's Dynarray library does guarantee the absence of memory leaks.

hector's higher-order operations do not detect an attempt to modify a vector while an operation is in progress. For example, in iter f v, the function f must not modify the vector v, but a violation of this rule is not detected by hector. In contrast, OCaml's Dynarray library detects some (albeit not all) violations of this rule at runtime.

Comparison with OCaml's Dynamic Arrays

hector's vectors are similar to those offered by OCaml's Dynarray library.

Compared with hector, OCaml's Dynarray library offers stronger guarantees: see Words of Caution above.

hector's polymorphic vectors and monomorphic vectors are generally slightly faster than OCaml's dynamic arrays, and on some operations, can be up to 2x faster. hector's integer vectors are generally significantly faster than OCaml's dynamic arrays, and on some operations, can be up to 5x faster. hector's integer vectors are not scanned by the garbage collector.

hector offers fast (but dangerous) unchecked random access operations, unsafe_get and unsafe_set, which OCaml's Dynarray library does not have.

Via unsafe_borrow, hector offers direct access to the data array, allowing direct read and write operations; OCaml's Dynarray library does not (and cannot) offer this feature.

hector's stable_sort is slightly faster than Array.stable_sort, and can be significantly faster than Array.stable_sort if the data is already sorted or almost sorted.

A few operations have different behavior in Dynarray and in hector:

1. hector's compare behaves like List.compare, not like Dynarray.compare. Dynarray.compare implements a preorder on vectors that is not is the lexicographic preorder.
2. hector allows append v v, which Dynarray forbids.
3. hector allows applying get_last to an empty vector, which Dynarray forbids.

A few operations exist in Dynarray but not in hector:

1. hector does not offer to_seq_reentrant and to_seq_rev_reentrant. This is intentional. The semantics of these operations is, in my opinion, unclear. A user who needs these operations can implement them outside hector.
2. hector does not offer capacity. This is intentional. Because hector does not guarantee that a vector's capacity is equal to the length of its data array, it might be confusing to expose the function capacity.

Several operations exist in hector but not in Dynarray:

1. sub,
2. concat,
3. fill,
4. blit,
5. sort, stable_sort, fast_sort,
6. unsafe_get,
7. unsafe_set,
8. unsafe_borrow,
9. push_array_segment,
10. iter_down,
11. find,
12. show,
13. the submodule Stack.