5 ms·

Well, that's good, sorry for asking. I've had a lot of people point at the big-0 notation of that linked-list append and tell me that it's faster than an Array

• bad_user 12y ago
  > 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.
  • frowaway001 12y ago
    Nice effort, but judging from the non-sense emitted by jbooth, he won't understand the things you are explaining anyway.
  • jbooth 12y ago
    Hey, so I agree with your analysis in general, and sorry for being opaque earlier (was at work), but you totally got what I was driving at and explained it probably better than I could have. 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.
  • room271 12y ago
    > 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 :)) 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?
    • bad_user 12y ago
      Yes, I wasn't talking about a single writer. That was a new paragraph. Sorry about not making that clear.
      • room271 12y ago
        Ah cool, just wanted to clarify as I'm only a beginner for much of this stuff, but found your posts very interesting. Thanks!
• Dewie 12y ago
  > Well, that's good, sorry for asking. Gotta test for any chinks in the armour.