Stability of order-dependent functions in Jane Street libraries

In Jane Street Core_kernel, Hashtbl has functions iter and to_alist that rely on an implicit ordering of data elements. The functor-created Table modules also have those functions; Hash_set has iter and to_list.

Should I have any confidence that the ordering used by such functions will remain stable across Jane Street releases? A prudent programmer might assume “no”, but being prudent is lots of work.

In general, not just Core’s case, I wouldn’t assume anything about the order of hashtable elements unless the interface explicitly guarantees something. If your application requires a certain element order, you probably should maintain some additional data structure for that.

In fact, even within a single version of a library, you shouldn’t assume different runs of the program to have the same order of hashtable elements. Not sure about Core, but Stdlib.Hashtbl offers randomized hash tables to avoid denial-of-service attacks.
Even without explicit randomization, I wouldn’t assume any ordering since there’s no explicit guarantee that the hashtable resizing and collision handling are fully deterministic.

1 Like

To complement @sim642’s answer. If that’s an important operation for you and don’t mind to switch from O(1) to O(log n) complexity then simply use a Stdlib.Map. The ones in the Stdlib guarantee you an iteration ordering (from the docs it’s unclear whether Base.Map does).

1 Like