package core_kernel

Release v0.17.0

• Enum

  • Add make_param_optional_comma_separated_with_default_doc.
  • Expose the optional argument ?strip_whitespace:bool in make_param_optional_comma_separated.
  • Add a functorized version of to_string.
  • Expose command_friendly_name so the transformation can be reused by other libraries.

• Hash_heap

  • Expose comparator.

• Iobuf

  • Add {Poke,Fill}.date_string_iso8601_extended.
  • Add Iobuf.{Poke,Fill}.padded_decimal.
  • Add Unsafe.Poke.bin_prot_with_known_size.
  • Rename blit_explanation_trunc to blit_string_trunc.
  • Add maybe_blit_int.
  • Add bigstring_view and unsafe_bigstring_view.

• Limiter

  • Token_bucket.try_reconfigure now includes an allow_limit_decrease parameter.

• Nonempty_list

  • Add map2, map2_exn, cartesian_product, fold_nonempty and map_of_list_with_key_multi.

• Pairing_heap

  • Add pop_while.

• Timing_wheel

  • Add advance_clock_stop_at_next_alarm.

• Total_map

  • Add S_plain.of_alist_exn.
• Move Uopt to a separate package.

• Vec

  • Add maybe_get_local, grow_to_include, grow_to_include', grow_to', to_local_list, to_sequence, to_sequence_mutable, of_sequence, clear_imm, foldi, foldi_local_accum.
  • Add Expert.unsafe_inner.

• Weak_hashtbl

  • Add clear.

• Weak_pointer

  • Add create_full.

Old pre-v0.16 changelogs (very likely stale and incomplete)

As Core_kernel is built on top of Base, you might want to have a look at Base's changelog.

git version

• Deprecated failwithp in favor of failwiths, and made failwiths's ~here argument required.
• Renamed functions in Fqueue to make it consistent with Queue and Fdeque. top, top_exn, and discard_exn remain as deprecated aliases to peek, peek_exn, and drop_exn.
• Removed deprecated values Fqueue.{enqueue_top, bot_exn, bot}.
• Removed Obj_array in favor of Uniform_array.
• Remove deprecated Std module.

v0.12

• Added Digit_string_helpers.read_int63_decimal.
• Added List.zip_with_remainder which zips as many elements as possible and then returns the unzipped remained of the longest input, if the input lists have different lengths.
• Added Bigbuffer.add_bin_prot to append the bin-protted representation of a value at the end of the buffer.
• Reexport Base.Buffer.
• Added labels to function parameters in the Quickcheck module.
• Deprecate Timing_wheel_ns.alarm_upper_bound in favor of Timing_wheel_ns.max_allowed_alarm_time.
• Deprecated Array.replace arr i ~f in favor of using arr.(i) <- (f (arr.(i)))
• Removed functions that were deprecated in 2016 and 2017 from the Array and Set modules.
• Removed Int_replace_polymorphic_compare in favor of Int.Replace_polymorphic_compare.

v0.11

• Add Bigstring.unsafe_resize to allow reallocating in place.
• Moved Splittable_random to its own library. Available at http://github.com/janestreet/splittable_random
• Remove Time.*.Stable, leaving Time.Stable as the only submodule that exports stable conversions. Clients of Time should refer to stable modules as Time.Stable.X where they were previously using Time.X.Stable.
• Added Md5.digest_bin_prot. This gives an easy way to write t -> Md5.t for any Binable value.
• Added a Stable_comparable.V1 module type.
• Changed fold_until's interface: instead of returning a Finished_or_stopped_early.t it now takes a finish callback.
• Deprecated the [Std] module.

v0.10

• Renamed Float.to_string as to_string_12, to reflect its 12-digit precision. And introduce a new Float.to_string with the behavior of Float.to_string_round_trippable.
• Many changes to Set_once, including requiring %here at calls to get_exn, set, and set_exn
• Improved Quickcheck's interface for giving explicit length values or ranges for random lists and strings.
• Removed Stable_workaround modules that are no longer necessary since we upgraded to OCaml 4.04.
• Exposed Date.add_days_skipping, a generalization of add_business_days and add_weekdays
• Added Total_map.data, that just calls Map.data on the underlying map
• Deprecated Array.empty, which was already deprecated in Base.
• Added function Gc.add_finalizer_last, which is like add_finalizer, except that the function is only called when the value has become unreachable for the last time.
• Added to module Maybe_bound: [@@deriving bin_io] and module Stable.
• Added module Optional_syntax, with interfaces S, S1, and S2, used by modules that expose an Optional_syntax submodule for use with match%optional.
• Switched Weak_hashtbl to use Gc.add_finalizer_last, rather than Weak_pointer's emulation based on Ephemeron.
• Re-implemented Weak_pointer directly in terms of OCaml's Weak module, rather than using Ephemeron.
• Moved Bigstring.map_file to Core, since it depends on Unix.
• Optimized Heap.merge_pairs by removing a closure allocation.
• Fixed String_id's no-whitespace-on-edge check for String_id.Set etc.
• Changed Version_util to store build_time as a Time.t rather than using a Date.t and a Time.Ofday.t.
• Added functor String_id.Make_with_validate, so that we can create identifiers that perform custom validation on creation.
• Added Core_kernel.print_s, for pretty printing a sexp to stdout. (jane/Core.print_s)
• Added to Bigstring a number of bounds-checked versions of functions dealing with integers, corresponding to existing unsafe versions.
• Added String.take_while and rtake_while.
• Improved Heap.sexp_of_t and Heap.Removable.sexp_of_t.
• Added Md5 module, a wrapper around OCaml's Digest module.
• Added stable serialization of Time, in Time.Stable.With_utc_sexp.V2.
• In Univ_map, exposed Type_equal.Id.t for Key.t types.
• Changed Gc.Stat.sexp_of_t so it no longer drops precision in the minor_words, promoted_words, and major_words fields.
• Added Map.merge_skewed function that only traverses one of its arguments, unlike Map.merge, which traverses both.
• Improved Obj_array inlining.
• Optimized Deque.clear to only walk the queue, rather than the entire backing array.
• Optimized Bus by adding writeN functions that can be inlined.
• Removed Bus's variable arity write function, making write be for arity-1 buses only, with write2, write3, and write4 for other arities.
• Added Core_kernel_stable.Time, which includes stable types for Time.Span.t and Time.With_utc_sexp.t..
• In Unique_id.Id, changed Hashable to Hashable.S_binable.
• Exposed Core_kernel.ifprintf.
• Added module Queue.Stable.
• Changed Bus.create's allow_subscription_after_first_write argument to on_subscription_after_first_write and added a choice that causes the bus to remember the last value written to it and send it to new subscribers.
• Renamed Flags.subset to is_subset, for consistency.
• Made module Core_kernel.Bytes be an extension of Base.Bytes.
• Add bytes functions to Bigstring and Bigbuffer.
• Exposed type Host_and_port.t as a record type.
• Added function Total_map.for_all.
• Added function Date.add_years, which just calls Date.add_months d 12*n.
• Moved Time.Ofday.of_string parsing into a separate module so that it can eventually be shared between Time and Time_ns. Made of_string reject nonsense inputs (e.g 0:00:0 and 1:-0:3e1).
• Reworked Time.Ofday.to_string to avoid using to_parts, improving its performance.
• Made Time.Span.Parts and Time_ns.Span.Parts the same by adding the ns field to Time.Span.Parts. Updated create functions for Span and Ofday to accept ?ns. Fixed Time_ns.Ofday.create to be precise rather than round-tripping through Time.Ofday.
• Optimized Pool, Thread_safe_queue, Time_ns, and Timing_wheel_ns by moving some error branches into [@inline never] functions.
• Merged Heap.Removable into Heap.
• Changed Heap.remove's implementation to use the usual pairing-heap delete algorithm, which has amortized O(log(n)) complexity the same complexity as removing the min value, without the memory problem of the current implementation.
• Added module Heap.Unsafe, with non-allocating alternatives to Elt.t.
• Removed Time's and Time_ns's Ofday.end_of_day value, and added start_of_next_day and approximate_end_of_day as replacements.
• Deprecated blit functions that mutate strings.
• Switched Core_kernel to -safe-string.
• Fixed String's quickcheck generator to use size as an upper bound.
• Added function Sequence.merge_all, which uses Fheap.
• Added module type Identifiable.S_plain, which is like Identifiable.S but does not export t_of_sexp.
• Deprecated Bigsubstring's and Substring's of_string and of_bigstring functions. One should use create for sharing.
• Added Date.Days module, a date representation optimized for linear arithmetic (e.g. add_days) rather than for extracting year/month/day.
• Changed Hashtbl, Hash_set, Map, and Set generic creation functions to use a first-class module like Base rather than a comparator or hashable.
• Added Quickcheck.test_or_error, an Or_error-based version of test.
• Split Time.Zone.shift_epoch_time into absolute_time_of_relative_time and relative_time_of_absolute_time to make its uses clearer.

v0.9

113.43.00

• This feature implements String.Caseless.is_prefix and String.Caseless.is_suffix functions which check if some string is prefix or suffix of another ignoring case.
• Hash_set now supports the intersection operation

• Add functions to create Maps and Sets from Hashtbls or a Hash_sets. Existing code that do that sort of things usually end up going through an intermediate assoc list, which is not particularly efficient. The friction of inlining something better at the app level feels just too verbose so usually it's not done. We hope that by offering the right util in core, those call sites can be updated for something both shorter and more efficient.

  Note: we do not currently carry 'cmp cmp witnesses into our Hashtbls and Hash_sets the same way we do it for Maps and Sets. There exists cases where the following code would actually raise:

  let map_of_hashtbl (hashtbl : (M.t, 'a) Hashtbl.t) = hashtbl |> Hashtbl.to_alist |> M.Map.of_alist_exn ;;

  If the hashtbl and the M.Map do not use the same compare function, and there exists some keys a1, and a2 such that:

  (Hashtbl.hashable hashtbl).compare a1 a2 <> 0 && M.compare a1 a2 = 0

  So, in the context of that feature there was a choice to be made. Either Map.of_hashtbl can silently replace previous binding while folding over the hashtbl, or can raise.

  Conservatively, the choise to raise was taken, thus the function has the usual _exn suffix: Map.of_hashtbl_exn

  For sets, the context is suffisiently different so as to deliberatly not apply the same approach. Like when using Set.of_list one wants to aggreate values from a container into a set. Hashtbl keys and Hash_set values are just a different kind of container than a list, but the added value of raising in that function in case the hash set or the hashtbl have dups is not clear, so that path was not pursued.

  With more work, we could (and someday maybe will) have Hashtbl and Hash_set carry comparison witnesses and create versions of those functions that cannot raise and reuse the comparison and the compare witness of the hashtbl or hash_set.

  In the process of implementing Map.of_hashtbl_exn it appeared that Map.of_alist was inefficiently doing the lookup twice for each element to be inserted. The feature fixes this.

• Name the non-t arguments to Error.tag and similar functions to allow easier partial application.
• Name the non-t arguments to Error.tag and similar functions to allow easier partial application.

• Map.Stable

  Added Map.Stable, including a Make functor for making stable map types.

• Binary search by time for Queue_ts.
• Automatic, randomized testing based on Haskell's "Quickcheck" library.

• Introduce Quickcheck.Generator.geometric and add/modify functions based on it:

  • rename Generator.size to Generator.small_non_negative_int
  • add Generator.small_positive_int
  • document the above in terms of Generator.geometric

• The following segfaults:

  open Core.Std;; let s = Stack.create();; Stack.push s 1.0;; Stack.push s 2.0;; Stack.push s 3.0;;

  This is because we put floats together with non-floats in the same array without care.

  In particular, if you call Array.init ~f such that f 0 returns a float, then ocaml will decide to create an unboxed float array (tagged with Double_array). It will then proceed to call f i and try to unbox each assuming they all are pointers to floats. If f i happens to return an immediate (such as Obj.magic ()) instead of a pointer, this segfaults.

  Queue and Deque don't seem to suffer from the same problem because they both create arrays initially populated with immediates so the arrays end up not tagged with Double_array. It happens that it's safe to put floats into such arrays, so let's use the same trick in Stack. The plan is to eventually use (a safety wrapper over) Obj_array in all of Stack, Queue, Deque (jane/stack-segfault feature).

• Added Set.Stable, including a Make functor for making stable set types.

• Renamed the "Stable" module type to "Stable_without_comparator", in anticipation of requiring a comparator and comparator witness in the module type called "Stable".

  This is the first in a chain of features which will push us towards including comparator witnesses in stable type definitions, so that defining stable sets and maps is easier.

• Added back a "Stable" module type that now includes a comparator witness type and corresponding comparator value.

  Defining the comparator stuff in a stable way will allow us to define stable set and map types that are equivalent to their non-stable counterparts. (See child features)

  Along the way, added Identifiable.Make_using_comparator to the family of _using_comparator functors, to help with this task.

• Introduce a Blang submodule which has infix operators and other convenient shortcuts.

  In a world where increasingly we are writing configuration as OCaml code, it seems right that we should focus not only on the sexp DSL but the OCaml one as well.

• Moved the Stable Comparable.V1.Make into comparable.ml (as usual) rather than in stable_containers.ml.

• Renamed:

  lib/core_kernel/test --> lib/core_kernel/test-bin

  since these directories contain executables to run rather than libraries with standard unit tests. This is in preparation for moving the standard unit tests to a more "normal" test directory.

• Move unit tests from core_kernel/src to core_kernel/test.
• Split out a sub-signature of Binable.S containing only functions, for use in the definition of recursive modules.
• Split out a *_using_comparator variant of the functor Comparable.Map_and_set_binable.
• Automatic, randomized testing based on Haskell's "Quickcheck" library.

• Add a flag to Quickcheck.test_no_duplicates to allow some percentage of values to be duplicates.

  This is primarily in preparation for changing the "no-duplicates" tests for random function generation to be extensional (based on results for a fixed set of inputs) rather than intensional (based on sexps constructed by Quickcheck). This design change is also a good axis of flexibility in general.

• Remove the exception declarations in quickcheck.ml and use Error.raise_s and %message instead.
• In quickcheck.ml, swap the order of module Observer and module Generator. This feature just swaps them and makes no other change. This is in preparation for an upcoming feature that will introduce dependency of Generator on Observer, which will be easier to read as an incremental diff.
• Add a top-level filter option to Quickcheck.test. The behavior of top-level filter is a lot easier to reason about than nested recursive filters, especially with respect to attempts-vs-failures. This is in preparation for removing generator "failure" as a first-order concept and simplifying the model of generators.
• Add Container.S0 + a sub function to substring stuff

• Adds phantom type to Validated as witness of invariant

  The witness prevents types from different applications of the Validated functors from unifying with one another.

• Added Int.Stable to Core.Stable.
• Added Fqueue.of_list, an inverse of Fqueue.to_list.
• Added Int.Stable.V1, implementing Comparable.Stable.V1.S, so that one can use Int.V1.Map.t and Int.V1.Set.t in stable types.
• Remove the Quickcheck.Generator.fn_with_sexp type and all the sexp arguments to Quickcheck.Observer.t constructors.
• Added String.Stable.V1, implementing Comparable.Stable.V1.S, so that one can use String.V1.Map.t and String.V1.Set.t in stable types.

• Added to Monad.Syntax.Let_syntax:

  val return : 'a -> 'a t

  so that when one does:

  open Some_random_monad.Let_syntax

  return is in scope.

  Most of the diff is the addition of let return = return in the necessary places. The rest is changing uses of return to Deferred.return in contexts where some other monad was opened, shadowing Deferred.return.

• Implement Sequence.of_lazy to allow entirely lazily-computed sequences (rather than just lazily computing the elements).
• Add Array.random_element

• Container.fold_result-and-until

  Containers learned to fold using a f that returns a Result.t, bailing out early if necessary

  Containers also learned to fold_until: fold using a f that returns

  Continue of 'a | Stop of 'b

  terminating the fold when f returns Stop _.

  fold_until evaluates to Finished of 'a if f never returns Stop _ Stopped_early of 'b when the f returns Stop _

• Deprecates most of the In_channel and Out_channel equivalents in Pervasives, deleting a little bit of garbage along the way

• Emulate 63bit integers on 32bit platform so that we have same semantic in 32bit and 64bit arch.

  • same bin_prot
  • same max_value/min_value

  We use the same kind of encoding as native int on 64bit architecture (with a twist). A 63bit integer is a 64bit integer with its bits shifted to the left. (In OCaml, in 64 bit, an int is a 64 bit integer shifted to the left, with the immediate bit set to 1).

• Add Fqueue.map implementation.

• This is the followup to the earlier deprecation of Map.iter and Hashtbl.iter.

  • Changes the deprecated Map.iter and Hashtbl.iter and Map.filter functions to iterate over values only instead of both keys and values. (For the old behavior, use the non-deprecated iteri or filteri functions instead).
  • Analogous changes have been made to Deferred_map, Multi_map, Total_map, Fold_map, Extended_hashtbl, Pooled_hashtbl, Bounded_int_table, Imm_hash.

  This may break code that upgrades directly to this version from before these functions were deprecated, or code that continued to use Map.iter or Hashtbl.iter or Map.filter after deprecation. As mentioned above, use iteri and filteri instead.

  Additionally:

  • Deprecates Hashtbl.iter_vals. (Use Hashtbl.iter instead.)
  • Adds some missing functions to a few of the minor associative container classes.

• Add popcount (count # of 1 bits in representation) operation for int types.

  ┌───────────────────────────────────────┬──────────┬────────────┐ │ Name │ Time/Run │ Percentage │ ├───────────────────────────────────────┼──────────┼────────────┤ │ int_math.ml popcount_bench_overhead │ 2.11ns │ 57.12% │ │ int_math.ml int_popcount │ 3.17ns │ 85.72% │ │ int_math.ml int32_popcount │ 3.70ns │ 99.95% │ │ int_math.ml int64_popcount │ 3.70ns │ 99.96% │ │ int_math.ml nativeint_popcount │ 3.70ns │ 100.00% │ └───────────────────────────────────────┴──────────┴────────────┘

• Fix Time_ns.next_multiple to use integer division instead of floating point division.

• Move the contents of time_ns.mli to time_ns_intf.ml in both core and core_kernel, and clean up the presentation of the signatures a bit in both.

  Also adds Int63 to Std_internal.

• Move Unit_of_time out of Core.Time.Span and into Core_kernel. Move Core.Time_ns.Span.{to,of}_unit_of_time into Core_kernel.Time_ns.Span.
• Add a stable submodule to Byte_units
• Deleted Core_kernel.Flat_queue, which is unused.
• Deprecated Array.empty, in favor of || .
• Add some useful functions to Or_error

• Improve the interface and error message of Quickcheck.test_no_duplicates.

  The function no longer supports equality-based duplicate tests, which were unused and inefficient. It only supports compare-based tests.

  The error message now groups values with the number of duplicates produced, sorted in descending order so the most common duplicates come early. It also includes all duplicates generated up to the maximum trial count, rather than stopping as soon as the cutoff threshold is reached.

• Now that the Decimal module no longer means "decimal" (it's only functionality is to change sexp converters and bin-io to rejecting nan and inf values), rename it as Float_with_finite_only_serialization, to better befit its semantics.

  In addition to a pile of renames, this also changes many references to Decimal.t or decimal in mlis to float, since the decimal type didn't really convey any extra semantics about the type; just about the serializers.

• Prompted by the embarrassing Stack segfault bug we decided to put the unsafe Obj.magic stuff present in various array-backed data structures (Queue, Deque, Stack) in a single place.

  We introduce the following new modules:

  • Uniform_array: a wrapper on top of Obj_array that makes the elements homogeneous. It's equivalent to Array in semantics, but differs in performance and in how it interacts with Obj.magic.
  • Option_array: 'a Option_array.t is semantically equivalent to 'a Option.t Array.t, but avoids allocation of Some values, instead representing None by Obj.magic'ing a distinguished value.

  On top of making things safer, this feature happens to improve performance:

  Original benchmarks:

  $ ./array_queue_old.exe -quota 2 Estimated testing time 1.43333m (43 benchmarks x 2s). Change using -quota SECS. ┌────────────────────────────────────┬─────────────────┬─────────────┬───────────────┬──────────┬────────────┐ │ Name │ Time/Run │ mWd/Run │ mjWd/Run │ Prom/Run │ Percentage │ ├────────────────────────────────────┼─────────────────┼─────────────┼───────────────┼──────────┼────────────┤ │ enqueue_dequeue_mixed │ 36_016_512.46ns │ 999_835.00w │ 2_096_659.14w │ 7.14w │ 100.00% │ │ pipeline │ 175.89ns │ │ │ │ │ │ blit_transfer 0 │ 7.39ns │ │ │ │ │ │ blit_transfer 1 │ 78.26ns │ │ │ │ │ │ blit_transfer 2 │ 93.91ns │ │ │ │ │ │ blit_transfer 4 │ 127.53ns │ │ │ │ │ │ blit_transfer 8 │ 195.41ns │ │ │ │ │ │ blit_transfer 16 │ 351.20ns │ │ │ │ │ │ blit_transfer 32 │ 647.15ns │ │ │ │ │ │ blit_transfer 64 │ 1_168.12ns │ │ │ │ │ │ blit_transfer 128 │ 2_288.00ns │ │ │ │ │ │ enqueue 10 │ 440.79ns │ 42.00w │ │ │ │ │ enqueue 1000000 │ 23_268_213.72ns │ 526.00w │ 2_096_658.71w │ 6.71w │ 64.60% │ │ Queue.enqueue + dequeue:1 │ 15.59ns │ │ │ │ │ │ Queue.enqueue + dequeue:2 │ 14.38ns │ │ │ │ │ │ Queue.enqueue + dequeue:4 │ 15.23ns │ │ │ │ │ │ Queue.enqueue + dequeue:8 │ 16.40ns │ │ │ │ │ │ Queue.enqueue + dequeue:16 │ 16.33ns │ │ │ │ │ │ Queue.enqueue + dequeue:32 │ 16.44ns │ │ │ │ │ │ Queue.enqueue + dequeue:64 │ 16.54ns │ │ │ │ │ │ Queue.enqueue + dequeue:128 │ 15.18ns │ │ │ │ │ │ Queue.enqueue + dequeue:256 │ 16.58ns │ │ │ │ │ │ Queue.enqueue + dequeue:512 │ 16.65ns │ │ │ │ │ │ Linked_queue.enqueue + dequeue:1 │ 53.33ns │ 3.00w │ 3.02w │ 3.02w │ │ │ Linked_queue.enqueue + dequeue:2 │ 53.95ns │ 3.00w │ 3.02w │ 3.02w │ │ │ Linked_queue.enqueue + dequeue:4 │ 54.64ns │ 3.00w │ 3.02w │ 3.02w │ │ │ Linked_queue.enqueue + dequeue:8 │ 55.18ns │ 3.00w │ 3.02w │ 3.02w │ │ │ Linked_queue.enqueue + dequeue:16 │ 55.57ns │ 3.00w │ 3.02w │ 3.02w │ │ │ Linked_queue.enqueue + dequeue:32 │ 55.78ns │ 3.00w │ 3.03w │ 3.03w │ │ │ Linked_queue.enqueue + dequeue:64 │ 55.67ns │ 3.00w │ 3.02w │ 3.02w │ │ │ Linked_queue.enqueue + dequeue:128 │ 56.64ns │ 3.00w │ 3.03w │ 3.03w │ │ │ Linked_queue.enqueue + dequeue:256 │ 56.28ns │ 3.00w │ 3.03w │ 3.03w │ │ │ Linked_queue.enqueue + dequeue:512 │ 56.15ns │ 3.00w │ 3.03w │ 3.03w │ │ │ Deque.enqueue + dequeue:1 │ 16.36ns │ │ │ │ │ │ Deque.enqueue + dequeue:2 │ 15.06ns │ │ │ │ │ │ Deque.enqueue + dequeue:4 │ 15.07ns │ │ │ │ │ │ Deque.enqueue + dequeue:8 │ 17.13ns │ │ │ │ │ │ Deque.enqueue + dequeue:16 │ 17.22ns │ │ │ │ │ │ Deque.enqueue + dequeue:32 │ 17.37ns │ │ │ │ │ │ Deque.enqueue + dequeue:64 │ 17.23ns │ │ │ │ │ │ Deque.enqueue + dequeue:128 │ 16.69ns │ │ │ │ │ │ Deque.enqueue + dequeue:256 │ 16.99ns │ │ │ │ │ │ Deque.enqueue + dequeue:512 │ 17.52ns │ │ │ │ │ └────────────────────────────────────┴─────────────────┴─────────────┴───────────────┴──────────┴────────────┘

  New benchmarks:

  ./array_queue.exe -quota 2; Estimated testing time 1.43333m (43 benchmarks x 2s). Change using -quota SECS. ┌────────────────────────────────────┬─────────────────┬─────────────┬───────────────┬──────────┬────────────┐ │ Name │ Time/Run │ mWd/Run │ mjWd/Run │ Prom/Run │ Percentage │ ├────────────────────────────────────┼─────────────────┼─────────────┼───────────────┼──────────┼────────────┤ │ enqueue_dequeue_mixed │ 28_693_436.79ns │ 999_835.00w │ 2_096_658.82w │ 6.82w │ 100.00% │ │ pipeline │ 163.08ns │ │ │ │ │ │ blit_transfer 0 │ 7.40ns │ │ │ │ │ │ blit_transfer 1 │ 78.14ns │ │ │ │ │ │ blit_transfer 2 │ 86.72ns │ │ │ │ │ │ blit_transfer 4 │ 105.65ns │ │ │ │ │ │ blit_transfer 8 │ 143.44ns │ │ │ │ │ │ blit_transfer 16 │ 219.64ns │ │ │ │ │ │ blit_transfer 32 │ 386.75ns │ │ │ │ │ │ blit_transfer 64 │ 692.08ns │ │ │ │ │ │ blit_transfer 128 │ 1_331.16ns │ │ │ │ │ │ enqueue 10 │ 393.34ns │ 42.00w │ │ │ │ │ enqueue 1000000 │ 18_775_585.92ns │ 526.00w │ 2_096_658.55w │ 6.55w │ 65.44% │ │ Queue.enqueue + dequeue:1 │ 14.53ns │ │ │ │ │ │ Queue.enqueue + dequeue:2 │ 13.73ns │ │ │ │ │ │ Queue.enqueue + dequeue:4 │ 10.61ns │ │ │ │ │ │ Queue.enqueue + dequeue:8 │ 14.56ns │ │ │ │ │ │ Queue.enqueue + dequeue:16 │ 12.14ns │ │ │ │ │ │ Queue.enqueue + dequeue:32 │ 11.10ns │ │ │ │ │ │ Queue.enqueue + dequeue:64 │ 11.22ns │ │ │ │ │ │ Queue.enqueue + dequeue:128 │ 11.52ns │ │ │ │ │ │ Queue.enqueue + dequeue:256 │ 11.52ns │ │ │ │ │ │ Queue.enqueue + dequeue:512 │ 11.00ns │ │ │ │ │ │ Linked_queue.enqueue + dequeue:1 │ 52.42ns │ 3.00w │ 3.03w │ 3.03w │ │ │ Linked_queue.enqueue + dequeue:2 │ 52.52ns │ 3.00w │ 2.98w │ 2.98w │ │ │ Linked_queue.enqueue + dequeue:4 │ 52.68ns │ 3.00w │ 2.98w │ 2.98w │ │ │ Linked_queue.enqueue + dequeue:8 │ 53.21ns │ 3.00w │ 2.98w │ 2.98w │ │ │ Linked_queue.enqueue + dequeue:16 │ 69.40ns │ 3.00w │ 2.97w │ 2.97w │ │ │ Linked_queue.enqueue + dequeue:32 │ 55.23ns │ 3.00w │ 3.02w │ 3.02w │ │ │ Linked_queue.enqueue + dequeue:64 │ 54.24ns │ 3.00w │ 3.02w │ 3.02w │ │ │ Linked_queue.enqueue + dequeue:128 │ 55.25ns │ 3.00w │ 3.02w │ 3.02w │ │ │ Linked_queue.enqueue + dequeue:256 │ 55.10ns │ 3.00w │ 3.02w │ 3.02w │ │ │ Linked_queue.enqueue + dequeue:512 │ 55.47ns │ 3.00w │ 3.02w │ 3.02w │ │ │ Deque.enqueue + dequeue:1 │ 11.73ns │ │ │ │ │ │ Deque.enqueue + dequeue:2 │ 11.63ns │ │ │ │ │ │ Deque.enqueue + dequeue:4 │ 11.65ns │ │ │ │ │ │ Deque.enqueue + dequeue:8 │ 12.86ns │ │ │ │ │ │ Deque.enqueue + dequeue:16 │ 12.86ns │ │ │ │ │ │ Deque.enqueue + dequeue:32 │ 12.99ns │ │ │ │ │ │ Deque.enqueue + dequeue:64 │ 12.86ns │ │ │ │ │ │ Deque.enqueue + dequeue:128 │ 12.91ns │ │ │ │ │ │ Deque.enqueue + dequeue:256 │ 12.81ns │ │ │ │ │ │ Deque.enqueue + dequeue:512 │ 12.85ns │ │ │ │ │ └────────────────────────────────────┴─────────────────┴─────────────┴───────────────┴──────────┴────────────┘

• Array.truncate makes it really hard to use unsafe_get safely: even things in Array module itself fail to do it properly.

  For example, this thing reliably segfaults:

        let a = Array.create ~len:2 "foo" in
  Array.iter a ~f:(fun s ->
    printf "%s" s;
    Array.truncate a ~len:1)

  We should rename truncate to unsafe_truncate and stop claiming that the array length is allowed to change over time.

• Byte_units.Stable uses type substitution, not equality, so there is no Byte_units.Stable.V1.t

  Fix this by changing to type equality

• Remove Quickcheck.Generator.failure.

  This is in preparation for moving to a model of generators for which there is no notion of "failure".

• Change Int*.gen* to use a uniform distribution.

  A simple distribution is easier to reason about, and does not require tricky tuning. The previous distribution was tuned to hit some notion of "common values", and so that it might frequently produce duplicates with itself, which was arbitrary, hard to tune, and meant it spent a lot of time generating only border cases.

  While some use cases might still want some border-case tuning, uniform distributions are probably a better basic building block, and are much easier to implement.

113.33.01

• Fix segfault in [Stack]
• Fix BSD build problem related to endian.h

113.33.00

• Rename Tuple.T2.map1 and Tuple.T2.map2 to map_fst and map_snd, following the convention of the accessors. Usually, numeric suffixes mean higher arities, not different fields.

• After discussion, rather than checking for overflow in Time_ns arithmetic, clarify that it's silently ignored. (Subsequent conversions may or may not notice.)

  We did identify the set of functions to document:

        Time_ns.Span.((+), (-), scale_int, scale_int63, create, of_parts)
  Time_ns.(add, sub, diff, abs_diff, next_multiple)

  Added Core_int63.(add_with_overflow_exn, abs_with_overflow_exn, neg_with_overflow_exn) in the course of abandoned work on overflow detection in Time_ns. These may be useful. mul_with_overflow_exn was abandoned because

  1. it's a lot of work to review
  2. there's a better approach: Go to the C level and check the high word of the product from the IMUL instruction, which is both simpler and faster.

• Changes related to Float.sign

  Float.sign currently maps -1e-8 and nan to Zero. Some users don't expect this. This feature addresses that via the following changes:

  • Float.sign renamed to Float.robust_sign. (Float.sign is still present, but deprecated.)
  • Float.sign_exn introduced which does not use robust comparison, and which raises on nan.
  • Sign pulled out of Float and made its own module, and sign : t -> Sign.t added to Comparable.With_zero. In particular, Int.sign : int -> Sign.t now exists. (In looking at existing uses of Float.sign, there was at least one case where the user was converting an int to a float to get its sign. That ended up being deleted, but it still seems desirable to have Int.sign. There were also record types with a field sign : Float.Sign.t where logically the type has no real connection to Float.)
  • Uses of Float.robust_sign revisited to make sure that's the behavior we want.
• Added Quickcheck tests for Hashtbl functions, using Map as a point of comparison. A lot of Hashtbl functions did not have tests, so I used an interface trick to require every function to show up in the test module. The easiest way to write a readable test for every function was to compare it to a similar datatype, so I went with Map.
• Allow clients of Hashtbl.incr and Hashtbl.decr to specify entries should be removed if the value is 0
• The type of symmetric_diff has a typo in it.
• Switched Timing_wheel_ns to use %message and %sexp.

• Improved the error message raised by Timing_wheel.add and reschedule if the supplied time is before the start of the current interval.

  Previously, the error message was something like:

  ("Timing_wheel.Priority_queue got invalid key" (key ...) (timing_wheel ...))

  Now, it will be like:

  ("Timing_wheel cannot schedule alarm before start of current interval" (at ...) (now_interval_num_start ...))

  The old message was confusing because key is less understandable than at, and because it didn't make clear that this is a usage error, as opposed to a Timing_wheel bug.

  Implementing this efficiently required adding a field to timing wheel:

  mutable now_interval_num_start : Time_ns.t

  so that the check done by add is fast.

• Add Comparable.Make_using_comparator.

  Since Map and Set already have Make_using_comparator functors, there's no particular reason for Comparable not to have one.

  More concretely, this will be useful when (if) we add stable containers to core: we can add a stable version of Comparable.Make, then pass the resulting comparator into the unstable functor to get equal types.

• Add a Total_map.Make_using_comparator functor to allow the creation of total maps which are type equivalent to regular maps.

• Change default major heap increments to be % of the heap size instead of a constant increment

  Also changed type of overhead parameters to Percent.t

• Remove modules Core.Std.Sexp.Sexp_{option,list,array,opaque}, which used to allow binability for types sexp_option, sexp_list, etc., but now serve no purpose.

• Change the signature of the output of Comparable.Make{,_binable}_using_comparator to not include comparator_witness.

  This is so that code like this will compile:

  include T include Comparable.Make_using_comparator (T)

• Changed Timing_wheel_ns so that it only supports times at or after the epoch, i.e. only non-negative Time_ns.t values. Times before the epoch aren't needed, and supporting negative times unnecessarily complicates the implementation.

  Removed fields from Timing_wheel_ns.t that are now constants:

  ; min_time : Time_ns.t ; max_time : Time_ns.t ; min_interval_num : Interval_num.t

• In Timing_wheel.t, cache alarm_upper_bound, which allows us to give an improved error message when Timing_wheel.add is called with a time beyond alarm_upper_bound.

• Add Sequence.merge_with_duplicates

  (** merge_with_duplicates_element t1 t2 ~cmp interleaves the elements of t1 and t2. Where the two next available elements of t1 and t2 are unequal according to cmp, the smaller is produced first. *) val merge_with_duplicates : 'a t -> 'a t -> cmp:('a -> 'a -> int)

  module Merge_with_duplicates_element : sig type 'a t = | Left of 'a | Right of 'a | Both of 'a * 'a @@deriving bin_io, compare, sexp end

• Add Set.merge_to_sequence

  (** Produces the elements of the two sets between greater_or_equal_to and less_or_equal_to in order, noting whether each element appears in the left set, the right set, or both. In the both case, both elements are returned, in case the caller can distinguish between elements that are equal to the sets' comparator. Runs in O(length t + length t'). *)

  val merge_to_sequence : ?order : Increasing (** default *) | Decreasing -> ?greater_or_equal_to : 'a -> ?less_or_equal_to : 'a -> ('a, 'cmp) t -> ('a, 'cmp) t -> 'a Merge_to_sequence_element.t Sequence.t

  module Merge_to_sequence_element : sig type 'a t = 'a Sequence.Merge_with_duplicates_element.t = | Left of 'a | Right of 'a | Both of 'a * 'a @@deriving bin_io, compare, sexp end

• Make Hashtbl.merge_into take explicit variant type

  type 'a merge_into_action = Remove | Set_to of 'a

  val merge_into : f:(key:'k key -> 'a1 -> 'a2 option -> 'a2 merge_into_action) -> src:('k, 'a1) t -> dst:('k, 'a2) t -> unit

  The f used to return 'a2 option, and it was unclear whether None meant do nothing or remove. (It meant do nothing.)

• Some red-black tree code showed a 15-20% speedup by inlining the comparison, rather than relying on the caml_int_compare external call. I've tried to cleanly apply it to Core_int (though it can't really be done without an Obj.magic), though this may be a better fit for a compiler patch to treat int comparisons as an intrinsic.

  Added an inline test for boundary cases. Presently it returns the identical values to caml_int_compare, though probably it should only be held to same sign results.

• Rename Hashtbl.[filter_]replace_all[i] to Hashtbl.[filter_]map[i]_inplace.
• Import debug.ml from incremental.
• Float_intf used 'float' sometimes where it means 't'.
• Added Identifiable.Make_with_comparator, for situations where you want to preserve the already known comparator, for example to define stable sets and maps that are type equivalent to unstable types and sets.

113.24.00

• Add Container.Make0 for monomorphic container types.
• Improved the performance of the implementation of Bounded_int_table.find.
• Switched to ppx
• Remove references to Core_list from Sequence.
• Added functions to Bigstring and Iobuf for reading unsigned 64-bit integers.
• Move Comparable.bound to Maybe_bound.t. The purpose is to break up dependencies between the two.
• Doubly_linked allocated during iteration. This became a large source of allocation for simple benchmarks like TCP pingpong (async/bench/pingpong). Some unnecessary allocations have been removed.
• Added Timing_wheel.next_alarm_fires_at_exn, which is useful to avoid allocation when you know the timing wheel isn't empty.
• Make versions of Binary_searchable.Make* that don't require a For_test argument. This allows Binary_searchable.Make to be used for types that don't easily convert from arrays.

• Add Quickcheckable interface to Core and move generators/observers into type modules.

  Renames core_list.ml to core_list0.ml, then adds a new core_list.ml with quickcheck generators and observers. This allows quickcheck.ml to use core_list0.ml without a dependency cycle.

  The feature also moves the contents of quickcheck.mli into quickcheck_intf.ml.

• Made Core.Unpack_buffer.Unpack_one.t be a unary type rather than a binary one, by hiding its partial_unpack type under an existential.

  This makes it possible to make Unpack_one into a monad because we can combine two Unpack_one.t's with different partial_unpack types into a new Unpack_one.t with a different partial_unpack type.

• https://github.com/janestreet/core_kernel/pull/20 Core.Std module is not found when compiling lib_test/pool_caml_modify_check.ml.

• Added an optional argument ?key_order for specifying the order of Map.to_alist output: either Increasing or Decreasing.

  The default key order is no longer left unspecified: we're now committed to the `Increasing, which was the old behavior.

• Add Sexpable.Of_sexpable2 functor, for symmetry with Binable.Of_binable2. Add sexpable.mli
• Added a function for sequencing computations stored in a total map: Total_map.sequence.
• Added Core.Bus, a publisher/subscriber system within the memory space of the program. This is a synchronous version of Async.Bus.
• Added Core_map.fold2 (fold based on the contents of two maps side-by-side).
• Core.Interfaces defines the Unit module type to be sig end. Increase uniformity with its other definitions by defining it to be Unit.S instead.
• Adapt Core_random.int to accept larger values than 1 lsl 30.
• Mark the Sexpable.Of_* and Binable.Of_* functors as stable.
• In Core_char.int_is_ok, used by of_int and of_int_exn, use int compare instead of polymorphic compare.
• Fix a few files where toplevel side effects might not be running when we don't pack libraries anymore and use -no-alias-deps.
• In Char.For_quickcheck, memoize construction of the filtered chars generators, since if they are used once, they are likely to be used many times, and the construction is costly compared to generating a single char.
• Extend Core_map to implement quickcheckable Extend Core_set to implement quickcheckable
• In Avltree.add, replace ?(replace = true) with ~replace. This both makes the behavior more explicit, and saves some allocation occasionally.
• Reimplement Avltree.iter directly, rather than using fold, which requires allocating a closure. This winds up being expensive during Hashtbl.iter.

• Add a function in Blang to deal with boolean expressions E representing the membership of elements in a set, given a universe U and a function projecting each atoms of E to a subset of U.

  {Blang.eval_set ~universe:js_tech resolve_named_set ("(or (and has-blue-eyes has-brown-hair) (and has-brown-eyes has-blue-hair))" |> Sexp.of_string |> t_of_sexp)}

• Expose more functions in univ_map interface
• Made Random.self_init by default raise if used in inline tests. One can opt out by passing ~allow_in_tests:true.
• In core_hashtbl.ml, maybe_resize_table allocates the same closure in each iteration of a for loop. Allocate it just once.
• Hashtbl.remove_one and Hashtbl.remove_multi are the same function, written twice. Remove remove_one and replace uses with remove_multi.

• Bigstring.unsafe_{get,set}-{,u}int8 used the generic bigarray access function without a type annotation. As a result the compiler generated a call to the generic C function.

  Fixed this by adding type annotations.

• Add new functions to map that add common missing functionality and/or that makes the interface more uniform and consistent with other container modules.

• Made Unpack_buffer.Unpack_one monadic so that users can easily compose file parsers

  Added a couple simple parsers as examples and for testing.

• Avoid use of polymorphic compare in Quickcheck. Make Quickcheck.Generator.bind_choice lazy: do not eagerly descend into all branches.

  Reduces memory overhead by setting a threshold on the probability of choices that are remembered and discarded by Quickcheck.iter and friends.

  Motivation: Currently, Quickcheck.iter and related functions guarantee never to repeat a choice from a generator. This winds up recording every choice ever made, which for a lot of generators is a prohibitive cost in space, and most of the recorded values are very unlikely to be repeated anyway.

  Implementation: This feature sets a probability threshold below which choices will not be remembered. Choosing a fairly low, but still non-zero, threshold means values are still very unlikely to be repeated, but memory usage stays low.

  As of this version, the benefits of "forgetting" unlikely-to-repeat values:

  ┌──────────────────────────────────────────┬──────────┬─────────┬──────────┬──────────┬────────────┐ │ Name │ Time/Run │ mWd/Run │ mjWd/Run │ Prom/Run │ Percentage │ ├──────────────────────────────────────────┼──────────┼─────────┼──────────┼──────────┼────────────┤ │ quickcheck.ml:Quickcheck.iter remember │ 20.26ms │ 16.33Mw │ 100.85kw │ 100.85kw │ 100.00% │ │ quickcheck.ml:Quickcheck.iter forget │ 17.65ms │ 16.21Mw │ 34.83kw │ 34.83kw │ 87.10% │ └──────────────────────────────────────────┴──────────┴─────────┴──────────┴──────────┴────────────┘

• Optimizations to:

  • various Float.t validation functions
  • various functions in Validate
  • List.fold_right
• Made the type of Option.compare compatible with @@deriving compare.
• Fixed an example code fragment in a comment in applicative_intf.ml

• In Core_hashtbl, the add_worker function used a bool ref both internally and to pass to Avltree to track whether a new key is added. This was allocated on every call to add or set, and set didn't even use its contents.

  This version pre-allocates the bool ref inside each Core_hashtbl.t and reuses it. It still can't be a mutable field because it does need to be passed to Avltree.

  After change:

  ┌───────────────────────────────────────────────────┬──────────────┬────────────┬────────────┬────────────┬────────────┐ │ Name │ Time/Run │ mWd/Run │ mjWd/Run │ Prom/Run │ Percentage │ ├───────────────────────────────────────────────────┼──────────────┼────────────┼────────────┼────────────┼────────────┤ │ Hashtbl.set no collisions │ 84.73ns │ 3.00w │ 0.83w │ 0.83w │ 0.01% │ │ Hashtbl.set w/ collisions │ 112.46ns │ │ │ │ 0.02% │ │ Hashtbl.change no collisions │ 82.74ns │ 3.50w │ 0.53w │ 0.53w │ 0.01% │ │ Hashtbl.change w/ collisions │ 191.50ns │ 4.56w │ 1.15w │ 1.15w │ 0.03% │ │ Hashtbl.merge no collisions │ 292_976.43ns │ 26_669.00w │ 15_381.62w │ 12_305.62w │ 48.52% │ │ Hashtbl.merge w/ collisions │ 603_822.86ns │ 33_001.00w │ 20_037.22w │ 16_961.22w │ 100.00% │ │ Hashtbl.add_exn no resize, no collisions │ 80_992.57ns │ 3_088.00w │ 4_102.63w │ 3_077.63w │ 13.41% │ │ Hashtbl.add_exn no resize, w/ collisions │ 178_080.05ns │ 4_621.00w │ 5_668.61w │ 4_643.61w │ 29.49% │ │ Hashtbl.add_exn w/ resize, no collisions │ 176_442.98ns │ 16_403.00w │ 9_222.64w │ 6_148.64w │ 29.22% │ │ Hashtbl.add_exn w/ resize, w/ collisions │ 297_577.29ns │ 19_472.00w │ 12_292.13w │ 9_218.13w │ 49.28% │ └───────────────────────────────────────────────────┴──────────────┴────────────┴────────────┴────────────┴────────────┘

  Before change:

  ┌───────────────────────────────────────────────────┬──────────────┬────────────┬────────────┬────────────┬────────────┐ │ Name │ Time/Run │ mWd/Run │ mjWd/Run │ Prom/Run │ Percentage │ ├───────────────────────────────────────────────────┼──────────────┼────────────┼────────────┼────────────┼────────────┤ │ Hashtbl.set no collisions │ 104.88ns │ 5.00w │ 1.26w │ 1.26w │ 0.02% │ │ Hashtbl.set w/ collisions │ 114.33ns │ 2.00w │ │ │ 0.02% │ │ Hashtbl.change no collisions │ 85.79ns │ 4.50w │ 0.58w │ 0.58w │ 0.02% │ │ Hashtbl.change w/ collisions │ 198.75ns │ 5.56w │ 1.28w │ 1.28w │ 0.04% │ │ Hashtbl.merge no collisions │ 307_857.59ns │ 31_787.00w │ 15_380.91w │ 12_304.91w │ 58.19% │ │ Hashtbl.merge w/ collisions │ 529_054.02ns │ 38_119.00w │ 20_015.32w │ 16_939.32w │ 100.00% │ │ Hashtbl.add_exn no resize, no collisions │ 77_708.20ns │ 5_135.00w │ 4_101.83w │ 3_076.83w │ 14.69% │ │ Hashtbl.add_exn no resize, w/ collisions │ 180_950.23ns │ 6_668.00w │ 5_638.77w │ 4_613.77w │ 34.20% │ │ Hashtbl.add_exn w/ resize, no collisions │ 177_492.82ns │ 19_476.00w │ 9_237.07w │ 6_163.07w │ 33.55% │ │ Hashtbl.add_exn w/ resize, w/ collisions │ 285_298.72ns │ 22_545.00w │ 12_330.90w │ 9_256.90w │ 53.93% │ └───────────────────────────────────────────────────┴──────────────┴────────────┴────────────┴────────────┴────────────┘

• In Core_hashtbl.add_worker, removed a match that avoided calling Avltree.add, but actually did hurt performance overall.

  Perhaps at some point before cross-module inlining, this was a helpful optimization. Right now it bypasses the mutation inside Avltree, so replacing a value in a non-colliding bucket (a Leaf) causes unnecessary re-allocation of the leaf.

  After changes:

  ┌───────────────────────────────────────────────────┬──────────────┬────────────┬────────────┬────────────┬────────────┐ │ Name │ Time/Run │ mWd/Run │ mjWd/Run │ Prom/Run │ Percentage │ ├───────────────────────────────────────────────────┼──────────────┼────────────┼────────────┼────────────┼────────────┤ │ Hashtbl.set no collisions │ 52.19ns │ 2.00w │ │ │ │ │ Hashtbl.set w/ collisions │ 112.04ns │ 2.00w │ │ │ 0.02% │ │ Hashtbl.change no collisions │ 87.25ns │ 4.50w │ 0.58w │ 0.58w │ 0.02% │ │ Hashtbl.change w/ collisions │ 195.85ns │ 5.56w │ 1.29w │ 1.29w │ 0.04% │ │ Hashtbl.merge no collisions │ 308_164.10ns │ 31_787.00w │ 15_380.91w │ 12_304.91w │ 58.48% │ │ Hashtbl.merge w/ collisions │ 526_914.80ns │ 38_119.00w │ 20_013.81w │ 16_937.81w │ 100.00% │ │ Hashtbl.add_exn no resize, no collisions │ 76_983.60ns │ 5_135.00w │ 4_100.44w │ 3_075.44w │ 14.61% │ │ Hashtbl.add_exn no resize, w/ collisions │ 174_712.92ns │ 6_668.00w │ 5_667.47w │ 4_642.47w │ 33.16% │ │ Hashtbl.add_exn w/ resize, no collisions │ 176_681.57ns │ 19_476.00w │ 9_231.75w │ 6_157.75w │ 33.53% │ │ Hashtbl.add_exn w/ resize, w/ collisions │ 280_448.62ns │ 22_545.00w │ 12_293.32w │ 9_219.32w │ 53.22% │ └───────────────────────────────────────────────────┴──────────────┴────────────┴────────────┴────────────┴────────────┘

  Before changes:

  ┌───────────────────────────────────────────────────┬──────────────┬────────────┬────────────┬────────────┬────────────┐ │ Name │ Time/Run │ mWd/Run │ mjWd/Run │ Prom/Run │ Percentage │ ├───────────────────────────────────────────────────┼──────────────┼────────────┼────────────┼────────────┼────────────┤ │ Hashtbl.set no collisions │ 104.88ns │ 5.00w │ 1.26w │ 1.26w │ 0.02% │ │ Hashtbl.set w/ collisions │ 114.33ns │ 2.00w │ │ │ 0.02% │ │ Hashtbl.change no collisions │ 85.79ns │ 4.50w │ 0.58w │ 0.58w │ 0.02% │ │ Hashtbl.change w/ collisions │ 198.75ns │ 5.56w │ 1.28w │ 1.28w │ 0.04% │ │ Hashtbl.merge no collisions │ 307_857.59ns │ 31_787.00w │ 15_380.91w │ 12_304.91w │ 58.19% │ │ Hashtbl.merge w/ collisions │ 529_054.02ns │ 38_119.00w │ 20_015.32w │ 16_939.32w │ 100.00% │ │ Hashtbl.add_exn no resize, no collisions │ 77_708.20ns │ 5_135.00w │ 4_101.83w │ 3_076.83w │ 14.69% │ │ Hashtbl.add_exn no resize, w/ collisions │ 180_950.23ns │ 6_668.00w │ 5_638.77w │ 4_613.77w │ 34.20% │ │ Hashtbl.add_exn w/ resize, no collisions │ 177_492.82ns │ 19_476.00w │ 9_237.07w │ 6_163.07w │ 33.55% │ │ Hashtbl.add_exn w/ resize, w/ collisions │ 285_298.72ns │ 22_545.00w │ 12_330.90w │ 9_256.90w │ 53.93% │ └───────────────────────────────────────────────────┴──────────────┴────────────┴────────────┴────────────┴────────────┘

• Add new functions to hashtbl that add common missing functionality and/or that makes the interface more uniform and consistent with other container modules.
• Add a bunch of functions to list and array that add common missing functionality and/or that make their interfaces more uniform and consistent with other container modules.

• Rewrite Hashtbl.merge to be simpler and faster.

  After changes:

  ┌──────────────────────────────────────┬──────────┬─────────┬──────────┬──────────┬────────────┐ │ Name │ Time/Run │ mWd/Run │ mjWd/Run │ Prom/Run │ Percentage │ ├──────────────────────────────────────┼──────────┼─────────┼──────────┼──────────┼────────────┤ │ Hashtbl.merge no collisions │ 172.57us │ 17.44kw │ 9.22kw │ 7.69kw │ 48.76% │ │ Hashtbl.merge w/ collisions │ 284.55us │ 20.61kw │ 11.53kw │ 9.99kw │ 80.41% │ │ Pooled_hashtbl.merge no collisions │ 260.57us │ 5.20kw │ 19.18kw │ 3.09kw │ 73.63% │ │ Pooled_hashtbl.merge w/ collisions │ 353.88us │ 5.20kw │ 19.18kw │ 3.09kw │ 100.00% │ └──────────────────────────────────────┴──────────┴─────────┴──────────┴──────────┴────────────┘

  Before changes:

  ┌──────────────────────────────────────┬──────────┬─────────┬──────────┬──────────┬────────────┐ │ Name │ Time/Run │ mWd/Run │ mjWd/Run │ Prom/Run │ Percentage │ ├──────────────────────────────────────┼──────────┼─────────┼──────────┼──────────┼────────────┤ │ Hashtbl.merge no collisions │ 309.59us │ 31.79kw │ 15.38kw │ 12.30kw │ 48.91% │ │ Hashtbl.merge w/ collisions │ 526.67us │ 38.12kw │ 19.97kw │ 16.90kw │ 83.21% │ │ Pooled_hashtbl.merge no collisions │ 469.41us │ 7.32kw │ 35.29kw │ 3.12kw │ 74.16% │ │ Pooled_hashtbl.merge w/ collisions │ 632.96us │ 7.32kw │ 35.29kw │ 3.12kw │ 100.00% │ └──────────────────────────────────────┴──────────┴─────────┴──────────┴──────────┴────────────┘

• Make Hashtbl functions raise an exception if a callback passed in as an argument mutates one of the hash tables being worked on.

  Usually, though not always, this comes up for iteration functions. Once a hash table has been mutated, it is unsafe to continue operating on it, as its structure may have changed. Buckets and their contents may have been moved or resized; continuing may result in skipping key/value pairs, repeating key/value pairs, or executing unsafe operations.

  This feature adds a mutation_allowed flag to hash tables. Each mutating operation first checks the flag, and raises if it is not set. Each operation with callbacks that must not mutate unsets the flag before calling the callbacks, and restores the flag's original value when it finishes.

  We compared the timing of this implementation to an alternate implementation using a mutation counter, and the time and space used for this implementation was much better for iteration and within epsilon of the other for single-key operations like set.

• Array function names related to zipping are all over the place. Make them match List, which has a nice uniform naming scheme.

  • Rename combine -> zip_exn
  • Rename split -> unzip
  • (zip remains named as zip)
• Add ~key and ~data labels to Hashtbl.filteri_inplace
• Added Hash_set.to_hashtbl, by analogy to Set.to_map.

• Since we are mutating avltrees in place, make sure the compiler sees the type parameters as invariant.

  Tested that a segfaulting example doesn't compile anymore.

• Add label f to Hashtbl.change, Map.change, & family.

  Introduce the new function update in those modules, which enforces statically the presence of a resulting value

  Example:

  -|val Hashtbl.change : 'a t -> key -> ('a option -> 'a option) -> unit

  +|val Hashtbl.change : 'a t -> key -> f:('a option -> 'a option) -> unit +|val Hashtbl.update : 'a t -> key -> f:('a option -> 'a) -> unit

  The motivation for the introduction of update is that in an overwhelming majority of the places where Hashtbl.change is used in our codebase, it is statically known that a new value shall be computed and stored. The use of the dynamism offered by change, which can return an option, is error prone.

  The addition of the label is considered acceptable in consideration to external libraries depending on core, because a missing label is just a warning, and we do not guarantee stability in the presence of -warn-error = true.

• Changed Source_code_position.t from:

  @@deriving bin_io, sexp

  to:

  @@deriving sexp_of

  and made sexp_of use the human-readable format, "FILE:LINE:COL", rather than the unreadable format. Removed Source_code_position.t_hum, which is now obsolete.

  If one wants a serialized source-code position, one can use Source_code_position.Stable.

• Added Ref.set_temporarily, for temporarily setting a ref to a value for the duration of a thunk.

  val set_temporarily : 'a t -> 'a -> f:(unit -> 'b) -> 'b

• Add the function singleton : 'a -> 'a t in the stack containers. It cannot be added to Container.S directly because some container never have exactly 1 element.
• Made Core.Array match Invariant.S1.

• Change the interface of Make_iterable_binable* to give the control back to the user when deserializing Bin_protted data.

  Improve the bin_prot deserialization of Maps and Sets. We construct a balanced tree directly instead of relying on Map.add / Set.add. This is possibile because the size of the map is known and elements are sorted.

  The complexity goes down from n.log(n) to n.

  In case the comparison function changes (and the invariant is not respected), there is a fallback to reconstruct the whole map from scratch.

• Add a function to blit a Rope.t into a Buffer.t.

• Hashtbl differs from some other core containers with idiosyncratic naming of iteration functions. Change to be consistent and to more closely match the conventions for List and Array.

  Hashtbl:

  • Copy iter -> iteri.
  • Add a deprecation tag to iter.
• Made Bag.invariant and Doubly_linked.invariant match Invariant.S1.

• Map differs from some other core containers with idiosyncratic naming of iteration functions. The current Map name conventions are also internally inconsistent as well (ex: current Map.iter vs Map.map vs Map.mapi). Change to be consistent and to more closely match the conventions for List and Array.

  Map:

  • Copy filter -> filteri.
  • Add a deprecation tag to filter.

• Map differs from some other core containers with idiosyncratic naming of iteration functions. The current Map name conventions are also internally inconsistent as well (ex: current Map.iter vs Map.map vs Map.mapi). Change to be consistent and to more closely match the conventions for List and Array.

  Map:

  • Copy iter -> iteri.
  • Add a deprecation tag to iter.
• Made Core.Set_once match Invariant.S1.
• Add Bigstring.concat.
• For Core.Unique_id, exposed @@deriving typerep.
• Expose Hashtbl.hashable, analogous to Map.comparator.
• Adds a constant-time val mem_elt : 'a t -> 'a Elt.t -> bool to Doubly_linked and Bag
• Add Ordering.to_int which can be useful when one is writing a comparison function. Instead of dealing with the int directly, one can return Ordering.t values and transform them later into ints.
• Float.int_pow: Fast computation of x ** n when n is an integer.
• Make Core_kernel.Std.Nothing.t enumerable. There's no particular reason not to.
• Minor improvements to queue interface

• Call Caml.Pervasives.do_at_exit before printing an exception and exiting

  The default ocaml uncaught exception handler does this. It is especially useful for curses applications as the at_exit handler has a chance to put back the terminal in a good state before printing the exception and backtrace.

  Do the same in Core and Async.

• Removed big literals so that the compiler does not complain in 32bit
• Add List.range', a generalization of List.range.

• Add some functions to Map that are present in Hashtbl:

  • remove_multi
  • partition_tf
  • partitioni_tf
  • partition_map
  • partition_mapi
• Add a Map.nth_exn as a missing complementary function to nth
• Renamed Validate.fail_sexp as fail_s, to follow our new *_s convention for Sexp.t-taking functions.

• Sequence.split_n_eagerly returns a pair of sequences, but every element of the first sequence has already been evaluated by the time it returns. This feature just makes the first component of the tuple a list instead of a sequence, and renames split_n_eagerly to split_n.

  Additionally, this feature adds a new chunks_exn function, which just applies split_n until the input sequence is empty.

• Removed Timing_wheel's default alarm_precision, to force people to think about the precision they want when they create a timing wheel.
• In Timing_wheel.Config.sexp_of_t, used @sexp_drop_default with level_bits.

• Write a better-performing Array.filter_mapi function, and implement Array.filter_map, Array.filter_opt, Array.partitioni_tf, and Array.partition_tf in terms of it.

  Slightly worse for zero-length input arrays, about unch'd if we're filtering out almost everything (eq_zero), better on most everything else.

  ┌────────────────────────────────────────────────────┬─────────────────┬─────────────┬─────────────┬─────────────┬────────────┐ │ Name │ Time/Run │ mWd/Run │ mjWd/Run │ Prom/Run │ Percentage │ ├────────────────────────────────────────────────────┼─────────────────┼─────────────┼─────────────┼─────────────┼────────────┤ │ core\_array.ml:filter old-filter-even:0 │ 12.37ns │ 9.00w │ │ │ │ │ core\_array.ml:filter old-filter-even:1 │ 77.44ns │ 15.00w │ │ │ │ │ core\_array.ml:filter old-filter-even:10 │ 207.10ns │ 36.00w │ │ │ │ │ core\_array.ml:filter old-filter-even:100 │ 1_699.41ns │ 261.00w │ │ │ │ │ core\_array.ml:filter old-filter-even:1000 │ 56_320.50ns │ 1_009.00w │ 2_506.01w │ 1_004.01w │ 0.30% │ │ core\_array.ml:filter old-filter-even:10000 │ 469_134.89ns │ 10_009.00w │ 25_007.38w │ 10_005.38w │ 2.46% │ │ core\_array.ml:filter old-filter-even:100000 │ 4_421_742.22ns │ 100_009.00w │ 250_130.09w │ 100_128.09w │ 23.17% │ │ core\_array.ml:filter new-filter-even:0 │ 13.87ns │ 14.00w │ │ │ │ │ core\_array.ml:filter new-filter-even:1 │ 57.64ns │ 18.00w │ │ │ │ │ core\_array.ml:filter new-filter-even:10 │ 196.28ns │ 35.00w │ │ │ │ │ core\_array.ml:filter new-filter-even:100 │ 1_361.04ns │ 215.00w │ │ │ │ │ core\_array.ml:filter new-filter-even:1000 │ 21_473.76ns │ 1_014.00w │ 1_001.02w │ │ 0.11% │ │ core\_array.ml:filter new-filter-even:10000 │ 204_033.12ns │ 10_014.00w │ 10_001.14w │ 0.14w │ 1.07% │ │ core\_array.ml:filter new-filter-even:100000 │ 2_058_144.47ns │ 100_014.00w │ 100_002.00w │ 1.00w │ 10.78% │ │ core\_array.ml:filter old-filter-eq_zero:0 │ 12.21ns │ 9.00w │ │ │ │ │ core\_array.ml:filter old-filter-eq_zero:1 │ 71.23ns │ 15.00w │ │ │ │ │ core\_array.ml:filter old-filter-eq_zero:10 │ 174.80ns │ 24.00w │ │ │ │ │ core\_array.ml:filter old-filter-eq_zero:100 │ 1_212.70ns │ 114.00w │ │ │ │ │ core\_array.ml:filter old-filter-eq_zero:1000 │ 23_347.51ns │ 13.00w │ 1_007.00w │ 6.00w │ 0.12% │ │ core\_array.ml:filter old-filter-eq_zero:10000 │ 210_509.83ns │ 13.00w │ 10_007.00w │ 6.00w │ 1.10% │ │ core\_array.ml:filter old-filter-eq_zero:100000 │ 1_912_253.91ns │ 13.00w │ 100_007.01w │ 6.01w │ 10.02% │ │ core\_array.ml:filter new-filter-eq_zero:0 │ 13.70ns │ 14.00w │ │ │ │ │ core\_array.ml:filter new-filter-eq_zero:1 │ 56.56ns │ 18.00w │ │ │ │ │ core\_array.ml:filter new-filter-eq_zero:10 │ 179.42ns │ 27.00w │ │ │ │ │ core\_array.ml:filter new-filter-eq_zero:100 │ 1_254.49ns │ 117.00w │ │ │ │ │ core\_array.ml:filter new-filter-eq_zero:1000 │ 20_968.06ns │ 16.00w │ 1_001.02w │ │ 0.11% │ │ core\_array.ml:filter new-filter-eq_zero:10000 │ 204_299.82ns │ 16.00w │ 10_001.13w │ 0.13w │ 1.07% │ │ core\_array.ml:filter new-filter-eq_zero:100000 │ 2_019_283.81ns │ 16.00w │ 100_001.91w │ 0.91w │ 10.58% │ │ core\_array.ml:filter old-filter-neq_zero:0 │ 12.14ns │ 9.00w │ │ │ │ │ core\_array.ml:filter old-filter-neq_zero:1 │ 32.72ns │ 11.00w │ │ │ │ │ core\_array.ml:filter old-filter-neq_zero:10 │ 219.18ns │ 48.00w │ │ │ │ │ core\_array.ml:filter old-filter-neq_zero:100 │ 1_902.76ns │ 408.00w │ 0.12w │ 0.12w │ │ │ core\_array.ml:filter old-filter-neq_zero:1000 │ 82_032.44ns │ 2_007.00w │ 3_998.20w │ 1_997.20w │ 0.43% │ │ core\_array.ml:filter old-filter-neq_zero:10000 │ 850_234.44ns │ 20_007.00w │ 40_014.86w │ 20_013.86w │ 4.46% │ │ core\_array.ml:filter old-filter-neq_zero:100000 │ 7_345_941.05ns │ 200_007.00w │ 400_407.82w │ 200_406.82w │ 38.49% │ │ core\_array.ml:filter new-filter-neq_zero:0 │ 13.66ns │ 14.00w │ │ │ │ │ core\_array.ml:filter new-filter-neq_zero:1 │ 18.26ns │ 14.00w │ │ │ │ │ core\_array.ml:filter new-filter-neq_zero:10 │ 201.04ns │ 43.00w │ │ │ │ │ core\_array.ml:filter new-filter-neq_zero:100 │ 1_404.33ns │ 313.00w │ │ │ │ │ core\_array.ml:filter new-filter-neq_zero:1000 │ 22_829.70ns │ 2_012.00w │ 1_001.02w │ │ 0.12% │ │ core\_array.ml:filter new-filter-neq_zero:10000 │ 218_872.52ns │ 20_012.00w │ 10_001.21w │ 0.21w │ 1.15% │ │ core\_array.ml:filter new-filter-neq_zero:100000 │ 2_121_340.68ns │ 200_012.00w │ 100_002.77w │ 1.77w │ 11.12% │ │ core\_array.ml:filter old-filter_map-int:0 │ 9.58ns │ 5.00w │ │ │ │ │ core\_array.ml:filter old-filter_map-int:1 │ 68.46ns │ 11.00w │ │ │ │ │ core\_array.ml:filter old-filter_map-int:10 │ 191.66ns │ 32.00w │ │ │ │ │ core\_array.ml:filter old-filter_map-int:100 │ 1_492.60ns │ 257.00w │ │ │ │ │ core\_array.ml:filter old-filter_map-int:1000 │ 57_155.42ns │ 1_005.00w │ 2_507.01w │ 1_005.01w │ 0.30% │ │ core\_array.ml:filter old-filter_map-int:10000 │ 522_177.50ns │ 10_005.00w │ 25_008.54w │ 10_006.54w │ 2.74% │ │ core\_array.ml:filter old-filter_map-int:100000 │ 5_945_405.67ns │ 100_005.00w │ 250_170.69w │ 100_168.69w │ 31.15% │ │ core\_array.ml:filter new-filter_map-int:0 │ 12.03ns │ 10.00w │ │ │ │ │ core\_array.ml:filter new-filter_map-int:1 │ 53.63ns │ 14.00w │ │ │ │ │ core\_array.ml:filter new-filter_map-int:10 │ 164.16ns │ 31.00w │ │ │ │ │ core\_array.ml:filter new-filter_map-int:100 │ 1_263.42ns │ 211.00w │ │ │ │ │ core\_array.ml:filter new-filter_map-int:1000 │ 23_113.12ns │ 1_010.00w │ 1_001.02w │ │ 0.12% │ │ core\_array.ml:filter new-filter_map-int:10000 │ 218_152.23ns │ 10_010.00w │ 10_001.15w │ 0.15w │ 1.14% │ │ core\_array.ml:filter new-filter_map-int:100000 │ 2_217_307.86ns │ 100_010.00w │ 100_002.11w │ 1.11w │ 11.62% │ │ core\_array.ml:filter old-filter_map-float:0 │ 9.32ns │ 5.00w │ │ │ │ │ core\_array.ml:filter old-filter_map-float:1 │ 66.68ns │ 13.00w │ │ │ │ │ core\_array.ml:filter old-filter_map-float:10 │ 182.86ns │ 42.00w │ │ │ │ │ core\_array.ml:filter old-filter_map-float:100 │ 1_496.56ns │ 357.00w │ │ │ │ │ core\_array.ml:filter old-filter_map-float:1000 │ 76_479.74ns │ 2_005.00w │ 3_507.02w │ 2_005.02w │ 0.40% │ │ core\_array.ml:filter old-filter_map-float:10000 │ 694_999.59ns │ 20_005.00w │ 35_011.08w │ 20_009.08w │ 3.64% │ │ core\_array.ml:filter old-filter_map-float:100000 │ 8_694_669.26ns │ 200_005.00w │ 350_476.44w │ 200_474.44w │ 45.56% │ │ core\_array.ml:filter new-filter_map-float:0 │ 12.29ns │ 10.00w │ │ │ │ │ core\_array.ml:filter new-filter_map-float:1 │ 58.24ns │ 16.00w │ │ │ │ │ core\_array.ml:filter new-filter_map-float:10 │ 142.67ns │ 41.00w │ │ │ │ │ core\_array.ml:filter new-filter_map-float:100 │ 1_119.41ns │ 311.00w │ │ │ │ │ core\_array.ml:filter new-filter_map-float:1000 │ 14_262.66ns │ 2_010.00w │ 1_001.02w │ │ 0.07% │ │ core\_array.ml:filter new-filter_map-float:10000 │ 136_448.05ns │ 20_010.00w │ 10_001.23w │ 0.23w │ 0.71% │ │ core\_array.ml:filter new-filter_map-float:100000 │ 1_282_005.01ns │ 200_010.00w │ 100_003.14w │ 2.14w │ 6.72% │ │ core\_array.ml:filter old-filter_map-boxed:0 │ 9.48ns │ 5.00w │ │ │ │ │ core\_array.ml:filter old-filter_map-boxed:1 │ 71.16ns │ 13.00w │ │ │ │ │ core\_array.ml:filter old-filter_map-boxed:10 │ 197.40ns │ 42.00w │ │ │ │ │ core\_array.ml:filter old-filter_map-boxed:100 │ 1_762.40ns │ 357.00w │ │ │ │ │ core\_array.ml:filter old-filter_map-boxed:1000 │ 86_220.67ns │ 2_005.00w │ 3_507.02w │ 2_005.02w │ 0.45% │ │ core\_array.ml:filter old-filter_map-boxed:10000 │ 828_291.42ns │ 20_005.00w │ 35_011.84w │ 20_009.84w │ 4.34% │ │ core\_array.ml:filter old-filter_map-boxed:100000 │ 7_955_395.61ns │ 200_005.00w │ 350_441.44w │ 200_439.44w │ 41.68% │ │ core\_array.ml:filter new-filter_map-boxed:0 │ 14.43ns │ 10.00w │ │ │ │ │ core\_array.ml:filter new-filter_map-boxed:1 │ 59.24ns │ 16.00w │ │ │ │ │ core\_array.ml:filter new-filter_map-boxed:10 │ 198.19ns │ 41.00w │ │ │ │ │ core\_array.ml:filter new-filter_map-boxed:100 │ 1_580.21ns │ 311.00w │ │ │ │ │ core\_array.ml:filter new-filter_map-boxed:1000 │ 52_045.31ns │ 2_010.00w │ 2_011.01w │ 1_010.01w │ 0.27% │ │ core\_array.ml:filter new-filter_map-boxed:10000 │ 479_239.44ns │ 20_010.00w │ 20_012.42w │ 10_011.42w │ 2.51% │ │ core\_array.ml:filter new-filter_map-boxed:100000 │ 4_389_392.06ns │ 200_010.00w │ 200_135.09w │ 100_134.09w │ 23.00% │ │ core\_array.ml:filter old-partition_tf:0 │ 16.55ns │ 16.00w │ │ │ │ │ core\_array.ml:filter old-partition_tf:1 │ 128.08ns │ 29.00w │ │ │ │ │ core\_array.ml:filter old-partition_tf:10 │ 554.15ns │ 111.00w │ │ │ │ │ core\_array.ml:filter old-partition_tf:100 │ 4_853.58ns │ 921.00w │ 0.46w │ 0.46w │ 0.03% │ │ core\_array.ml:filter old-partition_tf:1000 │ 201_289.06ns │ 5_016.00w │ 9_015.21w │ 5_010.21w │ 1.05% │ │ core\_array.ml:filter old-partition_tf:10000 │ 1_796_749.87ns │ 50_016.00w │ 90_040.96w │ 50_035.96w │ 9.41% │ │ core\_array.ml:filter old-partition_tf:100000 │ 19_084_871.85ns │ 500_016.00w │ 902_187.67w │ 502_182.67w │ 100.00% │ │ core\_array.ml:filter new-partition_tf:0 │ 28.29ns │ 23.00w │ │ │ │ │ core\_array.ml:filter new-partition_tf:1 │ 103.78ns │ 31.00w │ │ │ │ │ core\_array.ml:filter new-partition_tf:10 │ 504.10ns │ 96.00w │ │ │ │ │ core\_array.ml:filter new-partition_tf:100 │ 3_869.52ns │ 726.00w │ 0.23w │ 0.23w │ 0.02% │ │ core\_array.ml:filter new-partition_tf:1000 │ 122_807.29ns │ 4_023.00w │ 5_013.04w │ 2_010.04w │ 0.64% │ │ core\_array.ml:filter new-partition_tf:10000 │ 1_197_596.39ns │ 40_023.00w │ 50_020.05w │ 20_017.05w │ 6.28% │ │ core\_array.ml:filter new-partition_tf:100000 │ 10_458_344.09ns │ 400_023.00w │ 500_590.94w │ 200_587.94w │ 54.80% │ └────────────────────────────────────────────────────┴─────────────────┴─────────────┴─────────────┴─────────────┴────────────┘

• Added Binable.Of_sexpable functor.
• Install the sexp exception printer sooner so that we can get proper %test_result ... errors in things that come before core_kernel.
• In Stable_unit_test.Make functors, include all test failures rather than just the first. This is useful for updating batches of expected bin_io results when stabilizing a module.
• Remove an unnecessary cast in or_error.ml