Possible improvements to Java's ArrayList/Scala's ArrayBuffer?

Question

Currently, the "growing" algorithm figures out that the Array backing the ArrayList/ArrayBuffer is too small for the requested operation and copies the contents to the beginning of a larger array.

jsuereth explains it very well in the comments of this thread:

ArrayBuffer is great for append but not as good for prepend. Java's ArrayList will actually try to amortize costs to prepend as well, making it slightly better in my opinion. Yes ArrayBuffer is probably good enough if you're just appending on to a list and indexing elements.

Wouldn't it be a good enhancement to make the location of the old contents depend on the last operation, based on the assumption that this operation might be called more often in the future?

I. e.:

if append needs a larger array, copy the existing contents to the front of the new array:
```
[x|x|x|x|x|x] 
       |
       v
[x|x|x|x|x|x| | | | | ]
```
if prepend needs a larger array, copy the existing contents to the back of the new array:
```
[x|x|x|x|x|x] 
       |
       v
[ | | | | |x|x|x|x|x|x]
```

Will this solve the performance problems for prepend, while generally making the algorithm a bit more adaptive to usage patterns? (Worst case would be alternatively appending/prepending large stuff ...)

Are there any other data structures which already take the last operation into account when growing the underlying structure?

If you need such a data structure, please be my guest. Or maybe you should use a LinkedList instead. — solendil
– solendil, Commented May 31, 2011 at 12:02
Maybe the "Wouldn't it be a good enhancement [...]" or the "Will this solve [...]" parts? — soc
– soc, Commented May 31, 2011 at 12:05
The first is very subjective and the second very localized. "Wouldn't it be a good enhancement?" is a discussion-question, for which SO isn't well-suited. "Will this solve [...]?" is a very-specific question to which the answer is "try it". — Joachim Sauer
– Joachim Sauer, Commented May 31, 2011 at 12:07
It's not about enforcing some arbitrary standards (not that WP admins ever do that!), but about choosing the appropriate venue. This is probably better suited as a bug report (ideally with a patch!) to the OpenJDK. — Joachim Sauer
– Joachim Sauer, Commented May 31, 2011 at 12:12

Peter Lawrey · Accepted Answer · 2011-05-31 12:06:28Z

4

Perhaps what you need is ArrayDeque. This has an O(1) operation for append and prepend (unless the capacity is changed)

This has an array where it has a index to the head and tail which allows it to write the start or end position without having to shuffle all the entries down/up.

answered May 31, 2011 at 12:06

Peter Lawrey

535k83 gold badges770 silver badges1.2k bronze badges

Sign up to request clarification or add additional context in comments.

10 Comments

soc Over a year ago

This sound like pretty much what I imagined. Does the growing also take the requested operation into account? Or will the old array just copied to the middle of the new one?

Peter Lawrey Over a year ago

The expense of the operation doesn't depend on the position of the data so there is no advantage is arranging the data from a particular point. It happens to copy the data so the head = 0, but this is not a requirement.

soc Over a year ago

Yes, it might be asymptomatically the same, but if I always prepend, it requires far more growing operations than taking the last operation into account.

Peter Lawrey Over a year ago

Where do you get "if I always prepend, it requires far more growing operations"? I repeat, "This has an O(1) operation for append and prepend" They cost the same regardless of position. This is the whole point of suggesting this class.

soc Over a year ago

My question is specially focused on the performance problems when growing the underlying array. I know that both head and tail "normally" have O(1). I thought that was perfectly clear...

|

pap · Accepted Answer · 2011-05-31 12:10:33Z

3

In the general sense, MOST pre-defined structures and algorithms are based on some assumption of the most common use-cases. As it's impossible to create a "general" implementation that covers every possible scenario, there will always be some outside cases where the approach is less than optimal.

If your particular use-case is performance-critical enough that this is a problem, my suggestion is to create your own Array implementation, tailored to your usage. Beware the sub-optimization devil though. Rarely it's actually worth the increased cost of maintenance to save those few odd CPU cycles or bytes of memory.

answered May 31, 2011 at 12:10

pap

27.7k6 gold badges44 silver badges46 bronze badges

Comments

gustafc · Accepted Answer · 2011-05-31 12:07:28Z

2

You can use ArrayDeque for an array-backed data structure with fast prepend.

answered May 31, 2011 at 12:07

gustafc

29k7 gold badges75 silver badges105 bronze badges

Comments

axel22 · Accepted Answer · 2011-06-01 21:39:19Z

2

If you're not going to do a lot of lookups, and just be doing linear traversals, then go for the UnrolledBuffer - an unrolled linked list implementation. Otherwise, a Vector and its +: should be an efficient choice.

answered Jun 1, 2011 at 21:39

axel22

32.4k10 gold badges127 silver badges139 bronze badges

1 Comment

soc Over a year ago

Interesting. And thanks for letting me know that this class exists .. I have never seen it before!

Collectives™ on Stack Overflow

Possible improvements to Java's ArrayList/Scala's ArrayBuffer?

4 Answers 4

10 Comments

Comments

Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

10 Comments

Comments

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related