1

My code requires me to create a large (301x301x19 items) ArrayList that has some initial values (some are 0, some are 1, etc) every time I call a function. The starting values are always the same and need to be loaded into the array every time the function is called so that the function has its own copy of these initial values to mess with.

Originally I was recalculating the array every time the function was called, but that proved to be laughably slow; instead, I am now calculating the initial array only once and am making local copies of it every time the function is called (so that I can change the values without changing the initial array's values).

However, copying the array is still proving to be prohibitively slow (well over 3/4ths of the computation time is spent just copying this array). I have tried the following:

// oldList is an ArrayList<Byte>
ArrayList<Byte> newList = new ArrayList<Byte>(oldList);

// oldList is an ArrayList<Byte>
ArrayList<Byte> newList = new ArrayList<Byte>();
newList.addAll(oldList);

// oldList is a Byte[]
ArrayList<Byte> newList = new ArrayList<Byte>(Arrays.asList(oldList));

All of these methods are simply too slow for my application; is there any faster technique to do this or am I out of luck?

Ingulit
  • 1,141
  • 1
  • 10
  • 20
  • 1
    Holding bytes in arrays in memory is not effective computing. I would be interested in why you had to use arrays / lists? If you can possibly do so, use the Stream classes – ne1410s Sep 23 '14 at 20:07
  • possible duplicate of [How to effectively copy an array in java?](http://stackoverflow.com/questions/2589741/how-to-effectively-copy-an-array-in-java) – bovino Marcelo Bezerra Sep 23 '14 at 20:10
  • Do you always modify all the values? Isn't there some pattern of invariance you can exploit and save on copying? – biziclop Sep 23 '14 at 20:21
  • 1
    Having said that, you can start by replacing the `ArrayList` with a simple byte array. – biziclop Sep 23 '14 at 20:26
  • 1
    use byte[] rather than ArrayList –  Sep 23 '14 at 20:42

1 Answers1

4

In summary:

  1. Aim to design out the need to copy so many large data structures (a hard problem, I know)
  2. Avoid pointer chasing, use arrays rather than ArrayLists. If your objects contain other objects, try to replace them with primitives. The ultimate here is to reduce to an array of primitives, such as a byte array
  3. Compact your data structures, use arrays, smaller types; the goal is to gain the same amount of benefit from copying less actual bytes
  4. Use System.arrayCopy
  5. If you still want to go still faster, then take memory layout and responsibility away from the JVM and use sun.misc.Unsafe directly (otherwise known as 'running with scissors')

Changing to a more easily copied data structure, and using System.arraycopy is going to be about as fast as you can get with the approach that you outlined in your question.

System.arraycopy is implemented as a native call. Most JVM providers will have prepared a native version that makes use of native instructions to accelerate the memory copying.

Unfortunately copying large regions of memory has unintended side effects within the JVM, mostly around the Garbage Collector.

  1. during a mem copy the JVM cannot access a safe point, this prevents STW GC from starting
  2. GC not starting causes threads that did pay attention to the safe point to wait longer, creating weird stalls on threads that have nothing to do with this work
  3. a large array may not fit within the TAB (a thread local buffer used to accelerate object allocations), meaning that object allocation slows down as it enters special case code

  4. large objects increase the likelihood of premature tenuring during GC cycles, which increases the frequency of more costly older gen/full GCs (in oppose to the cheaper young gen GCs)

    • NB: for the above effects to be seen, we must be talking about very high rates of allocations and discardings. Most algorithms that do a few allocations and copies here and there will not see these problems; modern JVMs can even cope with fairly high rates, these problems do not occur until a threshold is exceeded and plates that we had been spinning on poles start to hit the floor.
Chris K
  • 11,622
  • 1
  • 36
  • 49
  • I think, while direct memory access is an interesting option, it's a complete overkill in this case. – biziclop Sep 23 '14 at 20:59
  • @biziclop that is good to hear, it should always be an approach of last resort; that said, also do not under estimate how much faster it can be. I have seen improvements of > 8 times with such techniques. – Chris K Sep 23 '14 at 21:01
  • As usual when optimising, know how fast you need the code to go and measure and adjust frequently. – Chris K Sep 23 '14 at 21:06