The various list reversals all look correct - is the compiler manual a good enough test to diff before or after, or are there already relevant tests in the testsuite which would catch the search list ending up in the wrong order?

That's a good point, I wanted to compare the .3o outputs but I forgot. I will check and report Thanks!

(Initially I had inlined the deduplication code in the function itself, which saves two list reversals, but there is no performance impact in doing so, so I went for the more separated code.)

(Note: the timings above are given when generating the documentation with ocamldoc.opt, and without counting the analysis part (which still dominates runtime). I haven't measured the bytecode speed difference (it may be smaller), so I'll check also that.)

Re. List.mem: I did do a git grep and many place are using this quadratic-looking pattern, but then in common cases (the list is small) this is faster than the set-based solution. So I think it makes sense to keep them, and wait to detect places that actually get large inputs before making changes. (On the other hand, li @ [x] is an anti-pattern as far as I'm concerned.)

All good - I'd initially wondered about suggestion the inlining of the reversal, but it sounds as though having to append short lists to a long list dominates the saving of the two overall list reversals. We need the TRMC patch 🙂

The initial algorithm was quadratic and the new one is linear, so the constant factors don't matter much -- the new runtime is negligible.

I confirm that the produced manpages are exactly identical. On my machine today, the current make rule (using bytecode ocamldoc instead of native ocamldoc) goes from 16s to 14s with the patch -- not much of a difference. I guess I'll look at using the native ocamldoc by default when available, in another PR.