求一个数组中元素的最大值和最小值

无心人 · 发表于 2010-12-22 09:28:02

读会同时读到cache，写直接写内存的
难道是读比写慢的原因

mathe · 发表于 2010-12-22 11:58:35

写也是到Cache,不一定到内存,所以像下面的代码:
初时x=0,y=0
线程1:
x=1;
y=1;
...
线程2:
if(y==1&&x==0){
...
}

线程2这个if中的内容是有可能被执行到的.

G-Spider · 发表于 2010-12-27 18:21:29

8# liangbch
奇怪，你说带宽为6.4GB/s ，你的read为6826MB/s >6.4GB/s ，难道还没有真正达到内存瓶颈？

liangbch · 发表于 2010-12-28 13:13:55

我认为，测试软件得到的结果并不是100%精确，他总是存在误差，所有9#的测试结果大于理论值。
我家那台老电脑是DDR400,但是实测内存带宽明显小于理论值。
11#的内存也是DDR400, 理论带宽是3.2GB/s,但11#给出的内存读性能却比理论值高出好多，竟达到4.1GB/s

G-Spider · 发表于 2010-12-28 13:56:11

24# liangbch
这样想就好了，呵呵，那个getMaxMin_SSE4 已在我这机子没啥潜力了，直接抱走。。

liangbch · 发表于 2011-1-1 23:16:48

1# liangbch

　采用32M的测试样本，运行在Intel I5-750 4核CPU，同时测试这6个函数。每个函数均取5次测试结果的最小值，结果如下：
getMaxMin1:    0.064071 seconds
getMaxMin_asm:  0.065478 seconds
getMaxMin_SSE4: 0.016766 seconds
getMaxMin_MT2_v1:    0.027156 seconds
getMaxMin_MT4_v1:    0.014782 seconds
getMaxMin_MT2_v2:    0.014681 seconds
getMaxMin_MT4_v4:    0.014684 seconds

liangbch · 发表于 2011-1-2 21:53:24

到目前为止，我编写了12个版本的求一个无符号整数数组的最大值和最小值的函数，函数名称和运行速度见下。
测试环境：i5-750四核CPU, DDR3-1333,2G内存, 测试的数据为32M个无符号整数,给出的时间值为5次测试的最小值。

getMaxMin1: 0.060888 秒
getMaxMin1_asm: 0.065483 秒
getMaxMin1_SSE4: 0.016788 秒
getMaxMin2: 0.128427 秒
getMaxMin2_asm1: 0.040059 秒
getMaxMin2_asm2: 0.040233 秒

getMaxMin_MT2_v1: 0.027078 秒
getMaxMin_MT4_v1: 0.014741 秒

getMaxMin_MT2_v2: 0.014625 秒
getMaxMin_MT4_v2: 0.014714 秒

getMaxMin_MT2_v3: 0.020532 秒
getMaxMin_MT4_v3: 0.014684 秒

函数getMaxMin1是一个最普通的版本，使用C语言书写，每个数需作2次比较，使用随机数据，CPU的分支预测部件预测成功的概率非常高。故速度很快。

函数getMaxMin1_asm是一个使用汇编语言书写的版本，使用 cmovb 指令消除分支，使得程序的性能与分支预测无关，速度得到保证，相比能够准确做分支预测的版本getMaxMin1，速度稍慢。测试结果表明，如果分支预测的正确率很高，消除分支并不能提高速度。

函数getMaxMin1_SSE4是一个使用汇编语言书写的版本，不同getMaxMin1_asm，这个函数使用SSE4 指令PMINUD和PMAXUD，一次可求4个DWORD的最大或者最小值，内存读则使用movdqa指令，一次读取4个DWORD，这个版本充分展示了SSE4指令的威力，速度竟达 getMaxMin1_asm 的四倍，几乎吃掉了整个内存带宽。

函数 getMaxMin2: 也是用C语言的书写的版本，每2数需要3次比较，比较次数较getMaxMin1更少，但是每2个数的3次比较中，第一次比较时是一个数据依赖的分支，CPU分支预测的准确率大约为50%，分支预测失败的惩罚大大降低了速度，速度仅为getMaxMin1的50%左右。

函数getMaxMin2_asm1：这个函数是 getMaxMin2的汇编版本，使用cmovb 指令消除了每2个数的3次比较，消除分子的效果非常明显，速度竟提高到300%。
函数getMaxMin2_asm2：这个函数也是 getMaxMin2的汇编版本，在每个循环步中，比getMaxMin2_asm1多了1条指令，但减少了内存访问，内存访问的减少并没有完全抵消一条mov指令的开销，速度和getMaxMin2_asm1大体相当，但多次测试的结果显示比getMaxMin2_asm1略慢。

后6个函数是2线程和4线程的版本。
getMaxMin_MT2_v1是getMaxMin1的2线程版本，速度提高到单线程版本的200%以上，在误差范围内，速度为单线程版本的2倍，和理论吻合。
getMaxMin_MT4_v1是getMaxMin1的4线程版本，速度提高到单线程版本的400%以上，在误差范围内，速度为单线程版本的4倍左右，和理论吻合。
getMaxMin_MT2_v2是getMaxMin1_SSE4的2线程版本，速度仅仅提高13%,一个线程的getMaxMin1_SSE4函数几乎吃到了整个内存带宽，故getMaxMin_MT2_v2性能的提高受限于内存带宽，并没有达到单线程版本的200%。
getMaxMin_MT4_v2是getMaxMin1_SSE4的4线程版本，速度和双线程版本getMaxMin_MT2_v2相同。性能的提高受限于内存带宽，并没有达到单线程版本的400%。
getMaxMin_MT2_v3是getMaxMin2_asm1的2线程版本，速度为单线程版本的195%，在误差范围内，速度为单线程版本的2倍，和理论吻合。
getMaxMin_MT4_v3是getMaxMin2_asm1的4线程版本，性能的提高受限于内存带宽，并没有达到单线程版本的400%。

以下4个多线程版本函数的性能几乎完全相同，而且实际性能都小于理论值，说明多线程函数的执行单元虽然是独立的，但他们共享相同的物理内存，多线程并行的性能受限于内存的总带宽，当总的内存存取达到物理内存带宽的限制，增加线程数并不能提高实际性能。
getMaxMin_MT4_v1: 0.014741 秒
getMaxMin_MT2_v2: 0.014625 秒
getMaxMin_MT4_v2: 0.014714 秒
getMaxMin_MT4_v3: 0.014684 秒

liangbch · 发表于 2011-1-2 22:06:50

给出6个单线程函数的源代码

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "defs.h"
#include "findMaxMin.h"
void getMaxMin1(DWORD *pData,int len,DWORD *min,DWORD *max)
{
int i;
*min=~0;
*max=0;
for (i=0; i<len; i++)
{
if ( pData[ i ] > *max)
*max=pData[ i ];
if (pData[ i ]< *min)
*min=pData[ i ];
}
}
void getMaxMin1_asm(DWORD *pData,int len,DWORD *min,DWORD *max)
{
DWORD _min, _max;
__asm
{
mov esi, pData
mov ecx, len
lea edi, [esi+ecx*4]
mov eax, 0xffffffff //min
mov edx, 0 //max
loop_start:
cmp esi, edi
jge next10
cmp [esi], eax
cmovb eax,[esi]
cmp [esi], edx
cmova edx,[esi]
add esi, 4
jmp loop_start
next10:
mov _min, eax
mov _max, edx
}
*min=_min;
*max=_max;
}
void getMaxMin2(DWORD *pData,int len,DWORD *min,DWORD *max)
{
int i;
if (len % 2 ==0 )
{
if ( pData[0] > pData[1] )
{
*max= pData[0];
*min= pData[1];
}
else
{
*max= pData[1];
*min= pData[0];
}
i=2;
}
else
{
*max= *min= pData[0];
i=1;
}
for (;i<len;i+=2)
{
if ( pData[ i ] > pData[ i+1] )
{
if ( pData[ i ]> *max)
*max=pData[ i ];
if ( pData[ i+1]< *min)
*min=pData[ i+1];
}
else
{
if ( pData[ i ] < *min)
*min=pData[ i ];
if ( pData[ i+1]> *max)
*max=pData[ i+1];
}
}
}
void getMaxMin2_asm1(DWORD *pData,int len,DWORD *min,DWORD *max)
{
DWORD _min, _max;
__asm
{
mov esi, pData
mov ecx, len
lea edi, [esi+ecx*4]
and ecx,1
jz next10
//next00: next % 2 ==1
mov eax, [esi]
mov edx, [esi]
add esi,4
jmp next20
next10: // len % 2 ==0
mov eax,[esi] // eax: min
mov edx,[esi+4] // edx, max
cmp eax,edx
jb next15
xchg eax,edx
next15:
add esi,8
jmp next20
loop_start:
mov ebx, [esi] //ebx=min(pData [i] , pData [ i+1]
mov ecx, [esi+4] //ebx=max(pData [i] , pData [ i+1]
cmp ebx, ecx
cmova ebx, [esi+4]
cmova ecx, [esi]
cmp eax, ebx
cmova eax, ebx
cmp edx, ecx
cmovb edx, ecx
add esi, 8
next20:
cmp esi, edi
jb loop_start
mov _min, eax
mov _max, edx
}
*min=_min;
*max=_max;
}
_declspec(naked)
void getMaxMin2_asm2(DWORD *pData,int len,DWORD *min,DWORD *max)
{
#define PAR_PDATA 4
#define PAR_LEN 8
#define PAR_MIN 12
#define PAR_MAX 16
#define REG_MIN esi
#define REG_MAX edi
#define REG_CUR_TMP ecx
#define REG_CUR_MIN eax
#define REG_CUR_MAX edx
#define REG_PDATA ebx // pData
#define REG_PEND ebp // pData+len
__asm
{
push ebx
push ebp
push esi
push edi
mov REG_PDATA, dword ptr[esp+16+PAR_PDATA]
mov ecx,dword ptr[esp+16+PAR_LEN]
test ecx,1
jz next10
//next00: next % 2 ==1
lea REG_PEND, [REG_PDATA+ecx*4]
mov REG_MIN, [REG_PDATA]
mov REG_MAX, [REG_PDATA]
add REG_PDATA,4
jmp next20
next10: // len % 2 ==0
lea REG_PEND, [REG_PDATA+ecx*4]
mov REG_MIN,[REG_PDATA]
mov REG_MAX,[REG_PDATA+4]
cmp REG_MIN,REG_MAX
jb next15
xchg REG_MIN,REG_MAX
next15:
add REG_PDATA,8
jmp next20
loop_start:
mov REG_CUR_MIN, [REG_PDATA] //ebx=min(pData [i] , pData [ i+1]
mov REG_CUR_MAX, [REG_PDATA+4] //ebx=max(pData [i] , pData [ i+1]
cmp REG_CUR_MIN, REG_CUR_MAX
mov REG_CUR_TMP, REG_CUR_MIN
cmova REG_CUR_MIN, REG_CUR_MAX
cmova REG_CUR_MAX, REG_CUR_TMP
cmp REG_MIN, REG_CUR_MIN
cmova REG_MIN, REG_CUR_MIN
cmp REG_MAX, REG_CUR_MAX
cmovb REG_MAX, REG_CUR_MAX
add REG_PDATA, 8
next20:
cmp REG_PDATA, REG_PEND
jb loop_start
mov eax, [esp+16+PAR_MIN]
mov edx, [esp+16+PAR_MAX]
mov [eax], REG_MIN
mov [edx], REG_MAX
pop edi
pop esi
pop ebp
pop ebx
ret
}
}
_declspec(naked)
void getMaxMin1_SSE4(DWORD *pData,int len,DWORD *min,DWORD *max)
// 使用SSE4.1 指令计算数组的最大最小值
// 寄存器的使用
// eax: 存放最小值
// edx: 存放最大值
// xmm0: 当前取得的4个整数
// xmm1: 存放最小值
// xmm2: 存放最大值
/* PMINUD and PMAXUD are SSE4.1 instruciton
The usage for PMINUD
Compares packed unsigned dword integers in the destination operand (first operand)
and the source operand (second operand), and returns the minimum for each packed
value in the destination operand.
Operation
IF (DEST[31:0] < SRC[31:0])
THEN DEST[31:0] 􀃅 DEST[31:0];
ELSE DEST[31:0] 􀃅 SRC[31:0]; FI;
IF (DEST[63:32] < SRC[63:32])
THEN DEST[63:32] 􀃅 DEST[63:32];
ELSE DEST[63:32] 􀃅 SRC[63:32]; FI;
IF (DEST[95:64] < SRC[95:64])
THEN DEST[95:64] 􀃅 DEST[95:64];
ELSE DEST[95:64] 􀃅 SRC[95:64]; FI;
IF (DEST[127:96] < SRC[127:96])
THEN DEST[127:96] 􀃅 DEST[127:96];
ELSE DEST[127:96] 􀃅 SRC[127:96]; FI;
*/
#define MIN_128REG xmm1
#define MAX_128REG xmm2
#define MIN_32REG eax
#define MAX_32REG edx
#define PT_REG esi
#define END_REG edi
#define PAR_PDATA 4
#define PAR_LEN 8
#define PAR_MIN 12
#define PAR_MAX 16
{
__asm
{
push esi
push edi
mov MIN_32REG, 0xffffffff // min=0xffffffff
xor MAX_32REG, MAX_32REG // max=0
//phase1:
mov ecx, dword ptr[esp+8+PAR_LEN] // len
mov PT_REG, dword ptr[esp+8+PAR_PDATA] // pData
lea END_REG, [PT_REG+ecx*4] // edi=pData + len
jmp cmp10
loop1_start:
cmp [PT_REG], MIN_32REG
cmovb MIN_32REG,[PT_REG]
cmp [PT_REG], MAX_32REG
cmova MAX_32REG,[PT_REG]
add PT_REG, 4
cmp10:
test PT_REG, 0x0f
jz phase2
cmp PT_REG, END_REG
jb loop1_start
phase2:
mov ecx, dword ptr[esp+8+PAR_LEN] // len
mov END_REG, dword ptr[esp+8+PAR_PDATA] // pData
lea END_REG, [END_REG+ecx*4] // edi=pData + len
and END_REG, 0xfffffff0 // clear bit0-bit3 and make edi % 16==0
movd MIN_128REG, MIN_32REG
pshufd MIN_128REG, MIN_128REG, 00000000b // xmm1 = R0:R0:R0:R0
movd MAX_128REG, MAX_32REG
pshufd MAX_128REG, MAX_128REG, 00000000b // xmm2 = R0:R0:R0:R0
jmp cmp20
loop2_start:
movdqa xmm0, xmmword ptr[PT_REG]
PMINUD MIN_128REG, xmm0
PMAXUD MAX_128REG, xmm0
add PT_REG,16
cmp20:
cmp PT_REG, END_REG
jb loop2_start
phase3:
movd ecx, MIN_128REG
cmp ecx, MIN_32REG
cmovb MIN_32REG,ecx //MIN_32REG=min(min_32REG,bit0-31(MIN_128REG))
psrldq MIN_128REG, 4 //MIN_128REG >>=4
movd ecx, MIN_128REG
cmp ecx, MIN_32REG
cmovb MIN_32REG,ecx //MIN_32REG=min(min_32REG,bit32-63(MIN_128REG))
psrldq MIN_128REG, 4 //MIN_128REG >>=4
movd ecx, MIN_128REG
cmp ecx, MIN_32REG
cmovb MIN_32REG,ecx //MIN_32REG=min(min_32REG,bit64-95(MIN_128REG))
psrldq MIN_128REG, 4 //MIN_128REG >>=4
movd ecx, MIN_128REG
cmp ecx, MIN_32REG
cmovb MIN_32REG,ecx //MIN_32REG=min(min_32REG,bit96-127(MIN_128REG) )
//-----------------------------------------------
movd ecx, MAX_128REG
cmp ecx, MAX_32REG
cmova MAX_32REG,ecx //MAX_32REG=max(max_32REG,bit0-31(MAX_128REG))
psrldq MAX_128REG, 4 //MAX_128REG >>=4
movd ecx, MAX_128REG
cmp ecx, MAX_32REG
cmova MAX_32REG,ecx //MAX_32REG=max(max_32REG,bit32-63(MAX_128REG))
psrldq MAX_128REG, 4 //MAX_128REG >>=4
movd ecx, MAX_128REG
cmp ecx, MAX_32REG
cmova MAX_32REG,ecx //MAX_32REG=max(max_32REG,bit64-95(MAX_128REG))
psrldq MAX_128REG, 4 //MAX_128REG >>=4
movd ecx, MAX_128REG
cmp ecx, MAX_32REG
cmova MAX_32REG,ecx //MIN_32REG=max(max_32REG,bit96-127(MIN_128REG))
mov END_REG, dword ptr[esp+8+PAR_PDATA] // pData
mov ecx, dword ptr[esp+8+PAR_LEN] // len
lea END_REG, [END_REG+ecx*4] // edi=pData + len
jmp cmp30
loop3_start:
cmp [PT_REG], MIN_32REG
cmovb MIN_32REG,[PT_REG]
cmp [PT_REG], MAX_32REG
cmova MAX_32REG,[PT_REG]
add PT_REG, 4
cmp30:
cmp PT_REG, END_REG
jb loop3_start
RET_VALUE:
mov ecx, dword ptr[esp+8+PAR_MIN] //*min
mov dword ptr [ecx],MIN_32REG
mov ecx, dword ptr[esp+8+PAR_MAX] //*max
mov dword ptr [ecx],MAX_32REG
emms
pop edi
pop esi
ret
}
}

复制代码

liangbch · 发表于 2011-1-2 22:14:00

本楼给出包括VC2008工程文件的所有源代码。

gxqcn · 发表于 2011-1-4 08:19:38

非常赞赏这种讨论方式，有代码、有数据、有分析结论，相当完整，非常方便大家参考。

账号		自动登录	找回密码
密码			欢迎注册

[原创] 求一个数组中元素的最大值和最小值

评分