Я сейчас считаю, что сравнивать каждое число с 3-8 по мере его добавления
Нет, вы сильно усложняете это. Вы не хотите выполнять линейный поиск j (индекс по счетчикам), например arr[i] == j, просто используйте j = arr[i].
Стандартный способ построения гистограммы - ++counts[ arr[i] ]. В вашем случае вы знаете, что возможные значения - 3..8, поэтому вы можете сопоставить значение массива с ведром счетчика с помощью arr[i] - 3, поэтому вы будете работать с counts[0..5]. Команда назначения памяти add с режимом адресации с масштабированным индексом может сделать это в одной инструкции x86 , учитывая значение элемента в регистре.
Если возможные значения не являются смежными , вы обычно используете таблицу ha sh для сопоставления значений для подсчета сегментов. Вы можете думать об этом простом случае как о тривиальной функции ha sh.
Поскольку вы генерируете случайные числа для заполнения arr[i] одновременно с гистограммой, вы можете комбинировать их две задачи, и вместо вычитания 3 просто еще не добавляйте его.
; inputs: unsigned len, int *values, int *counts
; outputs: values[0..len-1] filled with random numbers, counts[] incremented
; clobbers: EAX, ECX, EDX (not the other registers)
fill_array_and_counts:
push ebp
mov ebp, esp
push esi ; Save/restore the caller's ESI.
;; Irvine32 functions like RandomRange are special and don't clobber EAX, ECX, or EDX except as return values,
;; so we can use EDX and ECX even in a loop that makes a function call.
mov edi, [ebp + 16] ; int *counts ; assumed already zeroed?
mov edx, [ebp + 12] ; int *values ; output pointers
mov ecx, [ebp + 8] ; size_t length
MakeArray: ; do{
mov eax, UPPER - LOWER + 1 ; size of random range, calculated at assemble time
call RandomRange ; eax = 0 .. eax-1
add dword ptr [edi + eax*4], 1 ; ++counts[ randval ]
add eax, LOWER ; map 0..n to LOWER..UPPER
mov [edx], eax ; *values = randval+3
add edx, 4 ; values++
dec ecx
jnz MakeArray ; }while(--ecx);
pop edi ; restore call-preserved regs
pop ebp ; including tearing down the stack frame
ret
Если вызывающий не обнуляет массив counts за вас, вы должны сделать это самостоятельно, возможно, с помощью rep stosd с EAX = 0 как memset элементов двойного слова ECX, а затем перезагрузите EDI и ECX из аргументов стека.
Я предполагаю, что UPPER и LOWER - это константы времени сборки, например UPPER = 8 или LOWER equ 3, поскольку вы использовали для них имена в верхнем регистре, и они не являются аргументами функций. В таком случае нет необходимости выполнять математические вычисления во время выполнения, просто позвольте ассемблеру вычислить UPPER - LOWER + 1 за вас.
Я избегал инструкции loop , потому что она медленная , и не делает того, что нельзя сделать с другими простыми инструкциями.
Один стандартный трюк с производительностью для гистограмм с несколькими сегментами - иметь несколько массивов счетчиков и разворачивать их: Способы векторизации гистограммы в SIMD? . Это скрывает задержку сохранения / перезагрузки, когда один и тот же счетчик должен увеличиваться несколько раз подряд. Однако ваши случайные значения, как правило, позволяют избежать длинных прогонов одного и того же значения, поэтому производительность в наихудшем случае избегается.
Для больших массивов может быть что-то выиграть от AVX2, поскольку существует только 6 возможных блоков: * Микрооптимизация гистограммы с 4 ведрами большого массива или списка . (И вы можете сгенерировать случайные числа в векторах SIMD с помощью AVX2 xorshift128 + PRNG, если хотите.)