Mantis Bug Tracker

View Issue Details Jump to Notes ] Issue History ] Print ]
IDProjectCategoryView StatusDate SubmittedLast Update
0006343OCamlOCaml backend (code generation)public2014-03-07 12:242014-03-13 10:40
Reporterfrisch 
Assigned Tofrisch 
PrioritynormalSeverityfeatureReproducibilityhave not tried
StatusresolvedResolutionfixed 
PlatformOSOS Version
Product Version 
Target VersionFixed in Version4.02.0+dev 
Summary0006343: Making better use of extra slots in the symbol corresponding to the current unit
DescriptionThe compilation of unit has recently been changed to map value identifiers defined in sub-modules into extra slots of the symbol corresponding to the current unit. This makes it possible to access those values directly by a single indirection from the global symbol. Unfortunately, this ability is not used optimally. For instance, consider:

==============================
module A1 = struct
  module A2 = struct
    let r = ref 1
  end
end

let f () = !A1.A2.r
==============================

Here, A2 and 4 are stored in extra slots of the global (fields number 2 and 3 respectively). Unfortunately, the reference to r in f still goes through 4 indirections from the global symbol, while 2 would be enough.

On a related note, if we put an .mli on this unit which forces some non-trivial coercions on A1 (e.g. an empty signature for A1), then it's even worse, since the indirections don't start from the global symbol, but from the function's environment (which is now required, the closure is no longer constant). To fix this part, one could keep extra slots in the global to store the uncoerced version of module identifiers, so that they can be accessed from this root symbol.
TagsNo tags attached.
Attached Filesdiff file icon pr_6343.diff [^] (2,807 bytes) 2014-03-07 14:53 [Show Content]

- Relationships
related to 0005537resolvedfrisch reducing repeated indirections to access variables in nested modules 

-  Notes
(0011024)
frisch (developer)
2014-03-07 15:06

I've attached a patch which attacks the main issue (not using existing global slots as a faster way to access nested value identifiers) by enriching the notion of approximation tracked during the closure conversion with a new case to represent the nth field of a global.

In the long tradition of meaningless but funny micro-benchmarks (Xavier, you're welcome :-)), I've tested the patch with:

module A1 = struct
  module A2 = struct
    let r = ref 1
  end
end

let f () =
  for i = 1 to 10000 do
    incr A1.A2.r
  done;
  !A1.A2.r

let () =
  for i = 1 to 100000 do ignore (f ()) done


and it runs about twice as fast as with the current trunk.

This would need to be checked, but I believe the patch could allow to simplify Translmod to avoid keeping track of a lambda-substitution to map identifiers to global field references.

That said, another approach would be to attack the issue precisely in Translmod directly, in order to get a nicer lambda code. One advantage is that it could in theory benefit more easily to bytecode (if we switch to the tranl_store way of compiling structures), which might be nicer for js_of_ocaml in particular.
(0011025)
frisch (developer)
2014-03-07 15:20

This seems to be related to 0005537 and 0005573.
(0011028)
frisch (developer)
2014-03-07 17:59

The patch also fixed the "related" note of the original ticket. Consider for instance:

foo.mli:
module A1 : sig end
val f : unit -> int


foo.ml:
module A1 = struct let r = ref 1 end
let f () = !A1.r

The "r" value is put in a global slot, and the "A1" block is created by accessing this global slot. This information is preserved in the approximation of A1, so that when the lambda code accesses A1.r, the closure conversion knows that the value can be retrieved from the global slot.

If A1 is completely hidden from the interface (or if "r" is added to it, so that there is no coercion involved), the lambda code for accessing A1.r will be quite different (it will start from the global symbol, not from the local A1 block), but the end result will be the same.
(0011033)
frisch (developer)
2014-03-10 11:08

Patch committed to trunk (commit 14452). It has the effect of turning more functions into closed ones, even if they seemingly have free variables in the lambda code (this already used to be the case, but less frequently). In such cases, we can allocate the corresponding closures statically (commit 14453).

- Issue History
Date Modified Username Field Change
2014-03-07 12:24 frisch New Issue
2014-03-07 14:53 frisch File Added: pr_6343.diff
2014-03-07 15:06 frisch Note Added: 0011024
2014-03-07 15:20 frisch Note Added: 0011025
2014-03-07 15:33 frisch Relationship added related to 0005537
2014-03-07 17:52 frisch Description Updated View Revisions
2014-03-07 17:59 frisch Note Added: 0011028
2014-03-10 11:08 frisch Note Added: 0011033
2014-03-13 10:40 frisch Status new => resolved
2014-03-13 10:40 frisch Fixed in Version => 4.02.0+dev
2014-03-13 10:40 frisch Resolution open => fixed
2014-03-13 10:40 frisch Assigned To => frisch


Copyright © 2000 - 2011 MantisBT Group
Powered by Mantis Bugtracker