быстрое сравнение массивов в iOS

Question

Мне нужно перемещать небольшой 2D-массив значений вокруг гораздо большего 2D-массива значений и устанавливать любые значения большего массива, которые больше, чем соответствующие значения в меньшем массиве, до значений меньшего массива. Подумайте о компоновке изображений, вроде, но используя два 2D-массива поплавков. Мне нужно сделать это в несколько раз быстрее, чем это возможно. Просто интересно, есть ли какой-то способ оптимизации с помощью NEON Assembly, рамки Accelerate или какого-либо другого метода, о котором я не слышал. Будет ли что-то намного быстрее, чем двойной вложенный цикл для сравнения и замены значений? Например, возможно, было бы быстрее хранить значения как 1D-массив вместо 2D-массива? Или быстрее получить доступ к значениям по строкам, а не по каждому столбцу? Просто пытаясь выжать любую дополнительную скорость, которую я могу получить, но не знаю, как это сделать.

Answer 1

Я не знаю никаких функций в инфраструктуре Accelerate, которые будут делать то, что вы хотите. Вы можете определенно использовать NEON для ускорения его, не переходя непосредственно на язык ассемблера, используя vmin_f32, который может обрабатывать две пары поплавков за один раз, или используя vminq_f32 для обработки четырех пар за раз.

Эти ссылки могут помочь вам начать работу с помощью встроенных функций, но я на самом деле не имеют никакого лучший совет для вас:

How to use the multiply and accumulate intrinsics in ARM Cortex-a8?
ARM Information Center - NEON Intrinsics
ARM NEON Optimization. An Example

Я нашел тех, прибегая к помощи neon intrinsics tutorial.

Кроме того, пакет инструментов разработчика включает в себя некоторые ARM архитектуры документации:

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

Если вам нужно сравнить один-размерные C массивы structs, вы можете попробовать memcmp(), чтобы узнать, эффективнее ли он, чем цикл for. Если вы можете позволить себе какой-то хэш-массива, вы можете значительно повысить производительность для случаев, когда массивы отличаются. Например, если у вас есть массив поплавков, вы можете использовать их сумму как хэш. Если хэши массивов отличаются, вам не нужно сравнивать массивы вообще. С другой стороны, если вы ожидаете, что массивы на самом деле равны в большинстве случаев, вычисление хэша будет только замедлять работу.

Быть творческим с помощью расчета хэша также может помочь. В случае 2D массивов хэш может быть полиномом 1D хэшей массивов или даже struct с метаданными, как размеры массивов, хэш хэшей 1D массивов и т.д.

EDIT: на моей машине memcmp() примерно в 2 раза быстрее, чем прямолинейный однопоточный цикл for при сравнении больших массивов поплавков в наихудшем сценарии (когда массивы равны).