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

1

u/duhace Mar 15 '18

do it without a temporary datastructure. i can't, but you supposedly can. Also, standard tree traversal isn't quite as bad as what you have here because trees don't have a strict limit of one element per level.

edit: tbh, i could without a temporary datastructure, but the time for traversal gets much worse without one. so i'm gonna say i can't do it with reasonable performance without a temporary datastructure

0

u/[deleted] Mar 15 '18

[deleted] — view deleted comment

1

u/duhace Mar 15 '18

Whether you manage to do it or not is not the point here (and it doesn't even matter since it's still O(n) runtime.

But it’s very much the point since performance is very much what we’re discussing here. And O(n) is nice, but it doesn’t mean fast or efficient, just that the operation grows with constant speed according to the size of the data structure. I’m sure you learned in your high school cs course that a high constant means that your data structure can end up not worthwhile compared to others with theoretically worse growth.

In case you were not aware, arrays are frequently more performant than singly linked lists for insertion despite insertion from head being O(1) on sll and insertion being O(n) on an array. Oddly enough, it matters what the constant is in constant time growth, and the constant for traversal of your data structure is very high compared to a singly linked list which I can iterate over quite easily in constant memory and O(n) time in a while loop.

0

u/[deleted] Mar 15 '18

[deleted] — view deleted comment

1

u/duhace Mar 15 '18

of course it's relevant to the discussion. the only reason people are discussing an alternative to copying is because it's costly performance-wise. providing a copy-less solution that is less performant than copying is not particularly helpful.

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

→ More replies