0005205: Performance bug: pushing let-alias inside loop body

View Issue Details [ Jump to Notes ]

[ Issue History ] [ Print ]

Project

Category

View Status

Date Submitted

Last Update

0005205

OCaml

OCaml general

public

2011-01-17 10:23

2012-09-25 20:38

Reporter

frisch

Assigned To

xleroy

Priority

high

Severity

minor

Reproducibility

have not tried

Status

closed

Resolution

fixed

Platform

OS Version

Product Version

Target Version

Fixed in Version

3.13.0+dev

Summary

0005205: Performance bug: pushing let-alias inside loop body

Description

ocamlopt inlines some local bindings that are pure and used once. However, the notion of "used once" is syntactic, which allows some non-trivial expressions (typically field projection) to be pushed within a loop body instead of being evaluated once outside the loop.

Here is an example:

=================================================================
type t1 = {x:int}
type t2 = {y:t1}

let f {y = {x = x1}} {y = {x = x2}} {y = {x = x3}} {y = {x = x4}} =
(*
  let x1 = abs x1 in
  let x2 = abs x2 in
  let x3 = abs x3 in
  let x4 = abs x4 in
*)

  let r = ref 0 in
  for i = 1 to 1000000 do
    for j = 1 to 1000 do
      r := x1 + x2 + x3 + x4;
    done
  done;
  !r

let () =
  let r = {y = { x = 2 }} in
  Printf.printf "%i\n%!" (f r r r r)
=================================================================

On a Linux x64 (Intel Core i7, 2.80 GHz), this program takes 2.34 seconds
and only 1.18 seconds after uncommenting the first lines in f. The effect of these lines is to force the field accesses to be done outside the loop. (On simpler loops, the processor does an amazing job of removing the indirection overhead.)

The same problem appear because of pushing field accessed inside lambdas, e.g.:

=================================================================
  let rec f () = r := x1 + x2 + x3 + x4 in
  for i = 1 to 1000000 do
    for j = 1 to 1000 do
      f ()
    done
  done;
=================================================================

(Timing goes from 5s to 1.5s by enabling the 'let xi = abs xi' lines.)

Tags

No tags attached.

Attached Files

fix_5205.diff [^] (3,404 bytes) 2011-01-17 11:08 [Show Content] [Hide Content]

Index: simplif.ml
===================================================================
--- simplif.ml	(revision 10928)
+++ simplif.ml	(working copy)
@@ -262,38 +262,50 @@
 
   (* First pass: count the occurrences of all identifiers *)
   let occ = Hashtbl.create 83 in
+  let binding_depth = Hashtbl.create 83 in (* only kept for let-bound ids *)
+  let max_usage_depth = Hashtbl.create 83 in
+  let depth = ref 0 in  (* bumped inside lambda and loop bodies *)
+  let get_ref tbl v =
+    try Hashtbl.find tbl v
+    with Not_found ->
+      let r = ref 0 in
+      Hashtbl.add tbl v r;
+      r
+  in
+  let bind v =
+    Hashtbl.add binding_depth v !depth;
+    Hashtbl.add max_usage_depth v (ref !depth);
+  in
   let count_var v =
     try
       !(Hashtbl.find occ v)
     with Not_found ->
       0
-  and incr_var v =
-    try
-      incr(Hashtbl.find occ v)
-    with Not_found ->
-      Hashtbl.add occ v (ref 1) in
-
+  in
+  let use_var v =
+    incr (get_ref occ v);
+    if Hashtbl.mem binding_depth v then
+      let d = Hashtbl.find max_usage_depth v in
+      d := max !d !depth
+  in
   let rec count = function
-  | Lvar v -> incr_var v
+  | Lvar v -> use_var v
   | Lconst cst -> ()
   | Lapply(l1, ll, _) -> count l1; List.iter count ll
-  | Lfunction(kind, params, l) -> count l
+  | Lfunction(kind, params, l) -> count_deeper l
   | Llet(str, v, Lvar w, l2) when not !Clflags.debug ->
       (* v will be replaced by w in l2, so each occurrence of v in l2
          increases w's refcount *)
-      count l2;
-      let vc = count_var v in
-      begin try
-        let r = Hashtbl.find occ w in r := !r + vc
-      with Not_found ->
-        Hashtbl.add occ w (ref vc)
-      end
+      Hashtbl.add occ v (get_ref occ w);
+      (try Hashtbl.add max_usage_depth v (Hashtbl.find max_usage_depth w) with Not_found -> ());
+      count l2
   | Llet(str, v, l1, l2) ->
+      bind v;
       count l2;
       (* If v is unused, l1 will be removed, so don't count its variables *)
       if str = Strict || count_var v > 0 then count l1
   | Lletrec(bindings, body) ->
-      List.iter (fun (v, l) -> count l) bindings;
+      List.iter (fun (_, l) -> count l) bindings;
       count body
   | Lprim(p, ll) -> List.iter count ll
   | Lswitch(l, sw) ->
@@ -307,8 +319,8 @@
   | Ltrywith(l1, v, l2) -> count l1; count l2
   | Lifthenelse(l1, l2, l3) -> count l1; count l2; count l3
   | Lsequence(l1, l2) -> count l1; count l2
-  | Lwhile(l1, l2) -> count l1; count l2
-  | Lfor(_, l1, l2, dir, l3) -> count l1; count l2; count l3
+  | Lwhile(l1, l2) -> count l1; count_deeper l2
+  | Lfor(_, l1, l2, dir, l3) -> count l1; count l2; count_deeper l3
   | Lassign(v, l) ->
       (* Lalias-bound variables are never assigned, so don't increase
          v's refcount *)
@@ -318,6 +330,11 @@
   | Lifused(v, l) ->
       if count_var v > 0 then count l
 
+  and count_deeper l =
+    incr depth;
+    count l;
+    decr depth
+
   and count_default sw = match sw.sw_failaction with
   | None -> ()
   | Some al ->
@@ -363,7 +380,7 @@
   | Llet(Alias, v, l1, l2) ->
       begin match count_var v with
         0 -> simplif l2
-      | 1 when not !Clflags.debug ->
+      | 1 when !(Hashtbl.find max_usage_depth v) = Hashtbl.find binding_depth v && not !Clflags.debug ->
              Hashtbl.add subst v (simplif l1); simplif l2
       | n -> Llet(Alias, v, simplif l1, simplif l2)
       end

Relationships

has duplicate

0005288

closed

xleroy

fix escaping pattern aliases

Notes
(0005773) frisch (developer) 2011-01-17 10:27	The faulty optimization is implemented in Simplif.simplify_lets. I suggest to keep track of the depth where let variables are bound (bumping the depth when entering a lambda or loop body) and used, and not inline aliases which are used at a deeper level than their definition.

(0005774) frisch (developer) 2011-01-17 11:08	Suggested fix attached.

(0005777) frisch (developer) 2011-01-17 14:22	As an extra benefit, the patch avoids keeping references to useless parts of data structures. I'm wondering whether inlining let-aliases used only once is really a good heuristic. Isn't it generally better to load from memory early in order to improve pipelining? Has someone done any benchmark to see if the heuristic is useful?

Issue History
Date Modified	Username	Field	Change
2011-01-17 10:23	frisch	New Issue
2011-01-17 10:27	frisch	Note Added: 0005773
2011-01-17 11:08	frisch	File Added: fix_5205.diff
2011-01-17 11:08	frisch	Note Added: 0005774
2011-01-17 14:22	frisch	Note Added: 0005777
2011-05-17 16:48	doligez	Status	new => acknowledged
2011-05-17 16:48	doligez	Priority	normal => high
2011-06-10 09:14	frisch	Relationship added	has duplicate 0005288
2011-06-11 15:16	xleroy	Assigned To	=> xleroy
2011-06-11 15:16	xleroy	Status	acknowledged => resolved
2011-06-11 15:16	xleroy	Fixed in Version	=> 3.13.0+dev
2012-09-25 20:38	xleroy	Status	resolved => closed
2012-09-25 20:38	xleroy	Resolution	open => fixed