Learnings from benchmarking OxCaml-flavoured SWAR memchr

Learning
, , , ,
1

Hi everyone, just wanted to share a benchmarking project that I had created over the past few days for testing out OxCaml:

I come from 10+ years of Rust, started hacking on it when it still had the Ruby-inspired closure syntax where parameters denoted by the two pipes are written inside of the block instead of outside of it (i.e. {|arg| statements;} instead of |arg| { statements; }). Certainly not the earliest batch, but early enough to know that before Rust was self-hosted, the compiler was written in OCaml, which is why I’m really interested in seeing how OCaml is “learning from its child”. I had a brief stint in writing OCaml at a startup, but that was too short of a time to consider myself familiar with it.

The README.md of the repo does a fairly good job in explaining the intricate details, and admittedly AI was used to write it, but what AI cannot tell you is the experience of writing it. Yes, I used AI, but no, I did not let it write everything, because one of the aims of this exercise is to help me learn both OCaml and OxCaml.

Let’s go through the good, the bad and the ugly parts of coding in OxCaml. Bear in mind that some of these points are due to me being an OCaml noob and am still learning things about the language.

The Good

The conciseness and the compile-times. I’m absolutely floored by just how elegant idiomatic OCaml source code looks. Everything just works without much ceremony: no braces nor brackets, no random fn keywords, and most importantly no cruft that gets in the way – you just let there = light, and there was light. Not only that, the compile-verify-rewrite loop is quite fast, precisely because compile times are amazingly fast, so fast that even utop exists as a REPL, allowing me to test ideas out before committing to them. These aren’t things that a Rustacean is used to: normally what happens is that whenever I encounter a new crate, I rely on docs.rs for documentation about the features coming from the crate, or spend time creating a new unit test and compiling it to see how it works. I can really now see why OCaml developers would want to continue writing OCaml despite it not being one of the most popular languages out there.

Dune. This sort of ties back into the previous point on conciseness: build configuration is really just tuples/s-expressions. While I can still pretty much achieve the same effects in Rust with Cargo.toml, everything being s-expressions in dune means that there really isn’t much overhead. I now come to think of this style as minimally yet sufficiently concise, e.g. the brackets in an s-expression is the minimal structure around data, and semantics simply just fall out from what you put between the brackets. Integration with C is pretty seamless as well, along with Rust, though the latter still requires teaching dune to use cargo, which doesn’t really strike me as surprising as C is much more well-established as the lingua franca in systems programming.

[@@zero_alloc]. This is what OxCaml brings to the table and it delivers right away – mark your vals with it in your interface definitions, and it’ll immediately try and catch any possible allocations that you make within your function. I’m used to zero-cost abstractions so being made aware that some language features aren’t free in terms of allocations was quite new to me (I’m looking at you, option). It makes sense upon closer inspection, but the initial surprise is still there – I guess I’m just really not used to thinking that nice language features have non-trivial costs associated with them. Anyway, the annotation certainly took a page from Rust, where the check happens all at compilation time, so code that compiles with that annotation is guaranteed not to allocate anything by the compiler. I love my parents.

Mutable local variables. I know enough OCaml to know that the standard way is to use 'a ref, but seeing how mutable just works exactly the way I thought without much fanfare was quite nice. It also doesn’t require using the ! prefix when “dereferencing” the variable to read its value; the only downside is that it still does require <- for assignment. That’s inevitable, since = has been overloaded with too much meaning; in fact, the odd one out here is logical equality, since let-bindings and record fields are arguably both in the same category of assignment operators.

Unboxed tuples and records. They just work as expected, even in patterns. You really just need to prefix everything with #, and it’ll work, e.g. the common pattern that I often use in Rust when I need to return or bind two or more values at the same time is to use tuples, and in OxCaml it’s pretty much the same:

let #(a, b) = if cond then #(#8L, foo) else #(#3L, bar)

Automatic byte alignment. OCaml strings and byte arrays are automatically aligned to a whole number of words, so I never need to worry about misalignment when reading the final partial word, nor requiring a prologue to first advance bytes so that it lands on a word boundary.

The Bad

Functionality incompleteness. This may just be a result of OxCaml still being a fairly new language extension, but some basic operations just aren’t there when I reach out for them during development – logical infix operators, bit shifting, and even comparison infix operators. Some of them are not even in stdlib at all, but rather part of the compiler intrinsics – I had to dig Bytes.unsafe_get_in64_ne_indexed_by_int64 out from the compiler source code in order to know that such functionalities even existed, and an unsafe load for unsigned int8 currently doesn’t exist even as an intrinsic anywhere. On the other hand, I get why the polymorphic infix operators don’t work – 'a has the value layout, and int64# has bits64, and structural comparison between the two just wouldn’t work. It would be so great if the polymorphic operators also ignores the layout that the arguments have as long as they match.

Performance impacts on certain functions. Specifically, the ones that mix-and-match parameters with their boxed and unboxed counterparts. This may not actually affect anything, but I’ve been lied to by Claude so many times that I have to put this up, because intuitively speaking, unboxing and especially boxing has a non-negligible cost associated with them, and e.g. Int64_u.shift_{left,right} requires me to use an unboxed 2nd argument to indicate how many bits I want to shift by. I’ve been told that boxing for comparison using Int64_u.compare doesn’t allocate anything despite having to compare the resulting boxed integer, and Claude says the disassembly from memchr.a proves it:

Int64_u.(compare ((to_int i) + 8) n < 0)
---
22a:  lea    0x11(%rbx,%rbx,1),%r12   ; 2i + 17, i.e. tagged(i + 8)
22f:  cmp    %rdi,%r12                ; vs tagged n
232:  jg     280

I really can’t know for sure whether this is every instruction emitted by the expression since i originally was an unboxed integer, and Claude may be missing the context where i is being retagged/reboxed again just to make this comparison.

The unboxed variant looks like the following:

Int64_u.(compare (i + #32L) (of_int n) < 0)
---
101:  lea    0x20(%rbx),%r12      ; i + 32
109:  cmp    %rsi,%r12            ; vs n, pre-untagged at 0xd7
10c:  jg     224

Taken at face value, both generate the same number of instructions and all but the parameters are identical, so if there’s anything that’s different, it has to be the hidden costs of the parameters being passed to these instructions. This bit matters, because it’s in the hot loop execution path, and every instruction or nanosecond we save here can scale up to micro or even milliseconds saved.

Ergonomics. This cuts both ways, I really like the localized imports that I showcased above with Int64_u.(expression) instead of tagging each function repeatedly, but doing it over and over again gets repetitive. I could indeed use a local import by doing let open Int64_u in, however there are times where this doesn’t work as expected, especially when I have to deal with boxed integers of varying sizes as well, like the aforementioned int. I don’t think this is a problem that can be solved generally unless we solve the problem of polymorphic layouts, so I’d still list this as a pain point.

The ugly

No continues/breaks/early returns. This is starting to get really ugly – while I understand the argument from functional programmers that imperative code can usually be rewritten in a purer functional style without mutation, we’re now in systems programming land, and every instruction emitted counts, and not being able to directly jump to where I want using continues, breaks or returns is a huge hole in my repertoire. Take for example, the code that I had to use to force an early exit in the loop:

 while Int64_u.(i + #8L <= n64) do
  let r = swar_raw (Bytes.unsafe_get_int64_ne_indexed_by_int64 s i) in
  if not Int64_u.(r land mask = #0L) then (
    hit <- i;
    i <- n64)
  else i <- Int64_u.(i + #8L)
done

See what I did here? I essentially have to assign n64 to i so that the loop condition fails just to “break” from the loop. And we’re not done here either, because i denotes the offset at which to start reading bytes, so a later loop needs it to be preserved:

if Int64_u.(hit >= #0L) then i <- hit;

I got lucky here because I am able to recover i quite easily as I’ve assigned it to hit, but one can easily imagine that you can’t be as lucky with other loops. You may have to keep spare variables around just to store the state of the loop when you break it, just to preserve it and use it on subsequent code paths. Granted, this may not be as much of a problem as I make it to be, since it’s not on the hot execution path but rather done at most once every loop, but continue is certainly not the case. I guess in a proper TCO’d recursive function, calling the function again with new parameters would be equivalent to a continue, but I haven’t tested it out enough yet to really conclude that TCO is as fast as an imperative loop.

Attributes can be trivially defeated. Not an OxCaml problem per se, but I accidentally defeated the usage of [@inline always] in the idiomatic ML flavour of memchr because the function I’m annotating captures a variable from the environment:

let[@inline always] swar_raw w =
  let w = Int64_u.(w lxor cs) in
  Int64_u.((w - ones) land lognot w)
in

Both cs and ones aren’t passed in as parameters, so now swar_raw becomes a real function that gets allocated on the stack, which means both [@@zero_alloc] and the benchmark’s mWd/Run didn’t catch it, as they measure heap allocations. Unfortunately, even stack allocations still cost performance, because calling functions are not free and requires setting up the call frame, loading the environment variables from memory, saving the context in the callee, and cleaning up before returning to the callee, none of which are trivial costs that can easily be eliminated.

Admittedly, this was my personal skill issue for not being well-versed enough in OCaml, I just have a feeling that the compiler should have at least warned me that it isn’t inlining the function as I told it to due to captured variables. Fixing this bug immediately brought the ML functional style memchr implementation down to the same speed as the imperative ML style memchr, and maybe even 1-2% faster based on benchmarks.

Closing thoughts

Let’s put into perspective about the numbers: OCaml’s Byte.index is about 10x slower than the Rust/C equivalent, whereas OxCaml managed to get it down to about only 1.3x slower. This magnitude of difference is a huge win! With OxCaml as a language extension that may have its features upstreamed, OCaml can now have its system’s slice of the cake and eat it too by being in the same order of magnitude as C/Rust. I’d say that OxCaml has completely justified its raison d’être, especially on the part where one can write idiomatic-ish OCaml syntax sprinkled with unboxed integers and still get performance close to bare metal.

I think it’s also good to address the friction points while developing in OxCaml – while writing this post, I’ve also tried to write a largely safe, idiomatic Rust version of memchr, and that alone is already about 10% faster than the OxCaml equivalent. What I wanted to bring up here isn’t my varying skill levels in these two languages (although it may have indeed played a factor), but rather how the programming language’s philosophy guides the way you think. If you’ve heard of linguistic relatively or the older Sapir-Whorf hypothesis in linguistics, this is exactly that, applied to programming languages – Rust is fundamentally about building safe, robust and efficient software, so the language features such as zero-cost abstractions, horrendously long compile times, bloated compiler error messages is designed exactly for you to write code that’s going to be safe and fast by default.

OCaml is not that, and it doesn’t have to pretend to be something it isn’t either, because it also has advantages over Rust that is hard to replicate there – fast compile times, layouts that are so uniform to the point where you really don’t think about them, tail-call optimizations that brings loops/recursions close to bare-metal speed, and a richer type system that supports GADTs and monads, and let’s not forget – without OCaml, there wouldn’t be Rust. There’s clearly still a lot that OCaml can offer to the world, and we (basically just me) still haven’t seen all it has to offer yet.

The pain points that I’ve listed are mostly because OxCaml is ostensibly written for systems programmers to write efficient code, and the syntax/tooling right now simply doesn’t exactly support those goals just yet. Making it run faster is great; allowing anyone to easily write programs that are by default running efficiently is awesome.

What’s next

OxCaml has SIMD support via oxcaml_simd, so that’s the natural next step to test and see how it fares when compared with the optimized C and Rust versions, the latter provided by BurntSushi’s memchr crate (yes, it’s his real username). After that, I’m looking to see if I can port some small and self-contained Rust crates over to OxCaml and continue experimenting on the performance characteristics. Bear in mind that memchr is a constrained example operating with only the input arguments; it’ll be interesting to see how it works with systems that require storage and memory over time.

Other than that, comments and suggestions are very welcome! I’m sure I must have made several dumb mistakes here and there when it comes to OCaml/OxCaml conventions, and I’m open to hearing what you think that can be improved!

2

It’s great to hear so many good things about OxCaml! Here are a few comments of some of the specific points:

There’s a big performance difference between boxing and tagging. Here your examples concern tagging so I’ll comment only on that, but things would be very different if boxing was involved.

The tagging and untagging operations are simple arithmetic expressions, so not only are they relatively cheap to start with, they can sometimes be combined with other arithmetic expressions in which case the tagging becomes essentially free. This is what happens in your first example, where the tagging of i gets merged with the addition of 8. The second example doesn’t benefit from it, so there an additional untagging operation on n somewhere that isn’t showed (if n is also used untagged elsewhere, this untagging could end up shared though).

I’m also very pleased to see that the transformation of compare x y < 0 to x < y is actually relied on by someone! We implemented that as a kind of a hack some time ago and I wasn’t sure if it was actually useful.

This one I admit still bothers me. There are workarounds, for example you could write the following code:

let exception Found in
try
while Int64_u.(i + #8L <= n64) do
  let r = swar_raw (Bytes.unsafe_get_int64_ne_indexed_by_int64 s i) in
  if not Int64_u.(r land mask = #0L) then (
    hit <- i;
    raise_notrace Found)
  else i <- Int64_u.(i + #8L)
done
with Found -> ()

It works, should get compiled to efficient code (with OxCaml), but it’s still a bit heavy and I wish we had a lighter syntax for that.

Regarding tail recursion, the compiler should have no problem turning tail-recursive functions into regular loops, but because of the way we implement it it might not work for your case. Typically, if you want to use inside a loop a mutable variable that is defined outside the loop the compiler will complain. Using a regular ref could work (the compiler can transform it into a mutable variable after the loop transformation), but you would have no error if it doesn’t.

I’m a bit surprised by your report here. Functions that capture variables can be inlined as well as closed functions. In some cases inlining is not enough to remove the closure allocation, so it’s possible that you still ended up with an unnecessary allocation. But I would be curious to have more details here as if there were function calls left, passing cs and ones as parameters shouldn’t have made them disappear.

Also, you’re right that calling functions is not free, but the ABI for calling functions in O(x)Caml is not the same one as in C, so if you’re only familiar with the standard ABI your estimation of the cost of a function call might be a bit off. For instance, all registers are caller-save, and no parameters get passed on the stack unless you have way too many of them (I think the limit is more than 70 on all supported platforms).

3

It is sometimes ergonomical to write while body do () done loops, e.g.:

while 
  if not Int64_u.(i + #8L <= n64) then false
  else
    let r = swar_raw (Bytes.unsafe_get_int64_ne_indexed_by_int64 s i) in
    if not Int64_u.(r land mask = #0L) then (hit <- i; false)
    else (i <- Int64_u.(i + #8L); true)
do
  ()
done
4

Thanks for pointing that out! That was the confusing part that tripped me up – was tagging and boxing the same thing? They essentially have the same syntax: of_{type} and to_{type}, so it was difficult to understand just by inspection whether the code is doing one or the other.

Ultimately, I’d argue that while the compare function is quite a handy Swiss army knife for all infix comparison operators, the load-bearing (pardon my Claude-speak) part of what we’re discussing here is the signal of intent: compare a b < 0 by inspection is essentially 2 operations, whilst a < b is just one. If I didn’t know about the implementation details of either, then I’d assume a < b would be the infix operator specifically optimized for this comparison, even though the generated assembly is similar or even the most efficient for both cases.

I actually tried this approach earlier, but with a slight twist – I put exception Found on the toplevel as let exception Found in causes an allocation, which gets banned by [@@zero_alloc]. I ultimately didn’t go forward with this approach, because what happens now is that the code now has two resulting code paths: one where it breaks from the loop, and the other where it didn’t and the loop was exhausted. That’s what your example has, but as I thought more about it, there’s actually no reason why I couldn’t just break after the loop ends so that the two paths converge:

exception Found
try
  while Int64_u.(i + #8L <= n64) do
    let r = swar_raw (Bytes.unsafe_get_int64_ne_indexed_by_int64 s i) in
    if not Int64_u.(r land mask = #0L) then (
      hit <- i;
      raise_notrace Found)
    else i <- Int64_u.(i + #8L)
  done;
raise_notrace Found
with Found -> () (* merged codepaths go here *)

Obviously I’d still need to test this out and see whether this emits the same assembly instructions as a break, but it is one possible general solution to any case that requires a break in a loop.

Let’s dive into this one further because this is where I got stumped as well. First, this is the original code that I tried:

let ml_memchr (s @ local read) c n =
  let ones = Int64_u.of_int (Sys.opaque_identity 0x0101_0101_0101_0101) in
  let mask = Int64_u.(ones lsl 7) in
  let cs = Int64_u.mul ones (Int64_u.of_int (Char.code c)) in
  let[@inline always] swar_raw w =
    let w = Int64_u.(w lxor cs) in
    Int64_u.((w - ones) land lognot w)
  in
  let rec bytes i =
    if Int64_u.to_int i >= n then -1
    else if Bytes.unsafe_get_int8_indexed_by_int64 s i land 0xFF = Char.code c
    then Int64_u.to_int i
    else bytes Int64_u.(i + #1L)
  in
  let rec word i =
    if Int64_u.to_int i + 8 > n then bytes i
    else if
      not
        Int64_u.(
          swar_raw (Bytes.unsafe_get_int64_ne_indexed_by_int64 s i) land mask
          = #0L)
    then bytes i
    else word Int64_u.(i + #8L)
  in
  let rec block i =
    if Int64_u.to_int i + 32 > n then word i
    else
      let r0 = swar_raw (Bytes.unsafe_get_int64_ne_indexed_by_int64 s i) in
      let r1 =
        swar_raw
          (Bytes.unsafe_get_int64_ne_indexed_by_int64 s Int64_u.(i + #8L))
      in
      let r2 =
        swar_raw
          (Bytes.unsafe_get_int64_ne_indexed_by_int64 s Int64_u.(i + #16L))
      in
      let r3 =
        swar_raw
          (Bytes.unsafe_get_int64_ne_indexed_by_int64 s Int64_u.(i + #24L))
      in
      if not Int64_u.(r0 lor r1 lor r2 lor r3 land mask = #0L) then
        if not Int64_u.(r0 land mask = #0L) then word i
        else if not Int64_u.(r1 land mask = #0L) then word Int64_u.(i + #8L)
        else if not Int64_u.(r2 land mask = #0L) then word Int64_u.(i + #16L)
        else word Int64_u.(i + #24L)
      else block Int64_u.(i + #32L)
  in
  block #0L [@nontail]

Note the [@nontail] annotation at the very last line, because without it, the compiler will complain:

File "src/memchr.ml", line 189, characters 2-7:
189 |   block #0L
        ^^^^^
Error: This value is local
         because it is allocated at file "src/memchr.ml", lines 166-187, characters 16-35 containing data
         which is local to the parent region
         because it closes over the value s at file "src/memchr.ml", line 169, characters 68-69
         which is local to the parent region.
       However, the highlighted expression is expected to be local to the parent region or global
         because it is the function in a tail call.

Lines 166-187 is talking about the definition of let rec block i, whereas line 169 is specifically talking about the let r0 = swar_raw ... line within let rec block i.

I admit I found it hard to decipher what it is trying to warn me about, because it seemed to be telling me that a local variable is escaping to the outer parent region, so my instinct was to add the exclave keyword, and I asked Claude about it. It came back to me saying that I should instead use [@nontail] to silence the warning, and I’ve been reassured by it that this is a “standard idiom, and Base uses it in exactly this situation”.

Now that I’m looking at it with fresh eyes, it’s actually clear now that it did highlight that s is being closed over by block, which then makes it a region-local closure that’s calling itself after capturing s, and this is a soundness problem because the next recursive call now references s again, which was freed at the end of the first call of block. The way I understand it is that s has been moved into the block closure, and the closure itself implements FnOnce in Rust-speak as s is marked as local, i.e. owned by ml_memchr and then had its ownership transferred to block.

This however still isn’t immediately obvious to me about why this particular closure is a problem when it comes to performance – I had to ask Claude to do a CMM dump to see that the issue here is that ones and cs are being loaded from the closure environment rather than being directly stored on any register, costing 8 extra memory loads per iteration of block as swar_raw uses both 4 times in a row to calculate r0 to r3. Anyhow, here’s the CMM dump of ml_memchr loads with the [@nontail] annotation:

(xor (load_mut int (+a (load val (+a my_closure 48)) i))
     (load int (+a to_cmm_split_173 16)))     ; cs, loaded from the closure
(- prim (load int (+a to_cmm_split_171 24)))  ; ones, loaded from the closure

That’s certainly the case here, now I learn something new too! I’m wondering why then the closure isn’t using the scratch registers to store cs and ones here then and instead chose to use loads, the plot thickens…

5

Thanks for the details. I investigated a bit your example, and I think that the only reason your program (as you showed it) didn’t get properly simplified away is that even with aggressive (-O3) settings, the block and word loops were not getting inlined properly.

If you add inlining attributes (let[@inline always] rec word ...) you should get a single function with no allocations.

I can also help you understand the local escaping error. The issue that you solved with [@nontail] is a known side-effect of local allocations: if a function performs local allocations, it has to reset its allocation stack before returning, so it cannot tail-call other functions unless the function and all its arguments are not local (in which case the reset can occur before the call).
OxCaml doesn’t really have ownership (at this moment), so your reasoning about s moving into block is wrong: s is a local parameter, so it lives on the parent’s stack and will never be destroyed during the call to ml_memchr.

Finally, the performance issue indeed comes from the reads of cs and ones from a closure. Since block wasn’t inlined, cs and ones were not directly in scope so they had to be loaded from a closure, either swar_raw’s one (if no further optimisations occur) or block’s one (the compiler can “unbox” swar_raw’s closure inside block’s closure, removing one level of indirection).
Inlining the functions all the way down restores the ability to use cs and ones directly.

As a last thing, the code you’ve shown for breaking out of the loop is actually equivalent to mine.
Here is a simple explanation with gotos and labels of how my version works:

try
  while (* loop_start: *) ... do
    ... raise Found (* goto found *) ...
    (* goto loop_start *)
  done
  (* goto try_end *)
with Found ->
  (* found: *)
  ()
  (* goto try_end *)
(* try_end: *)

Your version (with an extra raise Found) is actually slightly less efficient because you’re basically replacing the goto try_end at the end of the loop by goto found, which itself jumps to try_end. But I think the compiler should manage to perform the shortcut anyway, so in the end the difference might not be observable at all.

6

IIRC the Stdlib.Exit exception is often advised for these early-returns cases.

The Exit exception is not raised by any library function. It is provided for use in your programs.

7

Regarding using local exceptions, I don’t think we currently do something like: Turn local exceptions into jumps by alainfrisch · Pull Request #638 · ocaml/ocaml · GitHub

It would be nice to turn local exceptions that don’t escape into Static catches, so that then the exception raise would turn into a jump (and exceptions with arguments could pass arguments for “free” – no allocation). This could also efficiently enable more complicated patterns with multiple exceptions.

8

Indeed, that is exactly the missing piece before I can comfortably use exceptions as breaks. Without that patch, I’d be worried about the overhead that all proposals to mimic the functionality of break with exceptions would create. The PR got closed because it’s waiting for “typed effects and flambda to detect and optimize local exceptions” – what’s the conclusion there?

9

Flambda 2 (which is part of OxCaml) does optimise exceptions away in some cases. The exception does not have to be local, but it needs to use raise_notrace, and there must be no other ways to reach the exception handler (which is the hard part, as any non-inlined function call in the try ... with body is considered as potentially reaching the handler).
In the case of a local exception, it can also remove the exception allocation, although there is a small bit of code left that cannot be removed at the moment (it only increments a global counter, but it’s in C code so the OCaml optimiser doesn’t know what it’s doing and keeps it just in case).

As an example, all three of the following functions get optimised to simple jumps:

let f r =
  let exception Jump_f in
  try
  while !r do
    if !r then raise_notrace Jump_f
    else ()
  done
  with Jump_f -> ()

exception Jump_g

let g r =
  try
  while !r do
    if !r then raise_notrace Jump_g
    else ()
  done
  with Jump_g -> ()

let h (type a) r v =
  let exception Jump_h of a in
  try
  while !r do
    if !r then raise_notrace (Jump_h (!v))
    else ()
  done;
  !v
  with Jump_h x -> x

(I have used references to simulate non-determinism without introducing a function call.)

10

Okay, so I verified from the generated assembly that exception catching really does compile down to a simple jump in my program. I’m going to walk through exactly how I convinced myself about it by showing the disassembly and the surface OCaml code that I believe it was generated from:

 14a:   4c 8b 0c 18             mov    (%rax,%rbx,1),%r9
 14e:   49 31 d1                xor    %rdx,%r9
 151:   4d 89 cc                mov    %r9,%r12
 154:   49 83 f4 ff             xor    $0xffffffffffffffff,%r12
 158:   49 29 f9                sub    %rdi,%r9
 15b:   4d 21 e1                and    %r12,%r9
 15e:   49 21 f1                and    %rsi,%r9
 161:   4d 85 c9                test   %r9,%r9
 164:   75 0e                   jne    174 <camlMemchr__memchr_11_29_code+0x154>

This part here seems to correspond to the SWAR memchr operation: first, I’ve inspected manually that both rdi and rsi holds ones and mask respectively (i.e. 0x0101... and 0x8080...); rdi is then used to subtract whatever’s in the r9 register, while cs is used to AND the r9 register, then r9 gets compared with 0 via the test r9, r9 instruction, which suggests that the entire operation is emitted by the following OCaml expression:

let w = Int64_u.((Bytes.unsafe_get_int64_ne_indexed_by_int64 s i) lxor cs) in
let r = Int64_u.((w - ones) land lognot w) in
if not Int64_u.(r land mask = #0L) then raise_notrace Exit

I’ve made some modifications, but it’s essentially equivalent to the surface OCaml code here:

Naturally, the next step is to check and see whether the code at 174 corresponds to the statements following the exception catching of Exit:

 174:   49 89 4e 40             mov    %rcx,0x40(%r14)
 178:   48 89 d9                mov    %rbx,%rcx
 17b:   48 d1 e1                shl    $1,%rcx
 17e:   4c 8b 04 24             mov    (%rsp),%r8
 182:   49 29 c8                sub    %rcx,%r8
 185:   49 83 f8 01             cmp    $0x1,%r8
 189:   7e 5d                   jle    1e8 <camlMemchr__memchr_11_29_code+0x1c8>

It’s a bit cryptic, but what’s happening here is that since OCaml integers are tagged, there needs to be some arithmetic calculation to both tag and untag them. As a result, OCaml int can only represent 63-bit integers on 64-bit machines, because the lowest bit is reserved for the tag. What is a tag used for, really? Without it, the OCaml GC can’t distinguish between a pointer and an integer, so OCaml has a design trade-off to represent 1 bit less of integer in order to enable storage of ints as just an immediate value, rather than boxing it as I’ve initially assumed and corrected by @vlaviron above. In OCaml GC’s scheme, a tag bit of 1 means immediate value, whereas 0 denotes a pointer.

With that all said, the operation of tagging a raw int64# now becomes clear – we just need to shift left by 1, and then add 1, i.e. tag(i) = 2i + 1. You’ll see on line 17b, it essentially is doing exactly that on rcx, but it seems to be missing the +1. It turns out that r8 stores a tagged integer, so r8 carries something like 2n + 1, and what happens if you subtract rcx from it? You’d get 2(n - i) + 1, and if i = n, then the result would just be 1, which is what line 185 is comparing against.

Line 189 is then doing a jump if the result is less than or equal to “0”, which essentially skips all the code following 189 and all the way to 1e8. That’s about 95 bytes skipped – not a small amount, which is suggestive that we are looking at a conditional statement that holds a substantial amount of code. I’m thus led to believe that the disassembly above corresponds to the following surface OCaml code:

Finally, the nail to the coffin is by looking further into what 1e8 holds:

 1e8:   48 c7 c0 ff ff ff ff    mov    $0xffffffffffffffff,%rax
 1ef:   48 8b 5c 24 08          mov    0x8(%rsp),%rbx
 1f4:   49 89 5e 40             mov    %rbx,0x40(%r14)
 1f8:   48 8d 44 00 01          lea    0x1(%rax,%rax,1),%rax
 1fd:   48 83 c4 28             add    $0x28,%rsp
 201:   c3                      ret

Finally we see a ret on line 201! This is a strong signal that we’ve reached the end of the function is now returning back to the caller. I have not really looked closely at what the registers are doing here, but I’m guessing it is restoring the caller’s stack frame and storing the return value into rax.

Conclusion

Notice how we didn’t even go over where the raise_notrace Exit became. This means that the compiler has indeed “swallowed” the exception altogether and didn’t emit any code whatsoever to represent it, because it is smart enough to know that Exit isn’t being used at all, so it eliminated all kinds of exception handling, even down to the raise.