performance of immutable collections?

[Pangea]

I was going thru the forums and seen a lot of discussion on the
performance of immutable collections. Can someone help answer the
below questions

1) Are Immutable* more performant than their counterparts in jdk? If
so is it at the expense of memory?
2) Is there a performance benchmark
3) Are there any general guidelines i should go thru before
considering any of these Immuatble* collections

thx

[Kevin Bourrillion]

My answer will sound like a cop-out, but I believe in what I'm saying.  Apologies for overexplaining.

The main reasons to use the immutable collections are all the fabulous benefits of immutability, as well-explained in Effective Java.  The secondary reasons are the improved readability you (usually) get in your code.  Third, with the exception of ImmutableList, our collections usually take up less memory, so you GC less often.

That's the important stuff.

Raw CPU speed?  To a first order of approximation, the performance is the same.  Heck, to a second order of approximation, it's the same, too.  These kinds of performance differences are nearly always absolutely dwarfed by bigger concerns -- I/O, lock contention, memory leaks, algorithms of the wrong big-O complexity, sheer coding errors, failure to properly reuse data once obtained (which may be solved by "caching" or simply by structuring the code better), etc. etc. etc.

If you really do have an extremely CPU-intensive critical section of code in which you want to use our libraries, and it really has been identified as one of your main performance bottlenecks, well then you don't want to take my word for this anyway; you want to do some real profiling of your own -- meaning of your actual application in actual real-world usage.

So, perhaps I'm just refusing to answer your question.  Perhaps you just really want to know that third order of approximation.  Well, the answer is that it's extremely difficult to tell, and effectively impossible to really know for sure.  Our collections might be faster than JDK collections for you, but slower for someone else.  They might be good today and bad tomorrow.  Even code written in C++ will execute on top of many layers of abstraction that cause its performance to appear nondeterministic; with Java, the situation is much "worse".  What you and I are writing is nothing more than executable pseudocode.

(I put "worse" in pseudocode because it's only the determinism of performance that's worse; performance in the aggregate keeps getting better by leaps and bounds, due to the very same improvements that make predictability worse.)

To build microbenchmarks covering the features of our library you're interested in, and make them as correct as they reasonably can be, will take a lot of effort, and produce results that won't even be all that meaningful to most of you most of the time.  That said, we're trying to do it anyway.

So, how's that for "not the answer you were hoping for"?

--
guava-...@googlegroups.com.
http://groups.google.com/group/guava-discuss?hl=en
unsubscribe: guava-discus...@googlegroups.com

This list is for discussion; for help, post to Stack Overflow instead:
http://stackoverflow.com/questions/ask
Use the tag "guava".

--
Kevin Bourrillion @ Google
internal:  http://go/javalibraries
external: guava-libraries.googlecode.com

[Kevin Bourrillion]

In the old days, studying the performance of code was more like physics or chemistry -- you could perform controlled experiments and get predictable results.  Occasionally our model needed to evolve, incorporating ideas like relativity and quantum physics, and as it evolved it got better at predicting and explaining the world.

But nowadays, that stack of all those various bits of genius that sit between your Java code and the bare metal more closely resemble a biological system.  Asking whether code A or code B will run faster is similar to asking whether patient A or patient B will have a heart attack tomorrow.  If we were omniscient, it may be theoretically possible to know this, but as it is, all the variables involved (which we can't always control or even observe) can overwhelm our predictive capability.

[Raymond Conner]

And, just in case you don't own Effective Java (Get it. Get it now! - 2nd edition)...

Immutable objects are completely thread-safe, without any need for synchronization.

They may be shared between threads freely.

They don't have to be defensively copied when used by other classes.

There are other reasons. Note that "immutable" has a very specific technical definition here. Lacking setters is not sufficient.

- Ray Conner

[Noble]

The question is , have you ever observed the performance of immutable
collections better than thatof JDK collections?. if performance
characteristics are unpredictable, you must be able to see Immutable
collections beating jdk collections at least in a few instances.

On Jan 29, 3:18 pm, Kevin Bourrillion <kev...@google.com> wrote:
> My answer will sound like a cop-out, but I believe in what I'm saying.
> Apologies for overexplaining.
>
> The main reasons to use the immutable collections are all the fabulous
> benefits of immutability, as well-explained in Effective Java.  The
> secondary reasons are the improved readability you (usually) get in your
> code.  Third, with the exception of ImmutableList, our collections usually
> take up less memory, so you GC less often.
>
> That's the important stuff.
>
> Raw CPU speed?  To a first order of approximation, the performance is the
> same.  Heck, to a second order of approximation, it's the same, too.  These

> kinds of performance differences are nearly always absolutely *dwarfed* by

> bigger concerns -- I/O, lock contention, memory leaks, algorithms of the
> wrong big-O complexity, sheer coding errors, failure to properly reuse data
> once obtained (which may be solved by "caching" or simply by structuring the
> code better), etc. etc. etc.
>
> If you really do have an extremely CPU-intensive critical section of code in
> which you want to use our libraries, and it really has been identified as
> one of your main performance bottlenecks, well then you don't want to take
> my word for this anyway; you want to do some real profiling of your own --
> meaning of your actual application in actual real-world usage.
>
> So, perhaps I'm just refusing to answer your question.  Perhaps you just
> really want to know that third order of approximation.  Well, the answer is

> that it's extremely difficult to tell, and effectively impossible to *really
> * know for sure.  Our collections might be faster than JDK collections for

> you, but slower for someone else.  They might be good today and bad
> tomorrow.  Even code written in C++ will execute on top of many layers of
> abstraction that cause its performance to appear nondeterministic; with
> Java, the situation is much "worse".  What you and I are writing is nothing
> more than executable pseudocode.
>

> (I put "worse" in pseudocode because it's only the *determinism* of

> performance that's worse; performance in the aggregate keeps getting better
> by leaps and bounds, due to the very same improvements that make
> predictability worse.)
>
> To build microbenchmarks covering the features of our library you're
> interested in, and make them as correct as they reasonably can be, will take
> a lot of effort, and produce results that won't even be all that meaningful
> to most of you most of the time.  That said, we're trying to do it anyway.
>
> So, how's that for "not the answer you were hoping for"?
>
>
>
>
>
> On Thu, Jan 28, 2010 at 7:38 AM, Pangea <yarav...@gmail.com> wrote:
> > I was going thru the forums and seen a lot of discussion on the
> > performance of immutable collections. Can someone help answer the
> > below questions
>
> > 1) Are Immutable* more performant than their counterparts in jdk? If
> > so is it at the expense of memory?
> > 2) Is there a performance benchmark
> > 3) Are there any general guidelines i should go thru before
> > considering any of these Immuatble* collections
>
> > thx
>
> > --
> > guava-...@googlegroups.com.
> >http://groups.google.com/group/guava-discuss?hl=en

> > unsubscribe: guava-discus...@googlegroups.com<guava-discuss%2Bunsubscribe@goog legroups.com>

[Tim Peierls]

This ("Have you ever observed...") is actually a new question, but Kevin's generous and detailed response to the original poster is sufficiently clear about how hard it is even to define what is meant by "better performance", at least in a useful way, that I don't think a new answer is called for.

One thing is for sure, though: On modern processors, immutability beats mutability any day of the week. It's not always easy to create immutable data structures by hand in a compact, maintainable way (I look back at my own code of not so long ago and find dozens of ad hoc approaches), so when someone offers me a low-cost way to make it easy, I'm inclined to use it.

--tim

[Noble]

nobody questions the utility of immutable collections. The point of
discussion here is performance

[Sam Berlin]

I think what Tim & folk have been saying is that, in general, the
immutable collections do not cause performance problems. In some
cases, they can provide performance benefits. But, few people will
try to convince you to switch to the immutable collections for the
performance gains -- instead, the main reason to use them is
readability, maintainability, thread-safety, and general sanity. If
micro-benchmarks are particularly important to your application, you
will have to do performance tests on the collections in your
environment and determine for yourself if they are worth it.

Sam