News for hackers. Stuff that matters.
Re:Notes on Distributed Systems for Young Bloods (2013) by eropple on Monday August 08, 2016 @06:10AM (#12246562)
Yup, and all of them have demonstrable edge cases where the GC will throw a rod. The random slagging of the most advanced virtual machine technology out there that doesn't cost four-plus digits is pretty funny, though.
Re:Notes on Distributed Systems for Young Bloods (2013) by catwell on Monday August 08, 2016 @06:36AM (#12246669)
The issue is not really the VM, it's the language. GC performance is somehow tied to the number of objects it has to deal with.

Java code tends to be object-oriented and create a lot of objects. Functional code can create significantly fewer objects, so even though the Java world has the best GCs (like Azul C4) those other languages typically give their GCs less work to do. That also means that if you write code that does give a lot of work to the GC in a functional language it can certainly perform very poorly as well.

Erlang is probably different, afaik creating lots of (lightweight) processes is frequent in Erlang. I don't know how the Erlang GC works so I can't really comment on that.

Re:Notes on Distributed Systems for Young Bloods (2013) by qohen on Monday August 08, 2016 @06:55AM (#12246736)
I don't know how the Erlang GC works so I can't really comment on that

If you're interested, here are a few helpful blogposts on the subject:

- This is a pretty short and readable post, though it's a bit old (2008): "Garbage Collection in Erlang" [0]

- A more detailed (and recent -- 2015) blogpost: "Erlang Garbage Collection Details and Why It Matters" [1].

- And this is the most up-to-date description, from April 2016 concerning Erlang R19, by Lukas Larsson, who works on the Erlang VM -- it is long, but well-written and has nice illustrations [2].

[0] http://prog21.dadgum.com/16.html

[1] https://hamidreza-s.github.io/erlang%20garbage%20collection%...

[2] https://www.erlang-solutions.com/blog/erlang-19-0-garbage-co...

Re:Notes on Distributed Systems for Young Bloods (2013) by qohen on Monday August 08, 2016 @07:39AM (#12246914)
Or, if you don't want to chase those blogposts down, here's the nutshell version, from reference [1]:

In order to explain current default Erlang’s GC mechanism concisely we can say; it is a Generational Copying garbage collection that runs inside each Erlang process private heap independently, and also a Reference Counting garbage collection occurs for global shared heap.

(To expand on that a little: each process has its own copy of everything that it needs -- if it needs something from another process, it'll get a copy in a message sent to its mailbox, so: no shared memory, links, etc.

This encapsulation means that when a process terminates, all its memory is instantly reclaimed -- no GC is required, since no other process can possibly be referencing any data in the process that's going away.

And, while a process is alive, there's per-process generational-copying GC, as mentioned.

However, for pragmatic reasons, items > 64 bytes are stored in a global heap and references to those items are passed used (i.e. to avoid sending large things around) -- that's where the ref-counting GC comes in).

Re:Notes on Distributed Systems for Young Bloods (2013) by dschiptsov on Monday August 08, 2016 @09:02AM (#12247360)
Yes, this strong process isolation is one of the design decisions which leads to the ultimate success of Erlang/OTP as a telecom platform. Joe Armstrong's thesis has explicit explanation why JVM is not suitable for telecom-grade reliability (no matter what sales people would tell you).

Another principal design decision, which complements share-nothing architecture, is a pure functional language with single "assignment". This greatly simplified runtime and VM itself which leads to more controlled and predictable behavior, suitable for soft-realtime systems.

The concept of drivers is another one, but it is irrelevant to this discussion.

Re:Notes on Distributed Systems for Young Bloods (2013) by catwell on Monday August 08, 2016 @05:30PM (#12251018)
Thank you for the explanation. I will read the links as well. Even if I don't use it, the design of Erlang is an interesting topic to study.
Re:Notes on Distributed Systems for Young Bloods (2013) by catnaroek on Monday August 08, 2016 @07:06AM (#12246774)
> Functional code can create significantly fewer objects

Functional programs, if anything, tend to create more objects than object-oriented ones. However:

(0) Objects tend to be shorter lived, because new versions of data structures will be written to new objects, rather than overwritten to old objects.

(1) Because functional programming deemphasizes object identities, the GC can duplicate or deduplicate objects with equal contents. It can even merge several nodes of a linked data structure into a single fat node, improving locality of reference. If object identities matter, these “optimizations” actually break your program.

(2) The invariant that old immutable objects can't point to newer ones (at least in a strict functional language, not a lazy one like Haskell) can be used to optimize the GC algorithm as well.

Re:Notes on Distributed Systems for Young Bloods (2013) by chrisseaton on Monday August 08, 2016 @06:55AM (#12246739)
How does functional programming lead to generally fewer objects allocated? I would guess that it leads to more, because functional data structures require allocation to make changes where imperative programming can make destructive updates without allocating.

Many functional languages allow imperative parts of course, but even in that case how is it less than the object oriented approach rather than just the same?

Re:Notes on Distributed Systems for Young Bloods (2013) by dschiptsov on Monday August 08, 2016 @07:20AM (#12246831)
It is not only about absolute number of objects created, of course. It is also how long they kept and how often the are changing.

Immutability gives simplifies everything including incremental, parallel GC and hence reduces the pauses for GC.

This is the big idea behind Clojure and Datomic - immutability makes everything simple (less complex runtimes) and even more scalable (share nothing means no locks, mutexes, busy waiting) and in the case of Erlang - fault tolerant (strong process isolation - no threads with shared stack or any writable data).

What is funny - everything has been well-researched and right principles formulated by Erlang team decades ago, and the resulting product just works for telecoms.

The two fundamental principles they described are 1) Posix threads and fault tolerance does not match. 2) Imperative code and GC does not match. While Golang, Lua or PyPy are trying really hard to disprove the second principle, Java is an existential proof.

Re:Notes on Distributed Systems for Young Bloods (2013) by catwell on Monday August 08, 2016 @05:48PM (#12251111)
That's kind of a digression, but the Lua GC is pretty simple (which is good) and not so efficient. The LuaJIT GC has some interesting features but sadly Mike Pall did not complete all of his plans for it.

What makes LuaJIT so efficient regarding the GC is that you can allocate memory that is not managed by it (using the FFI). You have to if you need to use a lot of memory anyway, since depending on the architecture GCd memory can be limited to as little as 1 GB.

Re:Notes on Distributed Systems for Young Bloods (2013) by pjmlp on Monday August 08, 2016 @07:03AM (#12246759)
Gut feeling, not sure how much this holds.

The majority of functional languages support value types (in the stack/global sense), which many OO languages that follow Smalltalk don't. Also escape analysis tends to be relatively weak in most JVM implementations (maybe Graal is the exception here).

Immutable data makes it easier to collect garbage when moving living data between nurseries, thus leading to shorter pauses as in imperative languages.

EDIT: Updated the sentence about escape analysis.

Re:Notes on Distributed Systems for Young Bloods (2013) by chrisseaton on Monday August 08, 2016 @07:05AM (#12246767)
I think as you say immutability is probably the real benefit of functional for GCs as it simplifies a lot. But that doesn't reduce the number of objects allocated, which was the claim made.
Re:Notes on Distributed Systems for Young Bloods (2013) by catnaroek on Monday August 08, 2016 @07:12AM (#12246799)
The directed graph of immutable objects and links between them is by necessity a DAG. Only mutation can introduce cycles. If 90-95% of your objects are immutable, your GC algorithm can be specifically optimized for them. For instance, the mark and compact phases could run concurrently (interleaved) and in-place.

(Yes, this means that, from a GC implementor's POV, a lazy language like Haskell mutates like crazy.)

Re:Notes on Distributed Systems for Young Bloods (2013) by notacoward on Monday August 08, 2016 @09:30AM (#12247534)
It seems to me that objects are being copied no matter what. In one world, mutation is common and the copying occurs within the GC subsystem. In the other world, mutation is rare and the programmer has to manage the copies manually. Pretending that the copies are wholly new objects which owe nothing to their predecessors strikes me as disingenuous. For all practical purposes, creating a new object that differs from its predecessor in one field is equivalent to mutating that field (except that it's far worse for performance).

Is moving a burden from the runtime to the programmer a good idea? Generally, no. There might be something about this particular case that makes it an exception to the general rule, but the point seems very far from proven.

Re:Notes on Distributed Systems for Young Bloods (2013) by zaphar on Monday August 08, 2016 @09:56AM (#12247750)
As I've been teaching myself rust this point has been hammered home hard. It's really eye opening to see all the copies plainly represented in code and the lifetime checker is really good about highlighting where you should be making a copy vs sharing a reference.

I haven't reached the stage where I can write performant Rust yet since I've only recently started to truly grok the borrow checker but I can see how longer term it will be easier to figure out how to make my code performant since the all the information required is front and center. It will be interesting to see whether that promise holds for rust code as the community matures.

Re:Notes on Distributed Systems for Young Bloods (2013) by catnaroek on Monday August 08, 2016 @11:05AM (#12248323)
> It's really eye opening to see all the copies plainly represented in code and the lifetime checker is really good about highlighting where you should be making a copy vs sharing a reference.

From a Rust POV (a useful one, even if you're using a higher-level language), when you use a garbage collector, technically everything is owned by the garbage collector, and merely borrowed by you. That's why in most languages you can get away with making shallow copies everywhere, even when Rust would tell you that a `.clone()` is in order.

Re:Notes on Distributed Systems for Young Bloods (2013) by catnaroek on Monday August 08, 2016 @10:55AM (#12248248)
> For all practical purposes, creating a new object that differs from its predecessor in one field is equivalent to mutating that field (except that it's far worse for performance).

(0) If the object has, say, just two or three fields (which isn't uncommon in functional languages, since they really tend to decompose everything in a piecemeal fashion), this is no big deal.

(1) If a functional language has substructural types (which admittedly most don't), the compiler can even tell, purely from type information, when an object won't be used anymore and can be overwritten anyway, as though you had used imperative assignment all along.

Re:Notes on Distributed Systems for Young Bloods (2013) by notacoward on Monday August 08, 2016 @01:50PM (#12249572)
So, best case, with proper type annotation and a really good optimizer, you get the performance you would have had with plain old mutability? Pardon me if I remain unconvinced that immutability is solving the problem adequately.
Re:Notes on Distributed Systems for Young Bloods (2013) by catnaroek on Wednesday August 10, 2016 @12:28PM (#12262930)
> you get the performance you would have had with plain old mutability

And muuuch better type safety. You can only mutate data in-place if either no one else has access to it, or it's wrapped in a mutex and you've taken a lock.

Re:Notes on Distributed Systems for Young Bloods (2013) by catwell on Monday August 08, 2016 @05:42PM (#12251081)
To be honest when I said that I can was thinking about how less boxing occurs in (statically typed) functional languages. But like you and others said in the thread immutability can actually result in the creation of more objects, they just have different life cycles and properties that make the work of the GC easier.
Re:Notes on Distributed Systems for Young Bloods (2013) by marcosdumay on Monday August 08, 2016 @01:48PM (#12249552)
> Functional code can create significantly fewer objects

Immutability means the number of individual objects explodes.

It also means those are easier to garbage collect, so you can have several different algorithms acting on different time-frames, alleviating the problem for the slower ones.