Mantis Bug Tracker

View Issue Details Jump to Notes ] Issue History ] Print ]
IDProjectCategoryView StatusDate SubmittedLast Update
0005324OCamlOCaml generalpublic2011-08-01 17:012016-01-20 15:42
Assigned To 
PlatformOSOS Version
Product Version3.12.0 
Target VersionFixed in Version 
Summary0005324: Linear Scan Register Allocator for ocamlopt and ocamlnat
DescriptionAs announced on the mailinglist, here is the first version of the linear scan algorithm for ocamlopt and ocamlnat.
TagsNo tags attached.
Attached Filesdiff file icon ocaml-linear-scan-20110801.diff [^] (32,036 bytes) 2011-08-01 17:01 [Show Content]
txt file icon timings_runtime_amd64.txt [^] (3,311 bytes) 2011-08-19 09:48 [Show Content]
txt file icon timings_runtime_i386.txt [^] (2,678 bytes) 2011-08-19 09:48 [Show Content]
diff file icon ocaml-linear-scan-20110819.diff [^] (31,379 bytes) 2011-08-19 10:03 [Show Content]
pdf file icon compiletime_timings.pdf [^] (82,678 bytes) 2011-08-24 20:45
pdf file icon runtime_timings.pdf [^] (83,598 bytes) 2011-08-24 20:45
diff file icon ocaml-linear-scan-20110903.diff [^] (35,759 bytes) 2011-09-03 18:02 [Show Content]
diff file icon ocaml-linear-scan20110929.diff [^] (33,790 bytes) 2011-09-29 15:47 [Show Content]
diff file icon ocaml-linear-scan-20111014.diff [^] (28,643 bytes) 2011-10-14 11:09 [Show Content]

- Relationships

-  Notes
frisch (developer)
2011-08-02 21:06

This patch is very interesting.

Could you post here some timings (compilation speed and performance of compiled code)?

Minor question about the patch: wouldn't it be cleaner to have a single function Asmgen.regalloc with a conditional on use_linscan, rather than having two functions called in sequence that do their job or nothing according to the situation?

Also, is it really necessary to redefine sys_time? (As opposed to using Sys.time which is in the stdlib.)
meurer (developer)
2011-08-03 10:20

I forwarded your questions. As said, it's the very first working patch, and there are no timing results yet.
meurer (developer)
2011-08-18 19:13

I've imported the most recent patch from Marcell with some cleanups, merged the latest changes from the 3.12 branch and uploaded the project to GitHub at [^] in the linear-scan-register-allocator branch (for reference).

Marcell did some benchmarking and will publish the results soon.
marcell (reporter)
2011-08-19 10:09

I've added timings for the runtime performance for amd64 and i386. Both showing the runtime for code compiled with the graph-coloring and the linear-scan algorithm and the ratio of the two measurements.

Although meurer already merged the latest changed into the GitHub-Repository I also added the latest diff.

I will add timings for the compilation time soon.
marcell (reporter)
2011-08-24 20:50

Added timing results for the compilation time and also added the runtime results again as a more readable diagram.
meurer (developer)
2011-09-03 18:03

I've updated the patch with several cleanups and uploaded a new diff.
meurer (developer)
2011-09-29 15:48

Updated patch, with several cleanups and fixes for the ARM port.
xleroy (administrator)
2012-01-31 09:03

Here is my analysis of this proposal. The "big" users of OCaml, esp. the members of the Caml consortium, push strongly towards improving the performance of ocamlopt-generated code, but don't really care about compilation times. Linear scan register allocation goes in a different direction: fast compilation times at the cost of slightly lower quality of the generated code. I would rather invest time and effort on replacing ocamlopt's Briggs-style graph coloring by George and Appel's IRC graph coloring: this should result in slightly faster generated code and slightly lower compilation times at the same time. For the time being, let me just put this PR in the "suspended" state.
meurer (developer)
2012-01-31 09:40

Ok, makes sense.
frisch (developer)
2016-01-19 17:52

The discussion has resumed here: [^]

- Issue History
Date Modified Username Field Change
2011-08-01 17:01 meurer New Issue
2011-08-01 17:01 meurer File Added: ocaml-linear-scan-20110801.diff
2011-08-02 21:06 frisch Note Added: 0006073
2011-08-03 10:20 meurer Note Added: 0006075
2011-08-18 19:13 meurer Note Added: 0006094
2011-08-19 09:48 marcell File Added: timings_runtime_amd64.txt
2011-08-19 09:48 marcell File Added: timings_runtime_i386.txt
2011-08-19 10:03 marcell File Added: ocaml-linear-scan-20110819.diff
2011-08-19 10:09 marcell Note Added: 0006095
2011-08-24 20:45 marcell File Added: compiletime_timings.pdf
2011-08-24 20:45 marcell File Added: runtime_timings.pdf
2011-08-24 20:50 marcell Note Added: 0006103
2011-09-03 18:02 meurer File Added: ocaml-linear-scan-20110903.diff
2011-09-03 18:03 meurer Note Added: 0006110
2011-09-29 15:47 meurer File Added: ocaml-linear-scan20110929.diff
2011-09-29 15:48 meurer Note Added: 0006134
2011-10-14 11:09 meurer File Added: ocaml-linear-scan-20111014.diff
2012-01-31 09:03 xleroy Note Added: 0006854
2012-01-31 09:03 xleroy Status new => resolved
2012-01-31 09:03 xleroy Resolution open => suspended
2012-01-31 09:40 meurer Note Added: 0006855
2016-01-19 17:52 frisch Note Added: 0015264

Copyright © 2000 - 2011 MantisBT Group
Powered by Mantis Bugtracker