Hacker News Reader

Comment by windlep | Hacker News Reader

"To create a garbage collector for the next decade, we turned to an algorithm from decades ago. Go's new garbage collector is a concurrent, tri-color, mark-sweep collector, an idea first proposed by Dijkstra in 1978."

So, the best GC for the next decade was proposed in 1978. Whatever computer scientists have proposed since then apparently hasn't been as good.... so they can all just pack it up and go home?

I'd be really really curious to hear from some academic computer scientists if the best that can be done was first proposed back then, and they've all just failed to find anything better since. Cause this is just downright depressing otherwise (If you actually want to believe that we're making progress).

View on HN

> Whatever computer scientists have proposed since then apparently hasn't been as good.... so they can all just pack it up and go home?

1. Most modern high-performance garbage collectors are both concurrent/incremental and generational. Generational GC is really important for throughput and I think Go will need to get it eventually.

2. The tri-color marking algorithm plus the idea of a nursery and tenured generation are all very old as far as ideas go, but the devil is in the details, and that's where the research lies. Hash tables, for example, date back to the '50s, but there's been constant research on refinements of the technique up to the present day.

Sometimes old ideas become worthwhile again because the hardware landscape changes.

An example from compilers: Register allocation for expressions (no cyclic dependencies) is an old and solved problem. For an expression like a+b+c+d+e+f, you wanted to order it like (a+(b+(c+(d+(e+f))))), because that minimizes register use. Then newer CPUs got out-of-order processing. Now you want ((a+b)+c)+(d+(e+f)), because in contrast to the previous order the CPU can now sum in parallel. Another case, where digging up an old algorithm helps.

What probably also happens a lot is that people reinvent stuff without knowing previous work.

I'm no academic (just a CS student), but from the very little I understand about GC algorithms, there's no free lunch. In other words, choosing GC isn't like shopping for a new condo... different algorithms have different advantages and implementation difficulties. There may also be caveats with some algorithms that others aren't plagued by. "Better" means different things to different people and in different situations.

For what it's worth, many of today's finest, most important algorithms are from the 50s-70s, or maybe special adaptations of them. Theory doesn't obsolete like technologies do.

No need to get depressed by this. Hard problems are still hard (until proven otherwise), and taking out the trash is the same today as it has ever been.

> For what it's worth, many of today's finest, most important algorithms are from the 50s-70s, or maybe special adaptations of them.

This is only the case/sensible for algorithms that have not been practically improved.

Another reason is that writing an efficient gc is a very complicated software engineering task. A concurrent continuously compacting pause-less gc is the cold fusion of the software world (i'm half-kidding because a ccc gc does work in practice). :) So Dijkstra could propose it, but he couldn't (afaik) code a high-performance proof of concept. If there was a toughness rating scale for engineering problems, then writing a CRUD app in Django would be a one and a good gc a 10.

The problem is that you have really complicated system (the gc) meeting low-level language. You need to write it in C or C++ for performance and for direct memory access. But it's a language that isn't suitable for complex algorithms so if you could choose, you'd rather pick Lisp or something. It wouldn't surprise me if it takes Google a very long time to get their awesome gc that they are planning for Go up and running even if they throw heaps of engineers at the problem.

Reply on news.ycombinator.com