GADTs for performance

ryanslade · October 29, 2020, 1:39pm

I’ve heard @Yaron_Minsky mention in a few talks and podcasts that GADTs can be used to improve performance, specifically around memory layout.

Does anyone have any examples of how this would work?

Is there a recording of this presentation anywhere? http://www.cs.cmu.edu/afs/.cs.cmu.edu//Web/Posters/POP-YMinsky17.pdf

pmonson711 · October 29, 2020, 2:17pm

I think the details in this article really help understand https://blog.janestreet.com/why-gadts-matter-for-performance/.

Like so much of the performance focus, it’s not valid in most cases and is generally about controlling memory location.

Yaron_Minsky · October 30, 2020, 12:19am

I’m not sure about “not valid in most cases”. Controlling memory matters in many kinds of real-world applications. And I’m really excited about some work we’re doing for making it easier in OCaml. This talk fro Stephen Dolan is an exciting preview of that work.

There’s also an RFC worth reading.

github.com

ocaml/RFCs/blob/881b220adc1f358ab15f7743d5cd764222ab7d30/rfcs/unboxed-types.md

# Unboxed types for OCaml

Suppose you define this type:

    type t = { x : Int32.t; y : Int32.t }

Values of this type carry 8 bytes of actual data. However, in OCaml,
values of this type are represented as:

  - an 8-byte pointer

  - to a 24-byte block  
    (8B header + 2x 8B fields)

  - pointing at two more 24-byte blocks  
    (8B header + 8B `caml_int32_ops` + 4B data + 4B padding)

Below is a proposed extension to OCaml to allow the layout of data
types to be controlled by the programmer. This proposal won't affect
the type defined above, but will allow you to define more compact

This file has been truncated. show original

Konstantin_Olkhovski · November 4, 2020, 2:03pm

@Yaron_Minsky It’s really exciting work! Is the plan to have this in ocaml trunk eventually?

xavierleroy · November 4, 2020, 5:36pm

The discussion on this RFC is very much open at this point. Personally, in reference to Stephen Dolan’s talk title, I prefer Lisp to C++.

coetry · November 4, 2020, 11:38pm

I very much prefer Lisp as a language over C++, but being able to represent data in a more compact way for performance when needed doesn’t sound like a bad idea to me! I’m purely speaking without any language design / implementation experience