Slow initialization of large array of small objects

Question

I've stumbled upon this case today and I'm wondering what is the reason behind this huge difference in time.

The first version initializes an 5k x 5k array of raw ints:

public void initializeRaw() {
 int size = 5000;
 int[][] a = new int[size][size];
 for (int i = 0; i < size; i++)
 for (int j = 0; j < size; j++)
 a[i][j] = -1;
}

and it takes roughly 300ms on my machine. On the other hand, initializing the same array with simple 2-int structs:

public class Struct { public int x; public int y; }
public void initializeStruct() {
 int size = 5000;
 Struct[][] a = new Struct[size][size];
 for (int i = 0; i < size; i++)
 for (int j = 0; j < size; j++)
 a[i][j] = new Struct();
}

takes over 15000ms.

I would expect it to be a bit slower, after all there is more memory to allocate (10 bytes instead of 4 if I'm not mistaken), but I cannot understand why could it take 50 times longer.

Could anyone explain this? Maybe there is just a better way to to this kind of initialization in Java?

EDIT: For some comparison - the same code that uses Integer instead of int/Struct works 700ms - only two times slower.

• skrtbhtngr: In the latter code, constructor for Struct is called (size)^2 times, one of the reasons...
• frostbite: I'd be curious to see the performance with Integer, may point to why primitives are to be preferred all things being equal.
• Pablo: You are deluding the yourself calling your class a struct. It is still a class and, with it, but comes all of the initialization overhead.
• apangin: -verbose:gc will explain a lot
• Piotr Zurkowski: Yes, it comes with an overhead, but why so huge? If I understand correctly using Integer should generate similar overhead, but in practice its only ~700ms - 2 times slower compared to 50.

Answer 1

I would expect it to be a bit slower, after all there is more memory to allocate (10 bytes instead of 4 if I'm not mistaken), but I cannot understand why could it take 50 times longer.

No, it's much worse than that. In the first case, you're creating 5001 objects. In the second case, you're creating 25,005,001 objects. Each of the Struct objects is going to take between 16 and 32 bytes, I suspect. (It will depend on various JVM details, but that's a rough guess.)

Your 5001 objects in the first case will take a total of ~100MB. The equivalent objects (the arrays) may take a total of ~200MB, if you're on a platform with 64-bit references... and then there's the other 25 million objects to allocate and initialize.

So yes, a pretty huge difference...

• Piotr Zurkowski: "gigabytes" is probably a bit too much here. 16 bytes (assuming single type pointer and two ints) adds up to 400 MB, added to 200MB of pointers should give 600MB. It is 6 times more memory indeed, but its definitely not 50. There are more calls to constructors indeed, but in practice, it should all come down to allocating and modifying 600MB. Is there no way to efficiently solve this? Having to split the structure into two smaller arrays that obfuscate the code to get improvement of the whole order of magnitude seems like an impossible requirement to me.
• Jon Skeet: @Piotr: You're right about the maths. Not sure what happened when I did it. But I don't see what's "impossible" about having to find a balance between clarity and performance. Those are often in tension.

Answer 2

When you create an array of 5000 ints, you are allocating all the space you need for all those ints in one go, as a single block of consecutive elements. When you assign an int to each array element, you are not allocating anything. Contrast that with an array of 5000 Struct instances. You iterate through that array and for every single one of those 5000 elements you allocate a Struct instance. Allocating an object takes a lot longer than simply writing an int value into a variable.

The fact that you have two-dimensional arrays doesn't make much compararive difference here, as it just means you do allocate 5000 array objects in both cases.

If you are timing an array of Integer objects, and you are then setting each element to -1, then you are not allocating separate Integer objects each time. Instead, you are using autoboxing, which means the compiler is implicitly calling Integer.valueOf(-1) and that method returns the same object from the cache each time.

UPDATE: Going back to addressing your concern, if I understand correctly, you have a requirement to keep 5000x5000 Structs in a 2D array, and you are disappointed that creating this array takes a lot longer than using primitives. To improve performance, you can create two arrays of primitives, one for each field of Struct, but this would reduce code clarity.

You can also create a single array of longs (since each long is double the size of an int) and use the & and>> operators to get your original ints. Again, this would reduce code clarity, but you'll only have one array.

However, you seem to be concentrating on a single part of the code, namely the creation of the array. You may well find that the processing you do on each element overshadows the time it takes to create the array. Profile your whole application and see if the creation of arrays is significant.

• Piotr Zurkowski: Thanks for an elaborate answer. The allocation takes huge part of processing time indeed - takes 15 sec and the whole processing of the data takes around 0.2 sec - that's why I noticed it. I never code in java, but after seeing that I was mostly interested if I'm just missing some java-specific solution - I'm surprised there aren't any. I guess a simple takeout from here is that you shouldn't really overuse small data structures (when there are many of them) to clean up the code, as its very expensive.
• Klitos Kyriacou: An interesting diversion is that, if you were using C#, you could have used a struct rather than a class and then it wouldn't cause the allocation of so many objects because the structs would indeed be part of the array itself. It's a bit drastic to change programming language just for this reason.
• frostbite: Does that mean autoboxing is not in play or is optimized when setting an Integer object with -1? I thought all primitive wrappers autoboxed under the hood.
• Klitos Kyriacou: Autoboxing is still in play, but it autoboxes your primitive value with an existing object instead of creating a new one. This typically happens for small values of int, and is implementation-dependent. For example, Oracle's implementation of Java 8 caches Integers with values from -128 to 127. (But you should never rely on that, e.g. by using the == operator on Integer.)