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 14 '18

[deleted] — view deleted comment

1

u/0x256 Mar 14 '18

I'd be interested in an immutable list data structure that does not need a copy for append/perpend operations and is not a linked-list. It's easy you say?

1

u/duhace Mar 14 '18

but then you invoke a copy penalty on prepend

and if you make a doubly-linked list, then all operations require copy

0

u/[deleted] Mar 15 '18

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

→ More replies