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.

In the latter code, constructor for Struct is called (size)^2 times, one of the reasons... — skrtbhtngr
– skrtbhtngr, Commented Dec 1, 2015 at 21:25
I'd be curious to see the performance with Integer, may point to why primitives are to be preferred all things being equal. — frostbite
– frostbite, Commented Dec 1, 2015 at 21:32
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. — Pablo
– Pablo, Commented Dec 1, 2015 at 21:33
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. — Piotr Zurkowski
– Piotr Zurkowski, Commented Dec 1, 2015 at 23:28

Jon Skeet · Accepted Answer · 2015-12-02 00:03:45Z

4

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...

edited Dec 2, 2015 at 0:03

answered Dec 1, 2015 at 21:29

Jon Skeet

1.5m893 gold badges9.3k silver badges9.3k bronze badges

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

2 Comments

Piotr Zurkowski Over a year ago

"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 Over a year ago

@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.

Klitos Kyriacou · Accepted Answer · 2015-12-02 00:21:42Z

3

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.

edited Dec 2, 2015 at 0:21

answered Dec 1, 2015 at 23:49

Klitos Kyriacou

11.9k3 gold badges50 silver badges86 bronze badges

4 Comments

Piotr Zurkowski Over a year ago

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 Over a year ago

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 Over a year ago

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 Over a year ago

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.)

Collectives™ on Stack Overflow

Slow initialization of large array of small objects

2 Answers 2

2 Comments

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related