[RESOLVED] speed improvement in multidimensional array mod

[andreaconsole]

Hi to everyone,
I suppose that the answer is "no way", but "asking is for free"...

I have a 3D array and I need to divide by a vixed value (256) every element of the array.
I'd like to do it in a faster way than using "nested for" code like this

for i=0 to x
    for j=0 to y
        for k=0 to z
             a(i,j,k)=b(i,j,k)\256
        next k
    next j
next i

is there any possibility?

[MartinLiss]

Instead of using a 3D array, how about using a UDT like

Private Type MyType
    a As Integer
    b As Integer
    c As Integer
End Type
Private MyTypeArray() As MyType

[andreaconsole]

it could be a good idea, but in my application i can't do it because I take the fist array from an object and I need to convert the values to use it with an API (CreateDIBitmap)

[Milk]

Have you tried changing the order of the loops? i.e. k, j, i, as opposed to i, j, k. One will be faster than the other because one will be sequential the other effectively random. I can't remember which would be best right now (am a bit tipsy) but I think it's the latter.

Its also possible to do a minor hack to allow VB to temporarily regard them as 1 dimensional, this would improve performance even move.

[andreaconsole]

Since I understand that there is no a general answer, I try to show my TEST code:
it's not definitive, but if you have any suggestion for optimizing it I will be happy

Private Sub Command2_Click()
Dim xsize As Long
Dim ysize As Long
Dim totsize As Long
Dim buffindex As Long
Dim bufferarray() As Long
Dim i As Long, j As Long   '<--- corrected


xsize = m_camera.CameraXSize
ysize = m_camera.CameraYSize
totsize = xsize * ysize 

ReDim bufferarray(xsize, ysize)
bufferarray = m_camera.ImageArray

ReDim byteBuffer(0 To totsize)

For i = 0 To xsize - 1
    buffindex = i * ysize
    For j = 0 To ysize - 1
        byteBuffer(buffindex + j) = bufferarray(i, j)
    Next j
Next i

For i = 1 To totsize
byteBuffer(i) = byteBuffer(i) \ 256   'make values compatible with bitmap (max ADU 255)
Next

paintImage 'paint image from bytebuffer in the picture. uses a pointer to bytebuffer

I have to add a dimension in the array in order to manage color images (now is for b&w)
paintimage is a sub that uses an API CreateDIBitmap. By now I don't know if the API works with multidimensional array so i linearized the first array, too...

[MartinLiss]

You don't seem to have defined x,y and z. If not then they are Variants and are very slow. Change them to Long.

[smUX]

You don't seem to have defined x,y and z. If not then they are Variants and are very slow. Change them to Long.

You might also have missed Dim i, j As Long...i is also variant as you have to define each variable individually so change that to Dim i As Long, j As Long too :-P

[Milk]

...as well, swap x to the inner loop that should also speed things up even more.

[andreaconsole]

You don't seem to have defined x,y and z. If not then they are Variants and are very slow. Change them to Long.

ok, i talked about x,y and z just to explain what I was saying at the beginning, but thank you for the suggestion. I usually try to avoid "variant" variables.

"Dim i, j As Long"

is an error, thanks for correcting me!
it should be as you said:
Dim i As Long, j As Long

[andreaconsole]

...as well, swap x to the inner loop that should also speed things up even more.

thanks, I didn't know there were any difference.
I'll try in future!

[Milk]

roughly 20%

[smUX]

roughly 20%

Would be useful for you to work out how many iterations it goes through by swapping the way it is set up...personally I don't believe it is going to make any difference because either way you have to work with the same amount of calculations. The only slight difference might be with the number of times the for/next lines are reached, but the main bulk of the speed is in the actual calculation being done :-)

[Merri]

Here is the hack Milk previously mentioned. If the result looks out-of-place then please note the Y and X may be in an incorrect order in the bufferArray and you may need to swap them around.

Option Explicit

Private Declare Sub PutMem4 Lib "msvbvm60" (ByVal Ptr As Long, ByVal Value As Long)
Private Declare Function VarPtrArray Lib "msvbvm60" (Arr() As Any) As Long



Private Sub Command2_Click()
    Dim xSize As Long
    Dim ySize As Long
    Dim totSize As Long
    Dim buffIndex As Long
    Dim bufferArray() As Long
    Dim i As Long, j As Long
    ' new: our array for a SAFEARRAY header and an array variable we apply the header to
    Dim lngHeader(5) As Long, hackBuffer() As Long
    
    xSize = m_Camera.CameraXSize
    ySize = m_Camera.CameraYSize
    totSize = xSize * ySize
    
    ' fix: remove one unused item for both dimensions
    ReDim bufferArray(xSize - 1, ySize - 1)
    bufferArray = m_Camera.ImageArray
    ' fix: remove one unused item
    ReDim bytebuffer(0 To totSize - 1)

    ' create a custom one dimensional SAFEARRAY
    lngHeader(0) = 1 ' one dimension
    lngHeader(1) = 4 ' Long = 32 bits = 4 bytes
    lngHeader(3) = VarPtr(bufferArray(0, 0)) ' array data location
    lngHeader(4) = totSize ' number of items in array
    
    ' use that header for array variable
    PutMem4 VarPtrArray(hackBuffer), VarPtr(lngHeader(0))
    
    ' then we do the simplest ever copy & process
    For i = 0 To totSize - 1
        ' hackArray points to the same data as bufferArray
        bytebuffer(i) = hackBuffer(i) \ 256
    Next i
    
    ' important to clean up before exiting procedure
    PutMem4 VarPtrArray(hackBuffer), 0

However it would be best if there was no multidimensional array in the first place, math for calculating indexes for X and Y with \ and Mod is insanely fast compared to using a multidimensional array (for internal VB6 reasons we do not have details of). The logic:

X = Index Mod Width
Y = Index \ Width
Index = Y * Width + X

[andreaconsole]

very very interesting code, Merri: this topic is becoming far more interesting than I expected!

However I found that the correct declaration is:

Private Declare Function VarPtrArray Lib "msvbvm60" Alias "VarPtr" (Arr() As Any) As Long

Moreover, I'd like to add that the original code, with optimizations you suggested, doesn't seem to be slower than yours, almost with arrays 1600x1600. Is it possible?

Private Sub Command2_Click()
Dim xSize As Long
Dim ySize As Long
Dim totSize As Long
Dim buffIndex As Long
Dim bufferArray() As Long
Dim fact As Integer
Dim i, j As Long

m_camera.StopExposure

xSize = m_camera.CameraXSize
ySize = m_camera.CameraYSize
totSize = xSize * ySize '262144
fact = m_camera.MaxADU \ 256

ReDim bufferArray(xSize - 1, ySize - 1)
bufferArray = m_camera.ImageArray
ReDim byteBuffer(0 To totSize - 1)

For i = 0 To xSize - 1
    buffIndex = i * ySize
    For j = 0 To ySize - 1
        byteBuffer(buffIndex + j) = bufferArray(i, j) \ fact
    Next j
Next i

paintImage 'paint image from bytebuffer in the picture

End Sub

[Milk]

Have a look a this thread

[Merri]

I don't know what code bufferArray = m_camera.ImageArray involves: it also may be a bottleneck. I find ReDim before it a bit confusing to tell the truth. Also, differences often only become more visible when the code is compiled. It is also good to tick on some advanced optimizations in the Compile tab, removing array overflow check makes things much much faster, but bad code may crash Windows.

[andreaconsole]

I don't know what code bufferArray = m_camera.ImageArray involves: it also may be a bottleneck. I find ReDim before it a bit confusing to tell the truth. Also, differences often only become more visible when the code is compiled. It is also good to tick on some advanced optimizations in the Compile tab, removing array overflow check makes things much much faster, but bad code may crash Windows.

reading m_camera.imagearray is the real bottleneck of this code: this is the reason I put the data in bufferarray. I didn't know that ReDim was superfluous, it works even without...

After compiling (and inverting i with j) I however found that the code with linearizated array is strangely slower than the other, and is much slower as the array dimension increases

Private Sub Command2_Click()
Dim xSize As Long
Dim ySize As Long
Dim totSize As Long
Dim buffIndex As Long
Dim bufferArray() As Long
Dim fact As Integer
Dim i As Long, j As Long   '<--- corrected AGAIN

m_camera.StopExposure

xSize = m_camera.CameraXSize
ySize = m_camera.CameraYSize
totSize = xSize * ySize '262144
fact = m_camera.MaxADU \ 256

'ReDim bufferArray(xSize - 1, ySize - 1)
bufferArray = m_camera.ImageArray
ReDim byteBuffer(0 To totSize - 1)

For j = 0 To ySize - 1
    buffIndex = j * xSize
    For i = 0 To xSize - 1
        byteBuffer(buffIndex + i) = bufferArray(i, j) \ fact
    Next i
Next j



paintImage 'paint image from bytebuffer in the picture

End Sub

PS I'm talking about compiled code

[Milk]

The slower version is likely be reading/writing the memory none sequentially, the faster sequentially. It makes a big difference much more than the 20% I drunkenly claimed last night. Your last example shows a Variant being used for i which I think Smux mentioned. Everything should be declared as Long.

I'm not sure how you benchmarked it but Merri's example is much faster than what you show in #14

Edit: What methods/properties does m_camera have? Does it have a Picture or hBmp property?

[andreaconsole]

I forgot to correct the declaration also in that sub...
However I benchmarked just making two different sub driven by two command button.
I found that the last code I posted is faster. To be accurate, I found that Merri's example is much slower the first time I press the button, then becames as fast as the previous, but never faster. I don't understand the reason for that, it's possible that my pc needs to be formatted indeed

[Milk]

I imagine you are getting those results because you are including things like m_camera.StopExposure and m_camera.ImageArray in the test. For meaningful results you should just try benchmarking the loop alone.