CODEWITHSUNDEEP
javaarrays
anoopelias
anoopelias

Reputation: 9548

Efficient array expansion in Java

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,

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

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

Upvotes: 2

Views: 603

Answers (1)

mikera
mikera

Reputation: 106351

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.

Upvotes: 5

Related Questions