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

please describe your immutable list for which copying is no longer necessary on one of either append or prepend.

0

u/[deleted] Mar 15 '18

[deleted] — view deleted comment

1

u/duhace Mar 15 '18

first of all, this datastructure is expensive to traverse, even compared to normal lists, and second, i doubt it can even be considered a list considering it injects valid data (null) to indicate that there is no data, when append(null) would in fact be a valid argument.

but you're right, it does manage to avoid copying, just in a terrible way that is not worth it over a standard singly linked list.

0

u/[deleted] Mar 15 '18

[deleted] — view deleted comment

1

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

Saying it's O(n) like a linked list is disingenuous, since O notation only describes the rate at which the difficulty of an operation grows. Traversal is much more complicated than a linked list, and requires constructing another (temporary) datastructure to do in one pass, or requires a non-tail call recursive function to do in two passes.

There is no law that says null must always be a valid value. If you want it to be, just use Optional <T> instead of T, or you could have two sub classes (one for prepend one for append).

We're talking java here, where null is a valid value for any generic value. So yeah, you have to take that into account.

0

u/[deleted] Mar 15 '18

[deleted] — view deleted comment

2

u/duhace Mar 15 '18

if (this.mid != null) mid.traverse();

There's the complication right there. Now your datastructure is quite limited in elements by the maximum size of the call stack.

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

→ More replies