Быстрый способ замены элементов в массиве - C
Скажем, у нас есть массив таких как:
const int size = 100000;
int array[size];
//set some items to 0 and other items to 1
Я бы хотел заменить все элементы, которые имеют значение 1 с другим значением, например 123456.
Это может быть тривиально реализовано с помощью:
for(int i = 0; i < size ; i++){
if(array[i] != 0)
array[i] = 123456;
}
Из любопытства, есть ли более быстрый способ сделать это, каким-то хитростью x86, или это лучший код для процессора?
Ответы
Ответ 1
В вашем конкретном случае, когда вы изначально имели 0 и 1, следующее может быть быстрее. Вам нужно будет это обозначить. Вы, вероятно, не можете сделать намного лучше с простым C, хотя; вам может понадобиться погрузиться в сборку, если вы хотите воспользоваться "обманом x86", который может существовать.
for(int i = 0; i < size ; i++){
array[i] *= 123456;
}
EDIT:
Код контрольной точки:
#include <time.h>
#include <stdlib.h>
#include <stdio.h>
size_t diff(struct timespec *start, struct timespec *end)
{
return (end->tv_sec - start->tv_sec)*1000000000 + end->tv_nsec - start->tv_nsec;
}
int main(void)
{
const size_t size = 1000000;
int array[size];
for(size_t i=0; i<size; ++i) {
array[i] = rand() & 1;
}
struct timespec start, stop;
clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &start);
for(size_t i=0; i<size; ++i) {
array[i] *= 123456;
//if(array[i]) array[i] = 123456;
}
clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &stop);
printf("size: %zu\t nsec: %09zu\n", size, diff(&start, &stop));
}
мои результаты:
Компьютер: четырехъядерный процессор AMD Phenom @2.5GHz, Linux, GCC 4.7, скомпилированный с
$ gcc arr.c -std=gnu99 -lrt -O3 -march=native
-
if версия: ~ 5-10 мс
-
*= версия: ~ 1,3 мс
Ответ 2
Для небольшого массива, такого как ваш, нет смысла пытаться найти другой алгоритм, и если значения не находятся в определенном шаблоне, простой цикл - это единственный способ сделать это в любом случае.
Однако, если у вас очень большой массив (мы говорим о нескольких миллионах записей), вы можете разделить работу на потоки. Каждый отдельный поток обрабатывает меньшую часть всего набора данных.
Ответ 3
Вы также можете сравнить это:
for(int i = 0; i < size ; i++){
array[i] = (~(array[i]-1) & 123456);
}
Я запускаю его через те же тесты, что и SchighSchagh, с небольшой или никакой разницей в моей настройке. Однако он может отличаться от вашего.
РЕДАКТИРОВАТЬ: Остановить прессы!
Я только что вспомнил, что x86 может "разворачивать" троичные операторы, если аргументы между ":" - это константы. Рассмотрим следующий код:
for(size_t i=0; i<size; ++i) {
array[i] = array[i] ? 123456 : 0;
}
Похоже на ваш оригинальный код, не так ли? Хорошо, демонтаж показывает, что он был скомпилирован без каких-либо ветвей:
for(size_t i=0; i<size; ++i) {
00E3104C xor eax,eax
00E3104E mov edi,edi
array[i] = array[i] ? 123456 : 0;
00E31050 mov edx,dword ptr [esi+eax*4]
00E31053 neg edx
00E31055 sbb edx,edx
00E31057 and edx,1E240h
00E3105D mov dword ptr [esi+eax*4],edx
00E31060 inc eax
00E31061 cmp eax,5F5E100h
00E31066 jb wmain+50h (0E31050h)
}
По производительности это кажется на первый взгляд или немного лучше, чем мое оригинальное решение SchighSchagh. Это более читаемо и более гибко. Например, он может работать с массивом [i] со значениями, отличными от 0 и 1.
Нижняя строка, контрольная точка И загляните в разборку.
Ответ 4
Массив достаточно мал, чтобы он входил в кеш, поэтому стоит использовать SIMD: (не проверено)
mov ecx, size
lea esi, [array + ecx * 4]
neg ecx
pxor xmm0, xmm0
movdqa xmm1, [_vec4_123456] ; value of { 123456, 123456, 123456, 123456 }
_replaceloop:
movdqa xmm2, [esi + ecx * 4] ; assumes the array is 16 aligned, make that true
add ecx, 4
pcmpeqd xmm2, xmm0
pandn xmm2, xmm1
movdqa [esi + ecx * 4 - 16], xmm2
jnz _replaceloop
Возможно, разворачивается на 2.
Если у вас SSE4.1, вы можете использовать трюк ShighSchagh с pmulld.
Ответ 5
Здесь некоторый код Win32 для профилирования различных версий алгоритма (скомпилированный с использованием VS2010 Express с использованием сборки по умолчанию): -
#include <windows.h>
#include <stdlib.h>
#include <stdio.h>
const size_t
size = 0x1D4C00;
_declspec(align(16)) int
g_array [size];
_declspec(align(16)) int
_vec4_123456 [] = { 123456, 123456, 123456, 123456 };
void Test (void (*fn) (size_t, int *), char *test)
{
printf ("Executing test: %s\t", test);
for(size_t i=0; i<size; ++i) {
g_array[i] = rand() & 1;
}
LARGE_INTEGER
start,
end;
QueryPerformanceCounter (&start);
fn (size, g_array);
QueryPerformanceCounter (&end);
printf("size: %u\t count: %09u\n", size, (int) (end.QuadPart - start.QuadPart));
}
void Test1 (size_t size, int *array)
{
for(size_t i=0; i<size; ++i) {
array[i] *= 123456;
}
}
void Test2 (size_t size, int *array)
{
for(size_t i=0; i<size; ++i) {
if(array[i]) array[i] = 123456;
}
}
void Test3 (size_t array_size, int *array)
{
__asm
{
mov edi,array
mov ecx, array_size
lea esi, [edi + ecx * 4]
neg ecx
pxor xmm0, xmm0
movdqa xmm1, [_vec4_123456] ; value of { 123456, 123456, 123456, 123456 }
_replaceloop:
movdqa xmm2, [esi + ecx * 4] ; assumes the array is 16 aligned, make that true
add ecx, 4
pcmpeqd xmm2, xmm0
pandn xmm2, xmm1
movdqa [esi + ecx * 4 - 16], xmm2
jnz _replaceloop
}
}
void Test4 (size_t array_size, int *array)
{
array_size = array_size * 8 / 12;
__asm
{
mov edi,array
mov ecx,array_size
lea esi,[edi+ecx*4]
lea edi,[edi+ecx*4]
neg ecx
mov edx,[_vec4_123456]
pxor xmm0,xmm0
movdqa xmm1,[_vec4_123456]
replaceloop:
movdqa xmm2,[esi+ecx*4]
mov eax,[edi]
mov ebx,[edi+4]
movdqa xmm3,[esi+ecx*4+16]
add edi,16
add ecx,9
imul eax,edx
pcmpeqd xmm2,xmm0
imul ebx,edx
pcmpeqd xmm3,xmm0
mov [edi-16],eax
mov [edi-12],ebx
pandn xmm2,xmm1
mov eax,[edi-8]
mov ebx,[edi-4]
pandn xmm3,xmm1
imul eax,edx
movdqa [esi+ecx*4-36],xmm2
imul ebx,edx
movdqa [esi+ecx*4-20],xmm3
mov [edi-8],eax
mov [edi-4],ebx
loop replaceloop
}
}
int main()
{
Test (Test1, "Test1 - mul");
Test (Test2, "Test2 - branch");
Test (Test3, "Test3 - simd");
Test (Test4, "Test4 - simdv2");
}
Он получил для тестов: C с использованием if()..., C с использованием множительной версии harold simd и моей версии simd.
Запуск много раз (помните, что при профилировании вы должны усреднять результаты по нескольким прогонам), разница между всеми версиями, кроме ветвящейся, значительно меньше.
Это не удивительно, так как algortihm делает очень мало работы для каждого элемента памяти. Это означает, что реальным лимитирующим фактором является пропускная способность между ЦП и памятью, процессор постоянно ждет, пока память догонит, даже когда процессор помогает предварительно запрограммировать данные (данные ia32 определяют и предварительно отбирают данные линейно).
Ответ 6
Вы можете использовать другой массив или какую-либо другую структуру данных, чтобы отслеживать индексы элементов, которые вы установили в один, а затем только посещать эти элементы. Это будет работать лучше всего, если только несколько элементов, которые установлены на один
Ответ 7
Это может оказаться быстрее.
for(int i = 0; i < size ; i++){
array[i] = ((123456 << array[i]) - 123456);
}
EDIT: Изменена побитовая операция для сдвига влево.
Ответ 8
еще один способ ускорить назначение массива, вы можете использовать встроенную сборку c. Как ниже,
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
const int size = 100000;
void main(void) {
int array[size];
int value = 1000;
__asm__ __volatile__("cld\n\t"
"rep\n\t"
"stosl\n\t"
:
:"c"(size*4), "a"(value), "D"(array)
:
);
printf("Array[0] : %d \n", array[0]);
}
Это должно быть скорость, когда мы сравнивали с простой программой c для назначения значений массива. А также команда stosl занимает 4 такта.
