# Int32 optimization puzzle

**URL:** <https://discuss.ocaml.org/t/int32-optimization-puzzle/13369>\
**Category:** Learning\
**Tags:** optimization\
**Created:** [November 4, 2023, 5:37pm UTC](https://discuss.ocaml.org/t/int32-optimization-puzzle/13369 "2023-11-04T17:37:54Z")\
**Posts on this page:** 4\
**Page:** 1

<div class="post-metadata">

**Author:** ![dbuenzli](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/dbuenzli/32/18_2.png) [@dbuenzli](https://discuss.ocaml.org/u/dbuenzli)\
**Post date:** [November 4, 2023, 5:37pm UTC](https://discuss.ocaml.org/t/int32-optimization-puzzle/13369/1 "2023-11-04T17:37:54Z")

</div>

I have the following code of which I don’t quite understand the performance behaviour.

This is a CRC-32 computation made with `int32` OCaml integers (I would like to get rid of [this int32 unboxing hack](https://github.com/dbuenzli/zipc/blob/main/src/zipc_deflate.ml#L76-L132) in a library, especially since it makes Adler-32 computation actually slower).

Basically on my machine (arm64, ocaml 14.1.0) the runs with the code below are done in 80ms (which is larger than when using the unboxing trick).

But if I replace in the `string` function the `k` indexing the table by say the `byte` and `Sys.opaque` identity the `k`, I get runs of 30ms. So something seems not to quite add up, I have looked at the assembly or the lambda code but nothing jumps to my eyes (though I’m rusty on that).

Has maybe someone a hint about what may be happening ?

```ocaml
cat - > /tmp/crc.ml <<EOF  
let poly = 0xedb88320l
let table =
  let init i =
    let c = ref (Int32.of_int i) in
    for k = 0 to 7 do
      c :=
        if Int32.logand !c 1l <> 0l
        then (Int32.logxor poly (Int32.shift_right_logical !c 1))
        else (Int32.shift_right_logical !c 1);
    done; !c
  in
  Bigarray.Array1.init Bigarray.int32 Bigarray.c_layout 256 init

let string s =
  let i = ref 0 and max = String.length s - 1 in
  let c = ref 0xFFFF_FFFFl in
  while (!i <= max) do
    let ci = Int32.to_int !c in
    let byte = String.get_uint8 s !i in
    let k = (ci lxor byte) land 0xFF in
    c := Int32.logxor
        (Bigarray.Array1.get table k : int32)
        (Int32.shift_right_logical !c 8);
    incr i;
  done;
  Int32.logxor !c 0xFFFF_FFFFl

let random ~length =
  let ic = In_channel.open_bin "/dev/random" in
  let finally () = In_channel.close_noerr ic in
  Fun.protect ~finally @@ fun () ->
  In_channel.really_input_string ic length |> Option.get

let test_speed crc_of_string s =
  let start = Sys.time () in
  let crc = crc_of_string s in
  let stop = Sys.time () in
  let dur = (stop -. start) *. 1000. in
  Format.printf "%dms %lx\n" (truncate dur) crc

let main () =
  let length = (20 * 1024 * 1024) in
  let s = random ~length in
  test_speed string s;
  test_speed string s

let () = if !Sys.interactive then () else main ()
EOF 
cd /tmp && ocamlopt crc.ml && ./a.out
```

---

<div class="post-metadata">

**Author:** ![silene](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/silene/32/2707_2.png) [@silene](https://discuss.ocaml.org/u/silene)\
**Post date:** [November 5, 2023, 7:12am UTC](https://discuss.ocaml.org/t/int32-optimization-puzzle/13369/2 "2023-11-05T07:12:06Z")

</div>

> [@dbuenzli](#):
>
> But if I replace in the `string` function the `k` indexing the table by say the `byte` and `Sys.opaque` identity the `k`, I get runs of 30ms. So something seems not to quite add up, I have looked at the assembly or the lambda code but nothing jumps to my eyes (though I’m rusty on that).

If I understand correctly, your replacement code indexes the array by just `byte` instead of `!c lxor byte` and thus no longer needs to wait for the memory load `c := table[k]` from the previous iteration to complete before processing further, right? Then it does not seem that surprising that your code becomes much faster, since the processor has a lot more leeway in reordering the instructions. But perhaps I am misunderstanding what changes your are making to your code.

---

<div class="post-metadata">

**Author:** ![dbuenzli](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/dbuenzli/32/18_2.png) [@dbuenzli](https://discuss.ocaml.org/u/dbuenzli)\
**Post date:** [November 5, 2023, 1:30pm UTC](https://discuss.ocaml.org/t/int32-optimization-puzzle/13369/3 "2023-11-05T13:30:51Z")

</div>

> [@dbuenzli](#):
>
> ```auto
> let byte = String.get_uint8 s !i in
> let k = (ci lxor byte) land 0xFF in
> ignore (Sys.opaque_identity k);
> c := Int32.logxor
> (Bigarray.Array1.get table byte : int32)
> (Int32.shift_right_logical !c 8);
> 
> ```

Just to make things clear ^.

But yes I guess you are right. Somehow my mental model eschews all the crazy stuff modern processors do.

---

<div class="post-metadata">

**Author:** ![dbuenzli](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/dbuenzli/32/18_2.png) [@dbuenzli](https://discuss.ocaml.org/u/dbuenzli)\
**Post date:** [November 8, 2023, 9:01pm UTC](https://discuss.ocaml.org/t/int32-optimization-puzzle/13369/4 "2023-11-08T21:01:52Z")

</div>

> [@dbuenzli](#):
>
> (I would like to get rid of [this int32 unboxing hack](https://github.com/dbuenzli/zipc/blob/main/src/zipc_deflate.ml#L76-L132) in a library, especially since it makes Adler-32 computation actually slower).

Just to wrap this up. I removed the `uint32` as `int` trick which I was really not happy with. Notably it changes the implementation for `js_of_ocaml` apps depending on the bitness of the platform on which you compile your app, which is ugly.

Instead I decided to take the slowdown\[1\] from 2.03s to 2.10s on unzipping the [silesia corpus](https://sun.aei.polsl.pl/~sdeor/index.php?page=silesia) (75Mo that uncompress to 202Mo) and focus to try to improve the CRC-32 computation as OCaml `int32`. That’s nevertheless worth pursuing since it eats quite a bit in unzipping archives.

To do this I turned to what the internet is to be liked for which is: people obsessing and maintaining webpages on niche subjects. Namely [fast CRC-32 computation](https://create.stephan-brumme.com/crc32).

I simply moved one step on the performance ladder shown there and [took the “slicing-by-4” approach](https://github.com/dbuenzli/zipc/commit/df566526e0e0ba751de3165728b81fc5b7205a1b). That lead to 1.69s\[2\] unzipping time and made me happy enough to simply go with that (for reference the `unzip` 6.00 tool on my machine takes 1.12s on that test case) .

* * *

1. But the 1.4 faster Adler-32. 

2. I did not try that technique with the `uint32` as `int` ;–)