(I just pushed an adjustment which should allow AppVeyor to complete)

I find it hard to draw any conclusion from the performance numbers given here. If I understood correctly, the benchmark suite does not test marshalling much (so the fact that the numbers are identical is not very informative). The compiler does rely on marshalling a bit (to create and read .cm{i,o,x} files), but the performance results are hard to interpret due to potential measurement noise. (Are those just one run of each, or a result aggregated from several runs?).

It would be useful to have a microbenchmark to measure marshalling speed regressions, so that people can get a quick estimate of potential performance regression for their workload if they know the fraction of time spent in marshalling. It may also be interesting to consider adding marshalling examples to the benchmark suite, for example a simple message-passing program (that just passes messages to itself for benchmarking purposes).

opam's state-loading mechanism can be turned fairly quickly into a micro-benchmark (see https://github.com/ocaml/opam/blob/master/src/state/opamRepositoryState.mli#L20). It's at least an important benchmark as it's used on virtually every opam anyone runs!

Hack (https://hacklang.org/) and Flow (http://flow.org/) both use the Marshal module extensively to write values into shared memory and read them out. The exact amount of Marshaling that we do depends on the source code we're analyzing, but our internal (unfortunately unsharable) workload is quite significant.

If it would be helpful, I can look to see what the impact on our workloads are and report back.

@samwgoldman Studying the impact of this PR on internal workloads would be quite useful. Does that mean Hack and Flow can build on trunk? If there's a fork that does build, it would be nice to have them in our benchmark suite.

@kayceesrk Alas, we won't build in trunk at the moment due to, at least, our dependency on ppx_deriving. This is just the first thing I ran into when I tried.

I agree it would be nice to have these in your benchmark suite. In the meantime, it seems like it shouldn't be too hard for me to backport this, although perhaps the results would not be as meaningful.

although perhaps the results would not be as meaningful.

Not much has changed in extern.c recently. So the results should be meaningful. Reg ppx, what we end up doing in sandmark is to commit the output of ppx pass so that we can compile the output program with different compiler versions. Perhaps something like this might work.

I used the red-black tree example from John Whitington's book, "More OCaml: Algorithms, Methods & Diversions" to create a red-black tree (https://gist.github.com/shakthimaan/2c33be7724c33735c80d9356d1db6837) of height 23 with only integer data, and tested the same with Marshal.to_bytes. The executable was created using the following command from the top-level sources directory:

$ ./runtime/ocamlrun ./ocamlopt -nostdlib -I stdlib file.ml

The time utility was used to measure the resource usage:

$ /usr/bin/time -v ./a.out

With no external_flags argument (Marshal.to_bytes data []), these are the results that differed between trunk (82d7971...) and the hash-table-for-marshaling branch:

Using Marshal.to_bytes data [Marshal.No_Sharing], the results that differed are provided below for reference:

Test system: Parabola GNU/Linux-libre system running Intel (R) Core (TM) i5-6200 CPU @ 2.30 GHz with 8 GB RAM.

Thanks for the numbers! For the first run (with sharing), this is a 15% runtime slowndown and a 22% increase in memory usage.

(I didn't expect an impact on memory usage, I guess this is the memory consumed by the hashtable structure itself?)

Unfortunately, it is hard to tell from your benchmark what is the time taken by marshalling itself, as you first build a not-so-small data structure. Could you measure the time taken by the datastructure construction for a run, so that it can be retracted from the time used to measure the slowndown? This could be done with just replacing the last two lines with

let time_before = Unix.gettimeofday ()
let u = create_binary_tree 23
let time_after = Unix.gettimeofday ()
let () =
  Printf.eprintf "%f\n%!" (time_after -. time_before)
let _ = Marshal.to_bytes u []

Thanks for your prompt reply! I used the following command to compile:

$ ./runtime/ocamlrun ./ocamlopt -nostdlib -I stdlib -I otherlibs/unix unix.cmxa file.ml

Here are the results for Marshal.to_bytes data []:

The following is the result for Marshal.to_bytes data [Marshal.No_Sharing]:

The numbers now do not look so good, because it seems that most of the time in the benchmark is spent before marshalling starts. For the first benchmark for example, marshalling takes (17.44 - 16.36 = 1.08) seconds on trunk, and (19.86 - 16.27 = 3.59) seconds after the patch, so we see a 232% slowdown!

Thanks for your comments. We are currently looking into profiling and optimizing the hashmap implementation.

We are currently looking into profiling and optimizing the hashmap implementation.

What was the reason for the choice of this implementation in the runtime initially? Many implementation of hashmap exists in C, do you consider comparing some of them before optimizing?

I think that it is going to be very hard to compete with the current implementation using a hashtable. You need to associate metadata to pointers, the current implementation is using writing the data where the pointer is; any hashing scheme is going to be substantially slower. Given that the metadata needs to be stored on all blocks encountered during serialization, it seems intuitive that a large slowdown is expected when serializing payloads with many smaller blocks. We can talk about whether the current slowdown is "too large", but it is not clear to me that you can hope to get a much smaller slowdown with more optimization.

On the other hand, a rather natural idea is the following: if the metadata is only used to preserve sharing, could your implementation at least have no overhead when No_sharing is used? I suspect that it is a performance bug in the current PR that you store pointers in the table even when No_sharing is set; fixing it (if it indeed is correct) should remove the overhead in No_sharing mode.

To go further: it should be possible to keep using the old scheme for objects that are in the minor heap, if the Multicore-GC design still guarantees that those are not mutated concurrently. I'm not sure whether this would be worth it, given that minor heaps are expected to be small (in your example clearly most data would live in the major heap), and that this would increase implementation complexity. But for applications that use message-passing with short values, possibly created right before marshalling start, this could be another way to remove the hashtable overhead.

For large payloads of small blocks on the major heap, I don't see any better approach than using an external map as with the current PR, or blocking parallel mutators.

I think that it is going to be very hard to compete with the current implementation using a hashtable. You need to associate metadata to pointers, the current implementation is using writing the data where the pointer is; any hashing scheme is going to be substantially slower.

This is true in general. If that's the only price to pay for multicore support, let it be. This said, some tuning of the hash table might help. For example, I find it suspicious that the hash table is resized only when a chain of collisions of length 100 was encountered. A well-maintained hash table should hit on the first try 90%+ of the time. The much maligned page table (in runtime/memory.c) achieves this, if I remember correctly.

if the metadata is only used to preserve sharing, could your implementation at least have no overhead when No_sharing is used?

This is a good suggestion, even though No_sharing is often unusable because it produces excessively big marshaled data.

it should be possible to keep using the old scheme for objects that are in the minor heap, if the Multicore-GC design still guarantees that those are not mutated concurrently.

That could be, but I fear it would make the marshaling implementation awfully complex.

This said, some tuning of the hash table might help. For example, I find it suspicious that the hash table is resized only when a chain of collisions of length 100 was encountered

I agree. The original goal of this hashtable was to minimise the number of minutes spent writing it. Apart from @shakthimaan's work here I think it's never been profiled or optimised. I imagine it could be made vastly faster.

It's not obvious to me that a hashing approach need be any slower than the current implementation. The current implementation does two passes over the object graph, since it needs to restore the headers that it's mutated after it's finished marshalling. A hashtable can be discarded in bulk.

Using allocated size of 60 MB, the hash table implementation is now only ~1.3 seconds slower than OCaml trunk for 16 million objects. A caml_init_alloc_size has also been included as a runtime parameter.

"Address modulo size of table" is a terrible hash function, and 60 Mb is way too much space overhead. You need to combine a decent hash function with a decent dynamic resizing strategy. That's all explained in textbooks such as TAOCP volume 3. For an example of implementation, look no further than the OCaml runtime system, file runtime/memory.c, functions caml_page_table_{lookup,resize,modify}.

• The addrmap code has now been updated to use Multiplicative Fibonacci hashing similar to caml_page_table{lookup, resize} implementation from runtime/memory.c.
• It is now only ~2s slower than OCaml trunk for 16 million objects for marshaling a binary tree of height 23.
• The hash table is doubled only when the load factor reaches 90%.

I got tired of the back-and-forth on this PR, so I wrote my own implementation: #9353.

I move to close this PR and concentrate the reviewing on #9353 instead.

This work has been superseded by #9353, which ended up being merged -- so the feature is in, and I am closing here.
Thanks for the initial work and performance investigation!