3

Context

I am implementing a seam carving algorithm.

I am representing the pixels in a picture as a 1D array

private int[] picture;

Each int represents the RGB of the pixel.

To access the pixels I use helper methods such as:

private int pixelToIndex(int x, int y) {return (y * width()) + x;}

The alternative would be to store in a 2D array:

private int[][] picture;

The seam carving algorithm has two parts.

Firstly, it does some image processing where it finds the horizontal or vertical connected seam with lowest energy. Here the pixel accesses jump around a bit across rows.

Secondly it removes this connected seam.

For vertical seams I mark the pixel to be removed with -1 and create a new picture array skipping the removed pixels like so:

int i = 0, j = 0;
while (i < temp.length) {
    if (picture[j] != -1) {
        temp[i++] = picture[j];
    }
    j++;
}
picture = temp;

For horizontal seams, given a specific column I shift all the pixels after the deleted pixel of that column up by one row as so:

for (int i = 0; i < temp.length; i++) {
    int row = indexToY(i);
    int col = indexToX(i);
    int deletedCell = seam[col];

    if (row >= deletedCell) temp[i] = picture[i + width()];
    else temp[i] = picture[i];
}
picture = temp;

The question

Obviously the 1D array uses less physical memory because of the overhead for each subarray but given the way I am iterating the matrix would the 2D array be more effectively cached by the CPU and thus more efficient?

How would the arrays differ in the way they would be loaded into the CPU cache and RAM? Would part of the 1D array go into the L1-cache? How would the 1D and 2D array be loaded into memory? Would it be dependent on size of the array?

david_adler
  • 9,690
  • 6
  • 57
  • 97
  • 2
    Why not isolate all changes behind a `createMatrix()`, `set(m, x, y)`, and `get(m, x, y)` -- and time both options (2D vs 1D) to see which one is faster? It would be trivial to remove this code for the most efficient-as-timed alternative in a few minutes, and you would be sure of your choice, as you could quote actual data applicable to your use-case. – tucuxi Apr 05 '16 at 14:20
  • You should consider what tucuxi said: Hide it behind some interface. Beyond that, one important hint: The layout (1D vs 2D) may affect the performance, but this will probably be negligible compared to the difference that is implied by the **iteration order**. So far more important than "1D vs 2D" is to make sure to nest loops like `for(y) for(x) { { pixelToIndex(x,y); }}` (instead of `for(x) for(y) ...`, referring to your suggested `pixelToIndex` implementation!). – Marco13 Apr 05 '16 at 14:59
  • And another hint, regarding an advantage of 1D arrays: They can be copied easily to the GPU. Seam Carving seems to be task that can nicely be implemented on the GPU, and if you want this, an 1D array is simpler to handle. (Maybe far fetched, but wanted to mention it) – Marco13 Apr 05 '16 at 15:01
  • The overhead of using a function call pixelToIndex for every pixel look up is going to vastly outweigh any benefit you might get by choosing 1D over 2D. – bhspencer Apr 05 '16 at 15:15
  • Are you sure about that @bhspencer? – david_adler Apr 05 '16 at 15:24
  • @david_adler you should profile it your self but yes, a function call adding a new frame to the stack is going to be more expensive than an index into an array. – bhspencer Apr 05 '16 at 16:10
  • Actually inlining with modern JIT JVMs make such function calls inexpensive. Ignore my comment. – bhspencer Apr 05 '16 at 17:32
  • Hi Sorry all for delaying, haven't looked at this post in a while reviewing now. – david_adler Aug 10 '17 at 07:02
  • @Marco13 RE: `is to make sure to nest loops like for(y) for(x) { { pixelToIndex(x,y); }}` Since I have to calculate horizontal and vertical seams the iteration order will be contrasting unless I transpose the matrix. For vertical seams I do perfect linear iteration row by row but for horizontal seams it is required that I iterate by column and therefore jump around a lot... – david_adler Aug 10 '17 at 07:07
  • This has been >1 year ago, I don't remember the context good enough. (It might be even worthwhile to transpose the data at the beginning before applying the algorithm, but that's something that you'd have to check - fortunately, it could *very* easily be switched on or off **iff** everything is hidden in an interface ;-)) – Marco13 Aug 10 '17 at 12:10

2 Answers2

2

An array of ints is just represented just as that: an array of int values. An array of arrays ... adds certain overhead. So, short answer: when dealing with really large amounts of data; plain 1-dimensional arrays are your friend.

On the other hand: only start optimizing after understanding the bottlenecks. You know, it doesn't help much to optimize your in-memory-datastructure ... when your application spends most of its time waiting for IO for example. And if your attempts to write "high performance" code yield "complicated, hard to read, thus hard to maintain" code ... you might have focused on the wrong area.

Besides: concrete performance numbers are affected by many different variables. So you want to do profiling first; and see what happens with different hardware, different data sets, and so on.

And another side note: sometimes, for the real number crunching; it can also be a viable option to implement something in C++ can make calls via JNI. It really depends on the nature of your problem; how often things will be used; response times expected by users; and so on.

GhostCat
  • 137,827
  • 25
  • 176
  • 248
  • This doesn't really answer the question at all. I was looking for in depth breakdown of what goes on under the hood when iterating multi dimensional arrays etc on a more generic level. Point taken I could do more profiling for my case but I was fishing for some theory. – david_adler Aug 10 '17 at 07:11
  • Thing is: with java, you don't have much of control. Most "relevant" aspects happen at runtime, and are defined by what the JIT implementation does for you. – GhostCat Aug 10 '17 at 07:57
1

Java has arrays of arrays for multi-dimensional arrays. In your case int[][] is an array of int[] (and of course int[] is an array of int). So, matrix is represented as a set of rows and pointers for each row. In this case it means that NxM matrix is occupying NxM for data and an array of pointers.

Since you can represent any matrix as an array you'll get less memory consumption storing it that way.

On the other hand address manipulation in case representing a 2D matrix as an arary is not that complex.

If we assume that you have a matrix that is NxM accessing and an Array with size NxM representing this matrix, yo can access element of Matrix[x,y] as Array[x*n+y].

Array[i] is compact and it has a high probability of being in L1 cache, or even in register cache.

Matrix[x,y] requires one memory read and addition Array[x*n+y] requires one multiplication and one addition.

So, I'll put my two cents on Array, but anyway it has to be tested (don't forget to wait for warming time for JIT compiler)

user987339
  • 10,519
  • 8
  • 40
  • 45
  • Thanks I sort of knew the above ^^ but well summarized. However, I was more interested in how iteration order interacts with the two data structures. I do however agree, the two options have to be profiled at the end of the day. – david_adler Aug 10 '17 at 07:16