2 ms·

I know how to do precise GC if you allow me to add a (pointer-size) header to all data living in the heap; i.e. to maintain the RTTI. I don't know how you do th

by ezyang 15y ago

I know how to do precise GC if you allow me to add a (pointer-size) header to all data living in the heap; i.e. to maintain the RTTI. I don't know how you do that if you're not allowed a header. Do C# and D have headers?

pcwalton 15y ago
I'm sure they do. There are a few things to note here: (1) In order for malloc to work, you need a header anyway (at least, unless your allocation fits in one of the fixed-size bins). (2) You can get around the header to some extent by sorting the fields of your objects so that pointers come first, and then all you need to do is to store the number of pointers (or a sentinel value). This is what Haskell does. Of course, this prevents low-level control over data representation. (3) You can tag (or NaN box) all your values. This is what most MLs do, as well as JS, many Lisps, etc. (4) You can use a map on the side from pointer to type info to avoid a header. This is what Rust in its early days did. It's worse than a header for memory consumption though, so it doesn't really buy much.
- ezyang 15y ago
  So, the thing that always gets Haskell folks when dealing with an implementation (2) is that you can't get uniform data representation when dealing with things like arrays. It means you have to unbox things. Arguably, the situation is not much better in malloc land; if you malloc a large multiple of your object size, you're explicitly saying, "I want this to be unboxed", but by this point you've wandered into generics land. (3) is annoying. Who likes 31-bit integers? Not I!
  - pcwalton 15y ago
    Yeah, I hate 31-bit integers too. It's not the only tagging scheme though; I prefer NaN boxing (used in SpiderMonkey among others). NaN boxing allows unboxed doubles and 32-bit ints, at the cost of increased register pressure and memory usage on 32-bit systems.

2 ms·

I know how to do precise GC if you allow me to add a (pointer-size) header to all data living in the heap; i.e. to maintain the RTTI. I don't know how you do th

by ezyang 15y ago

pcwalton 15y ago
I'm sure they do. There are a few things to note here: (1) In order for malloc to work, you need a header anyway (at least, unless your allocation fits in one of the fixed-size bins). (2) You can get around the header to some extent by sorting the fields of your objects so that pointers come first, and then all you need to do is to store the number of pointers (or a sentinel value). This is what Haskell does. Of course, this prevents low-level control over data representation. (3) You can tag (or NaN box) all your values. This is what most MLs do, as well as JS, many Lisps, etc. (4) You can use a map on the side from pointer to type info to avoid a header. This is what Rust in its early days did. It's worse than a header for memory consumption though, so it doesn't really buy much.
- ezyang 15y ago
  So, the thing that always gets Haskell folks when dealing with an implementation (2) is that you can't get uniform data representation when dealing with things like arrays. It means you have to unbox things. Arguably, the situation is not much better in malloc land; if you malloc a large multiple of your object size, you're explicitly saying, "I want this to be unboxed", but by this point you've wandered into generics land. (3) is annoying. Who likes 31-bit integers? Not I!
  - pcwalton 15y ago
    Yeah, I hate 31-bit integers too. It's not the only tagging scheme though; I prefer NaN boxing (used in SpiderMonkey among others). NaN boxing allows unboxed doubles and 32-bit ints, at the cost of increased register pressure and memory usage on 32-bit systems.