内存拷贝优化（2）-全尺寸拷贝优化

内存拷贝优化（2）-全尺寸拷贝优化

四年前写过一篇小内存拷贝优化：http://www.skywind.me/blog/archives/143

纠结了一下还是把全尺寸拷贝优化代码发布出来吧，没啥好保密的，

如今总结一下全尺寸内存拷贝优化的要点：

1. 策略区别：64字节以内用小内存方案，64K以内用中尺寸方案，大于64K用大内存拷贝方案。

2. 查表跳转：拷贝不同小尺寸内存，直接跳转到相应地址解除循环。

3. 目标对齐：64字节以上拷贝的先用普通方法拷贝几个字节让目标地址对齐，好做后面的事情。

4. 矢量拷贝：并行一次性读入N个矢量到 sse2 寄存器，再并行写出。

5. 缓存预取：使用 prefetchnta ，提前预取数据，等到真的要用时数据已经到位。

6. 内存直写：使用 movntdq 来直写内存，避免缓存污染。

部分理论，见论文：《Using Block Prefetch for Optimized Memory Performance》

但论文考虑问题比较单一，所以实际代码写的比论文复杂不少，目前在各个尺寸上基本平均能够加速 40%，比较GCC 4.9, VS2012的 memcpy，不排除未来的 libc, crt库继续完善以后，能够达到下面代码的速度。但我看libc和crt的 memcpy代码已经很久没人更新了，不知道他们还愿意继续优化下去么？

行了，具体实现各位读代码吧，需要 SSE2 指令集支持，gcc编译时需要 –msse2 一下，点击（more）展开代码，测试结果附在源文件最后注释部分：

//=====================================================================
//
// FastMemcpy.c - [email protected], 2012
//
// feature:
// 40% speed up in avg. vs standard memcpy (tested in vc2012/gcc4.9)
//
//=====================================================================
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <windows.h>
#include <emmintrin.h>

void *memcpy_tiny(void *dst, const void *src, size_t len)
{
    if (len <= 64) {
        register unsigned char *dd = (unsigned char*)dst + len;
        register const unsigned char *ss = (const unsigned char*)src + len;
        switch (len) {
        case 68:    *((int*)(dd - 68)) = *((int*)(ss - 68));
        case 64:    *((int*)(dd - 64)) = *((int*)(ss - 64));
        case 60:    *((int*)(dd - 60)) = *((int*)(ss - 60));
        case 56:    *((int*)(dd - 56)) = *((int*)(ss - 56));
        case 52:    *((int*)(dd - 52)) = *((int*)(ss - 52));
        case 48:    *((int*)(dd - 48)) = *((int*)(ss - 48));
        case 44:    *((int*)(dd - 44)) = *((int*)(ss - 44));
        case 40:    *((int*)(dd - 40)) = *((int*)(ss - 40));
        case 36:    *((int*)(dd - 36)) = *((int*)(ss - 36));
        case 32:    *((int*)(dd - 32)) = *((int*)(ss - 32));
        case 28:    *((int*)(dd - 28)) = *((int*)(ss - 28));
        case 24:    *((int*)(dd - 24)) = *((int*)(ss - 24));
        case 20:    *((int*)(dd - 20)) = *((int*)(ss - 20));
        case 16:    *((int*)(dd - 16)) = *((int*)(ss - 16));
        case 12:    *((int*)(dd - 12)) = *((int*)(ss - 12));
        case  8:    *((int*)(dd - 8)) = *((int*)(ss - 8));
        case  4:    *((int*)(dd - 4)) = *((int*)(ss - 4));
                    break;
        case 67:    *((int*)(dd - 67)) = *((int*)(ss - 67));
        case 63:    *((int*)(dd - 63)) = *((int*)(ss - 63));
        case 59:    *((int*)(dd - 59)) = *((int*)(ss - 59));
        case 55:    *((int*)(dd - 55)) = *((int*)(ss - 55));
        case 51:    *((int*)(dd - 51)) = *((int*)(ss - 51));
        case 47:    *((int*)(dd - 47)) = *((int*)(ss - 47));
        case 43:    *((int*)(dd - 43)) = *((int*)(ss - 43));
        case 39:    *((int*)(dd - 39)) = *((int*)(ss - 39));
        case 35:    *((int*)(dd - 35)) = *((int*)(ss - 35));
        case 31:    *((int*)(dd - 31)) = *((int*)(ss - 31));
        case 27:    *((int*)(dd - 27)) = *((int*)(ss - 27));
        case 23:    *((int*)(dd - 23)) = *((int*)(ss - 23));
        case 19:    *((int*)(dd - 19)) = *((int*)(ss - 19));
        case 15:    *((int*)(dd - 15)) = *((int*)(ss - 15));
        case 11:    *((int*)(dd - 11)) = *((int*)(ss - 11));
        case  7:    *((int*)(dd - 7)) = *((int*)(ss - 7));
                    *((int*)(dd - 4)) = *((int*)(ss - 4));
                    break;
        case  3:    *((short*)(dd - 3)) = *((short*)(ss - 3));
                    dd[-1] = ss[-1];
                    break;
        case 66:    *((int*)(dd - 66)) = *((int*)(ss - 66));
        case 62:    *((int*)(dd - 62)) = *((int*)(ss - 62));
        case 58:    *((int*)(dd - 58)) = *((int*)(ss - 58));
        case 54:    *((int*)(dd - 54)) = *((int*)(ss - 54));
        case 50:    *((int*)(dd - 50)) = *((int*)(ss - 50));
        case 46:    *((int*)(dd - 46)) = *((int*)(ss - 46));
        case 42:    *((int*)(dd - 42)) = *((int*)(ss - 42));
        case 38:    *((int*)(dd - 38)) = *((int*)(ss - 38));
        case 34:    *((int*)(dd - 34)) = *((int*)(ss - 34));
        case 30:    *((int*)(dd - 30)) = *((int*)(ss - 30));
        case 26:    *((int*)(dd - 26)) = *((int*)(ss - 26));
        case 22:    *((int*)(dd - 22)) = *((int*)(ss - 22));
        case 18:    *((int*)(dd - 18)) = *((int*)(ss - 18));
        case 14:    *((int*)(dd - 14)) = *((int*)(ss - 14));
        case 10:    *((int*)(dd - 10)) = *((int*)(ss - 10));
        case  6:    *((int*)(dd - 6)) = *((int*)(ss - 6));
        case  2:    *((short*)(dd - 2)) = *((short*)(ss - 2));
                    break;
        case 65:    *((int*)(dd - 65)) = *((int*)(ss - 65));
        case 61:    *((int*)(dd - 61)) = *((int*)(ss - 61));
        case 57:    *((int*)(dd - 57)) = *((int*)(ss - 57));
        case 53:    *((int*)(dd - 53)) = *((int*)(ss - 53));
        case 49:    *((int*)(dd - 49)) = *((int*)(ss - 49));
        case 45:    *((int*)(dd - 45)) = *((int*)(ss - 45));
        case 41:    *((int*)(dd - 41)) = *((int*)(ss - 41));
        case 37:    *((int*)(dd - 37)) = *((int*)(ss - 37));
        case 33:    *((int*)(dd - 33)) = *((int*)(ss - 33));
        case 29:    *((int*)(dd - 29)) = *((int*)(ss - 29));
        case 25:    *((int*)(dd - 25)) = *((int*)(ss - 25));
        case 21:    *((int*)(dd - 21)) = *((int*)(ss - 21));
        case 17:    *((int*)(dd - 17)) = *((int*)(ss - 17));
        case 13:    *((int*)(dd - 13)) = *((int*)(ss - 13));
        case  9:    *((int*)(dd - 9)) = *((int*)(ss - 9));
        case  5:    *((int*)(dd - 5)) = *((int*)(ss - 5));
        case  1:    dd[-1] = ss[-1];
                    break;
        case 0:
        default: break;
        }
        return dd;
    }   else {
        return memcpy(dst, src, len);
    }
}

void* memcpy_fast(void *destination, const void *source, size_t size)
{
    unsigned char *dst = (unsigned char*)destination;
    const unsigned char *src = (const unsigned char*)source;
    static size_t cachesize = 0x10000;
    size_t diff;

    // small memory copy
    if (size < 64) {
        return memcpy_tiny(dst, src, size);
    }

    // align destination to 16 bytes boundary
    diff = (((size_t)dst + 15) & (~15)) - ((size_t)dst);
    if (diff > 0) {
        memcpy_tiny(dst, src, diff);
        dst += diff;
        src += diff;
        size -= diff;
    }

    // medium size copy
    if (size <= cachesize) {
        __m128i c1, c2, c3, c4;
        
        if ((((size_t)src) & 15) == 0) {	// source aligned
            for (; size >= 64; size -= 64) {
                c1 = _mm_load_si128(((const __m128i*)src) + 0);
                c2 = _mm_load_si128(((const __m128i*)src) + 1);
                c3 = _mm_load_si128(((const __m128i*)src) + 2);
                c4 = _mm_load_si128(((const __m128i*)src) + 3);
                src += 64;
                _mm_store_si128((((__m128i*)dst) + 0), c1);
                _mm_store_si128((((__m128i*)dst) + 1), c2);
                _mm_store_si128((((__m128i*)dst) + 2), c3);
                _mm_store_si128((((__m128i*)dst) + 3), c4);
                dst += 64;
            }
        }
        else {							// source un-aligned
            for (; size >= 64; size -= 64) {
                c1 = _mm_loadu_si128(((const __m128i*)src) + 0);
                c2 = _mm_loadu_si128(((const __m128i*)src) + 1);
                c3 = _mm_loadu_si128(((const __m128i*)src) + 2);
                c4 = _mm_loadu_si128(((const __m128i*)src) + 3);
                src += 64;
                _mm_store_si128((((__m128i*)dst) + 0), c1);
                _mm_store_si128((((__m128i*)dst) + 1), c2);
                _mm_store_si128((((__m128i*)dst) + 2), c3);
                _mm_store_si128((((__m128i*)dst) + 3), c4);
                dst += 64;
            }
        }
    }
    else {		// big memory copy
        __m128i c1, c2, c3, c4;

        _mm_prefetch((const char*)(src), _MM_HINT_NTA);

        if ((((size_t)src) & 15) == 0) {	// source aligned
            for (; size >= 64; size -= 64) {
                _mm_prefetch((const char*)(src + 128), _MM_HINT_NTA);
                c1 = _mm_load_si128(((const __m128i*)src) + 0);
                c2 = _mm_load_si128(((const __m128i*)src) + 1);
                c3 = _mm_load_si128(((const __m128i*)src) + 2);
                c4 = _mm_load_si128(((const __m128i*)src) + 3);
                src += 64;
                _mm_stream_si128((((__m128i*)dst) + 0), c1);
                _mm_stream_si128((((__m128i*)dst) + 1), c2);
                _mm_stream_si128((((__m128i*)dst) + 2), c3);
                _mm_stream_si128((((__m128i*)dst) + 3), c4);
                dst += 64;
            }
        }
        else {							// source unaligned
            for (; size >= 64; size -= 64) {
                _mm_prefetch((const char*)(src + 128), _MM_HINT_NTA);
                c1 = _mm_loadu_si128(((const __m128i*)src) + 0);
                c2 = _mm_loadu_si128(((const __m128i*)src) + 1);
                c3 = _mm_loadu_si128(((const __m128i*)src) + 2);
                c4 = _mm_loadu_si128(((const __m128i*)src) + 3);
                src += 64;
                _mm_stream_si128((((__m128i*)dst) + 0), c1);
                _mm_stream_si128((((__m128i*)dst) + 1), c2);
                _mm_stream_si128((((__m128i*)dst) + 2), c3);
                _mm_stream_si128((((__m128i*)dst) + 3), c4);
                dst += 64;
            }
        }
        _mm_sfence();
    }

    return memcpy_tiny(dst, src, size);
}

void benchmark(int dstalign, int srcalign, size_t size, int times)
{
    char *DATA1 = (char*)malloc(size + 64);
    char *DATA2 = (char*)malloc(size + 64);
    size_t LINEAR1 = ((size_t)DATA1);
    size_t LINEAR2 = ((size_t)DATA2);
    char *ALIGN1 = (char*)(((64 - (LINEAR1 & 63)) & 63) + LINEAR1);
    char *ALIGN2 = (char*)(((64 - (LINEAR2 & 63)) & 63) + LINEAR2);
    char *dst = (dstalign)? ALIGN1 : (ALIGN1 + 1);
    char *src = (srcalign)? ALIGN2 : (ALIGN2 + 3);
    DWORD t1, t2;
    int k;
    
    Sleep(100);
    t1 = timeGetTime();
    for (k = times; k > 0; k--) {
        memcpy(dst, src, size);
    }
    t1 = timeGetTime() - t1;
    Sleep(100);
    t2 = timeGetTime();
    for (k = times; k > 0; k--) {
        memcpy_fast(dst, src, size);
    }
    t2 = timeGetTime() - t2;

    free(DATA1);
    free(DATA2);

    printf("result(dst %s, src %s): memcpy_fast=%dms memcpy=%d ms\n",  
        dstalign? "aligned" : "unalign", 
        srcalign? "aligned" : "unalign", (int)t2, (int)t1);
}


void bench(int copysize, int times)
{
    printf("benchmark(size=%d bytes, times=%d):\n", copysize, times);
    benchmark(1, 1, copysize, times);
    benchmark(1, 0, copysize, times);
    benchmark(0, 1, copysize, times);
    benchmark(0, 0, copysize, times);
    printf("\n");
}


#ifdef _MSC_VER
#pragma comment(lib, "winmm.lib")
#endif

int main(void)
{
    bench(32, 0x1000000);
    bench(64, 0x1000000);
    bench(512, 0x800000);
    bench(1024, 0x400000);
    bench(4096, 0x80000);
    bench(8192, 0x40000);
    bench(1024 * 1024 * 1, 0x800);
    bench(1024 * 1024 * 4, 0x200);
    bench(1024 * 1024 * 8, 0x100);
    return 0;
}
 

/*
result: gcc4.9 (msvc 2012 got a similar result):

benchmark(size=32 bytes, times=16777216):
result(dst aligned, src aligned): memcpy_sse2=180ms memcpy=249 ms
result(dst aligned, src unalign): memcpy_sse2=170ms memcpy=271 ms
result(dst unalign, src aligned): memcpy_sse2=179ms memcpy=269 ms
result(dst unalign, src unalign): memcpy_sse2=180ms memcpy=260 ms

benchmark(size=64 bytes, times=16777216):
result(dst aligned, src aligned): memcpy_sse2=162ms memcpy=300 ms
result(dst aligned, src unalign): memcpy_sse2=199ms memcpy=328 ms
result(dst unalign, src aligned): memcpy_sse2=410ms memcpy=339 ms
result(dst unalign, src unalign): memcpy_sse2=390ms memcpy=361 ms

benchmark(size=512 bytes, times=8388608):
result(dst aligned, src aligned): memcpy_sse2=160ms memcpy=241 ms
result(dst aligned, src unalign): memcpy_sse2=200ms memcpy=519 ms
result(dst unalign, src aligned): memcpy_sse2=313ms memcpy=509 ms
result(dst unalign, src unalign): memcpy_sse2=311ms memcpy=520 ms

benchmark(size=1024 bytes, times=4194304):
result(dst aligned, src aligned): memcpy_sse2=145ms memcpy=179 ms
result(dst aligned, src unalign): memcpy_sse2=180ms memcpy=430 ms
result(dst unalign, src aligned): memcpy_sse2=245ms memcpy=430 ms
result(dst unalign, src unalign): memcpy_sse2=230ms memcpy=455 ms

benchmark(size=4096 bytes, times=524288):
result(dst aligned, src aligned): memcpy_sse2=80ms memcpy=80 ms
result(dst aligned, src unalign): memcpy_sse2=110ms memcpy=205 ms
result(dst unalign, src aligned): memcpy_sse2=110ms memcpy=224 ms
result(dst unalign, src unalign): memcpy_sse2=110ms memcpy=200 ms

benchmark(size=8192 bytes, times=262144):
result(dst aligned, src aligned): memcpy_sse2=70ms memcpy=78 ms
result(dst aligned, src unalign): memcpy_sse2=100ms memcpy=222 ms
result(dst unalign, src aligned): memcpy_sse2=100ms memcpy=210 ms
result(dst unalign, src unalign): memcpy_sse2=100ms memcpy=230 ms

benchmark(size=1048576 bytes, times=2048):
result(dst aligned, src aligned): memcpy_sse2=200ms memcpy=201 ms
result(dst aligned, src unalign): memcpy_sse2=260ms memcpy=270 ms
result(dst unalign, src aligned): memcpy_sse2=263ms memcpy=361 ms
result(dst unalign, src unalign): memcpy_sse2=267ms memcpy=321 ms

benchmark(size=4194304 bytes, times=512):
result(dst aligned, src aligned): memcpy_sse2=281ms memcpy=391 ms
result(dst aligned, src unalign): memcpy_sse2=265ms memcpy=407 ms
result(dst unalign, src aligned): memcpy_sse2=313ms memcpy=453 ms
result(dst unalign, src unalign): memcpy_sse2=282ms memcpy=439 ms

benchmark(size=8388608 bytes, times=256):
result(dst aligned, src aligned): memcpy_sse2=266ms memcpy=422 ms
result(dst aligned, src unalign): memcpy_sse2=250ms memcpy=407 ms
result(dst unalign, src aligned): memcpy_sse2=297ms memcpy=516 ms
result(dst unalign, src unalign): memcpy_sse2=281ms memcpy=436 ms

*/

848 total views, 1 view today