9 ms·

Writing Performance Sensitive OCaml Code

131 points by sndean 9y ago

pkhagah 9y ago
> The OCaml garbage collector is a modern hybrid generational/incremental collector which outperforms hand-allocation in most cases. Unlike the Java GC, which gives GCs a bad name, the OCaml GC doesn't allocate huge amounts of memory at start-up, nor does it appear to have arbitrary fixed limits that need to be overridden by hand. From the linked article. Can anyone confirm or deny this? I have hard time believing this statement.
- Cieplak 9y ago
  @pron probably has the answer to this
- joshmarlow 9y ago
  Jane Street are big players in the OCaml community (they build/maintain what's arguably the defacto standard library for the language - Jane Street Core) and apparently make a lot of money being good at what they do; so I'm inclined to believe them.
  - haimez 9y ago
    Devils advocate: they're not doing anything better than anyone else in the market and they don't make a product. They're very invested in their ecosystem which is only as good as they make it because they have a very quiet, well funded (pun intended) echo chamber and a lot of spare cycles to maintain a STDLIB on top of their actual business.
    - deleted 9y ago
      [deleted]
- gsb 9y ago
  As far as it goes I think it is a pretty fair statement. However it is important to know of other decisions in the language which make it easier for the GC. Particularly, the use of tagged values and a GIL. Tagging makes it simpler to distinguish heap values from other values, and the GIL means that the GC does not need to operate concurrently.
- AlphaSite 9y ago
  It may be the but from a couple of talks I've gotten they go to pretty extreme lengths to maintain that performance.
- searealist 9y ago
  It's nonsense, the only way to make a GC fast is to use many times as much memory as manual management (about 6x to reach parity[1]). [1] https://people.cs.umass.edu/~emery/pubs/04-17.pdf https://people.cs.umass.edu/~emery/pubs/04-17.pdf
  - rwmj 9y ago
    This paper assumes that malloc/free is cost-free and that free is always called at the earliest possible place.
    - mcguire 9y ago
      The paper uses the Lea malloc, which is fast, but not free.
      - rwmj 9y ago
        By "cost-free" I mean that they use precise traces so that memory is always freed at the exact moment it is no longer used. So they underestimate (greatly IMHO) the memory used by malloc/free versus the garbage collector. It would be a superhuman programmer who always called free() on the line exactly following the last use of every piece of allocated memory. The second problem I have with the paper is that it underestimates the kinds of structures which GC makes possible -- eg sets of trees sharing nodes. And the corollary to that is that to implement those structures with malloc/free, programmers tend to reach for ref-counting, which adds to memory usage and is generally a terrible form of garbage collection for many other reasons. Nevertheless it's an interesting paper which does add to the debate (I studied it about 10 years ago). It is worth reading, even though I have concerns about the methodology and hence the results.
        searealist 9y ago
        > By "cost-free" I mean that they use precise traces so that memory is always freed at the exact moment it is no longer used. So they underestimate (greatly IMHO) the memory used by malloc/free versus the garbage collector. It would be a superhuman programmer who always called free() on the line exactly following the last use of every piece of allocated memory. Let's say you are correct, that the manual memory management presented in the paper is too unrealistic. What do you think real world manual memory management would bring the multiple to? 5x? 4x? > The second problem I have with the paper is that it underestimates the kinds of structures which GC makes possible -- eg sets of trees sharing nodes. And the corollary to that is that to implement those structures with malloc/free, programmers tend to reach for ref-counting, which adds to memory usage and is generally a terrible form of garbage collection for many other reasons. These data structures are extremely niche, and when used when sharing is not truly needed just lead to time/space inefficiencies.
- jblow 9y ago
  It is simply not true unless you have a pathological idea of "hand-allocation" (which to be fair, some programmers do program like). Let me put it this way ... all "garbage collection is fast" claims are saying the following thing: "It is faster for the programmer to destroy information about his program's memory use (by not putting that information into the program), and to have the runtime system dynamically rediscover that information via a constantly-running global search and then use what it gleans to somehow be fast, than it is for the programmer to just exploit the information that he already knows." It sure sounds like nonsense to me.
  - vvanders 9y ago
    Yup, an arena allocator that you drop at the end of an operation will always be faster than a GC.
    - gsb 9y ago
      Absolutely, but I think the "in most cases" of the original quote was meant to imply simple malloc/free style memory management rather than the use of tailored arena/region allocators.
    - _yosefk 9y ago
      Well, yeah, but if you need some of the allocated data at the end of the operation, you'll end up copying it, which will have a runtime cost, might introduce bugs (because of pointer invalidation and the ease of forgetting to update some pointers) and then none of the two will get counted as "cost of manual memory management." C++ with its value semantics encourages unnecessary copying tremendously and it's never counted as "cost of memory allocation" or "producing garbage", on the contrary, Stroustrup says things like "C++ is my favorite GC language because it generates so little garbage to begin with." This is not to say that it's fair to call OCaml "efficient" in the memory department based on a GC benchmark; TFA is full of examples where OCaml allocates things on the heap that TFA recommends to allocate elsewhere and shows you how to maul your code to get there. My only point is that how well a programming system uses memory is a very hard question because (A) there are many different use cases and (B) you can't isolate "memory performance" into a few easily measurable things like time spent allocating, time spent in GC and peak memory use - there are other things like what your program has to do outside of the allocator to cope with its semantics and how the performance of code using the memory objects is affected by the layout encouraged by the allocator and these things cannot be measured in isolation from the rest of the program.
- qznc 9y ago
  Java gave GCs a bad name? It made them mainstream!
  - _ph_ 9y ago
    In a sense, both :). Java made GC mainstream and since Hotspot has an excellent GC, solving the problem for many use cases. However, the Java language design is extremely performance-hostile with respect to memory allocations. Notable points are: - no value types mean, that there are tons of separate heap allocations which have to be referenced by pointers, this puts a ton of unnecessary load on the GC. It also means, that you fully depend on escape analysis when passing objects to functions for avoiding heap allocation. And the existing primitive types (int, float) often require boxing. - the design of the standard libraries was, especially at the beginning full of wasteful allocations. Most string handling code was a constant series of allocations (having 16 byte chars didn't help this either). - far to many Java libraries build extremely complex object hierarchies and protocols. Just reading from a text file means instantiating several objects. This adds to the GC pressure.
    - dom0 9y ago
      A good example how to not write performance sensitive code, in general, and specifically in Java, would be Minecraft. Though commercially successful Minecraft is (or at least was) an excellent study of how to not do stuff, be it memory management, networking or rendering (when I played Minecraft it still used immediate mode GL if I recall correctly)
- mcguire 9y ago
  Let's break it down. Hopefully someone can fill in the parts I don't know. > The OCaml garbage collector is a modern hybrid generational/incremental collector which outperforms hand-allocation in most cases. Ocaml is mostly functional and likes to allocate many short lived objects. With enough memory, a moving collector is very good at handling that load. > Unlike the Java GC, which gives GCs a bad name, the OCaml GC doesn't allocate huge amounts of memory at start-up, nor does it appear to have arbitrary fixed limits that need to be overridden by hand. Java's GC (-s; there's a bunch) use a heap with a fixed maximum size and an initial allocation. It has also received much more research attention over the decades. It also has a lot of knobs to fiddle with. I've run production Java web app servers with multi-gig heaps where almost all requests were handled in the young generation. The knobs and visibility were very nice. Ocaml doesn't use a fixed size heap, so it can conceivably take over all of memory. It also doesn't have all of the knobs. But it works pretty well.
jackmott 9y ago
anyone that can explain or refer to explanations of why ocaml boxes floats?
- thedufer 9y ago
  The section "OCaml Blocks and Values" at https://realworldocaml.org/v1/en/html/memory-representation-of-values.html https://realworldocaml.org/v1/en/html/memory-representation-... is a good explanation.
  - haimez 9y ago
    Let me summarize: academic language, it's easy for the GC that way, and "if you though that Float boxing would kill performance you wouldn't have started down this path"
    - ernst_klim 9y ago
      Afaik flabmbda can do some float unboxing, and float unboxing is not impossible until you use generic value. Nope, OCaml is not "academic" but a very pragmatic language.
- rbehrends 9y ago
  OCaml boxes pretty much everything that isn't an integer or a reference (though if you're using arrays/records of floats, those don't suffer an additional level of boxing). The result is that any type can be represented in a single machine word, making it easy to support polymorphism without specializing code (allowing, e.g., for shared generics). Keep in mind that OCaml's backend was designed decades ago when machines were much smaller, at a time when C++ was still reluctant to add generics with specialization because of code bloat.
- deleted 9y ago
  [deleted]
- mookid11 9y ago
  To allow IEEE compliant float with tagged pointers. However, note that floats are not boxed in the OCaml's arrays. Boxing floats is a pain because it makes the price of defining subroutines taking float arguments high.
gsg 9y ago
This is about a decade old, I think. With a substantial optimisation suite added to ocamlopt since, some of it will be out of date. The advice on inlining in particular is obsolete.
- harrisi 9y ago
  Hm, could you say why you think that? Looking at the github history it's hard to tell. The earliest history I can find for this page is from 2013[0], but it seems to be pretty clearly a transition and not the original writing of it. However, it's the only thing I can find in terms of aging the document. [0]: https://github.com/janestreet/janestreet.github.com/commit/77eea6fbcb122f98a5726c6cb88b5c5922529a6a https://github.com/janestreet/janestreet.github.com/commit/7...
  - gsg 9y ago
    I remember reading it a number of years ago. It's true that it may have been updated since then, although my guess would be that it has not.
  - rbehrends 9y ago
    What gsg has been referring to is the flambda framework [1], which has been available for a while. If you're using OPAM, install an flambda-enabled compiler with (e.g.) opam switch install 4.04.1+flambda [1] https://caml.inria.fr/pub/docs/manual-ocaml/flambda.html https://caml.inria.fr/pub/docs/manual-ocaml/flambda.html
- tempodox 9y ago
  Even so, it still contains lots of helpful explanations and starting points for those who haven't learned to eat assembly for breakfast yet. Current OCaml docs and own exploration should do the rest.
gcc_programmer 9y ago
In the first code snippet, they havr add $2, %rax but the function actually adds 1 to its argument.
- deleted 9y ago
  [deleted]
- thelema314 9y ago
  This is correct; OCaml integers are tagged with their LSB being 1 to indicate they're not a pointer. This means that the integer n is stored as 2n+1, and adding 1 requires modifying the stored value by 2.
chimtim 9y ago
re-write it in C++
mcguire 9y ago
"In the file called test_asm.ml the function f let f a = a+1 "The generated asm looks like the following:" camlTest_asm__f_33700: .L119: addq $2, %rax ret You sure about that? $2?
- mcguire 9y ago
  "Unlike floats, ints are represented as immediates, i.e., they are not allocated on the heap. To tag ints OCaml steals the LSB bit of an int and sets it to 1 always. This means that we get 63 bits of precision in OCaml ints and any int value n will appear in the assembly as 2n+1 (the LSB is always 1 and the bits of the number shifted one place in).*" Crap. Forgot about the tag bit. :-)
- brilee 9y ago
  From the article: Unlike floats, ints are represented as immediates, i.e., they are not allocated on the heap. To tag ints OCaml steals the LSB bit of an int and sets it to 1 always. This means that we get 63 bits of precision in OCaml ints and any int value n will appear in the assembly as 2*n+1 (the LSB is always 1 and the bits of the number shifted one place in).

131 points by sndean 9y ago

> The OCaml garbage collector is a modern hybrid generational/incremental collector which outperforms hand-allocation in most cases. Unlike the Java GC, which gives GCs a bad name, the OCaml GC doesn't allocate huge amounts of memory at start-up, nor does it appear to have arbitrary fixed limits that need to be overridden by hand. From the linked article. Can anyone confirm or deny this? I have hard time believing this statement.

Cieplak 9y ago
@pron probably has the answer to this
joshmarlow 9y ago
Jane Street are big players in the OCaml community (they build/maintain what's arguably the defacto standard library for the language - Jane Street Core) and apparently make a lot of money being good at what they do; so I'm inclined to believe them.
- haimez 9y ago
  Devils advocate: they're not doing anything better than anyone else in the market and they don't make a product. They're very invested in their ecosystem which is only as good as they make it because they have a very quiet, well funded (pun intended) echo chamber and a lot of spare cycles to maintain a STDLIB on top of their actual business.
  - deleted 9y ago
    [deleted]
gsb 9y ago
As far as it goes I think it is a pretty fair statement. However it is important to know of other decisions in the language which make it easier for the GC. Particularly, the use of tagged values and a GIL. Tagging makes it simpler to distinguish heap values from other values, and the GIL means that the GC does not need to operate concurrently.
AlphaSite 9y ago
It may be the but from a couple of talks I've gotten they go to pretty extreme lengths to maintain that performance.
searealist 9y ago
It's nonsense, the only way to make a GC fast is to use many times as much memory as manual management (about 6x to reach parity[1]). [1] https://people.cs.umass.edu/~emery/pubs/04-17.pdf https://people.cs.umass.edu/~emery/pubs/04-17.pdf
- rwmj 9y ago
  This paper assumes that malloc/free is cost-free and that free is always called at the earliest possible place.
  - mcguire 9y ago
    The paper uses the Lea malloc, which is fast, but not free.
    - rwmj 9y ago
      By "cost-free" I mean that they use precise traces so that memory is always freed at the exact moment it is no longer used. So they underestimate (greatly IMHO) the memory used by malloc/free versus the garbage collector. It would be a superhuman programmer who always called free() on the line exactly following the last use of every piece of allocated memory. The second problem I have with the paper is that it underestimates the kinds of structures which GC makes possible -- eg sets of trees sharing nodes. And the corollary to that is that to implement those structures with malloc/free, programmers tend to reach for ref-counting, which adds to memory usage and is generally a terrible form of garbage collection for many other reasons. Nevertheless it's an interesting paper which does add to the debate (I studied it about 10 years ago). It is worth reading, even though I have concerns about the methodology and hence the results.
      - searealist 9y ago
        > By "cost-free" I mean that they use precise traces so that memory is always freed at the exact moment it is no longer used. So they underestimate (greatly IMHO) the memory used by malloc/free versus the garbage collector. It would be a superhuman programmer who always called free() on the line exactly following the last use of every piece of allocated memory. Let's say you are correct, that the manual memory management presented in the paper is too unrealistic. What do you think real world manual memory management would bring the multiple to? 5x? 4x? > The second problem I have with the paper is that it underestimates the kinds of structures which GC makes possible -- eg sets of trees sharing nodes. And the corollary to that is that to implement those structures with malloc/free, programmers tend to reach for ref-counting, which adds to memory usage and is generally a terrible form of garbage collection for many other reasons. These data structures are extremely niche, and when used when sharing is not truly needed just lead to time/space inefficiencies.
jblow 9y ago
It is simply not true unless you have a pathological idea of "hand-allocation" (which to be fair, some programmers do program like). Let me put it this way ... all "garbage collection is fast" claims are saying the following thing: "It is faster for the programmer to destroy information about his program's memory use (by not putting that information into the program), and to have the runtime system dynamically rediscover that information via a constantly-running global search and then use what it gleans to somehow be fast, than it is for the programmer to just exploit the information that he already knows." It sure sounds like nonsense to me.
- vvanders 9y ago
  Yup, an arena allocator that you drop at the end of an operation will always be faster than a GC.
  - gsb 9y ago
    Absolutely, but I think the "in most cases" of the original quote was meant to imply simple malloc/free style memory management rather than the use of tailored arena/region allocators.
  - _yosefk 9y ago
    Well, yeah, but if you need some of the allocated data at the end of the operation, you'll end up copying it, which will have a runtime cost, might introduce bugs (because of pointer invalidation and the ease of forgetting to update some pointers) and then none of the two will get counted as "cost of manual memory management." C++ with its value semantics encourages unnecessary copying tremendously and it's never counted as "cost of memory allocation" or "producing garbage", on the contrary, Stroustrup says things like "C++ is my favorite GC language because it generates so little garbage to begin with." This is not to say that it's fair to call OCaml "efficient" in the memory department based on a GC benchmark; TFA is full of examples where OCaml allocates things on the heap that TFA recommends to allocate elsewhere and shows you how to maul your code to get there. My only point is that how well a programming system uses memory is a very hard question because (A) there are many different use cases and (B) you can't isolate "memory performance" into a few easily measurable things like time spent allocating, time spent in GC and peak memory use - there are other things like what your program has to do outside of the allocator to cope with its semantics and how the performance of code using the memory objects is affected by the layout encouraged by the allocator and these things cannot be measured in isolation from the rest of the program.
qznc 9y ago
Java gave GCs a bad name? It made them mainstream!
- _ph_ 9y ago
  In a sense, both :). Java made GC mainstream and since Hotspot has an excellent GC, solving the problem for many use cases. However, the Java language design is extremely performance-hostile with respect to memory allocations. Notable points are: - no value types mean, that there are tons of separate heap allocations which have to be referenced by pointers, this puts a ton of unnecessary load on the GC. It also means, that you fully depend on escape analysis when passing objects to functions for avoiding heap allocation. And the existing primitive types (int, float) often require boxing. - the design of the standard libraries was, especially at the beginning full of wasteful allocations. Most string handling code was a constant series of allocations (having 16 byte chars didn't help this either). - far to many Java libraries build extremely complex object hierarchies and protocols. Just reading from a text file means instantiating several objects. This adds to the GC pressure.
  - dom0 9y ago
    A good example how to not write performance sensitive code, in general, and specifically in Java, would be Minecraft. Though commercially successful Minecraft is (or at least was) an excellent study of how to not do stuff, be it memory management, networking or rendering (when I played Minecraft it still used immediate mode GL if I recall correctly)
mcguire 9y ago
Let's break it down. Hopefully someone can fill in the parts I don't know. > The OCaml garbage collector is a modern hybrid generational/incremental collector which outperforms hand-allocation in most cases. Ocaml is mostly functional and likes to allocate many short lived objects. With enough memory, a moving collector is very good at handling that load. > Unlike the Java GC, which gives GCs a bad name, the OCaml GC doesn't allocate huge amounts of memory at start-up, nor does it appear to have arbitrary fixed limits that need to be overridden by hand. Java's GC (-s; there's a bunch) use a heap with a fixed maximum size and an initial allocation. It has also received much more research attention over the decades. It also has a lot of knobs to fiddle with. I've run production Java web app servers with multi-gig heaps where almost all requests were handled in the young generation. The knobs and visibility were very nice. Ocaml doesn't use a fixed size heap, so it can conceivably take over all of memory. It also doesn't have all of the knobs. But it works pretty well.

jackmott 9y ago

anyone that can explain or refer to explanations of why ocaml boxes floats?

thedufer 9y ago
The section "OCaml Blocks and Values" at https://realworldocaml.org/v1/en/html/memory-representation-of-values.html https://realworldocaml.org/v1/en/html/memory-representation-... is a good explanation.
- haimez 9y ago
  Let me summarize: academic language, it's easy for the GC that way, and "if you though that Float boxing would kill performance you wouldn't have started down this path"
  - ernst_klim 9y ago
    Afaik flabmbda can do some float unboxing, and float unboxing is not impossible until you use generic value. Nope, OCaml is not "academic" but a very pragmatic language.
rbehrends 9y ago
OCaml boxes pretty much everything that isn't an integer or a reference (though if you're using arrays/records of floats, those don't suffer an additional level of boxing). The result is that any type can be represented in a single machine word, making it easy to support polymorphism without specializing code (allowing, e.g., for shared generics). Keep in mind that OCaml's backend was designed decades ago when machines were much smaller, at a time when C++ was still reluctant to add generics with specialization because of code bloat.
deleted 9y ago
[deleted]
mookid11 9y ago
To allow IEEE compliant float with tagged pointers. However, note that floats are not boxed in the OCaml's arrays. Boxing floats is a pain because it makes the price of defining subroutines taking float arguments high.

gsg 9y ago

This is about a decade old, I think. With a substantial optimisation suite added to ocamlopt since, some of it will be out of date. The advice on inlining in particular is obsolete.

harrisi 9y ago
Hm, could you say why you think that? Looking at the github history it's hard to tell. The earliest history I can find for this page is from 2013[0], but it seems to be pretty clearly a transition and not the original writing of it. However, it's the only thing I can find in terms of aging the document. [0]: https://github.com/janestreet/janestreet.github.com/commit/77eea6fbcb122f98a5726c6cb88b5c5922529a6a https://github.com/janestreet/janestreet.github.com/commit/7...
- gsg 9y ago
  I remember reading it a number of years ago. It's true that it may have been updated since then, although my guess would be that it has not.
- rbehrends 9y ago
  What gsg has been referring to is the flambda framework [1], which has been available for a while. If you're using OPAM, install an flambda-enabled compiler with (e.g.) opam switch install 4.04.1+flambda [1] https://caml.inria.fr/pub/docs/manual-ocaml/flambda.html https://caml.inria.fr/pub/docs/manual-ocaml/flambda.html
tempodox 9y ago
Even so, it still contains lots of helpful explanations and starting points for those who haven't learned to eat assembly for breakfast yet. Current OCaml docs and own exploration should do the rest.

gcc_programmer 9y ago

In the first code snippet, they havr add $2, %rax but the function actually adds 1 to its argument.

deleted 9y ago
[deleted]
thelema314 9y ago
This is correct; OCaml integers are tagged with their LSB being 1 to indicate they're not a pointer. This means that the integer n is stored as 2n+1, and adding 1 requires modifying the stored value by 2.

chimtim 9y ago

re-write it in C++

mcguire 9y ago

"In the file called test_asm.ml the function f let f a = a+1 "The generated asm looks like the following:" camlTest_asm__f_33700: .L119: addq $2, %rax ret You sure about that? $2?

mcguire 9y ago
"Unlike floats, ints are represented as immediates, i.e., they are not allocated on the heap. To tag ints OCaml steals the LSB bit of an int and sets it to 1 always. This means that we get 63 bits of precision in OCaml ints and any int value n will appear in the assembly as 2n+1 (the LSB is always 1 and the bits of the number shifted one place in).*" Crap. Forgot about the tag bit. :-)
brilee 9y ago
From the article: Unlike floats, ints are represented as immediates, i.e., they are not allocated on the heap. To tag ints OCaml steals the LSB bit of an int and sets it to 1 always. This means that we get 63 bits of precision in OCaml ints and any int value n will appear in the assembly as 2*n+1 (the LSB is always 1 and the bits of the number shifted one place in).