The Oracle JVM uses generational garbage collection[1]. Glossing over some details, this garbage collector divides objects into generations depending on how long they've been around, and also keeps track of references that cross generations. Objects that are newly created go into the first generation. If the objects don't refer to objects outside of the first generation, it is very cheap for the VM to determine they are in fact garbage. When the garbage collector gets run, objects that a still live get copied to another generation. Once the still live objects are copied out, the VM doesn't need to do any cleanup to get rid of the dead objects, it simply marks the whole memory block the first generation was in as available.
[1] Not that other JVMs don't, but I only know the official one.
simply marks the whole memory block the first
generation was in as available
That doesn't make any sense.On that GC run what if you just allocated an object, 0.01ms ago? You mean to tell me that it's either (a) deallocated before being used or (b) moved to the second generation already? Also, you need to basically stop the world for doing first-generation cleanup, as you described it, otherwise you're running into race-problems. That's insane.
Glossing over some details, no matter how efficient the GC is in regards to first generation treatment, you're still accessing the heap, which is an expensive operation, you're still potentially boxing/unboxing primitives in loops and you're also making single-dispatch virtual calls on those short-lived objects.
C++ has terrible performance when using heap-allocated values, but with stack-allocated objects C++ kicks Java's butt. And that's not the only potential problem for Scala, unless Scala adds some kind of tracing compiler that can avoid boxing/unboxing and runtime-dispatch when not necessary.
I don't think anyone actually expects the JVM to beat C++ using stack allocated objects[2]. Our concern is how well a garbage collector handles lots of small objects.
[1] Details on how the JVM GC works: http://www.oracle.com/technetwork/java/gc-tuning-5-138395.ht... [2] There is a switch, which will be on by default one day, that lets the JVM do escape analysis so it can allocate objects on the stack automatically.
However, there are places where a lot of object churn can really be problematic. In particular, I find that Android applications tend to be somewhat sensitive to this. However, even in desktop or server applications, a lot of object churn in a tight loop can be bad.
Also, isn't malloc() a misnomer for stack allocations?
∀f, ∀g, map g ∘ map f == map (f ∘ g)
because f or g could perform some side effect, or fail to terminate. (My example may be bogus, but I'm sure we can find some real one.)That's not an optimization any more, that's a language feature.
http://java.sun.com/docs/books/jvms/second_edition/html/Over...
You would not be using the stack for this.
Edit: thinking about this on the way back from lunch, read-heavy workloads give you the best case for persistent data structures, but that's still the same as for mutable structures, i.e. no object churn. I can't think of any cases where persistent structures would create less garbage.
Persistent data structures allow the VM or compiler to determine when things need to be copied. Mutable structures require programmers to worry about copies, so they will make copies when they feel they might be necessary. In very well-defined cases a smart programmer can optimize this to a point where it probably uses less memory than a persistent data structure, but in the average case (and with the average programmer), the VM will likely do a better job of knowing when to copy and when to not bother.
Persistent data structures intrinsically involve copying on updates, and no amount of compiler cleverness can avoid that. I can see the possibility for compiler magic with stream fusion, for example, but I'm not seeing it for data structures. The only win I can see is if you have multiple clients of your data structure holding references to multiple versions, but even there the compiler doesn't help you. Am I missing something?
The compiler magic can help you there. You are looking for linear types.
I don't have deep or broad experience, and it's ceretainly true (as I see it) that naive implementations provoke lots of GC. But it didn't seem obvious to me that OOPLs should provoke less, and it does seem reasonable that FPLs might easily provoke less.
I'd be interested to hear some of our more experienced HNers comment on this.