24 ms·

I'm working on a blog post on the subject, but this is something that needs more justification than an HN comment. To answer your questions: > What's a "copy-o

I'm working on a blog post on the subject, but this is something that needs more justification than an HN comment. To answer your questions: > What's a "copy-on-write reference"? A copy on write reference (CoW) is a pointer to some immutable data, that when written to, is copied to a new memory location first. > Does this mean that if write a function that takes a million-element list, and inside the function I mutate the last element, the entire list will be copied (inside the function, but invisibly to the outside)? Only if you use the original list later: big_list = [ ... ] new_big_list = mutate_last big_list print big_list This would copy `big_list` because we use it in `print` later. If you do not use big_list later: big_list = [ ... ] new_big_list = mutate_last big_list Or reassign the variable: big_list = [ ... ] big_list = mutate_last big_list the original list is not copied, because this is the last usage of a value, and last usages pass the actual value rather than CoW, allowing the program to mutate it directly. This is what Functional but in Place (FbiP) means - You can write code in a functional style, but when executed it will mutate data in place. > Can I even mutate lists or anything else? I don't see any clear information about whether Passerine has mutable data at all. So, this is less about Vaporization and more about Passerine. Passerine does not have mutable data, only mutable references to data*. So the reference can change (or like in a record, the reference in a field can change), but not the data itself. Because of FbiP, however, mutations are optimized to an actual mutation rather than a copy and an overwrite. * This is needed if one wishes to extend HM type inference to support mutation, IIRC. > Does this mean that any non-last usage is a copy? Any non-last usage is a potential copy. If the function you pass it to does not mutate the data, no copy will be made. Last references also include reassignments, so something like: big_list = [ ... ] for x in 0..100 { big_list = big_list.append x } Does not make 100 copies of `big_list`. > Again, are these eager copies or lazy copy-on-writes? These are eager copies, and immutablility is enforced by the language itself. This tradeoff has to be made, because mutable references allow for the construction of cycles. These references are reference counted if a copy of the closure is made or another closure closes over the same value in the same scope. It's safe to do this because these references are immutable, and when all closures referencing them go out of scope, they will be dropped. > How are non-closure references garbage collected? Non-closure references are 'garbage collected' when they go out of scope. Vaporization basically ties everything to the stack, and prevents values stored on the heap from becoming dissociated with it. > I would be interested in a much more detailed write-up of this memory management technique. Thanks for the interest! There's still a bit more formal verification to do, which is why I left this broad claim to the FAQ - we're rewriting the website, so the mention of it there is a bit outdated. Given that it was just asked here, it looks like I need to extend the FAQ some more, given how frequent of a question it is. ;P Have a nice day!

tom_mellior 6y ago
Thank you for the detailed answer. I'm looking forward to that blog post. One more question for now (a variant of something I asked before): How do you know a use is a last use? For example: foo = (list1 list2) -> { mutate_last list1 } The use of list1 in the mutate_last call is the only, and hence the last, use of list1. So mutate_last can mutate it in place. Right? Except if I call this function like: big_list = [ ... ] foo big_list big_list print big_list Then mutating in place will be incorrect. So how do you tell inside foo whether the call is the last use of the object referenced by list1? Heroic interprocedural pointer analysis? A uniqueness type system? Something else?
- slightknack 6y ago
  Thanks for discussing this with me and helping me work through it. To answer your question: Let's annotate the variable lifetimes. `'` indicates last use, `_n` indicates that a variable holds the same value. I'll only be annotating the values in question: foo = (list1_0 list2_0') -> { mutate_last list1_0' } big_list_0 = [ ... ] foo big_list_0 big_list_0 print big_list_0' Let's focus on this line. Because these both aren't the last reference to `big_list`, they're passed as a CoW reference. I'll use `&` to denote this: foo &big_list_0 &big_list_0 In `foo`, `list1_0 = &big_list_0` and `list2_0' = &big_list_0`. `list2_0` is never used, so this reference is immediately dropped (not the value itself, rather the reference to that value). Let's now look at the body of foo: mutate_last list1_0' Because list1_0 is a final reference, it's passed the value of the CoW reference, which is, well, the CoW reference. mutate list mutates this, and because the reference is copy-on-write, a copy of `&big_list_0` is returned. We'll call this `big_list_1`. So the CoW reference of a value is a CoW<Value>. a CoW reference of a CoW<Value> stays the same, it's still a CoW<Value>. > So how do you tell inside foo whether the call is the last use of the object referenced by list1? Heroic interprocedural pointer analysis? A uniqueness type system? Something else? Something else. Vaporization is not all compile-time magic, it depends on the runtime as well. You can basically sum it up with two operations: reference: Value or CoW<Value> -> CoW<Value> mutate: Value or CoW<Value> + mutation -> Value So when `mutate_list` mutates the list, depending on whether `list1` is a value or a CoW reference, either a copy will be made or it'll be mutated in place. I'm not claiming that Vaporization is the best approach to compile-time memory management, rather, it's more of a set of compiletime+runtime strategies that allow the interpretation of programs without garbage collection (in the traditional sense) So, the question becomes: how do we indicate whether something is a value or a CoW reference? Something along the lines of a tagged pointer will do. Passerine already uses NaN-tagging, so this fits right in. What about compiling to low-level targets, like LLVM IR, which don't really have a 'runtime' and rather specify the manual layout of structs and references? I'm not quite sure, but here's one possibility. All values that can escape a local scope exist in some region of memory allocated for local variables. When a function is called, we can pass a bitfield indicating which of the locals variables on the stack are CoW references, and which are not. When the runtime goes to mutate a reference, it quickly checks the bitfield (which can be stored in a register or in the call frame) whether it needs to make a copy before mutating. In practice, the check is just a quick bit-shift and `&`. Note that we can go a bit further: the bit-fields of all calls are known at compile time, so instead of copying and passing the bitfield itself, we can pass the index of the bitfield (which is a constant) to the function to use. In fact, I imagine you could somewhat 'monomorphize' this, so to speak, and generate different functions for different bitfields... but I'd have to think some more about this. Anyway, that's about it. I hope I've helped clear some things up. If you notice anything else slightly off, or if you'd like to discuss this further, please let me know :)

tom_mellior 6y ago

Thank you for the detailed answer. I'm looking forward to that blog post. One more question for now (a variant of something I asked before): How do you know a use is a last use? For example: foo = (list1 list2) -> { mutate_last list1 } The use of list1 in the mutate_last call is the only, and hence the last, use of list1. So mutate_last can mutate it in place. Right? Except if I call this function like: big_list = [ ... ] foo big_list big_list print big_list Then mutating in place will be incorrect. So how do you tell inside foo whether the call is the last use of the object referenced by list1? Heroic interprocedural pointer analysis? A uniqueness type system? Something else?

slightknack 6y ago
Thanks for discussing this with me and helping me work through it. To answer your question: Let's annotate the variable lifetimes. `'` indicates last use, `_n` indicates that a variable holds the same value. I'll only be annotating the values in question: foo = (list1_0 list2_0') -> { mutate_last list1_0' } big_list_0 = [ ... ] foo big_list_0 big_list_0 print big_list_0' Let's focus on this line. Because these both aren't the last reference to `big_list`, they're passed as a CoW reference. I'll use `&` to denote this: foo &big_list_0 &big_list_0 In `foo`, `list1_0 = &big_list_0` and `list2_0' = &big_list_0`. `list2_0` is never used, so this reference is immediately dropped (not the value itself, rather the reference to that value). Let's now look at the body of foo: mutate_last list1_0' Because list1_0 is a final reference, it's passed the value of the CoW reference, which is, well, the CoW reference. mutate list mutates this, and because the reference is copy-on-write, a copy of `&big_list_0` is returned. We'll call this `big_list_1`. So the CoW reference of a value is a CoW<Value>. a CoW reference of a CoW<Value> stays the same, it's still a CoW<Value>. > So how do you tell inside foo whether the call is the last use of the object referenced by list1? Heroic interprocedural pointer analysis? A uniqueness type system? Something else? Something else. Vaporization is not all compile-time magic, it depends on the runtime as well. You can basically sum it up with two operations: reference: Value or CoW<Value> -> CoW<Value> mutate: Value or CoW<Value> + mutation -> Value So when `mutate_list` mutates the list, depending on whether `list1` is a value or a CoW reference, either a copy will be made or it'll be mutated in place. I'm not claiming that Vaporization is the best approach to compile-time memory management, rather, it's more of a set of compiletime+runtime strategies that allow the interpretation of programs without garbage collection (in the traditional sense) So, the question becomes: how do we indicate whether something is a value or a CoW reference? Something along the lines of a tagged pointer will do. Passerine already uses NaN-tagging, so this fits right in. What about compiling to low-level targets, like LLVM IR, which don't really have a 'runtime' and rather specify the manual layout of structs and references? I'm not quite sure, but here's one possibility. All values that can escape a local scope exist in some region of memory allocated for local variables. When a function is called, we can pass a bitfield indicating which of the locals variables on the stack are CoW references, and which are not. When the runtime goes to mutate a reference, it quickly checks the bitfield (which can be stored in a register or in the call frame) whether it needs to make a copy before mutating. In practice, the check is just a quick bit-shift and `&`. Note that we can go a bit further: the bit-fields of all calls are known at compile time, so instead of copying and passing the bitfield itself, we can pass the index of the bitfield (which is a constant) to the function to use. In fact, I imagine you could somewhat 'monomorphize' this, so to speak, and generate different functions for different bitfields... but I'd have to think some more about this. Anyway, that's about it. I hope I've helped clear some things up. If you notice anything else slightly off, or if you'd like to discuss this further, please let me know :)