5 ms·

The Generic Dilemma (2009)

30 points by mpweiher 6y ago

okl 6y ago
As mentioned in the comments: "Maybe take a peek at Ada Generics. The generic instances are shared, and there is no boxing of types." RM12: https://www.adaic.org/resources/add_content/standards/05rm/html/RM-12.html https://www.adaic.org/resources/add_content/standards/05rm/h... RAT83: http://archive.adaic.com/standards/83rat/html/ratl-12.html http://archive.adaic.com/standards/83rat/html/ratl-12.html
- twic 6y ago
  I think C# generics also work this way, at least to an extent. For example, a single instance of generic hashmap code can store any value as long as it's one word in size, which the most common sizes of integer, floating-point number, and pointer are. EDIT: as many comments on that post say, sorry!
pansa2 6y ago
> The generic dilemma is this: do you want slow programmers, slow compilers and bloated binaries, or slow execution times? Now that the Go team has approved a design for generics, which of these did they choose? Or did they “somehow manage to avoid all three of these bad outcomes”?
- ainar-g 6y ago
  From what I could tell, they specifically worked out the current design in a way that allows them to change the implementation later. The current WIP code, as far as I know, mostly just compiles Generic Go code into the regular Go code, so closer to the “slow compilers” method, but the eventual goal seems to be some form of a hybrid approach[1]. EDIT: Here[2] is a direct link to what seems to be the most recent public DRAFT of the design document of the hybrid approach in question. [1]: https://groups.google.com/g/golang-dev/c/OcW0ATRS4oM https://groups.google.com/g/golang-dev/c/OcW0ATRS4oM [2]: https://go.googlesource.com/proposal/+/78bd52518d53994d3fe66aaf04c5075892855d0d/design/generics-implementation-gcshape.md https://go.googlesource.com/proposal/+/78bd52518d53994d3fe66...
lapinot 6y ago
None of the example languages (C,C++,java) have serious type systems (in the sense of mathematically well-behaved and expressive). I'll look at OCaml since that's the one i know best (and it's more low-level/perf-oriented than say Haskell's GHC imho). Now what's a generic: it doesn't say much. A generic function might first be parametrized by a type, like map : (T -> U) -> array T -> array U. These "generics" are called parametrically polymorphic functions. We can prove that their (untyped) implementation is the same for any type: they will just pass opaque values around. These should be compilable to a single asm routine, as long as there is an homogeneous way to copy them (so either the opaque arguments need to be behind pointers, or we need the function to take the length of the runtime representation of that type so that it can memcpy it). Now another type of "generic" are functions parametrized by a structure. These need their opaque arguments to satisfy some interface. The binding to the implementation of that interface can either be done by specializing the function to any given implementation, or by having vtables (or even by dynamic linking). The difference between this case and the polymorphic case is that here the underlying structure (eg "compare" or "insert") isn't done in a homogeneous way (single routine) for every type: the polymorphism is ad-hoc and not parametric. The vtable solution is a form of boxing and that impacts runtime, so you need to have good inlining passes (which enables "specialization"): indeed when you inline the box-taking function inside a context where the precise type of the (inside of the) box is statically known, you can constant-propagate (more generally: partialy-evaluate) the implementation of the structure functions: you locally unbox. So in the end for efficient compilation of languages with generics you need to have * an efficient compilation of parametrically polymorphic functions (by type erasure), * a good run-time representation of interface implementations (modules, ie structs with functions and other stuff) * and good inlining and partial-evaluation strategies for local unboxing. There are other optimizations that can help but these usually need some help from the programmer/library, like eliminating high-order arguments by defunctionalization (any finite set of functions can be represented by a datatype and an "eval" function, like how closures are implemented in rust). But then again, this is dependent on strategic inlining: very generic high-order functions like container "fold" should almost always get inlined so that we can specialize them to their argument function and defunctionalize.
- lapinot 6y ago
pif 6y ago
I have never understood this fetish for short compilation times. Compilation time is an extremely good investment if it lets me express exactly what I need and gives me the fastest possible program as a result.
- enqk 6y ago
  When building programs with user interfaces*, there are parts that _cannot_ be tested formally with either types or automated tests, because they require a human to test how things "feel." In that context, long compile times lengthen the build-evaluate feedback loop to a point that harms quality. * also note that APIs are user interfaces. So this harms way more than just programs with GUIs.
  - yamrzou 6y ago
    Same for data analysis. It is mostly exploratory and iterative work, with the need for a feeback loop (making plots, checking for unusual values, etc.) because the input data is unpredictable. That's why data scientists prefer interpreted languages and Jupyter Notebooks.
    - pif 6y ago
      That's also why you get the -O0 and -O3 options.
- lapinot 6y ago
  This. Big part of the most high-performance code (like crypto, linear-algebra or fft kernels) are even generated: you build a program that will generate a program that will get compiled (or is already asm). One can arguably say that the generator program is part of the compiler chain (takes parameters describing some algorithm and generates executable code). And these generators sometimes call out to SMT solvers or otherwise solve complicated algorithmic problems (integer programming problems for vectorizing with the polyhedral model). Hence these are specialized high-level compilers that take a long time to output extremly fast and small programs. Most people don't call the generators tho, they only use the generated code: long compilation time is no problem if you have good modular compilation. http://www.fftw.org/ http://www.fftw.org/ http://flopoco.gforge.inria.fr/ http://flopoco.gforge.inria.fr/ https://github.com/FStarLang/kremlin https://github.com/FStarLang/kremlin https://github.com/project-everest/vale https://github.com/project-everest/vale
millstone 6y ago
Swift has tried to address this by making specialization an optimization. When it compiles a generic function, it emits a single boxed implementation, like Java. But the optimizer may also choose to specialize it for concrete types, like C++ or Rust does. It sounds nice, but there's a huge performance difference between boxed and specialized. When you make a function generic, the compiler boxes values, conservatively emit retain/release, others. The difference is so large, it justifies giving the programmer levers to control specialization. Swift team has added "@_specialize" as a hint. I think they should go further. What I don't know is how specialized generics can participate in library evolution. If a dynamic library provides a sort routine, and you specialize it, what happens when the library changes? This is where a JIT or the .NET model (compile at install time) can pay off. Apple has laid some groundwork for this (bitcode, Rosetta 2) so they can certainly get there if they choose to. Anyways I think the real dilemma is whether generics are meant to be a performance optimization (C++, Rust) or just for typechecking (Java, C#). The cost of saying yes to performance is library evolution.

30 points by mpweiher 6y ago

okl 6y ago

As mentioned in the comments: "Maybe take a peek at Ada Generics. The generic instances are shared, and there is no boxing of types." RM12: https://www.adaic.org/resources/add_content/standards/05rm/html/RM-12.html https://www.adaic.org/resources/add_content/standards/05rm/h... RAT83: http://archive.adaic.com/standards/83rat/html/ratl-12.html http://archive.adaic.com/standards/83rat/html/ratl-12.html

twic 6y ago
I think C# generics also work this way, at least to an extent. For example, a single instance of generic hashmap code can store any value as long as it's one word in size, which the most common sizes of integer, floating-point number, and pointer are. EDIT: as many comments on that post say, sorry!

pansa2 6y ago

> The generic dilemma is this: do you want slow programmers, slow compilers and bloated binaries, or slow execution times? Now that the Go team has approved a design for generics, which of these did they choose? Or did they “somehow manage to avoid all three of these bad outcomes”?

ainar-g 6y ago
From what I could tell, they specifically worked out the current design in a way that allows them to change the implementation later. The current WIP code, as far as I know, mostly just compiles Generic Go code into the regular Go code, so closer to the “slow compilers” method, but the eventual goal seems to be some form of a hybrid approach[1]. EDIT: Here[2] is a direct link to what seems to be the most recent public DRAFT of the design document of the hybrid approach in question. [1]: https://groups.google.com/g/golang-dev/c/OcW0ATRS4oM https://groups.google.com/g/golang-dev/c/OcW0ATRS4oM [2]: https://go.googlesource.com/proposal/+/78bd52518d53994d3fe66aaf04c5075892855d0d/design/generics-implementation-gcshape.md https://go.googlesource.com/proposal/+/78bd52518d53994d3fe66...

lapinot 6y ago

None of the example languages (C,C++,java) have serious type systems (in the sense of mathematically well-behaved and expressive). I'll look at OCaml since that's the one i know best (and it's more low-level/perf-oriented than say Haskell's GHC imho). Now what's a generic: it doesn't say much. A generic function might first be parametrized by a type, like map : (T -> U) -> array T -> array U. These "generics" are called parametrically polymorphic functions. We can prove that their (untyped) implementation is the same for any type: they will just pass opaque values around. These should be compilable to a single asm routine, as long as there is an homogeneous way to copy them (so either the opaque arguments need to be behind pointers, or we need the function to take the length of the runtime representation of that type so that it can memcpy it). Now another type of "generic" are functions parametrized by a structure. These need their opaque arguments to satisfy some interface. The binding to the implementation of that interface can either be done by specializing the function to any given implementation, or by having vtables (or even by dynamic linking). The difference between this case and the polymorphic case is that here the underlying structure (eg "compare" or "insert") isn't done in a homogeneous way (single routine) for every type: the polymorphism is ad-hoc and not parametric. The vtable solution is a form of boxing and that impacts runtime, so you need to have good inlining passes (which enables "specialization"): indeed when you inline the box-taking function inside a context where the precise type of the (inside of the) box is statically known, you can constant-propagate (more generally: partialy-evaluate) the implementation of the structure functions: you locally unbox. So in the end for efficient compilation of languages with generics you need to have * an efficient compilation of parametrically polymorphic functions (by type erasure), * a good run-time representation of interface implementations (modules, ie structs with functions and other stuff) * and good inlining and partial-evaluation strategies for local unboxing. There are other optimizations that can help but these usually need some help from the programmer/library, like eliminating high-order arguments by defunctionalization (any finite set of functions can be represented by a datatype and an "eval" function, like how closures are implemented in rust). But then again, this is dependent on strategic inlining: very generic high-order functions like container "fold" should almost always get inlined so that we can specialize them to their argument function and defunctionalize.

lapinot 6y ago

pif 6y ago

I have never understood this fetish for short compilation times. Compilation time is an extremely good investment if it lets me express exactly what I need and gives me the fastest possible program as a result.

enqk 6y ago
When building programs with user interfaces*, there are parts that _cannot_ be tested formally with either types or automated tests, because they require a human to test how things "feel." In that context, long compile times lengthen the build-evaluate feedback loop to a point that harms quality. * also note that APIs are user interfaces. So this harms way more than just programs with GUIs.
- yamrzou 6y ago
  Same for data analysis. It is mostly exploratory and iterative work, with the need for a feeback loop (making plots, checking for unusual values, etc.) because the input data is unpredictable. That's why data scientists prefer interpreted languages and Jupyter Notebooks.
  - pif 6y ago
    That's also why you get the -O0 and -O3 options.
lapinot 6y ago
This. Big part of the most high-performance code (like crypto, linear-algebra or fft kernels) are even generated: you build a program that will generate a program that will get compiled (or is already asm). One can arguably say that the generator program is part of the compiler chain (takes parameters describing some algorithm and generates executable code). And these generators sometimes call out to SMT solvers or otherwise solve complicated algorithmic problems (integer programming problems for vectorizing with the polyhedral model). Hence these are specialized high-level compilers that take a long time to output extremly fast and small programs. Most people don't call the generators tho, they only use the generated code: long compilation time is no problem if you have good modular compilation. http://www.fftw.org/ http://www.fftw.org/ http://flopoco.gforge.inria.fr/ http://flopoco.gforge.inria.fr/ https://github.com/FStarLang/kremlin https://github.com/FStarLang/kremlin https://github.com/project-everest/vale https://github.com/project-everest/vale

millstone 6y ago

Swift has tried to address this by making specialization an optimization. When it compiles a generic function, it emits a single boxed implementation, like Java. But the optimizer may also choose to specialize it for concrete types, like C++ or Rust does. It sounds nice, but there's a huge performance difference between boxed and specialized. When you make a function generic, the compiler boxes values, conservatively emit retain/release, others. The difference is so large, it justifies giving the programmer levers to control specialization. Swift team has added "@_specialize" as a hint. I think they should go further. What I don't know is how specialized generics can participate in library evolution. If a dynamic library provides a sort routine, and you specialize it, what happens when the library changes? This is where a JIT or the .NET model (compile at install time) can pay off. Apple has laid some groundwork for this (bitcode, Rosetta 2) so they can certainly get there if they choose to. Anyways I think the real dilemma is whether generics are meant to be a performance optimization (C++, Rust) or just for typechecking (Java, C#). The cost of saying yes to performance is library evolution.