Efficient array expansion in Java

Question

In C/C++ we have realloc which will efficiently allocate additional space for an existing collection. I guess it is sub linear (or even constant) in complexity.

Is there a way to achieve the same in Java? Here are the items that I looked at,

Array resize is not possible,
Copying an array to another of bigger size is linear in complexity. Looked at both System.arrayCopy as well as Arrays.copyOf
ArrayList must be same as point 2 above.

Note : My requirement is to expand possibly an extremely large array to even further.

I think no, but you can get closer to it by using some factors like amortized time and using system methods. In this case System.arrayCopy is much faster. — Aditya Peshave
– Aditya Peshave, Commented Mar 22, 2014 at 4:31
Must it really be one large array? Unless you are interfacing it with something else (jni) I'd probably use a different structure--a linked list of arrays or something? You can still wrap it in a class that lets it interact with it however you like--that is all assuming you are talking an array more than, say, 1/3 the ram of your PC, if it's not that big I'd just do what Louis said, don't worry about it and let java handle it for you, Java will do very smart things in general. — Bill K
– Bill K, Commented Mar 22, 2014 at 4:40
@BillK, & louis, I get the general picture. Thank you for the inputs. — anoopelias
– anoopelias, Commented Mar 22, 2014 at 4:56

mikera · Accepted Answer · 2014-03-22 04:41:25Z

5

realloc is likely to be O(n) in practice, since it sometimes/often involves memory copying. In that sense, it's equivalent in theoretical complexity to allocating a new array in Java.

Now Java always zeros the newly allocated memory which may take it a bit longer, but OTOH the GC has insanely fast memory allocations so it may even be faster than realloc in some cases. I'd expect a strategy that involves allocating new arrays in Java to be overall roughly comparable in speed to realloc. Possibly Java is better for smaller arrays, C/C++ would have the edge for big arrays, but YMMV. You'd have to benchmark in your particular implementation and workload to be sure.

So overall:

Don't worry about it, just reallocate new arrays in Java
If you do this a lot, be sure to recreate arrays with more space than you need so that you don't need to reallocate with each single element added (this is what the Java ArrayList does internally.

Final but important point: unless you are writing very low level code, you probably shouldn't be worrying about this anyway. Just use one of the fine collection classes that already exist (Java Collections, Google Collections, Trove etc.) and let them handle all of this stuff for you.

answered Mar 22, 2014 at 4:41

mikera

107k28 gold badges265 silver badges427 bronze badges

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

2 Comments

anoopelias Over a year ago

Based on all your inputs, I get the idea. Will try with Arrays.copyTo and see how it goes. Thank you.

0x90 Over a year ago

+1 for trove and google collection

Collectives™ on Stack Overflow

Efficient array expansion in Java

1 Answer 1

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related