I have implemented the strlen()
function in different ways, including SSE2 assembly
, SSE4.2 assembly
and SSE2 intrinsic
, I also exerted some experiments on them, with strlen() in <string.h>
and strlen() in glibc
. However, their performance in terms of milliseconds (time) are unexpected.
My experiment environment:
CentOS 7.0 + gcc 4.8.5 + Intel Xeon
Following are my implementations:
strlen
using SSE2 assemblylong strlen_sse2_asm(const char* src){ long result = 0; asm( "movl %1, %%edi\n\t" "movl $-0x10, %%eax\n\t" "pxor %%xmm0, %%xmm0\n\t" "lloop:\n\t" "addl $0x10, %%eax\n\t" "movdqu (%%edi,%%eax), %%xmm1\n\t" "pcmpeqb %%xmm0, %%xmm1\n\t" "pmovmskb %%xmm1, %%ecx\n\t" "test %%ecx, %%ecx\n\t" "jz lloop\n\t" "bsf %%ecx, %%ecx\n\t" "addl %%ecx, %%eax\n\t" "movl %%eax, %0" :"=r"(result) :"r"(src) :"%eax" ); return result; }
2.strlen
using SSE4.2 assembly
long strlen_sse4_2_asm(const char* src){
long result = 0;
asm(
"movl %1, %%edi\n\t"
"movl $-0x10, %%eax\n\t"
"pxor %%xmm0, %%xmm0\n\t"
"lloop2:\n\t"
"addl $0x10, %%eax\n\t"
"pcmpistri $0x08,(%%edi, %%eax), %%xmm0\n\t"
"jnz lloop2\n\t"
"add %%ecx, %%eax\n\t"
"movl %%eax, %0"
:"=r"(result)
:"r"(src)
:"%eax"
);
return result;
}
3. strlen
using SSE2 intrinsic
long strlen_sse2_intrin_align(const char* src){
if (src == NULL || *src == '\0'){
return 0;
}
const __m128i zero = _mm_setzero_si128();
const __m128i* ptr = (const __m128i*)src;
if(((size_t)ptr&0xF)!=0){
__m128i xmm = _mm_loadu_si128(ptr);
unsigned int mask = _mm_movemask_epi8(_mm_cmpeq_epi8(xmm,zero));
if(mask!=0){
return (const char*)ptr-src+(size_t)ffs(mask);
}
ptr = (__m128i*)(0x10+(size_t)ptr & ~0xF);
}
for (;;ptr++){
__m128i xmm = _mm_load_si128(ptr);
unsigned int mask = _mm_movemask_epi8(_mm_cmpeq_epi8(xmm,zero));
if (mask!=0)
return (const char*)ptr-src+(size_t)ffs(mask);
}
}
I also looked up the one implemented in linux kernel, following is its implementation
size_t strlen_inline_asm(const char* str){ int d0; size_t res; asm volatile("repne\n\t" "scasb" :"=c" (res), "=&D" (d0) : "1" (str), "a" (0), "" (0xffffffffu) : "memory"); return ~res-1; }
In my experience, I also added the one of standard library and compared their performance.
Followings are my main
function code:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <xmmintrin.h>
#include <x86intrin.h>
#include <emmintrin.h>
#include <time.h>
#include <unistd.h>
#include <sys/time.h>
int main()
{
struct timeval tpstart,tpend;
int i=0;
for(;i<1023;i++){
test_str[i] = 'a';
}
test_str[i]='\0';
gettimeofday(&tpstart,NULL);
for(i=0;i<10000000;i++)
strlen(test_str);
gettimeofday(&tpend,NULL);
printf("strlen from stirng.h--->%lf\n",(tpend.tv_sec-tpstart.tv_sec)*1000+(tpend.tv_usec-tpstart.tv_usec)/1000.0);
gettimeofday(&tpstart,NULL);
for(i=0;i<10000000;i++)
strlen_inline_asm(test_str);
gettimeofday(&tpend,NULL);
printf("strlen_inline_asm--->%lf\n",(tpend.tv_sec-tpstart.tv_sec)*1000+(tpend.tv_usec-tpstart.tv_usec)/1000.0);
gettimeofday(&tpstart,NULL);
for(i=0;i<10000000;i++)
strlen_sse2_asm(test_str);
gettimeofday(&tpend,NULL);
printf("strlen_sse2_asm--->%lf\n",(tpend.tv_sec-tpstart.tv_sec)*1000+(tpend.tv_usec-tpstart.tv_usec)/1000.0);
gettimeofday(&tpstart,NULL);
for(i=0;i<10000000;i++)
strlen_sse4_2_asm(test_str);
gettimeofday(&tpend,NULL);
printf("strlen_sse4_2_asm--->%lf\n",(tpend.tv_sec-tpstart.tv_sec)*1000+(tpend.tv_usec-tpstart.tv_usec)/1000.0);
gettimeofday(&tpstart,NULL);
for(i=0;i<10000000;i++)
strlen_sse2_intrin_align(test_str);
gettimeofday(&tpend,NULL);
printf("strlen_sse2_intrin_align--->%lf\n",(tpend.tv_sec-tpstart.tv_sec)*1000+(tpend.tv_usec-tpstart.tv_usec)/1000.0);
return 0;
}
The result is : (ms)
strlen from stirng.h--->23.518000
strlen_inline_asm--->222.311000
strlen_sse2_asm--->782.907000
strlen_sse4_2_asm--->955.960000
strlen_sse2_intrin_align--->3499.586000
I have some questions about it:
- Why
strlen
ofstring.h
is so fast? I think its code should be identify tostrlen_inline_asm
because I copied the code from/linux-4.2.2/arch/x86/lib/string_32.c
[http://lxr.oss.org.cn/source/arch/x86/lib/string_32.c#L164] - Why
sse2 intrinsic
andsse2 assembly
are so different in performance? - Could someone help me how to disassembly the code so that I can see what has the function
strlen
of static library been transformed by the compiler? I usedgcc -s
but didn't find the disassembly ofstrlen from the <string.h>
- I think my code may be not very well, I would be appreciate if you could help me improve my code, especially assembly ones.
Thanks.
string.h
strlen
, because it knows that it does (and that the result will be the same every time). Did you check the asm output of the test loop? Writing microbenchmarks that measure what you actually want to measure is non-trivial.-O0
. I was wondering if that was the case, from how badly the intrinsics version performed. Did you even look at the asm that gets generated from intrinsics with-O0
?