9 ms·

> But all of these are much cheaper than developer labour and reputation damage caused by leaky/crashy software. And that's why so much effort has gone into ma

by geocar 7y ago

> But all of these are much cheaper than developer labour and reputation damage caused by leaky/crashy software. And that's why so much effort has gone into making it fast and low latency, but it was a false dichotomy: We can have memory safety without garbage collection. - Automatic reference counting: Most people know about Objective-C's efforts in this space, but it's admittedly less automatic than programmers would like so perhaps it doesn't get enough attention. And yet it should, since q/kdb+ uses reference counting exclusively, and it holds top performance numbers on a large number of data and messaging problems. - Linear lisp[1] asked functions to fully consume their arguments making (cons x y) basically a no-op. Again, no garbage collection, and no fragmentation (at least as long as all objects are cons), and yet no matter how promising this path looked, garbage collection got much more attention. - Rust's borrow checker/tracker makes ownership explicit; somewhat of a middle-ground between the two... There's other scattered efforts in this space, and I don't know about all of them but for more on "everything we know about languages is wrong", also consider that Perl5 uses plain old reference counting, executes the AST directly, and still outperforms python for data and IO[2]! I think the thing to take away is that memory management has to be automatically managed for developer sanity, not that garbage collection is the way to do it. [1]: http://home.pipeline.com/~hbaker1/LinearLisp.html http://home.pipeline.com/~hbaker1/LinearLisp.html [2]: The asyncio stuff in Python looks really promising though...

tempguy9999 7y ago
You say > but it was a false dichotomy: We can have memory safety without garbage collection. but then say > Automatic reference counting (ARC henceforth). Naive ARC is AFAIK very expensive as it causes a lot of updates at each pointer 'take' even if it's a read only (chasing pointers), trashing caches. Poss. even worse if multithreading is used as a memory barrier may have to be issued. Also it does not collect cycles. Also I've read it causes memory fragmentation (take that with a pinch of salt, that's from my memory!). ARC has some advantages but it has some real costs. Also and even more, if ARC is what you think it is, how is it not an implementation of GC? > Perl5 uses plain old reference counting, executes the AST directly, and still outperforms python for data and IO[2]! Ok... 1) outperforming python is not a high bar. 2) IO is usually handed off to the underlying OS so talking about IO performance is probably misleading. 3) Python now has a fallback non-ARC GC to pick up cycles. 4) GC in python is IIRC an implementation detail, not language-mandated. Finally, if it outperforms it, please provide a reference. I'll check out linear lisp if I can find the time.
- geocar 7y ago
  > Naive ARC is AFAIK very expensive as it causes a lot of updates at each pointer... Yes, and I think that's why people shy away from it. Language design can help a lot though: Array languages use reference counting almost exclusively because nesting objects is uncommon. That means no pointers to chase the vast majority of the time. > if ARC is what you think it is, how is it not an implementation of GC? Garbage Collection involves crawling live objects from roots to determine what's still alive. If you're not doing that, you might still be doing automatic memory management, but you're not doing GC. There's tricks (gardens, barriers, treadmills, colouring, etc) to do less work or less work at a time, but it remains predicated on the assumption is that you have more garbage than you have live objects so you're doing less work by only crawling the live objects. If this is true, then GC should be a win, but it's not true an awful lot of the time, which is why manual memory management always beats GC for performance (latency and throughput). [†]: notwithstanding your earlier point about pointer chasing... > I'll check out linear lisp if I can find the time. I can recommend everything Baker has written on this subject: it's all gold.
  - blattimwind 7y ago
    > Garbage Collection involves crawling live objects from roots to determine what's still alive. > If you're not doing that, you might still be doing automatic memory management, but you're not doing GC. Whether GC and automatic memory management are [significantly] different terms depends on who you ask, I don't think there is a consensus on that. In many cases however people tend to say GC as shorthand for tracing GC. I think in many cases we see ARC is "good enough", and in a JIT scenario you could remove many RC changes by effectively collapsing/merging scopes. OTOH it is quite clear that for the same workload tracing inevitably performs better.
- fnord123 7y ago
  >it causes a lot of updates at each pointer 'take' even if it's a read only This isn't required in the read-only case. If you're only borrowing the value, for example, taking a const& in C++ and not holding onto it, then you can cast to the underlying type and use the reference. In Rust you can also just borrow: https://play.integer32.com/?version=stable&mode=debug&edition=2018&gist=f3fc8391316a156065943e35584cdd59 https://play.integer32.com/?version=stable&mode=debug&editio... >trashing caches ARC is usually atomic reference counting. Indeed that will trash caches because it must invalidate the cache line where the reference count lives in other cores whenever it's updated. RC without atomicity won't invalidate cache lines on other cpus. FWIW, GCC has an extension to shared_ptr that doesn't use atomic reference counting: https://gcc.gnu.org/onlinedocs/libstdc++/manual/memory.html#shared_ptr.policy https://gcc.gnu.org/onlinedocs/libstdc++/manual/memory.html#... > Also I've read it causes memory fragmentation Any heap allocations not bound to an arena and not part of a compacting garbage collector is likely to cause memory fragmentation. Stack allocations for example are implicitly compacted. >Also and even more, if ARC is what you think it is, how is it not an implementation of GC? This is a "can submarines swim" type of question and is completely uninteresting (imo). >Finally, if [perl5] outperforms [python], please provide a reference. It doesn't. Not by a long shot. Reference: https://bitbucket.org/ewanhiggs/csv-game/ https://bitbucket.org/ewanhiggs/csv-game/
barrkel 7y ago
Reference counting is garbage collection. It's part of the mix of potential strategies for automatic collection of memory. As is static analysis of data flow, fwiw.
- geocar 7y ago
  In taxonomy, I say we have "automatic memory management" when we have some kind of `malloc()` type device and no need to `free()` it. Garbage collection is about visiting live objects to figure out what's alive and ignoring the dead stuff. Every theory about why GC can work (or be useful) is predicated on the idea that there is more garbage than live objects so you're touching less stuff. If all you do is mark/sweep, you're visiting the garbage as well, so GC research has led neatly into moving collectors (which don't ever touch the garbage). That's a win, and that's why GC is worth study. There are other kinds of "automatic memory management" though: reference counting, arena allocators (at a stretch), and object memory (I've only seen this on mainframes), and they're all worth some attention.
  - barrkel 7y ago
    > Garbage collection is about visiting live objects to figure out what's alive and ignoring the dead stuff That's a description of tracing GC, not a definition of GC. GC is whatever technology that enables what you've called automatic memory management: a kind of illusion that there is infinite memory, from the programmer's perspective. That might involve some mix of reference counting (Python is probably the biggest example), tracing (what you seem to think is all of GC), data flow analysis (e.g. escape analysis in some Java GC / JIT integration), etc.
    - seanmcdirmid 7y ago
      GC has always meant tracing GC while reference counting (ever since McCarthy invented it) was considered another form of automatic memory management (like using arenas, doing escape analysis, etc...). Only recently in hacker news have they become all merged into the same word, for some reason.
fao_ 7y ago
I think you mean "Automatic Garbage Collection", rather than just "Garbage Collection". The latter is exactly what you do in C when you use `free()`, the former is an automated system that does `free()` on your behalf at runtime. Indeed, the fact that you consider Rust's borrow checker to be part of the non-gc methods of handling memory, make it clear that you do indeed recognise this distinction, even thought it is merely implicit. For the record, Automatic Reference Counting can't collect self-referential objects. And is also considered a method of automatic garbage collection. I haven't heard of any research on ARC being done statically, if you have that it would indeed be interesting. Linear Lisp indeed looks extremely promising, I don't remember finding any code examples when I looked it up, it seems to be something that's languished in the theoretical department. HBaker has a series of really interesting papers, by the way, it's worth just going through his website :) There are a lot of nuggets of gold there. It might also be worth for you to read up on the Mercury compiler -- if you haven't already -- which boasts compile-time memory allocation: https://mercurylang.org/documentation/papers.html#mazur-thesis https://mercurylang.org/documentation/papers.html#mazur-thes...
- codetrotter 7y ago
  > I think you mean "Automatic Garbage Collection", rather than just "Garbage Collection". The latter is exactly what you do in C when you use `free()`, the former is an automated system that does `free()` on your behalf at runtime. To me, the difference between garbage collection and other memory management systems is that gc scans memory looking for memory that can be reclaimed. I don’t consider free() to be garbage collection. free() is the final step you do in any memory management scheme, it’s not a specific technique of memory management.
  - rickbutton 7y ago
    Your definition of garbage collector excludes reference counting, which does not require scanning memory. Reference counting is a form of garbage collection. The type of garbage collection you are referring to is the sub-type of "tracing" garbage collection. However, I agree, "free()" is not garbage collection, but rather a form of memory management, of which garbage collection is a subset, and manual (free) is another.
eru 7y ago
Compare the "Unified Theory of Garbage Collection" (https://www.cs.virginia.edu/~cs415/reading/bacon-garbage.pdf https://www.cs.virginia.edu/~cs415/reading/bacon-garbage.pdf). Reference counting is a variant of garbage collection. But yes, you can take ideas from their to make your garbage collection better. Linear/uniqueness typing is interesting. Clean is another language that uses something like it, and you can implement these ideas in Haskell as well. Though in practice you want affine typing, not linear typing. (Basically, you want to be able to drop arguments without explicitly having to consume them.) The important bit about linear typing / affine typing is that you use your arguments at most once, not that you have to use them at least once. That's how you can model mutation in a pure FP way, too. Not just GC.
cm2187 7y ago
Garbage collection also performs other performance improving functions like memory compaction.
tomp 7y ago
This comment is just bad and misinformed all over. (1) Automatic Reference Counting doesn't work; its equivalent in interpreted languages is, well, reference counting, which can be optimized quite a lot (though has some issues with multithreading), but cannot collect cycles. (2) therefore, if you want reference counting, you have to either also have GC (for cycles), or program carefully to avoid creating cycles (which is then only marginally better than C++) (3) your comment on Python vs Perl5 is just nonsense, Python uses reference counting as well (along with the occasional GC to collect cycles) (4) linear / uniqueness types (not exactly the same, but both can be used to ensure safe memory management) impose significant mental overhead on programmers as they prohibit many common patterns (5) Rust features a lot of "cheating" - pointers that allow mutation from multiple threads, reference-counted pointers, etc. - so obviously just ownership&borrowing isn't good enough conclusion: you can't have your cake and eat it too (at least according to current cutting edge research and implementations) - you either have GC or you have to be very careful/restricted when writing code
- StreamBright 7y ago
  It is weird, I do not feel restricted when I write non-GC code. Btw. you still need to pay attention with GCd languages no to leak references that cannot be GCd. Java has this sort of problems. Rust made it easy and simple to deal with memory in a non-malloc level while not having GC. Erlang on the other hand has a VM that makes GC much faster than in other languages. I can live with that because if you do it right it does not impact end user latency. For me both Rust and Erlang gives the cake + eat it feeling.
  - jerf 7y ago
    "I can live with that because if you do it right it does not impact end user latency." The vast majority of GC use does not impact end user latency. Thinking otherwise is either the availability heuristic at work, or you work in AAA videogames or another ultra-high-real-time-performance industry and don't realize you're not in the center of programming work, you're on an extreme. (A perfectly valid and sizeable extreme.) This may also be why you don't feel restricted; if you happen to work in any of the many places where a tree of references is adequate, you'll find Rust-style management to be a treat. If you work pervasively with graph structures in the core of your program, though, the experience can change. Pervasively-graph-type-structures are generally just a question of how you want your automated garbage collection to work, because I'm pretty sure getting the manual management correct otherwise is effectively impossible without an algorithm that's going to look a lot like a GC. That said, despite my disagreement, I also disagree with the people who, as of this writing, have downvoted your comment into grey. I feel like I've been seeing a burst of "downvote as disagreement" in the past couple of weeks.
mcguire 7y ago
Reference counting is garbage collection, and it's not a very good algorithm.
ernst_klim 7y ago
> Automatic reference counting > Rust's borrow checker/tracker makes ownership explicit So no compaction, no pointer-bump allocations? You have to reimplement these manually, aka reinvent GC while having ref-counter/region-based-mm overhead?

by geocar 7y ago

tempguy9999 7y ago

You say > but it was a false dichotomy: We can have memory safety without garbage collection. but then say > Automatic reference counting (ARC henceforth). Naive ARC is AFAIK very expensive as it causes a lot of updates at each pointer 'take' even if it's a read only (chasing pointers), trashing caches. Poss. even worse if multithreading is used as a memory barrier may have to be issued. Also it does not collect cycles. Also I've read it causes memory fragmentation (take that with a pinch of salt, that's from my memory!). ARC has some advantages but it has some real costs. Also and even more, if ARC is what you think it is, how is it not an implementation of GC? > Perl5 uses plain old reference counting, executes the AST directly, and still outperforms python for data and IO[2]! Ok... 1) outperforming python is not a high bar. 2) IO is usually handed off to the underlying OS so talking about IO performance is probably misleading. 3) Python now has a fallback non-ARC GC to pick up cycles. 4) GC in python is IIRC an implementation detail, not language-mandated. Finally, if it outperforms it, please provide a reference. I'll check out linear lisp if I can find the time.

geocar 7y ago
> Naive ARC is AFAIK very expensive as it causes a lot of updates at each pointer... Yes, and I think that's why people shy away from it. Language design can help a lot though: Array languages use reference counting almost exclusively because nesting objects is uncommon. That means no pointers to chase the vast majority of the time. > if ARC is what you think it is, how is it not an implementation of GC? Garbage Collection involves crawling live objects from roots to determine what's still alive. If you're not doing that, you might still be doing automatic memory management, but you're not doing GC. There's tricks (gardens, barriers, treadmills, colouring, etc) to do less work or less work at a time, but it remains predicated on the assumption is that you have more garbage than you have live objects so you're doing less work by only crawling the live objects. If this is true, then GC should be a win, but it's not true an awful lot of the time, which is why manual memory management always beats GC for performance (latency and throughput). [†]: notwithstanding your earlier point about pointer chasing... > I'll check out linear lisp if I can find the time. I can recommend everything Baker has written on this subject: it's all gold.
- blattimwind 7y ago
  > Garbage Collection involves crawling live objects from roots to determine what's still alive. > If you're not doing that, you might still be doing automatic memory management, but you're not doing GC. Whether GC and automatic memory management are [significantly] different terms depends on who you ask, I don't think there is a consensus on that. In many cases however people tend to say GC as shorthand for tracing GC. I think in many cases we see ARC is "good enough", and in a JIT scenario you could remove many RC changes by effectively collapsing/merging scopes. OTOH it is quite clear that for the same workload tracing inevitably performs better.
fnord123 7y ago
>it causes a lot of updates at each pointer 'take' even if it's a read only This isn't required in the read-only case. If you're only borrowing the value, for example, taking a const& in C++ and not holding onto it, then you can cast to the underlying type and use the reference. In Rust you can also just borrow: https://play.integer32.com/?version=stable&mode=debug&edition=2018&gist=f3fc8391316a156065943e35584cdd59 https://play.integer32.com/?version=stable&mode=debug&editio... >trashing caches ARC is usually atomic reference counting. Indeed that will trash caches because it must invalidate the cache line where the reference count lives in other cores whenever it's updated. RC without atomicity won't invalidate cache lines on other cpus. FWIW, GCC has an extension to shared_ptr that doesn't use atomic reference counting: https://gcc.gnu.org/onlinedocs/libstdc++/manual/memory.html#shared_ptr.policy https://gcc.gnu.org/onlinedocs/libstdc++/manual/memory.html#... > Also I've read it causes memory fragmentation Any heap allocations not bound to an arena and not part of a compacting garbage collector is likely to cause memory fragmentation. Stack allocations for example are implicitly compacted. >Also and even more, if ARC is what you think it is, how is it not an implementation of GC? This is a "can submarines swim" type of question and is completely uninteresting (imo). >Finally, if [perl5] outperforms [python], please provide a reference. It doesn't. Not by a long shot. Reference: https://bitbucket.org/ewanhiggs/csv-game/ https://bitbucket.org/ewanhiggs/csv-game/

barrkel 7y ago

Reference counting is garbage collection. It's part of the mix of potential strategies for automatic collection of memory. As is static analysis of data flow, fwiw.

geocar 7y ago
In taxonomy, I say we have "automatic memory management" when we have some kind of `malloc()` type device and no need to `free()` it. Garbage collection is about visiting live objects to figure out what's alive and ignoring the dead stuff. Every theory about why GC can work (or be useful) is predicated on the idea that there is more garbage than live objects so you're touching less stuff. If all you do is mark/sweep, you're visiting the garbage as well, so GC research has led neatly into moving collectors (which don't ever touch the garbage). That's a win, and that's why GC is worth study. There are other kinds of "automatic memory management" though: reference counting, arena allocators (at a stretch), and object memory (I've only seen this on mainframes), and they're all worth some attention.
- barrkel 7y ago
  > Garbage collection is about visiting live objects to figure out what's alive and ignoring the dead stuff That's a description of tracing GC, not a definition of GC. GC is whatever technology that enables what you've called automatic memory management: a kind of illusion that there is infinite memory, from the programmer's perspective. That might involve some mix of reference counting (Python is probably the biggest example), tracing (what you seem to think is all of GC), data flow analysis (e.g. escape analysis in some Java GC / JIT integration), etc.
  - seanmcdirmid 7y ago
    GC has always meant tracing GC while reference counting (ever since McCarthy invented it) was considered another form of automatic memory management (like using arenas, doing escape analysis, etc...). Only recently in hacker news have they become all merged into the same word, for some reason.

fao_ 7y ago

I think you mean "Automatic Garbage Collection", rather than just "Garbage Collection". The latter is exactly what you do in C when you use `free()`, the former is an automated system that does `free()` on your behalf at runtime. Indeed, the fact that you consider Rust's borrow checker to be part of the non-gc methods of handling memory, make it clear that you do indeed recognise this distinction, even thought it is merely implicit. For the record, Automatic Reference Counting can't collect self-referential objects. And is also considered a method of automatic garbage collection. I haven't heard of any research on ARC being done statically, if you have that it would indeed be interesting. Linear Lisp indeed looks extremely promising, I don't remember finding any code examples when I looked it up, it seems to be something that's languished in the theoretical department. HBaker has a series of really interesting papers, by the way, it's worth just going through his website :) There are a lot of nuggets of gold there. It might also be worth for you to read up on the Mercury compiler -- if you haven't already -- which boasts compile-time memory allocation: https://mercurylang.org/documentation/papers.html#mazur-thesis https://mercurylang.org/documentation/papers.html#mazur-thes...

codetrotter 7y ago
> I think you mean "Automatic Garbage Collection", rather than just "Garbage Collection". The latter is exactly what you do in C when you use `free()`, the former is an automated system that does `free()` on your behalf at runtime. To me, the difference between garbage collection and other memory management systems is that gc scans memory looking for memory that can be reclaimed. I don’t consider free() to be garbage collection. free() is the final step you do in any memory management scheme, it’s not a specific technique of memory management.
- rickbutton 7y ago
  Your definition of garbage collector excludes reference counting, which does not require scanning memory. Reference counting is a form of garbage collection. The type of garbage collection you are referring to is the sub-type of "tracing" garbage collection. However, I agree, "free()" is not garbage collection, but rather a form of memory management, of which garbage collection is a subset, and manual (free) is another.

eru 7y ago

Compare the "Unified Theory of Garbage Collection" (https://www.cs.virginia.edu/~cs415/reading/bacon-garbage.pdf https://www.cs.virginia.edu/~cs415/reading/bacon-garbage.pdf). Reference counting is a variant of garbage collection. But yes, you can take ideas from their to make your garbage collection better. Linear/uniqueness typing is interesting. Clean is another language that uses something like it, and you can implement these ideas in Haskell as well. Though in practice you want affine typing, not linear typing. (Basically, you want to be able to drop arguments without explicitly having to consume them.) The important bit about linear typing / affine typing is that you use your arguments at most once, not that you have to use them at least once. That's how you can model mutation in a pure FP way, too. Not just GC.

cm2187 7y ago

Garbage collection also performs other performance improving functions like memory compaction.

tomp 7y ago

This comment is just bad and misinformed all over. (1) Automatic Reference Counting doesn't work; its equivalent in interpreted languages is, well, reference counting, which can be optimized quite a lot (though has some issues with multithreading), but cannot collect cycles. (2) therefore, if you want reference counting, you have to either also have GC (for cycles), or program carefully to avoid creating cycles (which is then only marginally better than C++) (3) your comment on Python vs Perl5 is just nonsense, Python uses reference counting as well (along with the occasional GC to collect cycles) (4) linear / uniqueness types (not exactly the same, but both can be used to ensure safe memory management) impose significant mental overhead on programmers as they prohibit many common patterns (5) Rust features a lot of "cheating" - pointers that allow mutation from multiple threads, reference-counted pointers, etc. - so obviously just ownership&borrowing isn't good enough conclusion: you can't have your cake and eat it too (at least according to current cutting edge research and implementations) - you either have GC or you have to be very careful/restricted when writing code

StreamBright 7y ago
It is weird, I do not feel restricted when I write non-GC code. Btw. you still need to pay attention with GCd languages no to leak references that cannot be GCd. Java has this sort of problems. Rust made it easy and simple to deal with memory in a non-malloc level while not having GC. Erlang on the other hand has a VM that makes GC much faster than in other languages. I can live with that because if you do it right it does not impact end user latency. For me both Rust and Erlang gives the cake + eat it feeling.
- jerf 7y ago
  "I can live with that because if you do it right it does not impact end user latency." The vast majority of GC use does not impact end user latency. Thinking otherwise is either the availability heuristic at work, or you work in AAA videogames or another ultra-high-real-time-performance industry and don't realize you're not in the center of programming work, you're on an extreme. (A perfectly valid and sizeable extreme.) This may also be why you don't feel restricted; if you happen to work in any of the many places where a tree of references is adequate, you'll find Rust-style management to be a treat. If you work pervasively with graph structures in the core of your program, though, the experience can change. Pervasively-graph-type-structures are generally just a question of how you want your automated garbage collection to work, because I'm pretty sure getting the manual management correct otherwise is effectively impossible without an algorithm that's going to look a lot like a GC. That said, despite my disagreement, I also disagree with the people who, as of this writing, have downvoted your comment into grey. I feel like I've been seeing a burst of "downvote as disagreement" in the past couple of weeks.

mcguire 7y ago

Reference counting is garbage collection, and it's not a very good algorithm.

ernst_klim 7y ago

> Automatic reference counting > Rust's borrow checker/tracker makes ownership explicit So no compaction, no pointer-bump allocations? You have to reimplement these manually, aka reinvent GC while having ref-counter/region-based-mm overhead?