Yes I do. Worked 3 years on a soft real-time system with massive load, profiled the shit out of everything. There's an interesting discussion we could have about when immutable data-structures work best, when they've got problems and when it doesn't matter, especially given the extra benefits in dealing with accidental complexity. This isn't the right place though.
> Performance is important to some of us
Yes it is, but performance problems are fixed by means of profiling and optimizing the bottlenecks. Even in a system that has massive load, in many cases in doesn't matter and in some cases immutability increases performance by eliminating contention on reads. And seriously, most people invoking performance problems are not having those performance problems to begin with, therefore my assumption.
As I'm sure you know, when it comes to real-world situations, reducing inter-thread communication and isolating anything mutable is the key concern. That's why I find immutable wrappers that mock mutability to be a bit of a sideshow. You shouldn't have read contention with locking in the first place unless it's for a very good reason.
True, but you know how it is in practice :-)
For example I found that using persistent data-structures work best when you've got single producer, multiple consumers scenarios - so you mutate some state and you want to signal it over asynchronous boundaries to multiple consumers. With an immutable data-structure you just signal it, worry free and then you can keep on changing that state, completely non-blocking / wait-free and with good algorithmic complexity.
Actually non-blocking logic becomes really easy, as you can always shove an immutable value into an atomic reference (note - I'm not saying "wait free", which still takes a lot of work :))
So really, persistent data-structures are great in a multi-threading context, as long as you don't have multiple producers pounding on the same reference holding such an immutable value - if you do that, things can get bad, when compared to specialized concurrent mutable data-structures - because a good concurrent data-structure is able to distribute the contention in multiple buckets instead of just one. But then again, having multiple producers pounding on the same resource is just asking for trouble and has to be avoided, because Amdahl's law.
Also, as you've hinted at, the problem with a normal linked List is the level of indirection. And in general, persistent data-structures imply the usage of trees, which also implies indirections. More advanced persistent data-structures are much better than the linked list is and this is an active area of research, but on the whole there's still much room for improvement.
On the other hand, in my opinion when speaking about performance, the first problem one has is to actually use the available CPUs (e.g. getting CPU usage over, say 70-80%). Which usually is hard to achieve if you have a combination of CPU-bound and I/O-bound tasks and your I/O stuff is not asynchronous. Only after that you can then move on to optimizing the memory access patterns for cache locality and for minimizing the stop-the-world freezes.
Speaking about GC, that's another topic - persistent data-structures have a tendency to generate junk that is neither short term or long term and that invalidates the assumptions that current GCs are making. The JVM at least has really good GCs, but without paying for a pauseless one (like that one from Azul Systems), you can still end up into trouble if you don't pay attention - but then you fire up YourKit's Profiler, find the source for those STWs, optimize and it works out well.
All in all I encourage everybody to find a good library that implements persistent data-structures and integrate them in their toolbox.
The one thing I disagree with, in many server applications, is using the available CPUs is pretty easy. You've got thread pools handling various tasks, just crank them up. In JVM-land, a very heavy 512kb stack per thread is still not really much penalty to pay as long as you re-use them. Aggregate application performance then becomes a matter of completing tasks faster while creating less garbage.
So it all comes down to what you consider a 'task' and how you handle the handoffs between them. The architecture decisions at this level dwarf the improvements from using an array vs list, as you implied, but they also make the usage of immutable types somewhat irrelevant IMO. Seal off mutable code within single-task boundaries and it doesn't matter how ugly it is, as long as you're passing immutable types (just plain javabeans with final members are fine) between boundaries.
Anyways, just my opinion. Great comment.
Why the atomic reference here? I know that provides CAS but if we're talking about a single writer aren't you okay to just replace things anyway?
Thanks!
Gotta test for any chinks in the armour.
Yes.
> Performance is important to some of us.
... and in those cases, you don't have to use data structures that model your problem domain poorly.
The problem isn't "immutable data structures" or "theoretically robust" languages. The problem is finding ways to express computations and their constraints in a way that can be efficiently modeled for your problem domain.
So what will probably happen is that once you see your performance problems, you can pray that it's only some hot spots that you can then replace with faster code - often it's not, so you have 100 places using around 1% of your time budget for example, which is when you can go and start over.
As far as not understanding how awesome immutable data structure are.. I'd take a step back before you make assumptions about what other people understand. Do you know anything about cache hierarchy and memory models on modern CPUs? Performance is important to some of us.