Mantis Bug Tracker

View Issue Details Jump to Notes ] Issue History ] Print ]
IDProjectCategoryView StatusDate SubmittedLast Update
0007440OCamlmiddle end (typedtree to clambda)public2016-12-23 22:542017-03-07 13:17
Reportermarkghayden 
Assigned To 
PrioritynormalSeverityfeatureReproducibilityalways
StatusacknowledgedResolutionopen 
PlatformAMD64OSMacOSOS Version10.12.2
Product Version4.04.0 
Target VersionlaterFixed in Version 
Summary0007440: comparison operations on abstract types and max/min are not specialized
DescriptionSpecialization of integer and floating point comparisons (presumably also char and bool) seems to be brittle.

See the examples below where in many cases the comparison is not specialized and so external C call is made to the runtime comparison routine, losing an easy optimization opportunity to replace C call with assembly.

Also, Pervasives.min/max seem to never be specialized, even when inlined (which they should probably always be). To get specialization, you appear to need to write own functions, with type-casts.

Actual testing was done with 4.05.0 trunk.

(*********************************************************************)

let float_zero = 0.0 ;;

let int_zero = 0 ;;

(* Is specialized
 *)
let float_test0 v =
  v >= float_zero
;;

(* Is specialized
 *)
let int_test0 v =
  v >= int_zero
;;

(*********************************************************************)

module AbsFloat : sig type t val zero : t end = struct
  type t = float
  let zero = 0.0
end

(* Not specialized
 *)
let float_test1 v =
  v >= AbsFloat.zero
;;

(*********************************************************************)

module AbsInt : sig type t val zero : t end = struct
  type t = int
  let zero = 0
end

(* Not specialized
 *)
let int_test1 v =
  v >= AbsInt.zero
;;

(*********************************************************************)

(* Add inline for good measure.
 *)
let [@inline] min x y = if x <= y then x else y ;;
let [@inline] max x y = if x >= y then x else y ;;

(* Not specialized
 *)
let float_max0 (v0:float) (v1:float) =
  max v0 v1
;;

(* Is specialized
 *)
let float_max1 (v0:float) (v1:float) =
  if v0 >= v1 then v0 else v1
;;

(* Not specialized
 *)
let int_max0 (v0:int) (v1:int) =
  max v0 v1
;;

(* Is specialized
 *)
let int_max1 (v0:int) (v1:int) =
  if v0 >= v1 then v0 else v1
;;

(*********************************************************************)
Steps To ReproduceCompile attached ml file with various examples.
TagsNo tags attached.
Attached Files? file icon bf.ml [^] (1,321 bytes) 2016-12-23 22:54 [Show Content]

- Relationships
duplicate of 0007441acknowledged Array operations not specialization during inlining. 
duplicate of 0007442acknowledged array operations on abstract types are never specialized aka "Information Hiding Considered Harmful to Performance" 
related to 0005592resolved inlining does not reduce polymorphism to concrete type to generate optimized code 

-  Notes
(0017170)
xleroy (administrator)
2017-01-14 16:23

Your three reports (0007440, 0007441, 0007442) are manifestations of the same fact: the OCaml compiler performs type-based optimizations first, then erases types, then performs all the other optimizations. This is very unlikely to change in the near future, as it would require a total rewrite of the compiler.
(0017174)
markghayden (reporter)
2017-01-14 21:09

Thanks for the extra information. I guess if the Ocaml compiler was not designed to use type information for optimization in later optimization stages, that is the way it is.

Since there is little prospect of change, could limitations like these be documented? For instance, some developers might think "Array.fold_left (+.) 0.0 a" is good programming style, without understanding the resulting program will be 400-1000% slower than a hand-written loop (in addition to flushing the minor heap).

It seems as though for the foreseeable future, best-practices for developing efficient software with Ocaml include:

* Avoid use of abstract data types
* Avoid use of polymorphic array iterators, including all iterators in the Array module.
* Avoid use of polymorphic comparisons and similar functions such as min/max

Maybe there are some other suggestions the Ocaml team is aware of?

I think consideration should be given for addressing these at some point. In addition to the obvious direct effect on performance, these likely have follow-on effects when inlining is considered. For instance, when a call to caml_compare is specialized with an integer comparison or a polymorphic Array.get (which tests for type of array and makes possible allocation of boxed float) is replaced with instructions for simple array lookup, that makes the resulting code more attractive for inlining.
(0017176)
dobenour (reporter)
2017-01-15 03:33

xleroy: Would it be possible to add a partial monomorphization pass, when the whole program is available?

By partial monomorphization I mean a pass that monomorphizes everything it can. It can't get everything (due to polymorphic recursion, among other things). But it can get a lot of it.

This is an area where GHC's strongly typed Core Wins Big, but it does so via hand-written rewrite rules.

In Rust, using iterators doesn't cost ANY performance – in fact, in *helps* performance by eliminating bounds checks that aren't needed. This is possible because of monomorphization.

- Issue History
Date Modified Username Field Change
2016-12-23 22:54 markghayden New Issue
2016-12-23 22:54 markghayden File Added: bf.ml
2016-12-23 22:58 gasche Severity minor => feature
2016-12-23 22:59 gasche Relationship added related to 0005592
2017-01-14 16:21 xleroy Relationship added duplicate of 0007441
2017-01-14 16:21 xleroy Relationship added duplicate of 0007442
2017-01-14 16:23 xleroy Note Added: 0017170
2017-01-14 16:23 xleroy Status new => acknowledged
2017-01-14 16:23 xleroy Target Version => later
2017-01-14 21:09 markghayden Note Added: 0017174
2017-01-15 03:33 dobenour Note Added: 0017176
2017-02-23 16:42 doligez Category Ocaml optimization => -Ocaml optimization
2017-02-27 15:53 doligez Severity feature => tweak
2017-02-27 15:53 doligez Category -Ocaml optimization => middle end (typedtree to clambda)
2017-03-07 13:17 shinwell Severity tweak => feature


Copyright © 2000 - 2011 MantisBT Group
Powered by Mantis Bugtracker