12 ms·

You say > but it was a false dichotomy: We can have memory safety without garbage collection. but then say > Automatic reference counting (ARC henceforth).

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/
- tempguy9999 7y ago
  > This isn't required in the read-only case which is why I carefully used the word Naive, however I had little time to expand on it so I can't blame anyone for overlooking that. > If you're only borrowing the value... Then you give examples of manually offloading memory management to the programmer. It should be done, and I believe the book I reference covers it (can't find it now, sorry), but definitely not by the programmer else it's not automatic GC. > ARC is usually atomic reference counting. That won't make any necessary inter-core or inter-socket coherency traffic disappear. > Any heap allocations [...] is likely to cause memory fragmentation. My memory was that refcounting was particularly bad but feel free to disregard that as I can't justify it. I may well be wrong. > This is a "can submarines swim" type of question and is completely uninteresting (imo). eh? Puzzled... > it doesn't. thanks, will check.
viraptor 7y ago
> Naive ARC is AFAIK very expensive as it causes a lot of updates It also means you can't really rely on CoW after fork(). After a while your whole heap will be duplicated in every process because of the RC updates.
- fnord123 7y ago
  That's a nice point. yikes.
- geocar 7y ago
  A simple trick gets you around this: Don't use your system malloc() but instead map a tempfile (or a memfd) with MAP_SHARED and use the STM primitives to update your references. If you combine this trick with __attribute__((address_space(256))) your "pointers" are also the offsets in the tempfile. Or don't: Maybe you want two heaps. fork() gives you the option!
- simonask 7y ago
  Lots of things that people do don't work after `fork()`, though, to the point where `fork()` has become largely irrelevant in new code. For example, threads are not generally compatible. You can also easily run into issues with open files, file locks, etc. Of course, your point might still be relevant in "legacy" environments with poor threading support anyway. I would argue that those are gradually going away, as even interpreted languages without exposed threading support are increasingly using threads or adopting threads to accommodate performance needs.
  - viraptor 7y ago
    This is not legacy. Any application in Ruby, Python, Perl, ... is affected. Majority of the backends of current web have the issue of duplicated heap in all the workers. It's made slightly better by Python introducing gc.freeze in 3.7 (https://docs.python.org/3/library/gc.html#gc.freeze https://docs.python.org/3/library/gc.html#gc.freeze) and Ruby doing something similar soon, but not great.
- deleted 7y ago
  [deleted]
stouset 7y ago
> Naïve ARC is very expensive… So is/was garbage collection, and we’ve spent thirty years trying to squeeze every possible bit of performance out of it. Maybe it’s time to look at other approaches.
- pjmlp 7y ago
  Even more so from reference counting, given that it was the very first kind of garbage collection algorithms.
  - geocar 7y ago
    I don't think that's true. Garbage collection (to my knowledge) was invented by McCarthy back in the late 1950s[1] in the following three paragraphs of his paper "Recursive Functions of Symbolic Expressions and Their Computation by Machine": Nothing happens until the program runs out of free storage. When a free register is wanted, and there is none left on the free-storage list, a reclamation cycle starts. First, the program finds all registers accessible from the base registers and makes their signs negative. This is accomplished by starting from each of the base registers and changing the sign of every register that can be reached from it by a car − cdr chain. If the program encounters a register in this process which already has a negative sign, it assumes that this register has already been reached. After all of the accessible registers have had their signs changed, the program goes through the area of memory reserved for the storage of list structures and puts all the registers whose signs were not changed in the previous step back on the free-storage list, and makes the signs of the accessible registers positive again. That's mark/sweep! He adds as a footnote "We already called this process ``garbage collection'', but I guess I chickened out of using it in the paper--or else the Research Laboratory of Electronics grammar ladies wouldn't let me." but doesn't explain where the term came from. I suppose it's possible he didn't invent it, but I've never seen anything on that and I think most of the existing strategies used for memory allocation at the time were very explicit -- FORTRAN didn't even have ALLOCATE yet! Do you have a reference for that? [1]: http://www-formal.stanford.edu/jmc/recursive/node4.html http://www-formal.stanford.edu/jmc/recursive/node4.html

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/

tempguy9999 7y ago
> This isn't required in the read-only case which is why I carefully used the word Naive, however I had little time to expand on it so I can't blame anyone for overlooking that. > If you're only borrowing the value... Then you give examples of manually offloading memory management to the programmer. It should be done, and I believe the book I reference covers it (can't find it now, sorry), but definitely not by the programmer else it's not automatic GC. > ARC is usually atomic reference counting. That won't make any necessary inter-core or inter-socket coherency traffic disappear. > Any heap allocations [...] is likely to cause memory fragmentation. My memory was that refcounting was particularly bad but feel free to disregard that as I can't justify it. I may well be wrong. > This is a "can submarines swim" type of question and is completely uninteresting (imo). eh? Puzzled... > it doesn't. thanks, will check.

viraptor 7y ago

> Naive ARC is AFAIK very expensive as it causes a lot of updates It also means you can't really rely on CoW after fork(). After a while your whole heap will be duplicated in every process because of the RC updates.

fnord123 7y ago
That's a nice point. yikes.
geocar 7y ago
A simple trick gets you around this: Don't use your system malloc() but instead map a tempfile (or a memfd) with MAP_SHARED and use the STM primitives to update your references. If you combine this trick with __attribute__((address_space(256))) your "pointers" are also the offsets in the tempfile. Or don't: Maybe you want two heaps. fork() gives you the option!
simonask 7y ago
Lots of things that people do don't work after `fork()`, though, to the point where `fork()` has become largely irrelevant in new code. For example, threads are not generally compatible. You can also easily run into issues with open files, file locks, etc. Of course, your point might still be relevant in "legacy" environments with poor threading support anyway. I would argue that those are gradually going away, as even interpreted languages without exposed threading support are increasingly using threads or adopting threads to accommodate performance needs.
- viraptor 7y ago
  This is not legacy. Any application in Ruby, Python, Perl, ... is affected. Majority of the backends of current web have the issue of duplicated heap in all the workers. It's made slightly better by Python introducing gc.freeze in 3.7 (https://docs.python.org/3/library/gc.html#gc.freeze https://docs.python.org/3/library/gc.html#gc.freeze) and Ruby doing something similar soon, but not great.
deleted 7y ago
[deleted]

stouset 7y ago

> Naïve ARC is very expensive… So is/was garbage collection, and we’ve spent thirty years trying to squeeze every possible bit of performance out of it. Maybe it’s time to look at other approaches.

pjmlp 7y ago
Even more so from reference counting, given that it was the very first kind of garbage collection algorithms.
- geocar 7y ago
  I don't think that's true. Garbage collection (to my knowledge) was invented by McCarthy back in the late 1950s[1] in the following three paragraphs of his paper "Recursive Functions of Symbolic Expressions and Their Computation by Machine": Nothing happens until the program runs out of free storage. When a free register is wanted, and there is none left on the free-storage list, a reclamation cycle starts. First, the program finds all registers accessible from the base registers and makes their signs negative. This is accomplished by starting from each of the base registers and changing the sign of every register that can be reached from it by a car − cdr chain. If the program encounters a register in this process which already has a negative sign, it assumes that this register has already been reached. After all of the accessible registers have had their signs changed, the program goes through the area of memory reserved for the storage of list structures and puts all the registers whose signs were not changed in the previous step back on the free-storage list, and makes the signs of the accessible registers positive again. That's mark/sweep! He adds as a footnote "We already called this process ``garbage collection'', but I guess I chickened out of using it in the paper--or else the Research Laboratory of Electronics grammar ladies wouldn't let me." but doesn't explain where the term came from. I suppose it's possible he didn't invent it, but I've never seen anything on that and I think most of the existing strategies used for memory allocation at the time were very explicit -- FORTRAN didn't even have ALLOCATE yet! Do you have a reference for that? [1]: http://www-formal.stanford.edu/jmc/recursive/node4.html http://www-formal.stanford.edu/jmc/recursive/node4.html