[ANN] First release of baby

It is my pleasure to announce the first release of baby.

baby is an OCaml library that offers several implementations of balanced binary search trees. At this time, baby offers a replacement for OCaml’s Set module; it does not yet have a replacement for OCaml’s Map module.

Height-balanced and weight-balanced binary search trees are offered out of the box. Furthermore, to advanced users, the library offers a lightweight way of implementing other balancing strategies.

The following points offer a comparison between baby and OCaml’s Set library.

Better Performance

At the time of writing, baby offers generally better performance than OCaml’s Set library. Its operations are generally faster (sometimes much faster; sometimes slightly faster; sometimes slightly slower) than those of the Set library, and its memory allocation rate is slightly lower.

Constant-Time Cardinal

In contrast with the Set library, baby’s weight-balanced trees offer a cardinal function whose time complexity is O(1). They also offer a family of random access functions (get, index, etc.) whose time complexity is O(log n). Furthermore, by exploiting cardinality information, the functions subset and equal are sometimes able to return false in constant time.

Better Sharing

baby’s binary operations (union, inter, diff) take advantage of (and preserve) physical equality in a more aggressive way. This allows them to (sometimes) be faster and allocate less memory.

Adaptive Conversions To Sets

baby’s conversion functions of_list, of_array, and of_seq have adaptive complexity. If the input data is sorted, their complexity is O(n); otherwise, their complexity gracefully degrades down to O(n.log n).

More Operations

baby offers a few operations that do not exist in OCaml’s Set library:

  • The symmetric difference, xor;
  • The conversion functions of_array and to_array;
  • The extremum-removal functions remove_min_elt and remove_max_elt;
  • The enumeration API in the submodule Enum. Enumerations should be slightly faster than standard sequences, and are able to efficiently seek ahead, via the function from.

Documented Complexity

In baby, the time complexity of every operation is documented.

Compatibility

baby is perfectly compatible with OCaml’s Set library. In other words, using Baby.W.Set instead of Set is safe.

As a word of warning, though, if the equivalence relation on elements is coarser than equality (that is, if compare x y = 0 does not imply x = y), then Baby.W.Set and Set might behave differently when a choice must be made between two equivalent elements. This can occur in union, of_list, of_array, of_seq, add_seq, map.

16 Likes

I was confused by this sentence. After thinking about it, I think it that x = y must be understood as mathematical equality, not the OCaml polymorphic structural equality operator. With this interpretation, it makes sense, and the warning is that Set and Baby.W.Set may not pick the same element when adding several elements that compare to 0. Maybe using x == y instead of x = y in the warning would clarify the meaning ?

I also saw this comment at the start of Baby.cppo.ml:

(* Unfortunately, the OCaml compiler is pretty bad at optimization. In my
   experience, although it does usually inline functions when requested, it
   does not subsequently perform the simplifications that one might naturally
   expect. In particular, it does not simplify match-of-match, and cannot even
   simplify match-of-constructor. *)

Have you compared the results with and without flambda ? At least simplification after inlining should work with flambda, as well as match-of-constructor. Hopefully flambda2 will also support match-of-match soon, but I don’t think any of the current compilers do.

1 Like