An obvious further optimisation just occurred to me: if there is only one domain (i.e. a single-threaded program), then you may as well free the old frametable immediately. That way, the costs of ensuring that parallel Dynlink is safe are paid only by programs that actually do parallel Dynlinking.

Naive question, since this looks like GC-ing the tables, have you considered reference-counting the tables and dropping them as soon as they are no longer in use? This would avoid having to build a linked list of old tables altogether. I am missing why the ownership would be hard to track.

I also agree with the change (independently of my naive questions), however I am suggesting to add a Change entry as the release manager: this is the kind of usability change that matters when announcing the rc or beta releases and I like to be able to point to a change entry in those cases.

Naive question, since this looks like GC-ing the tables, have you considered reference-counting the tables and dropping them as soon as they are no longer in use?

The trouble is that refcounting causes contention because multiple concurrent readers are all synchronising on the shared reference count - that is, you pay synchronisation overheads even in the absence of any writers. (Maybe we can ensure that this structure isn't accessed too often and the overhead is manageable, I'm not sure)

The code seems to be careful to free the old frame descriptors lazily, only upon access to the new values. Is this an important optimization, compared to adding a call to try to free them at the end of each GC cycle?

No, it's not important. That approach makes sense to me!

I had a go at implementing the single-threaded optimisation, but it doesn't speed up the plugin-heavy Frama-C startup all that much. The trouble is that the OCaml 5 dynlink logic is fundamentally O(n^2) as it rebuilds the entire frame descriptor table each time, while the OCaml 4 version is O(n) as it mutates the existing one in-place.

(When writing this logic some years ago, I thought it would rebuild the table once per loaded .cmxs, which is annoying but bearable. It's much worse: it rebuilds the table once per module contained in each loaded .cmxs, because it needs a populated table between the initialisation of any two modules. There can be a lot of those)

I think the right fix is probably to think seriously about the frame descriptor table as a mutable concurrent hashtable, or to globally synchronise all accesses to the frametable. Both of these are things I was really hoping not to have to do (because apart from Dynlink, they're not necessary). That fix may have to wait for 5.1, though, as it seems a bit late in the release cycle to add a concurrent hashtable to the runtime! Something along the lines of what's here will have to do for 5.0, but I'll think about it a bit more to see if I can find an easy fix.

For read-heavy write-rarely data structures, we can implement synchronization by ensuring that modifying the structure provokes a stop-the-world event. Then we can read from any STW-registered mutator without any synchronization on reads. This seems reasonably easy/uninvasive to implement (famous last words...), provided the modifications don't occur too deeply inside the runtime code.

Any objections for merging this PR and eventually moving the discussion on a better implementation to an issue (I will push a change entry manually myself)?

We are discussing two issues in this PR:

• a memory leak
• a time-complexity regression compared to 4.x

The PR itself fixes only the memory leak, has been reviewed, and should indeed be merged asap (ideally in 5.0).

The time issue is less critical. We are talking about N=200 modules being loaded, and a memory leak proportional to N*2Mib is obvious to our users, whereas a N^2 time leak is less of a concern in practice.

It looks like the "time issue" is also causing a noticeable regression for Coq which also uses natdynlink heavily for its plugins -- see user report in #11926.

Currently, if I understand correctly, the code is doing as follows:

• we maintain a global list of all "frametable fragments" that have been "registered" by the dynlink machinery
• from a given state of the list we can compute a "frametable version", by linearly building a hash table from the list elements
• when we compute a frametable version, we cache it by storing it in the corresponding node of the "frametable fragments" list
• there is a "current frametable" which points to the latest frametable version, but mutators do not use atomic accesses to read the frametable (for efficiency reasons?) so they may access older frametable versions
• mutators "update" their view of the "current frametable" at least once per major cycle; when the current frametable is more than one major cycle old, we free all previous frametable versions

(We don't want to (1) require locking when accessing the frametable, which is a performance-critical operation, or (2) try to mutate a hash table while mutators could access it, which requires a complex concurrent hashtable implementation -- or locking on access, see (1).)

My proposed strategy would be as follows:

• we maintain a single global "frame descriptor" hash table, accessed without synchronization
• whenever we want to update the table to register a new fragment, we perform a stop-the-world to ensure that all mutators are stopped

I think that it's a bit of work to implement and test, but not that much either. (We did something similar to resize the minor heap and it works okay.) The resulting code would in fact probably be simpler than the current one.

Unfortunately a stop-the-world synchronization cannot remove the quadratic behaviour since the iteration responsible for the quadratic blowup is located in OCaml code. Instead of reallocating the frame descriptor table quadratically, you stop the world quadratically. In legacy single-threaded code this will show a speed-up, but the benefits in the long term are less clear (except for space).

I sketched another solution but I was not confident this was the right place to discuss the time complexity problem, so I replied at #11926 instead.

@gadmm I think that the quadratic behavior comes from the runtime code.

If we call caml_register_frametable N times:

then build_frame_descriptors is called N times on the current list of frametable fragments:

and each call on a list of length K<=N iterates on each element to build a hash table:

Am I missing something?

Instead with my implementation strategy we would have N stop-the-world pauses where each one "grows" the global hash table by adding the content of the new frametable fragment.

Right, sorry, I did not mean to write that you stop the world quadratically (though I did), this would be even worse.

What I meant is that the iteration responsible for calling caml_register_frametable a lot seems to be here:

I do not discard your solution, but I prefer one that makes caml_register_frametable inexpensive (being understood that the point of both solutions is to keep the cost low for the reader).

We don't want to (1) require locking when accessing the frametable, which is a performance-critical operation

What about a reader-writer lock? GC root scanning and backtrace construction would lock for reading, and only dynlink would lock for writing.

@stedolan was worried that the overheads of reference-counting would be too much for dealing with memory reclamation, so there would be the same (bigger?) worries for a reader-writer lock. But I am not convinced this would be too costly, I think this is a solution worth trying.

@gadmm thanks for your clarification.

it is not possible to place the stop-the-world section around [the iteration on all symbols]

Maybe we could move to a different API where we first "prepare" a bunch of frametables and then add them all at the same time (with a single pause). But that does make this approach more invasive.

I agree that trying the reader-writer lock first is a good choice.

What about a reader-writer lock? GC root scanning and backtrace construction would lock for reading, and only dynlink would lock for writing.

Reader-writer locks cause contention even between readers, since the lock state must be atomically updated whenever a reader enters or exits the critical section. It's possible that we could find a coarse enough locking strategy for this to work OK, but just wrapping every use of the frametable won't work. (Maybe just a big reader critical section around GC pauses and backtrace collection is fine? However, backtrace collection can happen very frequently)

Maybe we could move to a different API where we first "prepare" a bunch of frametables and then add them all at the same time (with a single pause). But that does make this approach more invasive.

I think this is easy and worth doing in any case, I've opened #11935 to that effect.

My intuition was that backtraces could be collected frequently, but not so frequently. I had in mind that the frametable was typically cold cache-wise, in which case the cost of an integer atomic update was negligible compared to other memory accesses. (The case where catchable exceptions are raised very often sounds like a case where you want to disable backtraces anyway.)

Still if you think the makeshift lock-free hash table could be useful despite this consideration and your separate improvement at #11935, let me know.