假设我们有一个这样的整数数组：
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 技巧，或者这是处理器的最佳代码？
对于您最初有 0 和 1 的特定情况，以下可能会更快。您必须对其进行基准测试。不过，使用纯 C 语言可能无法做得更好。如果您想利用可能存在的“x86 诡计”，您可能需要深入组装。
for(int i = 0; i < size ; i++){
array[i] *= 123456;
}
基准代码：
#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-10ms*=版本：~1.3ms对于像您这样的小数组，尝试找到另一种算法是没有用的，如果值不是特定模式，那么简单的循环是唯一的方法。
但是，如果您有一个非常大的数组（我们说的是几百万个条目），那么您可以将工作拆分为线程。每个单独的线程处理整个数据集的一小部分。
您可能还想对此进行基准测试：
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 解决方案相当或略胜一筹。不过，它更具可读性和灵活性。例如，它可以使用值不同于 0 和 1 的 array[i]。
底线，基准测试并查看反汇编。
该数组足够小，可以放入缓存中，因此使用 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，则可以将 SchighSchagh 的乘法技巧与pmulld.
这是一些用于分析各种版本算法的 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 使用 a if()...，C 使用乘法，harold 的 simd 版本和我的 simd 版本。
多次运行它（请记住，在分析时，您应该对多次运行的结果进行平均）除了分支版本明显较慢之外，所有版本之间几乎没有区别。
这并不奇怪，因为算法对每个内存项所做的工作很少。这意味着真正的限制因素是 CPU 和内存之间的带宽，CPU 一直在等待内存赶上，即使 cpu 帮助预取数据（ia32 线性检测和预取数据）。
这可能会更快。
for(int i = 0; i < size ; i++){
array[i] = ((123456 << array[i]) - 123456);
}
编辑：将按位运算更改为左移。
您可以使用另一个数组或其他一些数据结构来跟踪您设置为 1 的元素的索引，然后只访问这些元素。如果只有少数元素设置为 1，这将最有效
另一种加快数组分配的方法可以使用 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 个时钟周期。