My basic (starter) understanding of Functional
programming tells me that there should be more
object churn in a functional language ... and
thus Scala should have trouble with GC not the
Java implementation.
My experience is that in an OOP language, objects are brought forth, used, then discarded, oft-times requiring GC. My experience of well-implemented FP languages data streams through functions that have, in the large part, been optimised away.
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.
I can't find the link right now, but there was a blog post from one of the F# team at MS, saying the CLR team couldn't believe the rate at which he was allocating and deallocating memory, and some tuning needed to be done on the CLR to support F# performance. If you are working with recursion and folding rather than for-loops, under the covers you will be doing one malloc() per iteration, you will definitely need some sort of clever memory management rather than relying on just the OS's implementation.
Tail recursion has nothing to do with garbage collection in F#. You're going to have one allocation per iteration if you do e.g. a map over a list. In an imperative language you'd probably mutate the collection in place.
That's something else entirely compared to tail call optimization, but yes some functional languages (e.g. Haskell) do this. I don't think F# does stream fusion though.
I'd be surprised if the current implementation of F# didn't do anything of this sort. But as a language, I understand fusion is more difficult in ML than in Haskell: that's because ML is strict and non pure. Therefore, some of the assumptions you could do in a non-strict, pure language don't hold, and it may not be unconditionally true that
∀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.)
Sure, but the order of evaluation do change something. For instance, infinite lists won't ever terminate, but taking the first 42 elements of an infinite list will terminate in Haskell, and not in ML. If you want to fuse the whole thing, it won't change the Haskell program, but it may change the ML one, by making it terminate an return the correct result!
That's not an optimization any more, that's a language feature.
Yes. Though the situation is only that rosy in Haskell under some circumstances. It's easy to get space leaks that make your program use O(run-time) memory, if you are not careful with the laziness.
Only in some (read-heavy) workloads - in general I'd expect persistent data structures to generate more garbage, since mutability by definition allows you to modify and reuse nodes.
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 will win, when your structures have (potentially) multiple futures. If you use your objects in a linear way, then the best you can hope for is your compiler to be smart enough to do something that's as fast as in-place updates.
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?
High object churn shouldn't be a problem for the JVM, whether it is running Scala or Java code. Allocation lots of little objects and then discarding them shortly after is a use case the JVM is well optimized for. You would have to allocate an extraordinary number of such objects to see any real slowdown.
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.
Oracle have put an enormous amount of work into the JRockit GC to support determinism. It's very clever: you can say to it, no GC pauses longer than X milliseconds, and it will adjust its throughput to guarantee that. So you might get lower overall performance, but it will be predictable.
It all depends on the context. In code that is not performance-sensitive, a bit of object churn isn't a problem.
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.
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 can tell you is isn't being deallocated before being used, that would be a major bug. So, I guess it would get moved, but the GC probably won't run unless the first gen space is pretty full. I'm glossing over details because, well, the GC in the JVM is a very complicated piece of work, and I don't know much of the details, but the JVM does in fact default to a stop-the-world garbage collector[1].
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.
Thinking logically if some language is built on some other language then the derived language can be at most as fast as the underlying language
That is not true. Why? Because the C compiler optimizes at compile time, and the VM optimizes at compile time and at runtime. It can be much smarter at inlining, loop unrolling, etc.
The compilation path is Scala -> JVM bytecode [-> x86 assembly], not Scala -> Java -> JVM bytecode [-> x86 assembly]. At least, that's what I think your parent comment was saying.
I wonder where people are getting this (you're not the first person I've heard this from)? The syntax is not compatible at all. You can write programs in the same style, e.g. object oriented with inheritance, global state, side effects, and so on; but the similarity ends there.
Agreed. Likewise the article is wrong when it says Java is built "on top" of C/C++. It compiles to JVM bytecode which is JIT compiled to native machine code.
So its whole "thinking logically" premise is broken.
It's a gigantic stretch to read an article that benchmarks languages implementing a single type of function and conclude "It shows Scala to be faster compared to Java".
Thankfully the author realizes this in his conclusion - "it seems that difference in implementations is the cause for difference in the time taken by Java/Scala programs".
Or argue that the Scala language provides more information to the static compiler allowing it to produce better byte code. Has anyone done that analysis?
In general, the Java static compiler generates pretty poor-performing bytecode, no matter how much useful info you give it. This is by design, and relies on HotSpot to provide the necessary optimisations at runtime.
I'm no expert but I would assume that the Scala compiler is quite similar. Not much point in generating highly optimised bytecode when HotSpot will do the job for you.
That Google paper specifically said that they significantly refactored the algorithm to be more "scala-like" and got a much cheaper implementation than the canonical way it was implemented in other languages.
So, no, Scala is not faster than Java and probably won't be for a long time.
But yes, picking your algorithm is more important than language microbenchmarks.
Your phrasing is slanted. Citing the abstract of the paper:
> The implementations each use the languages’ idiomatic container classes, looping constructs, and memory/object allocation schemes. It does not attempt to exploit specific language and run-time features to achieve maximum performance.
Meaning, they went out of their way to write idiomatic Scala and idiomatic Java. No performance tweak in Java nor in Scala. The way you phrased it make it sound like they paid more attention to their Scala implementation. If you really think that, say so. Beware though: that would be a direct accusation of intellectual dishonesty.
To me, Google's paper looks like clear (though not iron strong) evidence that idiomatic Scala is is faster than idiomatic Java, with the chosen implementations. Shortening that into "Scala is currently faster than Java" doesn't seem such a stretch. Now if you want to compare idiomatic Java written in Java, and idiomatic Java written in Scala, fine, but I don't think it's a fair comparison.
Frankly, their discussion is a bit confusing because they did have optimized versions discussed in the text. And the optimized Scala version did make fundamental changes to the algorithm. They could have kept a better division between the two - idiomatic versus optimized - in both their results and their discussion.
So, jbooth is not accusing them of intellectual dishonesty. And if I consider the following three suppositions: jbooth's understanding of the paper was not complete, your understanding of the paper was not complete, and the people who wrote the paper are smart and hard working; then I simply conclude that performing and writing about this kind of study in a clear manner that will confuse none is very, very hard.
> your understanding of the paper was not complete,
Indeed: I have not read it. But now I plan to.
(Edit: since when a pubic recognition of one's own fault is worth a down vote? My not having read the paper provides meaningful context, by temporarily undermining my authority. Down vote the grand parent, but leave this one at 1 point!)
Read their section specifically on Scala. The algorithm as implemented in Scala was a different bag of oranges than the apples in the C/Java implementations.
If you want to say that idiomatic Scala is so great, fine, although I wouldn't be so absolutist about it (remember the article on HN 2 days ago about the scala for loop being 20x as expensive as the while loop because of something to do with closures?).
Anyways the point is that the comparison was not between two things that were at all the same. All that says is that this particular problem was better expressed in Scala, and nothing about how one was faster than the other.
And you should probably take a closer look at Figure 8 - note that the non-pro version of Scala that did not change the fundamental algorithm is still faster than the non-pro version of Java. The version you're mentioning is not in Figure 8.
Too lazy to read past the first page before breakfast, but:
All four implementations stay very close to the formal specification of the algorithm and do not attempt any form of language specific optimization or adaption.
So there appears to be some inconsistency in how they describe their methods.
The "pro" versions - the implementations that were tuned for performance by experts in that language - were not part of the main figure that compared runtimes (the table in Figure 8). All of the optimizations and reports of performance improvements were in the "Tunings" section, and were considered apart from the findings in Figure 8. Well, except for the Go Pro version, which blurs the division.
They could have used a sentence in the opening of the "Tunings" section to reiterate that the optimized versions are not represented in Figure 8. The different versions in Figure 8 are mostly tuning the GC, not tuning the implementation itself. And, strangely, they do include the Go Pro version in Figure 8. Certainly, though, the C++, Java and Scala Pro versions are not in Figure 8, which is where they drew most of their conclusions from.
My experience with Java and Scala in high profile, high traffic apps is that they are more or less exactly the same speed. Scala has historically had a much less performant (and buggy) collections library, so I've often used java collections from scala, but it's gotten better.
49 comments
[ 3.0 ms ] story [ 95.2 ms ] threadI 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.
Also, isn't malloc() a misnomer for stack allocations?
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.
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.
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.
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.
That is not true. Why? Because the C compiler optimizes at compile time, and the VM optimizes at compile time and at runtime. It can be much smarter at inlining, loop unrolling, etc.
So its whole "thinking logically" premise is broken.
Thankfully the author realizes this in his conclusion - "it seems that difference in implementations is the cause for difference in the time taken by Java/Scala programs".
I'm no expert but I would assume that the Scala compiler is quite similar. Not much point in generating highly optimised bytecode when HotSpot will do the job for you.
That Google paper specifically said that they significantly refactored the algorithm to be more "scala-like" and got a much cheaper implementation than the canonical way it was implemented in other languages.
So, no, Scala is not faster than Java and probably won't be for a long time.
But yes, picking your algorithm is more important than language microbenchmarks.
> The implementations each use the languages’ idiomatic container classes, looping constructs, and memory/object allocation schemes. It does not attempt to exploit specific language and run-time features to achieve maximum performance.
Meaning, they went out of their way to write idiomatic Scala and idiomatic Java. No performance tweak in Java nor in Scala. The way you phrased it make it sound like they paid more attention to their Scala implementation. If you really think that, say so. Beware though: that would be a direct accusation of intellectual dishonesty.
To me, Google's paper looks like clear (though not iron strong) evidence that idiomatic Scala is is faster than idiomatic Java, with the chosen implementations. Shortening that into "Scala is currently faster than Java" doesn't seem such a stretch. Now if you want to compare idiomatic Java written in Java, and idiomatic Java written in Scala, fine, but I don't think it's a fair comparison.
So, jbooth is not accusing them of intellectual dishonesty. And if I consider the following three suppositions: jbooth's understanding of the paper was not complete, your understanding of the paper was not complete, and the people who wrote the paper are smart and hard working; then I simply conclude that performing and writing about this kind of study in a clear manner that will confuse none is very, very hard.
Indeed: I have not read it. But now I plan to.
(Edit: since when a pubic recognition of one's own fault is worth a down vote? My not having read the paper provides meaningful context, by temporarily undermining my authority. Down vote the grand parent, but leave this one at 1 point!)
If you want to say that idiomatic Scala is so great, fine, although I wouldn't be so absolutist about it (remember the article on HN 2 days ago about the scala for loop being 20x as expensive as the while loop because of something to do with closures?).
Anyways the point is that the comparison was not between two things that were at all the same. All that says is that this particular problem was better expressed in Scala, and nothing about how one was faster than the other.
Give me some time. http://news.ycombinator.com/item?id=2678994
Again, I agree the results are confusing.
All four implementations stay very close to the formal specification of the algorithm and do not attempt any form of language specific optimization or adaption.
So there appears to be some inconsistency in how they describe their methods.
Maybe I'm missing something obvious here, but how can a language that compiles down to Java, be faster than Java?
Does C code execute faster than machine code?
They could have used a sentence in the opening of the "Tunings" section to reiterate that the optimized versions are not represented in Figure 8. The different versions in Figure 8 are mostly tuning the GC, not tuning the implementation itself. And, strangely, they do include the Go Pro version in Figure 8. Certainly, though, the C++, Java and Scala Pro versions are not in Figure 8, which is where they drew most of their conclusions from.