0

I am writing some performance critical Java Code and I am really no Java expert, to say this in advance.

I work with a model in which nearly all information can be calculated from the positions of non-zero entries in a changing array of about ~1000 integers (most of them zero). To reduce these calculations I am working on algorithms, that update the informations in constant time, when the array changes instead of recalculating them. This could lead to a lot of code like

...
info1[x][y][a] = ...
info1[x][x%2+y][b] = ...
if( info3[x][y][c]!=0 )
    info2[x][y] = ...
if( some condition involving ~10 array entries) {
/** some expensive algorithm that is hopefully called rarely **/
}
info3[x][y] = ...
...

So i expect maybe 10 of such consecutive and mainly independent array writes with minimal calculations which will make up a very large portion of the lines the program has to run through. Should I expect the number of such simple consecutive operations to be relevant or does Java have means to execute 20 consecutive simple array writes about as fast as it can execute 10 or 2?

user2426460
  • 15
  • 4
  • first thing that comes to my mind - use `Thread`s (especially if data is uncorrelated) – alex May 27 '13 at 22:47
  • The task is already paralleled in a larger context and the machines i expect to use for this won't have more than 4 cores. – user2426460 May 27 '13 at 22:52
  • 2
    An array write takes less than 5 nanoseconds on a standard desktop PC (i.e. you can perform 200 million writes per second). So 20 calls vs. 2 calls means 100 ns vs 10 ns. What *might* improve performance is to flatten the array (instead of `int[10][10][10]`, have a `int[1000]` and manually calculate the right index). Bottom line: profile your application. – assylias May 27 '13 at 22:57
  • 4
    You are falling into the trap of "optimising early". Implement something that works, **if** there's a performance problem, profile your code, and only *then* code something special for performance. – Bohemian May 27 '13 at 23:10
  • Thanks for that warning but this information is important to chose between incompatible approaches for a task of which I know for sure that it is performance critical because the program does nothing else than this for about 10^x times and it has to compete with other programs for the same purpose. – user2426460 May 28 '13 at 11:33
  • @assylias: thank you for the advice, I did some testing and at least in my example this speeded up the sequential array writes by ~50% (8 writes per loop, 10^10 executions. 1-dimensional with manual index calculation instead of 3-dimensional). – user2426460 May 29 '13 at 06:57
  • @user2426460 That makes sense - in particular, if you have nested loops and manage to replace by one linear loop on the flatten array, you should get a better cache locality and therefore a better performance. Make sure [you have written your benchmark properly](http://stackoverflow.com/questions/504103/how-do-i-write-a-correct-micro-benchmark-in-java) though, as there are many potential pitfalls. – assylias May 29 '13 at 08:54

2 Answers2

1

Not entirely clear what your question is, so I'll cover several points:

  • An array write is only a little slower than an array read. The operations of interest are (a) the array bounds check, (b) the array index calculation (basically multiplying by 4 - trivial), and the actual load/store.
  • Having multiple (number "N") short array assignment statements in a single straight-line code block is not a problem. At worst it's N times the work of the single statement.
  • Having "deep" multiple-dimension arrays is not a big deal either -- if you have a 3-dimension array, eg, a store to that looks like 2 array reads and one write.
  • For all of these scenarios the JITC will "love" simple array-intense code. There is lots of opportunity to "common" array bounds checks, array index calculations, etc, and even mediocre JITCs will do a pretty good job of this.
  • The one thing you need to watch out for, with very large arrays and long-running code, is the memory footprint, especially if you're multi-threading. Doing "sparse" updates to very large (multi-megabyte) arrays "dirties" a lot of cache lines and virtual memory pages, and, for the multi-threaded case, cache synchronization (if you somehow manage to arrange it) can become a bottleneck. But for only a few thousand array entries this is nowhere near being an issue.
Hot Licks
  • 47,103
  • 17
  • 93
  • 151
0

The actual process or reading and writing 20 elements of an array should not be much of a performance issue, although it would depend on how the code is performance critical. I would try the implementation you have to see if it meets your requirements, I believe the array data structure should be fast enough for most performance optimised tasks that are done in Java.

Source: recently working on re-implementing ArrayList for university work.