Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Carp – A statically typed Lisp, without a GC, for real-time applications

github.com

Post reply on HN
Print view View original

131–139 of 139 posts

Re: Carp – A statically typed Lisp, without a GC, for real-time applications

#131

Post by silon42 »

dwohnitmok wrote: post #107
silon42 wrote: post #61

Earlier quoted context omitted.

It's really surprising that it's rare in functional languages. Immutability seems like it should guarantee no cycles (?), so reference counting could be used.

The big thorn is closures, which show up all over the place in FP. You either need to limit closures vs ordinary functions (as e.g. Rust does), have manual memory annotations (such as e.g. what Swift does) or you basically need a GC. The former two choices are annoying if you really take advantage of functions as first-class citizens.

Yes, I thought that might be a problem... I guess Rust is the choice for me.

Re: Carp – A statically typed Lisp, without a GC, for real-time applications

#132

Post by astrange »

kragen wrote: post #90
silon42 wrote: post #61

Earlier quoted context omitted.

It's really surprising that it's rare in functional languages. Immutability seems like it should guarantee no cycles (?), so reference counting could be used.

Reference counting is usually very expensive, because even reading a variable updates the reference count, and ending a scope involves testing the reference count of every variable defined inside the scope and conditionally deallocating the referent. Without reference counting, here's the end of a hairy function scope that deallocates 15 local variables and restores two callee-saved registers: 11a6: 48 83 c4 78 add $…

> Reference counting is usually very expensive, because even reading a variable updates the reference count, and ending a scope involves testing the reference count of every variable defined inside the scope and conditionally deallocating the referent.

This is true, but if you can prove things about lifetimes then you can eliminate RC operations with that.

Also, GC is expensive for large processes because 1. peak memory is typically higher 2. you have to scan all of memory for pointers 3. that memory may have been swapped out. Of course this can be optimized too.

Re: Carp – A statically typed Lisp, without a GC, for real-time applications

#133

Post by kragen »

astrange wrote: post #132
kragen wrote: post #90

Earlier quoted context omitted.

Reference counting is usually very expensive, because even reading a variable updates the reference count, and ending a scope involves testing the reference count of every variable defined inside the scope and conditionally deallocating the referent. Without reference counting, here's the end of a hairy function scope that deallocates 15 local variables and restores two callee-saved registers: 11a6: 48 83 c4 78 add $…

> Reference counting is usually very expensive, because even reading a variable updates the reference count, and ending a scope involves testing the reference count of every variable defined inside the scope and conditionally deallocating the referent. This is true, but if you can prove things about lifetimes then you can eliminate RC operations with that. Also, GC is expensive for large processes because 1. peak mem…

> This is true, but if you can prove things about lifetimes then you can eliminate RC operations with that.

Yes, this is true, and in fact with Rust's lifetime analysis you can get excellent performance with reference counting in many places. There is more information about this in https://news.ycombinator.com/item?id=28879401 and https://news.ycombinator.com/item?id=28884775.

> Also, GC is expensive for large processes because 1. peak memory is typically higher 2. you have to scan all of memory for pointers 3. that memory may have been swapped out. Of course this can be optimized too.

It's true that a tracing GC usually requires significantly more memory than manual allocation or reference counting, though occasionally it doesn't, since to implement compacting you basically have to implement a tracing GC, so a GC can sometimes give you lower fragmentation.

It's not true that you have to scan all of memory for pointers, for two reasons:

1. You may have a region of memory that contains no pointers, like Erlang's binary storage.

2. Generational GCs only have to look for pointers in the nursery, the stack, and things marked by the write barrier. If they're GCing a generation that isn't the nursery, at that point they have to scan that generation too, but that's so much less frequent that it doesn't make GC expensive. You say, "Of course this can be optimized too," but actually almost all modern GCs are generational, since the late 01990s. Except...

3. Things like Erlang partition the heap into separate per-process heaps for a large number of lightweight processes. Each of these heaps can be GCed independently because you can't have pointers from one heap to another. "What about unreferenced processes?", you might ask. Well, Erlang doesn't GC processes; you have to explicitly create and destroy them, like a larger-granularity malloc/free, typically using a Rust-like ownership hierarchy to avoid process leaks. This works better than it sounds like it should.

Re: Carp – A statically typed Lisp, without a GC, for real-time applications

#134

Post by kragen »

p_l wrote: post #129
kragen wrote: post #120

Earlier quoted context omitted.

It's worth mentioning that (1) typically even ordinary reference counting avoids large pauses, because typically objects that go out of scope aren't the sole owners of a huge object graph, and that this is often but not always a significant improvement over (other simple kinds of) garbage collection; (2) there's a readily available tradeoff with reference counting known as "deferred decrement" which can meet hard rea…

The main difference in favour of GC in the first case is that GC gets you centralised place to control it. Generally GC offers more explicit, centralised control over allocation/deallocation, and I've seen it favoured over other schemes if dynamic memory management is necessary in critical code.

That's interesting! Is the idea that, for example, your interrupt handler can freely allocate memory and update pointers and stuff, and you make sure to run the GC often enough that there's always enough memory available for the interrupt handler when it fires? Has this been written up anywhere?

I usually think that the main advantage of GC is not a performance thing; it's that your program can pass around arbitrarily large and complex data structures as easily as it can pass around integers, without you having to think about how much memory they use or when it gets freed. Of course, not thinking about that can easily result in programs that use too much memory and die, or run your machine out of RAM; but for very many programs, either "compute a correct answer" or "die" are acceptable outcomes. You wouldn't want to program your antilock braking system that way, but lots of times people are willing to put up with programs crashing occasionally.

Re: Carp – A statically typed Lisp, without a GC, for real-time applications

#135

Post by astrange »

kragen wrote: post #133
astrange wrote: post #132

Earlier quoted context omitted.

> Reference counting is usually very expensive, because even reading a variable updates the reference count, and ending a scope involves testing the reference count of every variable defined inside the scope and conditionally deallocating the referent. This is true, but if you can prove things about lifetimes then you can eliminate RC operations with that. Also, GC is expensive for large processes because 1. peak mem…

> This is true, but if you can prove things about lifetimes then you can eliminate RC operations with that. Yes, this is true, and in fact with Rust's lifetime analysis you can get excellent performance with reference counting in many places. There is more information about this in https://news.ycombinator.com/item?id=28879401 and https://news.ycombinator.com/item?id=28884775 . > Also, GC is expensive for large proce…

> Generational GCs only have to look for pointers in the nursery, the stack, and things marked by the write barrier. If they're GCing a generation that isn't the nursery, at that point they have to scan that generation too, but that's so much less frequent that it doesn't make GC expensive. You say, "Of course this can be optimized too," but actually almost all modern GCs are generational, since the late 01990s.

I was going to come back and edit this to say "…when you violate an assumption of generational GC" but you somehow managed to instantly reply to my 3 days late post!

Though I'm not too familiar with how GC runtimes are really implemented; I thought generations were more or less based on allocation age but don't know if it actually does analysis to separate allocations that can't reference each other.

Re: Carp – A statically typed Lisp, without a GC, for real-time applications

#136

Post by kragen »

astrange wrote: post #135
kragen wrote: post #133

Earlier quoted context omitted.

> This is true, but if you can prove things about lifetimes then you can eliminate RC operations with that. Yes, this is true, and in fact with Rust's lifetime analysis you can get excellent performance with reference counting in many places. There is more information about this in https://news.ycombinator.com/item?id=28879401 and https://news.ycombinator.com/item?id=28884775 . > Also, GC is expensive for large proce…

> Generational GCs only have to look for pointers in the nursery, the stack, and things marked by the write barrier. If they're GCing a generation that isn't the nursery, at that point they have to scan that generation too, but that's so much less frequent that it doesn't make GC expensive. You say, "Of course this can be optimized too," but actually almost all modern GCs are generational, since the late 01990s. I wa…

I was just lucky! I didn't mean to play gotcha!

(I should write a HN user-agent to watch old threads, though.)

I should preface this by saying I've never actually written a GC, or maintained one someone else wrote, so I might be off-base here; this is just my understanding from reading books and papers:

The awesome thing about generational GC is that (normally) the generations are physically separate in memory, so the GC can avoid even looking at objects in generations older than the one it's emptying out. (Unless they might contain pointers to objects in that generation, that is, which is detected by the write barrier.)

This combines nicely with the potential killer advantage of copying collectors: they don't need to even look at garbage. So if your nursery (or Garden of Eden, if you prefer) is 8MiB and contains only 128 live objects averaging 64 bytes each, a non-concurrent nursery GC consists of walking the stack and any marked older objects, copying those 8192 bytes into the next generation while adjusting the relevant pointers, then resetting the allocation pointer to the beginning of the nursery. The other, say, 130,944 objects that were allocated in the nursery aren't even looked at by the GC, because nothing points to them. (Unless they have finalizers (destructors).) So the GC examines and copies on average 0.06 bytes per object allocated.

Initializing the objects in the first place, as you must do whether they're allocated by decrementing a stack pointer or anything else, is far more expensive.

Of course, most programs retain a larger fraction of their nursery objects than that, stack allocation makes better use of memory caches than a multi-megabyte nursery, and if your program keeps retaining nursery objects long enough, it will eventually need to GC one of the other generations. So GC still isn't free even in the throughput sense. But it's competitive with manual dynamic allocation.

Re: Carp – A statically typed Lisp, without a GC, for real-time applications

#137

Post by p_l »

kragen wrote: post #134
p_l wrote: post #129

Earlier quoted context omitted.

The main difference in favour of GC in the first case is that GC gets you centralised place to control it. Generally GC offers more explicit, centralised control over allocation/deallocation, and I've seen it favoured over other schemes if dynamic memory management is necessary in critical code.

That's interesting! Is the idea that, for example, your interrupt handler can freely allocate memory and update pointers and stuff, and you make sure to run the GC often enough that there's always enough memory available for the interrupt handler when it fires? Has this been written up anywhere? I usually think that the main advantage of GC is not a performance thing; it's that your program can pass around arbitraril…

For very tight code, like interrupt handler context, you usually avoid allocation at all (with some object caches to provide storage possibly), but yes.

Metronome is all about partitioning run-time into static slice of GC/mutator ensuring that mutator code has predictable performance - it is slower than if mutator was running full-tilt, but it means that unless you manage to horribly exceed GC performance in collection, you're not going to see a pause.

That said, GCs are faster than manual management usually thanks to pauses - if you look at total runtime, wall-clock time, and not latency. The most common algorithms trade latency for throughput and total wall-clock time.

Re: Carp – A statically typed Lisp, without a GC, for real-time applications

#138

Post by kragen »

p_l wrote: post #137
kragen wrote: post #134

Earlier quoted context omitted.

That's interesting! Is the idea that, for example, your interrupt handler can freely allocate memory and update pointers and stuff, and you make sure to run the GC often enough that there's always enough memory available for the interrupt handler when it fires? Has this been written up anywhere? I usually think that the main advantage of GC is not a performance thing; it's that your program can pass around arbitraril…

For very tight code, like interrupt handler context, you usually avoid allocation at all (with some object caches to provide storage possibly), but yes. Metronome is all about partitioning run-time into static slice of GC/mutator ensuring that mutator code has predictable performance - it is slower than if mutator was running full-tilt, but it means that unless you manage to horribly exceed GC performance in collecti…

Yeah, that's what I thought about interrupt handlers. (Also if you're allocating in your interrupt handler, your background thread can't allocate without either disabling interrupts or using some kind of lock-free synchronization.)

I still haven't read the Metronome paper.

I don't know if I'd go so far as to say GC is usually faster than manual memory management, even if we measure by throughput, but at least "often faster" is justifiable. I think usually you can find a way for manual memory management to be faster.

Re: Carp – A statically typed Lisp, without a GC, for real-time applications

#139

Post by jbjohns »

JoelMcCracken wrote: post #106
jbjohns wrote: post #76

Earlier quoted context omitted.

Why would immutability guarantee no cycles? Here is a line of valid haskell: star e = let (sp, a) = (Split a e, atom sp) in sp EDIT: I guess I should probably explain it: star is a function that takes an expression "e" and returns the value "sp" which is "Split a e" where "a" is the results of calling the "atom" function on "sp". This is creating a representation of a regex star operator. Note that the tuple defined…

I mean generally tying the knot is a useful technique, but I think these scenarios all require/exploit non-strict, which is in itself not really immutable in the sense most people use it. But yes, such code is often useful so that e.g. a parent xml node can refer to its childen nodes while also children nodes can refer to their parents. Anyway, I'm not sure about this, but I think you can't have circular data structu…

I'm fairly certain I've done similar things in Ocaml (in fact, I think it's where I learned this technique).
Post reply on HN