Question on Sixten's Flat Data Representation with Generics

[GunpowderGuy]

Hi Ollef,

I'm interested in how Sixten handles data representation. As far as I know, it's the only language that maintains a flat data layout while still supporting generic functions without runtime specialization.

I haven't been able to find much information on how Sixten achieves this. Could you provide any details on

-How type information is stored and used to allow generics to operate on unboxed data?
-Whether Sixty follows the same approach or differs in any way?
-If any other languages use a similar technique?

Thanks for your time, and I appreciate the work you're doing on this project!

[dlight]

I'm interested in how Sixten handles data representation. As far as I know, it's the only language that maintains a flat data layout while still supporting generic functions without runtime specialization.

Doesn't Rust also do this? Generics in Rust are monomorphized (compiled separately for each type rather than compiled just once)

[ollef]

Heya!

Let's look at an example of a polymorphic function and how it's compiled:

data List (a : Type) = Nil | Cons a (List a)

map : forall (a : Type) (b : Type). (a -> b) -> List a -> List b
map f Nil = Nil
map f (Cons x xs) = Cons (f x) (map f xs)

In a language with monomorphization, like Rust, each call to map with different type parameters makes the compiler generate a new map function specialized to the concrete type parameters. In the compiled binary, you get e.g.

map_Int_Int(f: Int -> Int, xs: List Int) -> List Int // map where a=Int, b=Int
map_Int_List_Int(f: Int -> List Int, xs: List Int) -> List (List Int) // map where a=Int, b=List Int

Sixten compiles map to a single function by passing the sizes of the types a and b to the function. In pseudocode, it'll look something like this:

map(a_size: usize, b_size: usize, f, xs: ptr) -> ptr {
  // A list node has room for a tag (Nil or Cons), an a, and a pointer to the next list element
  let result = malloc(tag_size + a_size + pointer_size)
  match xs[0] {
    Nil =>
      result[0] = Nil
    Cons =>
      result[0] = Cons
      let x = &xs[tag_size]
      let y = &result[tag_size] // Destination for the return value of `f`.
      f(x, y) // Size of argument and return value are dynamic: use destination-passing style.
      let xs = &xs[tag_size + a_size]
      result[tag_size + b_size] = map(a_size, b_size, f, xs)
  }
  result
}

Here the size parameters are used to determine the size and offsets of the different parts of the memory objects at runtime.

To answer the questions directly:

• How type information is stored and used: any time you see something of type Type in the source program, its compiled representation is the size of the type it represents. It's used to determine offsets and sizes of memory objects at runtime.
• Whether Sixty follows the same approach: Sixty mostly uses the same approach, but I've been experimenting with a memory object representation that stores pointers first, then non-pointer data, which allows sub-word sized data without alignment problems when implementing garbage collection. With this representation, Type compiles to two sizes (but you may e.g. pack them both into a 64-bit integer): the number of pointers and the number of non-pointer bytes.
• Other languages: Swift is also able to do something similar as far as I understand it.

Hope that helps!

[GunpowderGuy]

Hi Olle,

I'm seeking clarification on a couple of points:

When you refer to "type," are you indicating something akin to the 'a' in the data declaration data List a = Nil | Cons a (List a)?​

" but I've been experimenting with a memory object representation that stores pointers first, then non-pointer data, which allows sub-word sized data without alignment problems when implementing garbage collection. With this representation, Type compiles to two sizes (but you may e.g. pack them both into a 64-bit integer): the number of pointers and the number of non-pointer bytes."

Sorry, i didnt get this point

Additionally, in response to the mention of Rust, it's worth noting that Rust employs compile-time specialization through monomorphization. This can lead to increased compilation times and Highly polymorphic languages like Haskell, OCaml, and those with dependent types would require whole-program optimization to achieve similar static monomorphization.

Thank you for your insights.

[ollef]

When you refer to "type," are you indicating something akin to the 'a' in the data declaration data List a = Nil | Cons a (List a)?​

That's one of them, and also the a and b in the signature of map. I use forall syntax for implicit parameters, so these are actually additional parameters to the function, which are filled in by the type checker when it's used. In this case these implicit parameters are inferred to have type Type because of how they are used, which I should have probably clarified. I've edited the code above with implicit types.

Sorry, i didnt get this point

The details are probably not terribly important for the current discussion, but it's about how the fields are laid out in memory. To do accurate garbage collection, you need to know where the pointers are in any heap object. If you always put the pointers first, followed by non-pointer data, you only need to know how many pointers there are to be able to find them. Compare that to a scheme where the pointers can appear anywhere: you'd need a list or bit mask of where the pointers are.

And in a language like Sixten, information about the types is not static, since you can e.g. create types that depend on some data read from standard input. So you need a way to compute and combine the information about the pointers at runtime, and ideally it should not be very expensive to do so. With a pointers-first representation, these operations are cheap.

[GunpowderGuy]

Thanks, i get i now.

Since you are exploring new memory layouts, You may want to look into bit stealing. A 64 bit Pointer typically has 3 redundant LSB and 16 redundant MSB bits ( see double ended bit stealing ) . You could use the lsb for tags and the msb for number of pointers and non pointers.

There are many other alternatives such as reserving one or two bits to indicate an small pointed object Is small ( eg pair like ) , so it doesnt have to store a memory layout . This would reduce the memory compsumption of lists from 3 words per element down to 2. Bigger objects would still need a header but the relative cost is much smaller

[GunpowderGuy]

I think you could also use "subspaces" . Kind of memory regions that can only store objects of a single type, thus some data becomes implicit
Which of the methods do you think fits your projects the best ? @ollef

[ollef]

Since you are exploring new memory layouts, You may want to look into bit stealing. A 64 bit Pointer typically has 3 redundant LSB and 16 redundant MSB bits ( see double ended bit stealing ) . You could use the lsb for tags and the msb for number of pointers and non pointers.

There are many other alternatives such as reserving one or two bits to indicate an small pointed object Is small ( eg pair like ) , so it doesnt have to store a memory layout . This would reduce the memory compsumption of lists from 3 words per element down to 2. Bigger objects would still need a header but the relative cost is much smaller

Yes, I've experimented with stuff like this, e.g. using some bits of the pointer for the constructor tag, and some bits for the size. A problem with storing the size in the pointer is that you need a fallback mode for when the size doesn't fit in the stolen bits, where you store the size in the pointee instead. This means that getting the size involves branching and I start to wonder if it's not better to always store it in the pointee, leaving more bits in the pointer for the constructor tag. The constructor tag is not as problematic, as you can put limits on how many constructors are allowed per datatype in the source language (e.g. up to 2^16 which should be plenty).

I think you could also use "subspaces" . Kind of memory regions that can only store objects of a single type, thus some data becomes implicit Which of the methods do you think fits your projects the best ? @ollef

Not sure what you mean by this. Can you elaborate?

[playX18]

@ollef

I think you could also use "subspaces" . Kind of memory regions that can only store objects of a single type, thus some data becomes implicit Which of the methods do you think fits your projects the best ? @ollef

Not sure what you mean by this. Can you elaborate?

@GunpowderGuy got this idea from our discussion in PLDev discord, I actually used "subspaces" term which is not as widely used. In Scheme impls it's known as BiBOP (Big Bag of Pages), introduced by R.Kent Dybvig: https://legacy.cs.indiana.edu/~dyb/pubs/bibop.pdf

In essense, for each type there is a separate heap, thus GC does not have to store vtables for types, if object is identified to be from one space that is for strings it knows it's layout is [ length, data ... ] for example. ChezScheme is currently the most large runtime that implements this technique.

[ollef]

Ah, I see what you mean. What do you use for identifying types? Is it e.g. a static ID? In Sixten, new types can be made up at runtime, so you'd need a system to make up new (unique?) IDs for such types.

It does seem doable to at least bin heap objects based on their size (which is not uncommon for GCs and malloc implementations to do already).

[playX18]

Ah, I see what you mean. What do you use for identifying types? Is it e.g. a static ID? In Sixten, new types can be made up at runtime, so you'd need a system to make up new (unique?) IDs for such types.

It does seem doable to at least bin heap objects based on their size (which is not uncommon for GCs and malloc implementations to do already).

My VM uses pointer tagging so some values have inline tag which is assigned on allocation (let x = gc_alloc(sizeof(Pair)); x |= TYPE_PAIR;) And if type is on heap it has TYPE_HEAP_OBJECT which indicates that the first word of heap object is header. If this first word is tagged with TYPE_RECORD then first word is actually pointer to vtable of a record (Scheme structures essentially)

[GunpowderGuy]

Could the subspace concept be extended so all members of a subspace are of a certain type, like pair(int, ptr) ; pair(int,int) ; etc?

The idea is that storing the size or specific type of small objects is highly wasteful as it requires at least 50 percent over the actual data. 2 machine words for data and at least 1 for headers.

[ollef]

You could at least segregate based on size. Type might be problematic as there's currently no identifying information for types at runtime apart from their sizes.

With unboxed data you could also just not heap allocate it.

[GunpowderGuy]

Right, due to the nature of sixten's generics, one machine-word length heap allocated objects should be very very rare

[GunpowderGuy]

@ollef Btw. do you think an existing language could retrofit sixteen's data representation? Sixteen only stores things behind an indirection, if they are explicitely behind one like a pointer. I suppose an idris2 backend could store everything without indirections except when implicitly necessary such as recursive data structures?

A community that may have a lot of interest over this are jvm based language users. Traditionally when a jvm class ( their way to structure data ) stores another, the inner class must be behind an indirection. A feature called "values classes " is being added which makes it practicall for a class A to store a class B, if B is a value class. This is nice but the proposed extension for generic types to support unboxed classes seem very complicated.
I think that community should be investigating if sixteens unboxed generic could be used like so: Whenever a generic class A stores a class B whoose type will vary at runtime. B will be unboxed with sixteens method if B is a value class

[ollef]

I think this implementation strategy doesn't quite fit with Idris 2's multiplicities: in Idris, you're allowed to say that an argument to a function that is only used in types has multiplicity 0 and therefore doesn't need to be passed to the function at runtime. In Sixten, a value used in a type may be needed at runtime to calculate some type's size. I'm not quite sure how to reconcile these two systems, but maybe there's a way?

Some form of type passing could be a viable implementation strategy for Java with value classes. I have at least seen a C# dialect implementation that did type passing for generics, and that included unboxed struct handling which I think is more or less analogous to Java's value classes. Swift also does something similar.