1

I'm programming something in Java, for context see this question: Markov Model descision process in Java

I have two options:

byte[MAX][4] mypatterns;

or ArrayList mypatterns

I can use a Java ArrayList and append a new arrays whenever I create them, or use a static array by calculating all possible data combinations, then looping through to see which indexes are 'on or off'.

Essentially, I'm wondering if I should allocate a large block that may contain uninitialized values, or use the dynamic array.

I'm running in fps, so looping through 200 elements every frame could be very slow, especially because I will have multiple instances of this loop.

Based on theory and what I have heard, dynamic arrays are very inefficient

My question is: Would looping through an array of say, 200 elements be faster than appending an object to a dynamic array?

Edit>>>

More information:

  • I will know the maxlength of the array, if it is static.
  • The items in the array will frequently change, but their sizes are constant, therefore I can easily change them.
  • Allocating it statically will be the likeness of a memory pool
  • Other instances may have more or less of the data initialized than others
Community
  • 1
  • 1
bigcodeszzer
  • 916
  • 1
  • 8
  • 27
  • 1
    By dynamic array, are you referring to a `List`, such as an `ArrayList`? What theory and where have you heard that `ArrayList` is very inefficient compared to a plain array? It is not. – Andreas Dec 21 '15 at 01:05
  • Yes, and I was just editing it. – bigcodeszzer Dec 21 '15 at 01:07
  • ArrayList may not be inefficient I suppose, but what I've heard is static arrays are many times faster. Not sure if that's true, but that's what I understand. – bigcodeszzer Dec 21 '15 at 01:08
  • While normally an ArrayList is unavoidable, in this case I could actually choose, which is why I'm asking the question. – bigcodeszzer Dec 21 '15 at 01:09
  • It sounds to me like you are keeping a running window for computing through a time series or something alike. If that's the case I recommend a circular buffer. – Alex Suo Dec 21 '15 at 01:19
  • 1
    It is unlikely that any performance issues you may have is caused by using `ArrayList` instead of a plain array. Don't complicate your code for this, unless a Profiler shows you that the `ArrayList` is causing performance degradation. – Andreas Dec 21 '15 at 01:19
  • If @AlexSuo is right, and you're using a circular buffer, you should use an `ArrayDeque`. It's very efficient for that purpose. – Andreas Dec 21 '15 at 01:20
  • @AlexSuo Essentially yes, but I'm more concerned about how to store the results. As for the actual window, I was just going to use a stack. – bigcodeszzer Dec 21 '15 at 01:22
  • A static stack that is. – bigcodeszzer Dec 21 '15 at 01:23
  • @Andreas You right really, I should use a profiler first, but I'm also just curious about the question 'in theory' – bigcodeszzer Dec 21 '15 at 01:24
  • Actually, if you take a look at the api for `Stack` it says: "A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to this class." – azurefrog Dec 21 '15 at 01:28
  • @azurefrog Haven't gotten there yet. – bigcodeszzer Dec 21 '15 at 01:38
  • @azurefrog Those classes look like they are designed for dynamic stacks, mine is a static length – bigcodeszzer Dec 21 '15 at 01:40

3 Answers3

1

Any performance difference will not be visible, when you set initialCapacity on ArrayList. You say that your collection's size can never change, but what if this logic changes? Using ArrayList you get access to a lot of methods such as contains.

As other people have said already, use ArrayList unless performance benchmarks say it is a bottle neck.

scharette
  • 605
  • 1
  • 9
  • 25
m.aibin
  • 3,528
  • 4
  • 28
  • 47
1

The fastest way to iterate over bytes is as a single arrays. A faster way to process these are as int or long types as process 4-8 bytes at a time is faster than process one byte at a time, however it rather depends on what you are doing. Note: a byte[4] is actually 24 bytes on a 64-bit JVM which means you are not making efficient use of your CPU cache. If you don't know the exact size you need you might be better off creating a buffer larger than you need even if you are not using all the buffer. i.e. in the case of the byte[][] you are using 6x time the memory you really need already.

Peter Lawrey
  • 525,659
  • 79
  • 751
  • 1,130
  • Do you mean the byte size, or the number of bytes? I thought memory alignment occurred in multiples of 8 in Java? – bigcodeszzer Dec 21 '15 at 18:05
  • @bigcodeszzer The default memory alignment for objects is 8 bytes. However if you want a compact and efficient data structure you want a byte[] or similar for all the data so that each byte only uses byte. – Peter Lawrey Dec 22 '15 at 20:47
  • 1
    Oh I see, I guess I could do that and loop through with i+=4 or something. – bigcodeszzer Dec 23 '15 at 01:05
1

You right really, I should use a profiler first, but I'm also just curious about the question 'in theory'.

The "theory" is too complicated. There are too many alternatives (different ways to implement this) to analyse. On top of that, the actual performance for each alternative will depend on the the hardware, JIT compiler, the dimensions of the data structure, and the access and update patterns in your (real) application on (real) inputs.

And the chances are that it really doesn't matter.

In short, nobody can give you an answer that is well founded in theory. The best we can give is recommendations that are based on intuition about performance, and / or based on software engineering common sense:

  • simpler code is easier to write and to maintain,

  • a compiler is a more consistent1 optimizer than a human being,

  • time spent on optimizing code that doesn't need to be optimized is wasted time.

1 - Certainly over a large code-base. Given enough time and patience, human can do a better job for some problems, but that is not sustainable over a large code-base and it doesn't take account of the facts that 1) compilers are always being improved, 2) optimal code can depend on things that a human cannot take into account, and 3) a compiler doesn't get tired and make mistakes.

Stephen C
  • 698,415
  • 94
  • 811
  • 1,216