Why boxed data in Ocaml and GHC?
Paul Rubin
the types are known to the compiler), Ocaml and GHC both generated
boxed data, which seems like a substantial performance loss. Is my
impression correct? Why on earth do they do that? MLton apparently
does not.
Any idea about JHC? What's going on with that compiler, anyway?
Vityok
references from primitive values. This is very important for the
garbage collector to work properly.
In any case, this seems like a frequently asked question and there
should be more informative answers on the net.
With best regards,
Victor
Paul Rubin :
Torben Ægidius Mogensen
> I get the impression that even for int and float types (and of course
> the types are known to the compiler), Ocaml and GHC both generated
> boxed data, which seems like a substantial performance loss. Is my
> impression correct? Why on earth do they do that? MLton apparently
> does not.
The reason is a mixture of polymorphism and GC. GC needs to
distinguish pointers from non-pointers, so unboxed integers will be
problematic unless there is an external way to determine that they are
not pointers. With the traditional shared-code implementation of
polymorphism, there is no (simple) external way to do this, as a
polymorphic variable may hold either integers or pointers at different
times.
There are two traditional solutions to this:
1. Make sure all pointers are word-aligned (most are anyway) and
represent all integers as 2n+1, so the least significant bit is 1.
Hence, integers use only n-1 bits on an n-bit processor.
2. Box everything and start every boxed value with a descriptor that
identifies which of the subsequent fields are pointers.
The latter allows full n-bit integers, but adds cost of boxing and
unboxing.
If you, like MLton, specialize polymorphic functions to each instance,
you can use the context to see which words hold pointers: Each
activation record has a pointer to code that can GC the variables
(including substructures) in that activation record. Basically, each
type (including the types of activation records) has a GC method.
This requires a pure caller-saves strategy, as callee-saves variables
are not saved in the activation record in which they are created.
Also, a caller-saves startegy makes sure that the root set is held on
the stack when GC is activated (with a function call).
Another way to avoid tags for GC is to replace GC with region
analysis.
GHC may have another reason to box integers: Haskell is a lazy
language and GHC uses a socalled "tagless" implementation whereby
inspecting a value is done by jumping to a code pointer in its thunk,
which will either place the substructures of the value in specific
registers and return, or (if the value is not evaluated) evaluate the
value, overwrite the thunk and then return. Hence, every value that
might be unevaluated must be boxed in a thunk. Unboxed values in
Haskell are always evaluated, so they don't need thunks.
Torben
Paul Rubin
> ...GC needs to
> distinguish pointers from non-pointers, so unboxed integers will be
> problematic unless there is an external way to determine that they are
> not pointers. With the traditional shared-code implementation of
> polymorphism, there is no (simple) external way to do this
Ah, thanks. It didn't occur to me that the compiler didn't generate
different code for each type. Specialization sounds like a big
performance improvement. If I write some particular set of functions
non-polymorphically (i.e. with explicit type signatures) so that no
non-explicitly-type ints can enter some loop, will the compiler do the
right thing in Ocaml?
> Another way to avoid tags for GC is to replace GC with region
> analysis.
I wonder why this isn't done more widely, for languages like
ML, since they cons so much that even ephemeral GC is probably
pretty cache-unfriendly.
> GHC may have another reason to box integers: Haskell is a lazy
> language and GHC uses a socalled "tagless" implementation whereby
> inspecting a value is done by jumping to a code pointer in its thunk,
Interesting, I didn't know about this. I guess they must have
investigated other implementations for performance comparisons.
Lauri Alanko
Paul Rubin <http://phr...@NOSPAM.invalid> wrote:
> Ah, thanks. It didn't occur to me that the compiler didn't generate
> different code for each type. Specialization sounds like a big
> performance improvement. If I write some particular set of functions
> non-polymorphically (i.e. with explicit type signatures) so that no
> non-explicitly-type ints can enter some loop, will the compiler do the
> right thing in Ocaml?
No, ocaml doesn't optimize representations at this level. Ints always
have a tag bit.
> > Another way to avoid tags for GC is to replace GC with region
> > analysis.
>
> I wonder why this isn't done more widely, for languages like
> ML, since they cons so much that even ephemeral GC is probably
> pretty cache-unfriendly.
I suspect that most implementers aren't convinced that the complexity
of region analysis offsets the performance gains. For instance, the
MLton developers say:
We have considered integrating regions with MLton, but in our
opinion it is far from clear that regions would provide MLton
with improved performance, while they would certainly add a
lot of complexity to the compiler and complicate reasoning
about and achieving SpaceSafety.
Another approach to avoid tagging is type-passing: the representation
information about the values, when not statically known, is passed
separately to polymorphic functions. The GC can then retrieve this
information from the stack. I'm not sure if this technique has ever
been used in a "production-quality" compiler.
> > GHC may have another reason to box integers: Haskell is a lazy
> > language and GHC uses a socalled "tagless" implementation whereby
> > inspecting a value is done by jumping to a code pointer in its thunk,
>
> Interesting, I didn't know about this. I guess they must have
> investigated other implementations for performance comparisons.
In a lazy language, even if you statically know that a value is an
int, you still must do run-time dispatching since you cannot (in
general) know whether the value is already evaluated. Hence boxing is
inevitable.
The dispatch can be done in different ways, though: an alternative
would be to examine a tag and branch instead of always doing an
indirect jump. I think the original papers on the STG machine discuss
why the tagless representation is preferable.
However, note that GHC does quite a lot of work under the hood to
avoid boxing: if strictness analysis reveals that an int can be
evaluated prematurely without changing semantics, then an unboxed,
untagged representation can be used. Hence, arithmetic can often be
done without any overhead.
Lauri
Joachim Durchholz
> tor...@app-4.diku.dk (Torben Ægidius Mogensen) writes:
>> ...GC needs to
>> distinguish pointers from non-pointers, so unboxed integers will be
>> problematic unless there is an external way to determine that they are
>> not pointers. With the traditional shared-code implementation of
>> polymorphism, there is no (simple) external way to do this
>
> Ah, thanks. It didn't occur to me that the compiler didn't generate
> different code for each type.
It can also inflate the code.
For N parameters where you need different code for the boxed and the
unboxed case, you have 2^N possible combinations that you may have to
generate, so there's a trade-off here.
Nothing new really, this kind of trade-off is done manually in languages
that don't box their integers.
>> Another way to avoid tags for GC is to replace GC with region
>> analysis.
>
> I wonder why this isn't done more widely, for languages like
> ML, since they cons so much that even ephemeral GC is probably
> pretty cache-unfriendly.
The problem is that many values escape their lexical context in an FPL.
Region analysis will give you less and less gain the further a value can
escape; I'd assume that most compiler teams will judge that other
optimizations are more worth their time.
>> GHC may have another reason to box integers: Haskell is a lazy
>> language and GHC uses a socalled "tagless" implementation whereby
>> inspecting a value is done by jumping to a code pointer in its thunk,
>
> Interesting, I didn't know about this. I guess they must have
> investigated other implementations for performance comparisons.
There have been other implementations before. The tagless, spineless
machine at the heart of GHC is one of the things that turned out to work
as well as theory suggested.
I'm pretty sure that some other compiler would be predominant if another
approach had worked better.
Regards,
Jo
Paul Rubin
> > Ah, thanks. It didn't occur to me that the compiler didn't generate
> > different code for each type.
>
> It can also inflate the code.
> For N parameters where you need different code for the boxed and the
> unboxed case, you have 2^N possible combinations that you may have to
> generate, so there's a trade-off here.
> Nothing new really, this kind of trade-off is done manually in
> languages that don't box their integers.
Good point. I'm mainly thinking of basic functions like map and fold,
which would expand to very small code, and I'd think they might even
be inlined to turn some expressions into iterative loops. The
compiler could even try to use XMM instructions (SIMD vector
instructions) on the x86 in some cases.
> The problem is that many values escape their lexical context in an
> FPL. Region analysis will give you less and less gain the further a
> value can escape; I'd assume that most compiler teams will judge that
> other optimizations are more worth their time.
Right, you'd need a hybrid region/GC approach. But I do get the
impression that regions can help a lot with locality. I wonder if
these basic OCAML design decisions were made at a time when ram cache
misses weren't so expensive compared with today.
> There have been other implementations before. The tagless, spineless
> machine at the heart of GHC is one of the things that turned out to
> work as well as theory suggested.
> I'm pretty sure that some other compiler would be predominant if
> another approach had worked better.
Again, today's CPU's rely more on OOO execution and branch prediction
than they did a decade ago. I don't know how indirect jumps figure
into this. It's possible that GHC's approach costs more today
relative to checking a tag than it would have in the early Haskell
era.
Jon Harrop
> I get the impression that even for int and float types (and of course
> the types are known to the compiler), Ocaml and GHC both generated
> boxed data, which seems like a substantial performance loss. Is my
> impression correct?
No, ocamlopt certainly doesn't box all ints and floats. Ints are never boxed
(they are tagged) and floats are basically unboxed for the duration of a
function body.
Indeed, this is why OCaml is so fast.
--
Dr Jon D Harrop, Flying Frog Consultancy
The OCaml Journal
http://www.ffconsultancy.com/products/ocaml_journal/?usenet
Jon Harrop
> tor...@app-4.diku.dk (Torben Ægidius Mogensen) writes:
>> ...GC needs to
>> distinguish pointers from non-pointers, so unboxed integers will be
>> problematic unless there is an external way to determine that they are
>> not pointers. With the traditional shared-code implementation of
>> polymorphism, there is no (simple) external way to do this
>
> Ah, thanks. It didn't occur to me that the compiler didn't generate
> different code for each type.
To some extent, OCaml does. The main omission is that polymorphic functions
are not expanded and specialized for every choice of types to which they
are applied.
> Specialization sounds like a big performance improvement.
They can be, yes.
> If I write some particular set of functions
> non-polymorphically (i.e. with explicit type signatures) so that no
> non-explicitly-type ints can enter some loop, will the compiler do the
> right thing in Ocaml?
Almost certainly. Notable exceptions are when you remove polymorphism in the
interface (OCaml doesn't optimize this situation: you must specify the
monomorphic type at the definition) and when you call polymorphic functions
such as:
2 = 3
(1, 2) = (2, 3)
OCaml optimizes the former to int comparison but does not specialize and
unroll the latter to a pair of int comparisons (it uses the generic = and
applies it to the structures of two pairs).
>> Another way to avoid tags for GC is to replace GC with region
>> analysis.
>
> I wonder why this isn't done more widely, for languages like
> ML, since they cons so much that even ephemeral GC is probably
> pretty cache-unfriendly.
That is a lot of work and I see no evidence that it would be beneficial.
Jon Harrop
> It can also inflate the code.
> For N parameters where you need different code for the boxed and the
> unboxed case, you have 2^N possible combinations that you may have to
> generate, so there's a trade-off here.
There is a trade-off but I don't think that's it. I've never heard of a
language explicitly generating O(e^n) code just in case it is used. This is
usually implemented using whole-program passes that type specialize for all
uses. In that case you only get O(e^n) generated code if you have O(e^n)
code anyway. However, it requires whole-program optimizations.
C++ and MLton do this.
Neelakantan Krishnaswami
Lauri Alanko <l...@iki.fi> wrote:
>
> No, ocaml doesn't optimize representations at this level. Ints always
> have a tag bit.
However, Ocaml *will* optimize the representations of floats (ie, not
box them) if you add type annotations.
I think the reason it does not do the same for ints is that you don't
want the overflow/underflow behavior of your program to depend on
whether you put in a type annotation or not; that would be really
gross. And then there's no reason to take out the tag bit.
--
Neel R. Krishnaswami
ne...@cs.cmu.edu
Matthias Blume
> Joachim Durchholz wrote:
>> It can also inflate the code.
>> For N parameters where you need different code for the boxed and the
>> unboxed case, you have 2^N possible combinations that you may have to
>> generate, so there's a trade-off here.
>
> There is a trade-off but I don't think that's it. I've never heard of a
> language explicitly generating O(e^n) code just in case it is used. This is
> usually implemented using whole-program passes that type specialize for all
> uses. In that case you only get O(e^n) generated code if you have O(e^n)
> code anyway. However, it requires whole-program optimizations.
It is still true that in certain (pathological) cases,
type-specializing a program of size N generates 2^N code.
Bruce Stephens
[...]
> This is usually implemented using whole-program passes that type
> specialize for all uses. In that case you only get O(e^n) generated
> code if you have O(e^n) code anyway. However, it requires
> whole-program optimizations.
>
> C++ and MLton do this.
It's not required for C++. Some implementations do it, but many
don't.
(I guess if you take the position that "export" for templates is a
part of the standard then such behaviour *is* required for C++. But
almost nobody implements exported templates, so in reality C++ doesn't
necessarily do this.)
Jon Harrop
> In article <<f79tmv$6va$1...@oravannahka.helsinki.fi>>,
> Lauri Alanko <l...@iki.fi> wrote:
>>
>> No, ocaml doesn't optimize representations at this level. Ints always
>> have a tag bit.
>
> However, Ocaml *will* optimize the representations of floats (ie, not
> box them) if you add type annotations.
The float type will usually be inferred from context but, in general, it is
a good idea to write high-performance float code as large single blocks of
code and not factor into functions, partly because inferred types may be
polymorphic but also because unboxing is inhibited by function boundaries.
There are two major consequences of this:
1. Looping with "while" or "for" rather than recursive functions is faster
when floats persist between iterations.
2. The built-in polymorphic higher-order functions need to be replaced with
float-specific ones.
F# has the nice property that run-time types allow you to write generic
functions that dispatch to specialized functions when appropriate with
something like:
let norm = function
| :? float array as a -> Vector.norm a
| a -> Array.norm a
OCaml makes no attempt to hoist the "is float array" test, so you can easily
end up with it in your inner loop.
F# also provides type specialization via inlining. So you can mark a
polymorphic function like Array.fold_left as "inline" and it will be type
specialized when it is inlined.
My book "OCaml for Scientists" dedicates a chapter to the discussion of
high-performance computing using OCaml and describes all of these problems
and solutions in detail.
Peter C. Chapin
C++ compilers only generate the template specializations they need based
on how the templates are used. This doesn't have anything to do with
export and is universally implemented. But perhaps we are talking about
different things...
Peter
Tony Finch
>
>than they did a decade ago. I don't know how indirect jumps figure
>into this. It's possible that GHC's approach costs more today
>relative to checking a tag than it would have in the early Haskell
>era.
The Simons have been revisiting some ot the STG machine's basics:
http://research.microsoft.com/~simonpj/papers/ptr-tag/
Faster laziness using dynamic pointer tagging, Simon Marlow, Alexey
Rodriguez Yakushev, and Simon Peyton Jones. How to squeeze another 10-15%
performance out of GHC by tagging pointers.
http://research.microsoft.com/~simonpj/Papers/eval-apply/
How to make a fast curry: push/enter vs eval/apply, Simon Marlow and Simon
Peyton Jones, Proc International Conference on Functional Programming,
Snowbird, Sept 2004, pp4-15.
Tony.
--
f.a.n.finch <d...@dotat.at> http://dotat.at/
CROMARTY FORTH: SOUTHEASTERLY 3 OR 4, BECOMING CYCLONIC 5 TO 7, PERHAPS GALE 8
LATER. SLIGHT, INCREASING MODERATE OR ROUGH. RAIN. MODERATE OR GOOD,
OCCASIONALLY POOR.
ross...@ps.uni-sb.de
>
> Ah, thanks. It didn't occur to me that the compiler didn't generate
> different code for each type. Specialization sounds like a big
> performance improvement.
Specialization is only possible where polymorphism can be resolved
statically. This is the case in C++, but not necessarily in languages
featuring higher forms of polymorphism.
For example, in Ocaml you can pass around polymorphic values in a
first-class manner:
type poly = {pair : 'a.'a -> 'a -> 'a * 'a}
(* ... *)
let f poly = poly.pair (poly.pair 5)
When compiling f, there is no specific pairing function being used, so
you cannot specialize the polymorphic calls to it at compile time.
Other hurdles to specialization are existential types, polymorphic
recursion (both appearing in Haskell), or first-class modules (as in
some ML dialects).
Also note that specialization essentially screws separate compilation
(as witnessed by C++ or MLton).
- Andreas
Bruce Stephens
[...]
> C++ compilers only generate the template specializations they need
> based on how the templates are used.
You missed "in program units where the implementation is present".
If you have declarations in foo.h, a generic implementation in foo.cc,
and some use of the template in bar.cc, then in most implementations
(though not all) the link will fail.
When compiling bar.cc the compiler can see that it needs some
particular instantiation of parts of the template but it doesn't
attempt to recompile foo.cc to provide them.
Hence the tendency to put quite a bit of definition in header files,
and explicit instantiation, so you can put lines in foo.cc to
explicitly create versions of the template for particular types and
values.
From the perspective of functional languages with parametric types
this probably sounds horribly clunky and limited, but in practice it
works OK (does now, anyway, now that everyone's used to it).
> This doesn't have anything to do with export and is universally
> implemented. But perhaps we are talking about different things...
export (IIUC) lets you export template definitions, and in that case
everything ought to work.
Various compilers have done things like recording all template
definitions in a database somewhere, and the linker has special
support so if it find a template instantiation missing it can call the
compiler again, which can use this database.
Neelakantan Krishnaswami
Jon Harrop <j...@ffconsultancy.com> wrote:
> Neelakantan Krishnaswami wrote:
>>
>> However, Ocaml *will* optimize the representations of floats (ie, not
>> box them) if you add type annotations.
>
> The float type will usually be inferred from context but, in general, it is
> a good idea to write high-performance float code as large single blocks of
> code and not factor into functions, partly because inferred types may be
> polymorphic but also because unboxing is inhibited by function boundaries.
>
> There are two major consequences of this:
>
> 1. Looping with "while" or "for" rather than recursive functions is faster
> when floats persist between iterations.
Actually, this doesn't have anything to do with float boxing. A nested
for loop is faster than a nested recursive function because the Ocaml
compiler is not able to eliminate all the overhead for nested loops
written using recursive functions.
That is, if you have a nested for-loop like:
for i = 0 to 9 do
for j = 0 to 19 do
acc := !acc + 1
done
done
You could write a recursive function like this to mimic its behavior:
let rec outer i acc =
if i < 10 then
let rec inner j acc =
if j < 20 then
inner (j+1) (acc+1)
else
outer (i+1) acc (* This call is hard to eliminate *)
in
inner 0 acc
else
acc
Notice that you can't simply eliminate the call overhead for outer the
way you would for (say) the tail-recursive factorial, because the call
happens inside the body of inner. Furthermore, the two loop bodies are
in different procedures, which also inhibits register allocation and
other low-level optimizations.
You need a fancier analysis to figure this out -- John Reppy wrote a
paper, "Local CPS conversion in a Direct-Style Compiler" explaining
how to do it.
> F# has the nice property that run-time types allow you to write generic
> functions that dispatch to specialized functions when appropriate with
> something like:
>
> let norm = function
>| :? float array as a -> Vector.norm a
>| a -> Array.norm a
That's quite nice.
Jon Harrop
> In article <<46994473$0$1624$ed26...@ptn-nntp-reader02.plus.net>>,
> Jon Harrop <j...@ffconsultancy.com> wrote:
>> 1. Looping with "while" or "for" rather than recursive functions is
>> faster when floats persist between iterations.
>
Then why is the first of these two factorial functions 3x faster?
let f n =
let i = ref 1. in
for j=1 to n do
i := !i *. float j
done;
!i +. 0.0
let rec g i j n =
if j<=n then g (float j *. i) (j + 1) n else i +. 0.0
Neelakantan Krishnaswami
Jon Harrop <j...@ffconsultancy.com> wrote:
> Neelakantan Krishnaswami wrote:
>> In article <<46994473$0$1624$ed26...@ptn-nntp-reader02.plus.net>>,
>> Jon Harrop <j...@ffconsultancy.com> wrote:
>>> 1. Looping with "while" or "for" rather than recursive functions is
>>> faster when floats persist between iterations.
>>
>> Actually, this doesn't have anything to do with float boxing...
>
> Then why is the first of these two factorial functions 3x faster?
Because the Ocaml compiler is quite a bit worse than I thought it
was. You're right -- Ocaml *is* boxing floats in a non-nested,
tail-recursive loop with no polymorphism.
Not optimizing nested loops is hard, so it's understandable, but this
is frankly embarassing.
Paul Rubin
> Because the Ocaml compiler is quite a bit worse than I thought it
> was. You're right -- Ocaml *is* boxing floats in a non-nested,
> tail-recursive loop with no polymorphism.
>
> Not optimizing nested loops is hard, so it's understandable, but this
> is frankly embarassing.
I wonder if it's worth attempting profile-directed specialization.
You'd run the program with some instrumentation turned on and it
would measure the running time of the function under different
input types. Then you'd recompile and the type signatures that
used a lot of cpu time would get compiled to specialized versions.
Jon Harrop
> I wonder if it's worth attempting profile-directed specialization.
> You'd run the program with some instrumentation turned on and it
> would measure the running time of the function under different
> input types. Then you'd recompile and the type signatures that
> used a lot of cpu time would get compiled to specialized versions.
I don't find float boxing to be a problem in practice. OCaml is very simple,
which makes it very predictable.
Torben Ægidius Mogensen
GC can be quite cache-friendly if done right. Region analysis is
friendlier, since related values (such as elements of the same list)
are explicitly put into the same region, but harder on the programmer
-- to avoid space leaks, you often need to add annotations to guide
the regions analysis.
As for specialisation versus tagging, I would choose specialisation if
I were to make a high-performance implementation of a functional
language. While it does expand code, my experience is that the larger
a function is, the less polymorphic it is, so a large function is
unlikely to be used at more than one type -- the type may change
during program development, but at any one time there will be only one
instantiation. An exception is library code, which may be carefully
made to be polymorphic. but in any single program, you are unlikely
to use the same large library function in several instantiations.
Specialisation also help implementation of Haskell-style type classes
(no runtime dictionaries needed) and may give spin-off optimisations
after inlining functions from type-classes. The main disadvantages
are complexity in the compiler and loss of separate compilation. You
can still do parsing, type-checking and compilation to intermediate
form separately, but specialisation and subsequent optimisation is a
whole-program affair. C++ users have lived with this (and worse,
since templates aren't type-checked or even fully parsed until they
are applied) for a long time, so I can't see why it shouldn't work for
functional languages.
Torben