Use operations on multiple char at once ?

[bobot]

The function Bytes.get_int64_ne has been added in 4.08 (the underlying primitive something like 4.01). It allows to read directly an Int64 instead of reading char by char.

I don't know yet which speed up it could make to implement the different operations using it, but I was surprised nobody raised this possibility for this library.

[backtracking]

Hi François,
Thanks for pointing this out. Indeed, that would simplify the current code of function to_int64.

[bobot]

I though it could also speed-up bitwise functions like bw_and.

[bobot]

On a simple example replacing popcount and bw_and_in_place by functions that use int64 access, the time goes from 26s to 9s (26s to 15s for bw_and_in_place alone):

let pop v =
  let n = Bytes.length v.bits in
  let b = v.bits in
  let q = n lsr 3 in
  let q' = q lsl 3 in
  let r = ref 0 in
  for i = 0 to q - 1 do
    let i = i lsl 3 in
    r := !r + (Int64.popcount @@ Bytes.get_int64_ne b i)
  done;
  for i = q' to n - 1 do
    r := !r + Int.popcount (byte b i)
  done;
  !r

let[@inline always] bw_and_in_place_internal ~dst ~n b1 b2 =
  let q = n lsr 3 in
  let q' = q lsl 3 in
  for i = 0 to q - 1 do
    let i = i lsl 3 in
    Bytes.set_int64_ne dst i
      (Int64.( land ) (Bytes.get_int64_ne b1 i) (Bytes.get_int64_ne b2 i))
  done;
  for i = q' to n - 1 do
    set_byte dst i (byte b1 i land byte b2 i)
  done

It is also using Int.popcount. (In fact it is just a version coming from Containers or Base).

[backtracking]

Thanks @bobot for taking the time to make this experiment. Now I'm convinced that I should give it a try. At first sight, I would have thought that the boxing of int64 would be costly, but it seems it is not.

Note: your code is using Int64.popcount but there is no such thing is vanilla OCaml.

[bobot]

Those Int64 are unboxed automatically, even the local reference is unboxed. I used flambda for the tests, but I think without it the unboxing is still done.

Int.popcount and Int64.popcount comes from Containers and/or Base. In base, the first one uses the POPCNT, but not the second one, because they wanted to keep the unboxing. It is strange because we can use nowadays [@unboxed] for calling C code with unboxed value directly. I used an older version currently they are using https://github.com/janestreet/ocaml_intrinsics_kernel , which usese POPCNT https://github.com/janestreet/ocaml_intrinsics_kernel/blob/e133f6e9479bd0883c124c35acdbf1e7d6aac4e9/src/int64.ml#L39