Hacker News Reader

Comment by geocar | Hacker News Reader

> 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

[2]: The asyncio stuff in Python looks really promising though...

View on HN

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

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.

"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.

"Downvote as disagreement" is such a pervasive pattern that I Find myself doing it automatically even when I know that's not what downvote is "supposed" to be for. I suspect it's because I'm more likely to view posts that I disagree with as being poorly thought-out.

This even extends to platforms where downvoting is not a thing - witness 4chan's struggles with "sage is not a downvote" ("sage" being a function which allowed you to reply to a thread without bumping it to the top and extending its lifespan - again, intended to mark a thread as low qualit) until they finally gave up and made saging invisible.

Given how thoroughly inescapable downvoting-to-disagree seems, I wonder if it might not be better to just declare defeat, allow downvotes and upvotes to mean nothing beyond a signal of protest or agreement, and have a separate "this comment is low quality / this comment is high quality" buttons.

PG long ago said that it is ok to use downvotes (in part) to signal disagreement.

>It is weird, I do not feel restricted when I write non-GC code.

Some people don't feel C has any safety issues either -- perhaps they think all others are idiots and their code is mistake proof because they do it right.

> still need to pay attention with GCd languages no to leak references that cannot be GCd. Java has this sort of problems.

Unless you're doing weird things with class loaders, this is a non-issue.

> Erlang on the other hand has a VM that makes GC much faster than in other languages

What makes Erlang's VM make GC faster than other languages?

That's a very loaded question.

I don't think it's easy to point to one thing Erlang is doing and say that is why it's faster, partly because I think the way Erlang programmers are encouraged to write their programs also has an effect; The language itself may have a greater effect on its GC performance than the GC implementation itself.

As an example: In Erlang, we have function calls like F(X) but we also have message sends like F!X. Message sends get one type of memory treatment, while function calls get another one. The lifetime of objects you send via messaging is going to be different, and yet Java only has function(method) calls, so there's no way to hint this to Java. Maybe this information can be recovered with static/dynamic analysis, but in Erlang we have syntax to tell the VM what's going to happen.

If you want to learn more about Erlang's internals, I can recommend Joe's original paper on the subject:

http://citeseerx.ist.psu.edu/viewdoc/summary;jsessionid=0397...

since it describes a lot of the design that went into Erlang early, and:

http://www.it.uu.se/research/publications/lic/2005-001/

which while long, quite in-depth describes many of the sub-optimisations that can be realised on top of it.

Thanks for the links. That being said, new developments in GCs on the JVM (like Shenandoah and ZGC) are yielding very impressive results. Things like < 1ms pause times for heaps in the TB range. No other free GC for any other language approaches this as far as I'm aware, including golang's which people claim is fast, but completely gets destroyed for even heaps in the GB range (I did some benchmarks).

You came in guns blazing and then covered yourself in embarrassment already in the first two points you made.

The thing you said doesn't work is in use on millions of devices, working just fine. Or maybe you'd like to be more precise than "work".

Avoiding cycles and thinking about ownership is not programming carefully, it's merely programming. Really, manual memory management is not rocket science folks, just error prone. And RAII is reliable to the point that anyone that is capable of writing software can wield it.

>Really, manual memory management is not rocket science folks, just error prone

Doesn't have to be rocket science to be a cognitive burden. And we want to eliminate "error prone" factors...

And we did eliminate them.

But no one can seriously claim that GC is a magic bullet, because it's only clearly winning against plain C.

Carefully designed, popular languages are choosing RAII and reference counting implementations and those are very competitive.

C++ and Objective C inherited C's memory model and thus don't have a good memory management option. Rust is explicitly a systems language, meaning stronger memory models are out of scope, and then inherited most of C++'s idioms.

Other than those, what popular languages are specifically choosing reference counting as a primary GC method?

Swift.

Which inherits its memory management from Objective C.

Swift requires reference counting for compatibility with Objective-C code.

Apple could have gone the .NET way (RCW) to interface with COM reference counting, but that naturally would complicate the bindings to Objective-C runtime and existing libraries.

>Rust features a lot of "cheating" - pointers that allow mutation from multiple threads

You're confounding GC and synchronization of multi-threaded access here. What rust does with things like Arc other languages will need some other synchronization primitive to enable. Their GC or manual memory management does not guarantee the multi-threaded semantics. That's one of the advantages of the rust memory model, some patterns become multi-threaded without extra primitives (read-only borrows) and all of the primitives are compile-time checked for correctness.

>reference-counted pointers, etc. - so obviously just ownership&borrowing isn't good enough

In practice ownership and borrowing gets you a long way. I've only had to use a reference counted primitive (Arc) when that was the exactly correct semantics. I had a cache and both the caller and the original owner could drop the value first based on external input. No other static decision can be made and the ergonomics of writing that are very good. Rust seems already quite a bit better than having to be "very careful/restricted when writing code".

No, Rust is conflating memory safery and multithreading safety.

JVM state-of-the-art GC guarantees multithreaded memory safety.

AFAIK many wait-free data structures are pretty much impossible without a GC.

You start your response with "No" but don't actually argue against anything I've said.

> Rust is conflating memory safery and multithreading safety.

Rust doesn't conflate anything. It just gets some multi-threading safety for free as a result of its memory model. And then gets quite a few other multi-threading safety characteristics that no other mainstream language has from the type system. That several features in the language work together well is just a sign of good design.

> JVM state-of-the-art GC guarantees multithreaded memory safety.

This is where you're mixing the two unrelated concepts. Garbage collection does nothing for multi-threading safety. While the object is live and two threads hold a reference to it you need to synchronize access somehow. GC can't do anything about that.

> AFAIK many wait-free data structures are pretty much impossible without a GC.

This is unrelated to the previous points I made but isn't true either:

https://aturon.github.io/blog/2015/08/27/epoch/

By "conflating" I mean that Rust's memory management technology provides just one kind of multi-threading safety (i.e. "multiple readers/single-writer" model), but to implement other kinds of multi-threading-safe algorithms/data structures, you need to transcend beyond ownership+borrowing.

I think "epoch-based memory reclamation" (which Linux kernel also uses IIRC) is still a (primitive / limited / contained) form of GC. For those that aren't familiar with it, a quote from the article @pedrocr posted:

> The basic idea is to stash away nodes that have been unlinked from the data structure (the first source of reachability) until they can be safely deleted. Before we can delete a stashed node, we need to know that all threads that were accessing the data structure at the time have finished the operation they were performing.

So basically, the runtime needs to keep track of allocated objects until it's certain there are no more references to them... sounds like GC (the difference between this and a real GC is that (1) you know there's no cross-references between the nodes, so you don't need to mark&sweep but just need to keep track of the epoch, and (2) the nature of lock-free data structures is such that threads will move to the next epoch fairly soon (unless they infinite-loop)).

> By "conflating" I mean that Rust's memory management technology provides just one kind of multi-threading safety (i.e. "multiple readers/single-writer" model), but to implement other kinds of multi-threading-safe algorithms/data structures, you need to transcend beyond ownership+borrowing.

That's not "conflating" anything. You're just saying that "to do other things you need other stuff". Sure, to implement multi-threading you also need locks and semaphores and atomic variables sometimes. Rust provides all of those. There's nothing specific to GC vs non-GC there.

> So basically, the runtime needs to keep track of allocated objects until it's certain there are no more references to them... sounds like GC

Reference counting is not GC by most definitions. And if you want to define it like that Rust already has it.

> (the difference between this and a real GC is that (1) you know there's no cross-references between the nodes, so you don't need to mark&sweep but just need to keep track of the epoch, and (2) the nature of lock-free data structures is such that threads will move to the next epoch fairly soon (unless they infinite-loop)).

So the difference between this and GC is that it's nothing like GC... If reference counting, RCU, etc are all GC then there's nothing to discuss as it turns out languages like Rust have all the GC you need.

I agree, the model of lock-free data structures is pretty much perfect for reference counting (no cycles, shallow reference tree... just needs to be thread-safe). I wonder then why epoch-based approaches are used, which (sound like they) are more difficult / tricky to implement... I honestly have no idea. The only thing that comes to mind is that they seem to require another atomic primitive (atomic increment, otherwise lock-free data structures only require compare-and-swap), which might not be available on all platforms...

> AFAIK many wait-free data structures are pretty much impossible without a GC.

That makes no sense. You can implement a garbage collector in a manually managed program (or even just the specific parts that gain you the attributes required to accomplish something), so even if a GC made certain data structures easier, there's nothing to prevent their use in a manually managed language. The argument you're making is sort of like saying that certain things can only be accomplished in ain C or Java, and not in assembly.

More specifically to your actual assertion, anything a GC does for lock free data structures could be handled by a special routine or manually in a language where you handle memory manually.

> (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.

This is what weakrefs (or better data structures) are for. The Linux kernel uses reference counting incredibly effectively for almost every structure. I think that pretty much discounts any argument that reference counting cannot work.

> (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

"unsafe" isn't cheating and isn't even related to whether garbage collection is a good idea or not. Yes, Rust's ownership and borrowing model doesn't cover all programs and hence "unsafe" is required -- but "unsafe" doesn't use a garbage collector so the existence of "unsafe" doesn't change that Rust works without one.

I think the poster to whom you're responding means things like Cell and/or RefCell, which allow mutation behind the scenes while still being safe.

Right, but I think their main complaint is that RefCell is implemented using "unsafe" -- hence my point about "unsafe".

It's API is not `unsafe` though. Otherwise, every safe API depends on some `unsafe` call down the call graph.

I think we're both in agreement, I was phrasing things in a manner which I thought would better reference how GP thinks of unsafe. Obviously the API itself is safe, but the "cheating" GP was referring to was the fact that Rust requires "unsafe" under the hood in order to implement some safe operations (because the memory model doesn't cover all cases). You and I agree that this isn't a problem.

The point with weakrefs, though, is that they still require developer intervention.

Also, you can use most memory management facilities in Rust (including reference counting) without `unsafe`.

Correct, leaks are considered "safe" -- it's premature deallocations that are considered unsafe.

Reference counting is a garbage collection algorithm. It just isn't a very good one compared to semi space because its runtime is the number of dead objects not live objects.

Refefence counting is barely classifiable as garbage collection. The runtime is O(1) because you free the object immediately when it dies, there's no stage where you start looping over dead objects.

Weakrefs require “careful programming” i.e. knowing which ref must be a weakref.

By “cheating” I don’t mean “unsafe” but all kinds of pointers that aren’t just unique or borrowed such as different reference-counted pointers, the existence and use of which demonstrates that ownership+borrowing isn’t a complete memory-management technique. You need reference counting, therefore you need GC or careful programming.

Hopefully we discover some technology that makes these needs go away, but not so far AFAIK.

> (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

Such as?

I've found that linear style is generally just good coding style. When I get caught up on something I can't express linearly, it generally means I was trying to plough through with a dodgy approach; stopping and thinking through would have resulted in better code even in a GCed language.

Please don't call names in arguments here. Your first sentence is clearly against the site guidelines, and was quite unnecessary.

https://news.ycombinator.com/newsguidelines.html

Sorry. I get emotional about programming languages...

Me too, as do many others.

(1/2): It most certainly does work: q/kdb is an interpreted language and doesn't have cycles. Being an array language, nesting is uncommon, so chasing pointers isn't an issue either.

(3): I didn't say otherwise Python doesn't also do reference counting. Python however does have a bytecode and a GC, and perl5 does not and executes the AST directly. And yes perl5 is faster for many problems[†]. I think it's quite common that people believe that GC and bytecode are a win, and this is a simple and accessible example where it is not true.

(4): More significant than what? q/kdb is implemented in this style, and it's a huge advantage (reducing bugs) having your library handle allocation/deallocation over having the caller do these things so I tend to do it as well. What exactly are you comparing it to? The mental load of figuring out what's causing pauses is quite high since it requires considering the entire program, but linear programming is very easy and it obviates a lot of need for other kinds of memory management techniques.

(5): Good enough for what? Why is mixing static analysis with runtime analysis "cheating"? What would be "fair" in your mind?

[†]: https://benchmarksgame-team.pages.debian.net/benchmarksgame/...

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.

> 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.

> 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.

>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&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#...

> 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/

> 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.

In regards to memory fragmentation, you probably think of GC with compaction. Not all GCs are like that, but that is a plus for GCs if use the heap a lot and need cache friendliness.

> 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.

That's a nice point. yikes.

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!

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.

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) and Ruby doing something similar soon, but not great.

> 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.

Even more so from reference counting, given that it was the very first kind of garbage collection algorithms.

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

Compare the "Unified Theory of Garbage Collection" (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.

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-thes...

> 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.

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.

It depends who you ask. In my point of view, "reference counting" is a strategy that has nothing inherently to do with memory management and can even be manual instead of automatic. GC as the name implies should involve a collector of sorts.

Plain old refcounting cannot resolve circular references, which are inevitably leaked. To avoid leaks, most refcounting garbage collectors have a heuristic to occasionally run traces to clear out the cruft.

With moving/compacting collectors, you never even call free(), and this is a huge advantage over a mark/sweep:

First mark touches all the live objects, then sweep touches all the objects that aren't live. You're touching every object every cycle. Yuck.

A moving collector touches all the live objects, but now they have new memory addresses. We never need to touch the old garbage at all! Most advanced GC techniques are around trying to revisit live objects less frequently, but they all have this basic theme.

Other memory management techniques explore the other side: Just touching the garbage. That's what happens when you malloc+free manually, or do (automatic) reference counting.

So the value-question restated is this: Is there more ham than spam?

If we have more garbage, then the ideal GC strategy wins. If we have more living objects (and few/no garbage) then literally anything else wins.

We do seem to have more garbage in atom languages like Java, Erlang, Python, and so on, so it makes sense that GC gets much more love than the other side of the fence, but I wonder often if we're missing a trick.

I think the most widely accepted definition for "garbage collection" is something which frees memory automatically, as opposed to manually freeing memory (or other memory management schemes). In fact, the second paragraph of Wikipedia's page on garbage collection[1] says that "Garbage collection is essentially the opposite of manual memory management, which requires the programmer to specify which objects to deallocate and return to the memory system".

[1]: https://en.wikipedia.org/wiki/Garbage_collection_(computer_s...

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.

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.

> 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.

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.

> Only recently in hacker news have they become all merged

This is demonstrably not true. The Garbage Collection book by Jones is the key text in this area, and it covers reference counting under that term. It was published in 1996, before Hacker News existed.

There is also Bacon's Unified Theory of Garbage Collection, 2004, which said the two are on a spectrum that meets in the middle.

> all high-performance collectors (for example, deferred reference counting and generational collection) are in fact hybrids of tracing and reference counting

The updated Garbage Collection Handbook does as well.

That reason are academic worthy books describing garbage collection algorithms, I can provide a couple of them.

Lets start with the Garbage Collection Handbook, chapter 5.

> 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's definitely not what McCarthy meant by it. I understand that's probably a common view nontheless, but I can use sbrk() and the fact my computer has gobs of ram/swap, and I'm not going to call that garbage collection. I don't think this definition is useful.

If you re-read what I wrote now understanding what I mean when I say "garbage collection", perhaps we can talk about strategies for providing that infinite view of memory instead.

Actually, I think process termination is pretty useful as garbage collection. It's normally much more reliable for releasing resources, for one thing. And there's little sense in cleaning up RAM when you're just going to quit.

The kernel still deallocated those pages as an explicit [manual] result of a free-like call -- that just so happens to be named exit().

To seriously tell people that every C program running on unix has automatic "garbage collection" built-in seems like it would create very confusing conversations.

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

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

> 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?

Reply on news.ycombinator.com