# Why is int comparison not just (-)?

Let `a` and `b` be two ints (e.g. `let a = read_int() let b = read_int()`). Looking in compiler explorer, the function

``````let f() = Pervasives.compare a b
``````

calls `caml_int_compare`. I can write an optimised (I think) version of `compare`, monomorphic for int, as

``````let int_compare (x:int) y =
if x>y then 1
else if y>x then -1
else 0
``````

which at least doesnβt call any external function, but still has two branches. This is what Batteries does in its `BatInt` module.

But if the semantics of `compare` are just βif a>b then result>0, if a<b then result<0, if a=b then result=0β, then why isnβt int comparison just `(-)`? Wouldnβt this be much faster? This seems to me an important thing to micro-optimise, seeing as int comparison is used so pervasively throughout most ocaml code.

``````# let compare x y = x - y ;;
val compare : int -> int -> int
# compare 3 (-2) ;;
- : int = 5 (*β1 β*)
# compare 42 18 ;;
- : int = 24 (*β1 β*)
# compare 4 19 ;;
- : int = -15 (*β-1 β*)
# compare max_int min_int ;;
- : int = -1 (*β-1 β*)
``````

Beware over|underflows.

10 Likes

I happen to have played with exactly this today (I was wondering how to get rid of a call to `compare` on integers to avoid a Pervasives deprecation warning), and I started wondering how efficient the following would be in practice:

``````let compare_int (a : int) b =
let int_of_bool (b : bool) = (Obj.magic b : int) in
int_of_bool (a > b) - int_of_bool (a < b)
``````

the generated code looks nicer than the BatInt version suggested above (no branches), and I wonder how it compares in term of raw speed to calling the `caml_int_compare` C function (which is what the compiler does on a call to `compare` on integers).

2 Likes

This is in fact what `Base.Int.compare` (and therefore `Core.Int.compare`) does (at least, in the latest GitHub versionβI think the opam version is still using `Poly.compare`). Apparently, it is about 20%-25% faster.

``````open! Core
open Core_bench.Std

let a = Sys.opaque_identity 0
let b = Sys.opaque_identity Int.min_value

let compare_int (a : int) b =
let int_of_bool (b : bool) = (Obj.magic b : int) in
int_of_bool (a > b) - int_of_bool (a < b)
;;

let () =
[ Bench.Test.create ~name:"Poly.compare" (fun () -> Poly.compare a b)
; Bench.Test.create ~name:"Int.compare" (fun () -> compare_int a b)
]
|> Bench.make_command
|> Command.run
;;
``````

Output:

``````Estimated testing time 20s (2 benchmarks x 10s). Change using '-quota'.
ββββββββββββββββ¬βββββββββββ¬βββββββββββββ
β Name         β Time/Run β Percentage β
ββββββββββββββββΌβββββββββββΌβββββββββββββ€
β Poly.compare β   3.57ns β    100.00% β
β Int.compare  β   2.69ns β     75.33% β
ββββββββββββββββ΄βββββββββββ΄βββββββββββββ
``````
2 Likes

Nice, the bench example and array output.

Is int_of_bool using Obj.magic a hack to remove an if-then-else?

Yeah, otherwise it outputs a branch.