8 ms·

CPU registers and OCaml

117 points by dodders 11y ago

cosmicexplorer 11y ago
Why wouldn't the OCaml compiler optimize away the variable usage in the first example? It seems an easy optimization to make if they're only used once.
- rayiner 11y ago
  Look at the live ranges in the function (the range between where a variable is defined and where it is used, i.e. the range over which the variable has a value that must be preserved because it will be used in the future). Generally register allocation algorithms will be able to assign different variables to the same register if their live ranges do not interfere (i.e. overlap). If live ranges overlap, that means their value needs to be preserved simultaneously, and they can't use the same register. In the code, there is a lot of overlapping live ranges. E.g. ax and xx. Those can be eliminated by moving code around, but most register allocators do not move code.
  - cosmicexplorer 11y ago
    Is there not like a "-O3" option to try aggressive code manipulation like that? Or is moving code around just not done at all because it's difficult to do correctly?
    - pcwalton 11y ago
      I think rematerialization covers most of the cases in which you would benefit from doing that (such as ax and xx), and rematting is standard in advanced compilers like GCC/LLVM.
  - pcwalton 11y ago
    A lot of register allocators can rematerialize, though, and that can have much the same effect. (ax and xx should be candidates for rematting.)
    - rayiner 11y ago
      Good point. Though rematerialization is still pretty rare considering the entire universe of compilers (e.g. Academic projects like Ocaml was).
      - pcwalton 11y ago
        Yeah, I was always under the impression that ocamlopt is fairly Plan 9-like; it produces medium quality code quickly, and doesn't have the full suite of compiler optimizations that projects like LLVM or HotSpot have.
lispm 11y ago
There is <> missing in line 3 of the first code snippet.
froh42 11y ago
Use a better algorithm instead of worrying about processor registers. And if you start considering the computer architecture think about caches, memory latency and bursting first. Use a cache-conscious data structure. Optimizing at the register level is ridiculous, this is the least place where you get significant returns for the effort you spend. Oh, and make it correct first, make it fast second. Use a profiler.
- brudgers 11y ago
  There are places where slow correct is worse than fast wrong [for some definitions of "correct" and/or "wrong"]. Janestreet works where perfect is the enemy of the good, and are probably looking at registers because they have already squeezed caches for performance juice. This is a post where the quant context matters. It's not a sophomore CS student's blog.
pcwalton 11y ago
I talked with Chris Lattner a few years ago about register allocation and he had an interesting perspective. In his view (from what I remember; my recollection could be somewhat incorrect) most of the classical academic research on it is solving the wrong problem. Most formulations of register allocation are graph coloring algorithms designed to answer the question "is this function colorable using K registers without spilling?" The algorithms for handling the case when you do spill usually don't have as much thought put into them. But this is emphasizing the wrong aspect of the problem in practice; for almost any interesting function on the commonly used architectures (x86/ARM), the answer to the theoretical question is trivially "no" (because there are relatively few registers), and the most important practical problem is how to spill effectively (including deciding whether to spill versus split versus rematerialize, etc.) As I understand it, that's the idea behind LLVM's (relatively) new greedy allocator [1]: the graph-coloring part of the problem is simple, and the focus is on spilling and splitting, problems that the classical academic literature has tended to put less emphasis on. [1]: http://blog.llvm.org/2011/09/greedy-register-allocation-in-llvm-30.html http://blog.llvm.org/2011/09/greedy-register-allocation-in-l...
- DannyBee 11y ago
  I'm going to guess you have misunderstood what Chris said (with no offense meant) :) Spilling is actually a very well known and very well studied problem, and in fact, most compilers and research spend a lot of time figuring out how to place spill code and coealesce copies, not how to color things. Chris knows this. I had discussions with him (many many years ago, before he ever started at Apple) about GCC's register allocation approach vs what he was thinking of doing for LLVM. There are actually only so many good approaches to spill code /rematerialization/live range splitting you can use. At some point, it's really just a large integer-linear programming problem. Note that coloring is essentially free on SSA form. It's linear time or better.
  - pcwalton 11y ago
    Regardless, the whole point of the greedy allocator is to throw out the fancy list of active intervals that linear scan maintains in favor of doing something simpler that allows more flexibility in spilling/splitting, right? For example: "Live ranges being spilled without being split first cause the mess that the rewriter is working so hard to clean up. We would much rather split them into smaller pieces that might be assignable, but this would require the linear scan algorithm to backtrack. This is very expensive, and full live range splitting isn't really feasible with linear scan." i.e. a weakness of linear scan is that the active list approach helps it solve the coloring problem quickly and accurately, but it comes with a big drawback that live range splitting is hard, which is the wrong tradeoff in practice.
DannyBee 11y ago
"If the code has more than that many variables, OCaml compiler has to park the extra variables in memory and this parking is called spilling." This is just wrong. It would be accurate to say "If the code has more than that number of variables live at the same time". If the computations are not live at the same time, they can share a register.
deleted 11y ago
[deleted]
deleted 11y ago
[deleted]
gct 11y ago
The notion that there's only 13/16 registers (assuming x86) hasn't been true for a long time. There's hundreds in the latest cores from Intel. It's true there's only 13/16 names for them, but with register renaming there's way more places to actually put data than that.
- rayiner 11y ago
  Register renaming solves a different problem than the one outlined in the article. Renaming allows to to eliminate write after read dependencies. E.g. Computing a value, storing it to AX, doing something with AX, computing another value, storing it to AX, doing something with AX. If the two computations are independent, the AX dependency is false and the OOO core can execute them concurrently by storing the results into two different rename registers and rewriting the "doing something with AX" to source their inputs from those two different registers instead. In terms of live ranges, the first value stored in AX has a live range that does not overlap that if the second value stored in AX. So the compiler can reuse AX for those two values without problems. That's not true in the scenario of the article without moving code around. The live ranges overlap--you have to keep around two or more distinct values before any of them are used. You can't store the results into the same register without clobbering one of the values. So the compiler is forced to introduce a memory operation by spilling a value, and the CPU can't do anything to eliminate that after the fact.
deleted 11y ago
[deleted]
tempodox 11y ago
Those are interesting observations. When doing something like `let rec loop ...`, I got into the habit of using parameters for only those entities that might change from one iteration to the next. The rest (as being constant / invariant across iterations) dwells in the closure env, if only for the sake of making the source code shorter. The article shows nicely how this obvious mental shortcut has its (equally obvious) costs. It's also a nice practical demonstration of how reading disassemblies is still an integral part of understanding a language, even this relatively abstract ML descendant.
a-dub 11y ago
Does OCaml generate code that makes use of SIMD?

117 points by dodders 11y ago

Why wouldn't the OCaml compiler optimize away the variable usage in the first example? It seems an easy optimization to make if they're only used once.

rayiner 11y ago
Look at the live ranges in the function (the range between where a variable is defined and where it is used, i.e. the range over which the variable has a value that must be preserved because it will be used in the future). Generally register allocation algorithms will be able to assign different variables to the same register if their live ranges do not interfere (i.e. overlap). If live ranges overlap, that means their value needs to be preserved simultaneously, and they can't use the same register. In the code, there is a lot of overlapping live ranges. E.g. ax and xx. Those can be eliminated by moving code around, but most register allocators do not move code.
- cosmicexplorer 11y ago
  Is there not like a "-O3" option to try aggressive code manipulation like that? Or is moving code around just not done at all because it's difficult to do correctly?
  - pcwalton 11y ago
    I think rematerialization covers most of the cases in which you would benefit from doing that (such as ax and xx), and rematting is standard in advanced compilers like GCC/LLVM.
- pcwalton 11y ago
  A lot of register allocators can rematerialize, though, and that can have much the same effect. (ax and xx should be candidates for rematting.)
  - rayiner 11y ago
    Good point. Though rematerialization is still pretty rare considering the entire universe of compilers (e.g. Academic projects like Ocaml was).
    - pcwalton 11y ago
      Yeah, I was always under the impression that ocamlopt is fairly Plan 9-like; it produces medium quality code quickly, and doesn't have the full suite of compiler optimizations that projects like LLVM or HotSpot have.

lispm 11y ago

There is <> missing in line 3 of the first code snippet.

froh42 11y ago

Use a better algorithm instead of worrying about processor registers. And if you start considering the computer architecture think about caches, memory latency and bursting first. Use a cache-conscious data structure. Optimizing at the register level is ridiculous, this is the least place where you get significant returns for the effort you spend. Oh, and make it correct first, make it fast second. Use a profiler.

brudgers 11y ago
There are places where slow correct is worse than fast wrong [for some definitions of "correct" and/or "wrong"]. Janestreet works where perfect is the enemy of the good, and are probably looking at registers because they have already squeezed caches for performance juice. This is a post where the quant context matters. It's not a sophomore CS student's blog.

pcwalton 11y ago

I talked with Chris Lattner a few years ago about register allocation and he had an interesting perspective. In his view (from what I remember; my recollection could be somewhat incorrect) most of the classical academic research on it is solving the wrong problem. Most formulations of register allocation are graph coloring algorithms designed to answer the question "is this function colorable using K registers without spilling?" The algorithms for handling the case when you do spill usually don't have as much thought put into them. But this is emphasizing the wrong aspect of the problem in practice; for almost any interesting function on the commonly used architectures (x86/ARM), the answer to the theoretical question is trivially "no" (because there are relatively few registers), and the most important practical problem is how to spill effectively (including deciding whether to spill versus split versus rematerialize, etc.) As I understand it, that's the idea behind LLVM's (relatively) new greedy allocator [1]: the graph-coloring part of the problem is simple, and the focus is on spilling and splitting, problems that the classical academic literature has tended to put less emphasis on. [1]: http://blog.llvm.org/2011/09/greedy-register-allocation-in-llvm-30.html http://blog.llvm.org/2011/09/greedy-register-allocation-in-l...

DannyBee 11y ago
I'm going to guess you have misunderstood what Chris said (with no offense meant) :) Spilling is actually a very well known and very well studied problem, and in fact, most compilers and research spend a lot of time figuring out how to place spill code and coealesce copies, not how to color things. Chris knows this. I had discussions with him (many many years ago, before he ever started at Apple) about GCC's register allocation approach vs what he was thinking of doing for LLVM. There are actually only so many good approaches to spill code /rematerialization/live range splitting you can use. At some point, it's really just a large integer-linear programming problem. Note that coloring is essentially free on SSA form. It's linear time or better.
- pcwalton 11y ago
  Regardless, the whole point of the greedy allocator is to throw out the fancy list of active intervals that linear scan maintains in favor of doing something simpler that allows more flexibility in spilling/splitting, right? For example: "Live ranges being spilled without being split first cause the mess that the rewriter is working so hard to clean up. We would much rather split them into smaller pieces that might be assignable, but this would require the linear scan algorithm to backtrack. This is very expensive, and full live range splitting isn't really feasible with linear scan." i.e. a weakness of linear scan is that the active list approach helps it solve the coloring problem quickly and accurately, but it comes with a big drawback that live range splitting is hard, which is the wrong tradeoff in practice.

DannyBee 11y ago

"If the code has more than that many variables, OCaml compiler has to park the extra variables in memory and this parking is called spilling." This is just wrong. It would be accurate to say "If the code has more than that number of variables live at the same time". If the computations are not live at the same time, they can share a register.

deleted 11y ago

[deleted]

deleted 11y ago

[deleted]

gct 11y ago

The notion that there's only 13/16 registers (assuming x86) hasn't been true for a long time. There's hundreds in the latest cores from Intel. It's true there's only 13/16 names for them, but with register renaming there's way more places to actually put data than that.

rayiner 11y ago
Register renaming solves a different problem than the one outlined in the article. Renaming allows to to eliminate write after read dependencies. E.g. Computing a value, storing it to AX, doing something with AX, computing another value, storing it to AX, doing something with AX. If the two computations are independent, the AX dependency is false and the OOO core can execute them concurrently by storing the results into two different rename registers and rewriting the "doing something with AX" to source their inputs from those two different registers instead. In terms of live ranges, the first value stored in AX has a live range that does not overlap that if the second value stored in AX. So the compiler can reuse AX for those two values without problems. That's not true in the scenario of the article without moving code around. The live ranges overlap--you have to keep around two or more distinct values before any of them are used. You can't store the results into the same register without clobbering one of the values. So the compiler is forced to introduce a memory operation by spilling a value, and the CPU can't do anything to eliminate that after the fact.

deleted 11y ago

[deleted]

tempodox 11y ago

Those are interesting observations. When doing something like `let rec loop ...`, I got into the habit of using parameters for only those entities that might change from one iteration to the next. The rest (as being constant / invariant across iterations) dwells in the closure env, if only for the sake of making the source code shorter. The article shows nicely how this obvious mental shortcut has its (equally obvious) costs. It's also a nice practical demonstration of how reading disassemblies is still an integral part of understanding a language, even this relatively abstract ML descendant.

a-dub 11y ago

Does OCaml generate code that makes use of SIMD?