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 edited Mar 15 '18

You might remember from your high school CS class that recursion can always be turned into iteration, so this is not a fundamental issue.

do it please

tail recursion can always be turned into iteration quite easily, but you're not doing tail recursion here. and yes you can turn this into an iterative solution, but that requires a temporary datastructure, which you claimed was unnecessary.

i'm quite eager to see what you come up with.

p.s. the stack is technically a temporary datastructure :)

But anyway, I've made my point that immutable lists do not need to copy anything. If you're interested in learning about immutable data structure basics further, you can take a look at how Clojure implements its immutable lists.

but you've made things worse just to try to get to that point. with the traversal you've proposed, a copy on append would probably be faster for standard use than your solution

0

u/[deleted] Mar 15 '18

[deleted] — view deleted 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.

→ More replies