package base

You can search for identifiers within the package.

in-package search v0.2.0

Full standard library replacement for OCaml

Install

dune-project

Dependency

github.com Changelog MIT License Edit opam file Versions (19)

Authors

J

Jane Street Group, LLC

Maintainers

J

Jane Street developers

Sources

v0.17.3.tar.gz

md5=2100b0ed13fecf43be86ed45c5b2cc4d

sha512=628610caff7e124631870fa1e29661caac28bdfdb18750ee43b868037da3d65d6dd9023b4be7c4c52405679efb5e865a6632d95606a22b28a36636a6bf706ef3

doc/base/Base/Hash/index.html

Module `Base.Hash`Source

Sourcemodule type Full = sig ... end

Sourcemodule type S = sig ... end

Source

module F
  (Hash : S) : 
  Full
    with type hash_value = Hash.hash_value
     and type state = Hash.state
     and type seed = Hash.seed

The code of ppx_hash is agnostic to the choice of hash algorithm that is used. However, it is not currently possible to mix various choices of hash algorithms in a given code base.

We experimented with:

(a) custom hash algorithms implemented in OCaml and
(b) in C;
(c) OCaml's internal hash function (which is a custom version of Murmur3, implemented in C);
(d) siphash, a modern hash function implemented in C.

Our findings were as follows:

Implementing our own custom hash algorithms in OCaml and C yielded very little performance improvement over the (c) proposal, without providing the benefit of being a peer-reviewed, widely used hash function.

Siphash (a modern hash function with an internal state of 32 bytes) has a worse performance profile than (a,b,c) above (hashing takes more time). Since its internal state is bigger than an OCaml immediate value, one must either manage allocation of such state explicitly, or paying the cost of allocation each time a hash is computed. While being a supposedly good hash function (with good hash quality), this quality was not translated in measurable improvements in our macro benchmarks. (Also, based on the data available at the time of writing, it's unclear that other hash algorithms in this class would be more than marginally faster.)

By contrast, using the internal combinators of OCaml hash function means that we do not allocate (the internal state of this hash function is 32 bit) and have the same quality and performance as Hashtbl.hash.

Hence, we are here making the choice of using this Internalhash (that is, Murmur3, the OCaml hash algorithm as of 4.03) as our hash algorithm. It means that the state of the hash function does not need to be preallocated, and makes for simpler use in hash tables and other structures.

include Full
  with type state = Base_internalhash_types.state
   and type seed = Base_internalhash_types.seed
   and type hash_value = Base_internalhash_types.hash_value

Sourceval description : string

Name of the hash-function, e.g., "internalhash", "siphash"

Sourcetype state = Base_internalhash_types.state

state is the internal hash-state used by the hash function.

Sourceval fold_int : state -> int -> state

fold_<T> state v incorporates a value v of type <T> into the hash-state, returning a modified hash-state. Implementations of the fold_<T> functions may mutate the state argument in place, and return a reference to it. Implementations of the fold_<T> functions should not allocate.

Sourceval fold_int64 : state -> int64 -> state

Sourceval fold_float : state -> float -> state

Sourceval fold_string : state -> string -> state

Sourcetype seed = Base_internalhash_types.seed

seed is the type used to seed the initial hash-state.

Sourceval alloc : unit -> state

alloc () returns a fresh uninitialized hash-state. May allocate.

Sourceval reset : ?seed:seed -> state -> state

reset ?seed state initializes/resets a hash-state with the given seed, or else a default-seed. Argument state may be mutated. Should not allocate.

Sourcetype hash_value = Base_internalhash_types.hash_value

hash_value The type of hash values, returned by get_hash_value.

Sourceval get_hash_value : state -> hash_value

get_hash_value extracts a hash-value from the hash-state.

Sourcemodule For_tests : sig ... end

Sourcetype 'a folder = state -> 'a -> state

Sourceval create : ?seed:seed -> unit -> state

create ?seed () is a convenience. Equivalent to reset ?seed (alloc ()).

Sourceval of_fold : (state -> 'a -> state) -> 'a -> hash_value

of_fold fold constructs a standard hash function from an existing fold function.

Sourcemodule Builtin : sig ... end

Sourceval run : ?seed:seed -> 'a folder -> 'a -> hash_value

run ?seed folder x runs folder on x in a newly allocated hash-state, initialized using optional seed or a default-seed.

The following identity exists: run [%hash_fold: T] == [%hash: T]

run can be used if we wish to run a hash-folder with a non-default seed.