Why is int comparison not just (-)?

Learning
1

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.

2 
# 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
3

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
4

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
5

Nice, the bench example and array output.

6

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

7

Yeah, otherwise it outputs a branch.