Quick comparison of arrays in iOS

Question

I need to move a small 2D array of values ​​around a much larger 2D array of values ​​and set any values ​​of the larger array that are larger than the corresponding values ​​in the smaller array, for the values ​​of the smaller array. Think about composing images, sort of, but using two 2D arrays of floats. I need to do this several times faster than possible. It’s just interesting if there is some optimization method using NEON Assembly, Accelerate framework or any other method that I have not heard about. Will something be much faster than a double nested loop to compare and replace values? For example, it might be faster to store values ​​as a 1D array instead of a 2D array? Or is it faster to access the values ​​row by row rather than by each column? Just trying to squeeze out any extra speed I can get, but don’t know how to do it.

Answer 1

I do not know any features in the Accelerate infrastructure that will do what you want. You can definitely use NEON to speed it up without going directly to assembly language, using the built-in vmin_f32 to process two pairs of floats at a time, or using vminq_f32 to process four pairs at a time.

These links may help you get started with the built-in functions, but I have no better advice for you:

How to use multiply and accumulate internals in ARM Cortex-a8?

ARM Information Center - NEON Intrinsics
Optimization of ARM NEON. Example

I found them on the googling neon intrinsics tutorial .

In addition, the developer toolkit includes some documentation on the ARM architecture:

Xcode 4.2: /Developer/Library/PrivateFrameworks/DTISAReferenceGuide.framework/Versions/A/Resources/ARMISA.pdf
Xcode 4.3: /Applications/Xcode.app/Contents/Applications/Instruments.app/Contents/Frameworks/DTISAReferenceGuide.framework/Versions/A/Resources/ARMISA.pdf

Answer 2

If you need to compare one-dimensional arrays of C structs , you can try memcmp() to see if this is a more efficient for loop. If you can afford some kind of hash array, you can significantly improve performance for cases where arrays are different. For example, if you have an array of floats, you can use their sum as a hash. If the hashes of arrays are different, you do not need to compare arrays at all. On the other hand, if you expect arrays to actually be equal in most cases, computing a hash will only slow things down.

Being creative with hash calculation can also help. In the case of 2D arrays, the hash can be a polynomial of the hashes of a 1D array or even a struct with metadata such as array sizes, hash hashes of 1D arrays, etc.

EDIT: on my machine, memcmp() about 2 times faster than a straightforward single-threaded for loop when comparing large arrays of floats in the worst case (when the arrays are equal).