# JaneStreet's OCaml Core library's Hashtbl interfaces
**URL:** https://discuss.ocaml.org/t/janestreets-ocaml-core-librarys-hashtbl-interfaces/15323
**Category:** Learning
**Tags:** core, hashtbl
**Created:** [September 23, 2024, 6:57am UTC](https://discuss.ocaml.org/t/janestreets-ocaml-core-librarys-hashtbl-interfaces/15323 "2024-09-23T06:57:22Z")
**Posts on this page:** 17
**Page:** 1
### Author:  [@s.t.s](https://discuss.ocaml.org/u/s.t.s)
#### Post date: [September 23, 2024, 6:57am UTC](https://discuss.ocaml.org/t/janestreets-ocaml-core-librarys-hashtbl-interfaces/15323/1 "2024-09-23T06:57:22Z")
**Available Hash Table APIs**
The question is about which approach to constructing a hash table in Core is preferable.
I noticed that the JaneStreet’s Core Hashtbl library provides several interfaces to creating hash tables. Let’s assume that there’s no interest in polymorphic hash tables. Is there one approach that is most preferred? What is the role of `Make` functor there? Is the use of this functor a preferred approach? It seems that the use of `Key.Table` approach is referenced in earlier documentation, and I didn’t notice the presence of `Make` functor in the earlier versions of the `Hashtbl`. This suggests that maybe `Make` functor based approach is a more recent method.
I know that in the base library the `Make`-based approach has existed more or less from the beginning.
Given that, I don’t understand what the `Hashtbl.create` is doing there, whence we already have other approaches taking equivalent record of functions. Is this a legacy method?
A couple of similar inquiries appeared on the forum [here](https://discuss.ocaml.org/t/custom-type-key-for-core-hashtbl-create/11909) and [here](https://discuss.ocaml.org/t/hashtbl-make-vs-hashtbl-create-when-to-use-what/5652), but none had considered the issue of choosing an interface in the `Core`.
There’s a type `(_ , _, _) Hashtbl_intf.create_options_without_hashable` that emerges when a function `create` in the module generated by the `Make` is invoked. Now, this looks like a source of concern to me in the sense that hashable-based approach (and thus the `Table` functor? Just like in the old `Base` interface?) is suggested to be more normative rather.
* * *
**Constructing Families of Hash Tables**
If I would like to use hash tables that reference other hash tables (e.g. mapping from ids to property lists), is there a difference which interface I use as far as efficiency is concerned?
---
### Author:  [@mbarbin](https://discuss.ocaml.org/u/mbarbin)
#### Post date: [September 23, 2024, 8:57am UTC](https://discuss.ocaml.org/t/janestreets-ocaml-core-librarys-hashtbl-interfaces/15323/2 "2024-09-23T08:57:56Z")
Hello! That’s a great question thanks for asking. +1 I’m interested to know what someone from JS is going to respond.
Personally, I very much like the `take a first class module` approach of the containers interface from `Base`. It seems to go well with a general direction that the language could take in the future (consider for example the work on [modular-explicits](https://gallium.inria.fr/~remy/ocamod/modular-explicits.pdf)).
A point of friction I have with functors is that I never really know where to put the invocation in my code, and often end up either with unusual modules that I need to import in some ad-hoc way, or worse, end up with multiple invocations in different places of the functor with the same arguments. Using the first class module design solves this, and is my preferred way at the moment. I wish more currently-functorized libraries would add a support for an interface of that style, when possible!
A word of caution though, I don’t know whether having this cosmetic preference comes with attached downsides. Given that it is not as widely popular as the functor approach, there may be reasons behind it. I’d like to know more about this if someone has given it some thoughts.
---
### Author:  [@jjb](https://discuss.ocaml.org/u/jjb)
#### Post date: [September 23, 2024, 10:26am UTC](https://discuss.ocaml.org/t/janestreets-ocaml-core-librarys-hashtbl-interfaces/15323/3 "2024-09-23T10:26:28Z")
One point that may or may not be relevant in your case is that the compiler has an easier time optimizing the functor-based approach, at least according to the last benchmarks I know that focused on this, see [here](https://discuss.ocaml.org/t/functorial-vs-comparator-container-interfaces/5384).
---
### Author:  [@s.t.s](https://discuss.ocaml.org/u/s.t.s)
#### Post date: [September 23, 2024, 3:11pm UTC](https://discuss.ocaml.org/t/janestreets-ocaml-core-librarys-hashtbl-interfaces/15323/4 "2024-09-23T15:11:47Z")
I think, the functors could be applied to first-class modules. Given that functors also are [dependent types](https://cs3110.github.io/textbook/chapters/modules/functors.html), we actually have a tool that could yield a richer semantics.
What is bizarre to me is the distinction between `Hastbl.Make` and `Key.Table` based approaches. My _guess_ is that one of them is a legacy one.
---
### Author:  [@s.t.s](https://discuss.ocaml.org/u/s.t.s)
#### Post date: [September 23, 2024, 3:19pm UTC](https://discuss.ocaml.org/t/janestreets-ocaml-core-librarys-hashtbl-interfaces/15323/5 "2024-09-23T15:19:18Z")
The use of functors conceptually seems to make more sense, especially since apparently the functors could be applied to first-class modules, and thus there’s no restriction when such functionality is required (e.g. in dynamic loading it’s unavoidable).
Thank you for sharing the benchmark results. As a digression, I would like to note that the consistent results of Core, and the slightly lower speed at the higher optimization level, is perhaps explainable by the fact that the Core’s (and I assume Base’s) implementation of `Hashtbl` uses an array of AVL trees rather than array. In production, that seems to be a much more preferable solution than just an array, regardless of a slight performance drop.
---
### Author:  [@mbarbin](https://discuss.ocaml.org/u/mbarbin)
#### Post date: [September 23, 2024, 9:57pm UTC](https://discuss.ocaml.org/t/janestreets-ocaml-core-librarys-hashtbl-interfaces/15323/6 "2024-09-23T21:57:08Z")
As of v0.17:
- I can’t find a functor `Base.Hashtbl.Make`. Looks like `Base` only exports the first-class module pattern nowadays.
- If you are comparing solely `Core.Hashable.Make` (the Key.Table pattern) against `Core.Hashtbl.Make` my conclusion looking at [the code](https://github.com/janestreet/core/blob/6d8a862aacdbce87eeca0ac3d942001d546d4845/core/src/hashable.ml#L32) is that `Core.Hashable.Make` simply packages together several instantiations of hash related functors (`Hashtbl`, `Hash_set` and `Hash_queue`), and gives them standard names (`Table`, `Hash_set` and `Hash_queue`). `Core.Hashable.Make` actually calls `Core.Hashtbl.Make` under the hood to build the `Table` part (if you only need the table one, I suppose there’s no need to build the other 2).
```ocaml
module Make (T : sig
type t [@@deriving hash]
include Hashtbl.Key with type t := t
end) : S with type t := T.t = struct
include T
module Table = Hashtbl.Make (T)
module Hash_set = Hash_set.Make (T)
module Hash_queue = Hash_queue.Make (T)
let hashable = Table.hashable
end
```
---
### Author:  [@s.t.s](https://discuss.ocaml.org/u/s.t.s)
#### Post date: [September 23, 2024, 9:58pm UTC](https://discuss.ocaml.org/t/janestreets-ocaml-core-librarys-hashtbl-interfaces/15323/7 "2024-09-23T21:58:05Z")
> [@mbarbin](#):
>
> I can’t find a functor `Base.Hashtbl.Make`. Looks like `Base` only exports the first-class module pattern nowadays.
Right. It’s only available in Core, and used to be available in now-defunct Core\_kernel. This fact is one of the reasons why I’ve mentioned deprecation in my original posts.
> [@mbarbin](#):
>
> If you are comparing solely `Core.Hashable.Make` (the Key.Table pattern) against `Core.Hashtbl.Make` my conclusion looking at [the code](https://github.com/janestreet/core/blob/6d8a862aacdbce87eeca0ac3d942001d546d4845/core/src/hashable.ml#L32) is that `Core.Hashable.Make` simply packages together several instantiations of hash related functors (`Hashtbl`, `Hash_set` and `Hash_queue`), and gives them standard names (`Table`, `Hash_set` and `Hash_queue`). `Core.Hashable.Make` actually calls `Core.Hashtbl.Make` under the hood to build the `Table` part (if you only need the table one, I suppose there’s no need to build the other 2).
So, if all I need is just a hash table (to map ids to records or property lists, etc.), then by using `Hashtbl.Make`, I’ll be getting the same code and same API working as with the `Key.Table`, which in turn is an invocation of `Hashable.Make`?
A question arises, which approach would be more _idiomatic_? For you, but also perhaps for JaneStreet? For the latter case, is there a justification published? Some blog notes? (my Google-fu — which was utilized prior to publishing the original post — returned nothing on the latter 🫤).
---
### Author:  [@mbarbin](https://discuss.ocaml.org/u/mbarbin)
#### Post date: [September 23, 2024, 10:02pm UTC](https://discuss.ocaml.org/t/janestreets-ocaml-core-librarys-hashtbl-interfaces/15323/8 "2024-09-23T22:02:10Z")
> [@s.t.s](#):
>
> So, if all I need is just a hash table (to map ids to records or property lists, etc.), then by using `Hashtbl.Make`, I’ll be getting the same code and same API working as with the `Key.Table`, which in turn is an invocation of `Hashable.Make`?
I think so, yes. That’s my understanding of the code, reading a recent checkout of core (\>= v0.17, maybe true for older versions but I haven’t checked.)
---
### Author:  [@s.t.s](https://discuss.ocaml.org/u/s.t.s)
#### Post date: [September 23, 2024, 10:03pm UTC](https://discuss.ocaml.org/t/janestreets-ocaml-core-librarys-hashtbl-interfaces/15323/9 "2024-09-23T22:03:41Z")
Thank you. I wonder, why are there two different interfaces in the API in the first place? I mean, it’s relatively trivial to invoke the constructors, right?
---
### Author:  [@v-gb](https://discuss.ocaml.org/u/v-gb)
#### Post date: [September 28, 2024, 6:11pm UTC](https://discuss.ocaml.org/t/janestreets-ocaml-core-librarys-hashtbl-interfaces/15323/10 "2024-09-28T18:11:31Z")
The original API is the `Hashtbl.Make` one from Core, the newer one is the defunctorized one from both Base and Core.
Both are used a lot and are essentially straightforwardly interchangeable. The difference between `Foo.Table.create ()` and `Hashtbl.create (module Foo)` is whether you pass the information about the key being `Foo.t` is passed via the function name or a function argument.
The defunctorized API in Base was created for a few reasons:
- to reduce dependencies between modules. `Core.Int` contains `Core.Int.Table` so it must depend on `Core.Hashtbl` (or `Base.Hashtbl` perhaps). So if your code uses just one function of `Core.Int`, you end up linking `Core.Hashtbl` (and `Hash_set`, and `Map`, and `Set`, and `Hash_queue`, and whatever they bring along transitively). In Base, `Int` and `Map` are independent, and you still don’t need to apply a functor to use an map keyed by ints (unlike with the stdlib).
- to work better with `[@@deriving]`. With a list, if I have `type t = (A.t * B.t) list [@@deriving of_sexp]`, that types so long as `A.t` and `B.t` have `[@@deriving of_sexp]`, which is ideal (and similarly for any other derivers that are defined recursively on the type). With the Base interface, the same thing is true with `type t = B.t Hashtbl.M(A).t [@@deriving of_sexp]`. With `Core.Hashtbl.Make`, it’s not enough for `A.t` to support `of_sexp`, you need to add code around the `Hashtbl.Make` call to say so, which is boilerplate that’s redundant with the definition of `A`.
- not applying functors for maps, sets, hashtbls, hash\_sets etc is just less boilerplate to write (that boilerplate is reduced with the [`include functor` proposal](https://github.com/ocaml/RFCs/pull/43), but still), less noise in api docs, less space taken in .cmi, .cmt.
- removing an annoyance with the Core interface, not with `Hashtbl`, but with `Map` (and `Set`). The convention to define `Foo.Map` as the maps keyed by `Foo` means that it’s awkward in foo.ml to use maps keyed by something other than `Foo` (`Core.Map` is shadowed by `Foo.Map`). With `Base`, there’s no `Foo.Map`, so no problem.
Personally, I only use the defunctorized interfaces mostly for the boilerplate reasons.
---
### Author:  [@s.t.s](https://discuss.ocaml.org/u/s.t.s)
#### Post date: [September 28, 2024, 6:20pm UTC](https://discuss.ocaml.org/t/janestreets-ocaml-core-librarys-hashtbl-interfaces/15323/11 "2024-09-28T18:20:39Z")
Thank you for sharing this. This is very insightful.
May we conclude that the first-class module interface is now considered idiomatic? The JaneStreet’s blogs and other writings accessible through Google do not seem to suggest one way or another. Nor does the API documentation…
May we assume that there’s no cost in efficiency for use of first-class modules? The question is relevant for me also in considering what data representation to use in other parts of my program — that is whether the first-class modules are indeed viable for such purposes.
> [@v-gb](#):
>
> to work better with `[@@deriving]`. With a list, if I have `type t = (A.t * B.t) list [@@deriving of_sexp]`, that types so long as `A.t` and `B.t` have `[@@deriving of_sexp]`, which is ideal (and similarly for any other derivers that are defined recursively on the type). With the Base interface, the same thing is true with `type t = B.t Hashtbl.M(A).t [@@deriving of_sexp]`. With `Core.Hashtbl.Make`, it’s not enough for `A.t` to support `of_sexp`, you need to add code around the `Hashtbl.Make` call to say so, which is boilerplate that’s redundant with the definition of `A`.
I think, that in the module generated by functor, there’s still going to be a `[@@deriving]` annotation already embedded. Is it not transparent with functors? But transparent with first-class?
---
### Author:  [@v-gb](https://discuss.ocaml.org/u/v-gb)
#### Post date: [September 28, 2024, 9:08pm UTC](https://discuss.ocaml.org/t/janestreets-ocaml-core-librarys-hashtbl-interfaces/15323/12 "2024-09-28T21:08:22Z")
> May we conclude that the first-class module interface is now considered idiomatic? The JaneStreet’s blogs and other writings accessible through Google do not seem to suggest one way or another. Nor does the API documentation…
Both APIs are idiomatic. If you want to know the most idiomatic one, I don’t think that’s settled. The functor API is almost certainly used vastly more.
> May we assume that there’s no cost in efficiency for use of first-class modules? The question is relevant for me also in considering what data representation to use in other parts of my program — that is whether the first-class modules are indeed viable for such purposes.
I don’t expect any perf difference between the two APIs. The functors only gives functions to create new hash tables, so your calls to `Hashtbl.set` and `Hashtbl.find` will be exactly the same either way. `Stdlib.Hashtbl.Make` works differently, which I think the other thread was saying is more easily optimized by flambda.
> I think, that in the module generated by functor, there’s still going to be a `[@@deriving]` annotation already embedded. Is it not transparent with functors? But transparent with first-class?
Just take a silly “identity” functor, since there’s nothing `Hashtbl`-specific here:
```ocaml
module M(X : sig type t end) = struct
type t = X.t
end
module M_int = M(Int)
type t = M_int.t [@@deriving of_sexp]
```
That won’t type since `M_int.t` doesn’t provide `[@@deriving of_sexp]` even though `Int` does. You can fix it:
```ocaml
module M(X : sig type t [@@deriving of_sexp] end) = struct
type t = X.t [@@deriving of_sexp]
end
module M_int = M(Int)
type t = M_int.t [@@deriving of_sexp]
```
That solves the problem, but you’ve broken all the users of the functor that didn’t care about `of_sexp` and don’t want to provide it for their key. So an actual solution that supports all cases is:
```ocaml
module M(X : sig type t end) = struct
type t = X.t
module Provide_of_sexp(Y : sig val t_of_sexp : sexp -> X.t end) = struct
let t_of_sexp = Y.t_of_sexp
end
end
module M_int = struct
include M(Int)
include Provide_of_sexp(Int)
end
type t = M_int.t [@@deriving of_sexp]
```
That way, different callers can ask for the optional functionalities that they have the requirements for, like having of\_sexp on the input type to give of\_sexp on the output type. But when you apply the functor, you have to state that Int supports of\_sexp.
With first class modules, what happens instead is (taking a syntactic shortcut):
```ocaml
module M(X : sig type t end) = struct type t = X.t end
let m__t_of_sexp (type a) (module X : sig type t = a [@@deriving of_sexp] end) sexp =
X.t_of_sexp sexp
type t = M(Int).t [@@deriving of_sexp]
(* deriving ends up generating:
let t_of_sexp sexp = m__t_of_sexp (module Int) sexp *)
```
The code generated by the final `[@@deriving of_sexp]` directly requests of\_sexp from `Int`. And users of M who don’t request of\_sexp don’t have to provide it for the functor argument.
---
### Author:  [@s.t.s](https://discuss.ocaml.org/u/s.t.s)
#### Post date: [September 28, 2024, 9:32pm UTC](https://discuss.ocaml.org/t/janestreets-ocaml-core-librarys-hashtbl-interfaces/15323/13 "2024-09-28T21:32:07Z")
Thank you. I think both of your last two responses are a resolution to my original inquiry. Is there a suitable way to mark them? (I think, the “Solution” tag is limited to one per post…).
---
### Author:  [@s.t.s](https://discuss.ocaml.org/u/s.t.s)
#### Post date: [September 28, 2024, 9:37pm UTC](https://discuss.ocaml.org/t/janestreets-ocaml-core-librarys-hashtbl-interfaces/15323/14 "2024-09-28T21:37:52Z")
> [@v-gb](#):
>
> With first class modules, what happens instead is (taking a syntactic shortcut):
>
> ```auto
> module M(X : sig type t end) = struct type t = X.t end
> let m__t_of_sexp (type a) (module X : sig type t = a [@@deriving of_sexp] end) sexp =
> X.t_of_sexp sexp
>
> type t = M(Int).t [@@deriving of_sexp]
> (* deriving ends up generating:
> let t_of_sexp sexp = m__t_of_sexp (module Int) sexp *)
>
> ```
>
> The code generated by the final `[@@deriving of_sexp]` directly requests of\_sexp from `Int`. And users of M who don’t request of\_sexp don’t have to provide it for the functor argument.
As a side-note, I suppose that the `-O3` or `flambda` (my compiler is always built with `flambda`) would inline the code properly, even for first-class modules case.
---
### Author:  [@v-gb](https://discuss.ocaml.org/u/v-gb)
#### Post date: [September 28, 2024, 9:52pm UTC](https://discuss.ocaml.org/t/janestreets-ocaml-core-librarys-hashtbl-interfaces/15323/15 "2024-09-28T21:52:29Z")
> Thank you. I think both of your last two responses are a resolution to my original inquiry. Is there a suitable way to mark them? (I think, the “Solution” tag is limited to one per post…).
No idea!
> As a side-note, I suppose that the `-O3` or `flambda` (my compiler is always built with `flambda`) would inline the code properly, even for first-class modules case.
Inlining would work, but I don’t expect inlining alone to result in a speedup. What presumably helps is having a copy of `Hashtbl.find` and co with the specific hashing and comparison functions baked in, at least when they keys are cheap to manipulate, like integers. That specialization is easy to apply to `Stdlib.Hashtbl.Make`, not so much with `Base.Hashtbl` and `Core.Hashtbl`.
---
### Author:  [@s.t.s](https://discuss.ocaml.org/u/s.t.s)
#### Post date: [September 28, 2024, 9:55pm UTC](https://discuss.ocaml.org/t/janestreets-ocaml-core-librarys-hashtbl-interfaces/15323/16 "2024-09-28T21:55:33Z")
> [@v-gb](#):
>
> > Thank you. I think both of your last two responses are a resolution to my original inquiry. Is there a suitable way to mark them? (I think, the “Solution” tag is limited to one per post…).
>
> No idea!
I tagged the last post. Unfortunately, even a forum presents us with some design limitations to wrestle with… 🙄 😶
---
### Author:  [@s.t.s](https://discuss.ocaml.org/u/s.t.s)
#### Post date: [September 28, 2024, 9:59pm UTC](https://discuss.ocaml.org/t/janestreets-ocaml-core-librarys-hashtbl-interfaces/15323/17 "2024-09-28T21:59:56Z")
> [@v-gb](#):
>
> Inlining would work, but I don’t expect inlining alone to result in a speedup. What presumably helps is having a copy of `Hashtbl.find` and co with the specific hashing and comparison functions baked in, at least when they keys are cheap to manipulate, like integers. That specialization is easy to apply to `Stdlib.Hashtbl.Make`, not so much with `Base.Hashtbl` and `Core.Hashtbl`.
Thank you for sharing this observation. I’ll use the more conservative functor-based approach for the time being in my code. It become largely idiomatic in practice at this point. I wonder if flambda-2 (cf. [here](https://icfp23.sigplan.org/details/ocaml-2023-papers/8/Efficient-OCaml-compilation-with-Flambda-2)) would tackle this problem better. Maybe, even the issues with efficiency of objects, when the layout is known statically…