0

Right now I am optimizing my code but I am really stuck. I tracked down the time needed to run several commands and came to the conclusion that accessing a 3 dimensional array 'costs' the most time.

array1 is [Struct Data type], array2 is [[[UInt8]]]

I use:

for a in 0 ..< 600 {
    for b in 0..< 900 {
        array1[counter] = Struct(s:array2[var1][var2][var3])
    }
}

I used:

for a in 0 ..< 600 {
    for b in 0..< 900 {
         array1[counter] = Struct(s:UInt8(123))
    }
}

which got me a huge boost but is useless. I therefore concluded that accessing array2 takes most time. The loop which includes the first sample runs in 0.025 Seconds and the second in 0.005 Seconds.

How can I access a 3 dimensional array faster? I tried to make it into an 1 dim array which caused a lot of trouble because it is not explicit which index to use. It also isn't quite faster as I use Swift 4 which already has optimization. Thank you very much for all your help!

  • 1
    Can we see your code? In addition to answering your specific question we might also be able to advise you whether there is a better solution. – Imran Nov 26 '17 at 19:49
  • var1, var2 and var3 stem from mathematical operations which are quite specific and hard to understand. I edited the code above so everything is included. –  Nov 26 '17 at 19:55
  • You said `array2` is a three dimensional array but you also say it's `[UInt8]`. That doesn't make sense. – Sulthan Nov 26 '17 at 19:59
  • 1
    Please could you give a slightly clearer example? In the code you show, the code inside of the loop doesn't depend on either `a` or `b`; it's possible that the compiler would just hoist that out of the loop and then eliminate the loop to begin with. You say `var1`, `var2` and `var3` "*stem from mathematical operations*", have you considered that those operations might be the bottleneck rather than the array access? I'm skeptical that indexing into a three-deep nested array is significantly slower than a flat array. Also, just to check, you're building with optimisations enabled right? – Hamish Nov 26 '17 at 20:16
  • 2
    `[[[UInt8]]]` is not a three-dimensional array. It is an array-of-arrays-of-arrays. Each sub-array may be of a different size. That is not the same thing as a multi-dimensional array. Swift has no built-in multi-demensional array, but they're not difficult to build. See https://stackoverflow.com/questions/28936824/what-is-the-syntax-for-multidimensional-array-in-swift for a 2-dimensional example. (This relies on basically the same math as Imran's solution; it just packages it in a more convenient struct.) – Rob Napier Nov 26 '17 at 20:46
  • By the way, you talk about the above being slow. Is this on a debug build or release build? `Array` experiences substantial performance difference on debug and release builds, the latter being much faster. Before you go down the road of trying to optimize your code, make sure that the performance issue doesn't largely disappear with a release build (modified by editing your "scheme"). – Rob Nov 26 '17 at 21:06

1 Answers1

3

If you want to represent a 3d array of dimensions (nX,nY,nZ) as a 1d array use this conversion:

a_3d[x][y][z] <-> a_1d[nY*nX*z + nX*y + x]

For example for a 3x4x5 array:

a_3d[1][2][3] corresponds to a_1d[4*3*3+3*2+1] = a_1d[43]
Imran
  • 12,950
  • 8
  • 64
  • 79
  • What performance increases does this bring? Also you can reach some indexes (in your example 43) by two different sets of numbers (x,y and z). Thats what I meant by saying it is not explicit. –  Nov 26 '17 at 20:09
  • What do you mean you can reach some indexes by two different sets of numbers? Can you provide an example? – Imran Nov 26 '17 at 20:10
  • 1
    @Imran You mean `+ x`, not `+ n_x` at the end, right? Also note that Swift convention is `lowerCamelCase` for variable names, not `snake_case`. – Hamish Nov 26 '17 at 20:25
  • 1
    `Imran` is using 1 dimensional array which uses contigious memory.. Accessing it as such is much faster than using an array of array of arrays which would most likely have a reference to each array dimension (3 allocations). It would have to offset into each row to get the correct value. https://stackoverflow.com/a/17260025/1462718 – Brandon Nov 26 '17 at 20:42
  • So does the Speed improvement in using a 1d Array adress Swift 4, too? I think I remember someone at the WWDC saying they reduced the differences between 1d and multidimensional arrays concerning speed? –  Nov 26 '17 at 21:38
  • Here it says with Swift 4 using an 1d Array is as fast as using an array of arrays. What can we do now to improve speed? https://stackoverflow.com/questions/27139437/most-efficient-way-to-access-multi-dimensional-arrays-in-swift –  Nov 26 '17 at 21:46
  • Again, it's very hard to say without seeing the rest of your code or understanding what you are trying to accomplish outside of this loop. The loop itself seems hard to improve, but maybe you can come up with a [vectorized](https://en.wikipedia.org/wiki/Array_programming) implementation instead of a double loop. This is just one of many ideas we might be able to suggest if we knew more about what you were trying to accomplish. – Imran Nov 27 '17 at 07:31