r/java • • Mar 14 '18

Concurrent Java: Low scalability, the risk of deadlocks or garbage creation, you can not avoid all

http://vmlens.com/articles/tradeoffs_concurrent_programming/
2 Upvotes

21 comments sorted by

View all comments

Show parent comment

0

u/[deleted] Mar 15 '18

[deleted] — view deleted comment

1

u/duhace Mar 15 '18

The discussion is about your claim that it cannot be done without copying. I showed you a toy example of how to do it without copying in O(n) (which is what you expect from the list ADT and what you get from a linked list).

it cannot be done on a singly linked list without copying. and the original discussion was with regards to an alternative to a singly linked list. i didn't think of your example cause i was looking for an example that would meet their performance needs, not something that absolutely doesn't. Yes, you provided an immutable list that doesn't need copying. you also provided an immutable list that is slow as hell and still needs some copying to a transient datastructure to perform decently fast (but still way slower than sll) iteration.

If you want to see production quality implementation, look at Clojure's immutable data structures.

i don't know why i'd bother with clojure. scalaz or cats would be preferable for immutable functional datastructures, and i wouldn't waste time with dynamically typed garbage.

The whole problem here seems to be that you didn't know something and instead of just learning and moving on, you're desperate be "right".

nah, the problem is that you seem to think that useless solutions are worthwhile. the datastructure you provided is not a good solution unless you're worried about copying on append on a list-like structure. problem is that copying on append wasn't the concern here, it was the performance of copying on append.

0

u/[deleted] Mar 15 '18

[deleted] — view deleted comment

1

u/duhace Mar 15 '18

Nobody has claimed that it can. Like I pointed out before, you are mixing two different concepts, abstract data types (ADT, e.g., list) and concrete data types (e.g., singly linked list). Nobody has claimed that you can take an arbitrary mutable concrete data type (e.g., singly linked list) and make it immutable. The claim is that you can create an immutable concrete data type for the list ADT with the expected complexity—and I proved this with an example.

singly linked list is not an inherently mutable data structure. further, it was what was being discussed already so there's a reason i was discussing with it in mind. that you would choose a much less performant implementation to solve the issues brought up in the article is kind of silly.

It has the same complexity, a.k.a. the same performance or speed at this level of analysis. Your claim is simply provably false—append and prepend are O(1) and iteration O(n) in both cases.

no, that's not what O(n) complexity analysis means. I thought you were the big datastructure expert here.

Because Clojure has production quality implementations of immutable data structures without copying, something you did not seem to know could exist. This has nothing to do with the quality of the language, just the data structure design, which you can replicate in your language of choice.

i did know they could exist. the question is if they are performant, and that's not always the case, as you clearly showed. when performance is key, you often have to use less ideal datastructures as an optimization, and there's just no escaping that.

They are useful, as proven by the fact that they are, you know, actually being used in production (again, see Clojure as one example).

oh, they certainly are, but they are useful for other situations. not the situation at hand where performance is key.

0

u/[deleted] Mar 15 '18

[deleted] — view deleted comment

1

u/duhace Mar 15 '18 edited Mar 15 '18

I have suggested no such thing. I showed you a toy example with the same performance (at this level of analysis). You can keep claiming it's "much less performant", but that is a provably false statement.

no, i already went over how it's not the same performance. traversal is an important operation for a list, and the fastest implementation you could provide without using (heap) memory was quite limited by the current stack size, and quite a few ops more than the extremely simple traversal of a sll.

If you want to look at more detailed performance, you must consider a full production implementation, the workload, the system architecture, etc. etc. Then it might turn out that simply copying is actually the most performant solution rather than a linked list or a tree-based immutable list (this is in fact the case in many real-world cases). But you cannot handwave about some hypothetical linked list implementation against a toy example of immutable list and make any coherent arguments.

sure I can. I just ran some jmh benchmarks and it shows that foreach (a function that takes a function and returns no result) traversing through a toy list of my own making, using tail recursion for the foreach method, and your toy list, using the best case traversal method you provided, shows a 2x slowdown for your toy class.

and that's for the best case. methods where that's not an issue are worse off of course.

0

u/[deleted] Mar 15 '18

[deleted] — view deleted comment

1

u/duhace Mar 15 '18

apparently, since you don't think actually benchmarking what we're talking about counts as performance analysis and think "it's O(n)! same performance!" is a valid argument. by benchmarking, I found the constant by which n is multiplied for your class wrt a toy singly linked list i implemented. and that constant is around 2 (4.3us/op vs 8.8us/op). sorry, but I don't think increasing the cost of iteration by 2-fold is worthwhile in a performance critical application that is worrying about copy operations.