使用SSE2指令集加速字符替换

栏目: IT技术 · 发布时间: 4年前

内容简介:这个算是一个比较有用的提速的技巧吧,主要是刚刚在重构Yaf_Loader的时候又用到,想着这个操作比较常见,就专门拎出来做个小分享吧。我们在写代码的时候,在字符串处理的时候,可能会遇到这样的需求,就是把一个目标字符串中所有出现的某个字符a替换为另外一个字c,比如对于Yaf_Loader中,在处理命名空间的类名的自动加载的时候,我需要把所有的\替换为_, 一般通常的写法会是:

这个算是一个比较有用的提速的技巧吧,主要是刚刚在重构Yaf_Loader的时候又用到,想着这个操作比较常见,就专门拎出来做个小分享吧。

我们在写代码的时候,在字符串处理的时候,可能会遇到这样的需求,就是把一个目标字符串中所有出现的某个字符a替换为另外一个字c,

比如对于Yaf_Loader中,在处理命名空间的类名的自动加载的时候,我需要把所有的\替换为_, 一般通常的写法会是:

char *pos = class_name;
size_t len = class_name_len;
while ((pos = memchr(pos, '\\', len - (pos - name)))) {
    *pos++ = '_';
}

而目前SIMD指令的支持已经非常普遍,尤其SSE2,基本当代的CPU都支持, 可以通过cat /proc/cpuinfo来看cpu支持的SIMD指令集:

cat /proc/cpuinfo | grep flags
flags		: fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc arch_perfmon pebs bts rep_good xtopology nonstop_tsc aperfmperf pni pclmulqdq dtes64 monitor ds_cpl vmx smx est tm2 ssse3 cx16 xtpr pdcm pcid dca sse4_1 sse4_2 x2apic popcnt tsc_deadline_timer aes xsave avx f16c rdrand lahf_lm ida arat xsaveopt pln pts dts tpr_shadow vnmi flexpriority ept vpid fsgsbase smep erms

可见我的这个CPU支持sse, sse2, sse4.1, sse4.2,avx等

回到整体,我们知道SIMD 128指令集可以一次处理16个字符,上面的代码可以通过如下代码来等效实现:

char *pos = class_name;
size_t len = class_name_len;

const __m128i slash = _mm_set1_epi8('\\');
const __m128i delta = _mm_set1_epi8('_' - '\\');

while (len >= 16) {
    __m128i op = _mm_loadu_si128((__m128i *)pos);
    __m128i eq = _mm_cmpeq_epi8(op, slash);
    if (_mm_movemask_epi8(eq)) {
        eq = _mm_and_si128(eq, delta);
        op = _mm_add_epi8(op, eq);
        _mm_storeu_si128((__m128i*)pos, op);
    }
    len -= 16;
    pos += 16;
}

//接下来用传统方式处理后续不满16个字符的部分

这里面核心的代码部分是:

1. __m128i eq = _mm_cmpeq_epi8(op, slash);
2. eq = _mm_and_si128(eq, delta);
3. op = _mm_add_epi8(op, eq);
4. _mm_storeu_si128((__m128i*)pos, op);

我来一行一行解释,假设我们现在要处理的字符串是"G\Namespace\package\classname:

  • 第一行:拿16个字符和字符'\\'做比较,如果某位相等,则16位结果中对应的byte就为0xff(-1), 否则就为0, 那么对于:

    G\Namespace\pack

    来说,会得到结果:

    0 -1 000000000 -1 0000
  • 第二行: 如果对比的结果不全为零的话,就进行到这行,这行的核心思想是因为ascii码-和\之间差了3,所以我们通过and指令得到如下结果:
    0 -1 000000000 -1 0000
    &  3  3 333333333  3 3333
    -------------------------
       0  3 000000000  3 0000
  • 第三行: 我们把刚刚的delta结果加会到原始字符串中去,也就是:
    G \ Namespace \ pack
    +  0 3 000000000 3 0000
    ----------------------
       G _ Namespace _ pack
  • 第四行:把结果写回内存

这样以来,我就可以用一条指令同时检测16个字符,效率会大大提升。完整的实现可以参考: Yaf Commit log

之前在开发 PHP 7的时候,我也为PHP7引入过采用SIMD指令来实现快速的base64_encode/decode函数,有兴趣的可以参看 Base64 Encode with SSSE3 , 以后我有空了也可以分享下那个例子是怎么做的。

最后,关于SIMD指令集的速查,可以看这里: Intel Intrinsics Guide .


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

编程珠玑(第2版•修订版)

编程珠玑(第2版•修订版)

[美] Jon Bentley 乔恩•本特利 / 黄倩、钱丽艳 / 人民邮电出版社 / 2014-12 / 39

历史上最伟大的计算机科学著作之一 融深邃思想、实战技术与趣味轶事于一炉的奇书 带你真正领略计算机科学之美 多年以来,当程序员们推选出最心爱的计算机图书时,《编程珠玑》总是位于前列。正如自然界里珍珠出自细沙对牡蛎的磨砺,计算机科学大师Jon Bentley以其独有的洞察力和创造力,从磨砺程序员的实际问题中凝结出一篇篇不朽的编程“珠玑”,成为世界计算机界名刊《ACM通讯》历史上最受欢......一起来看看 《编程珠玑(第2版•修订版)》 这本书的介绍吧!

HTML 压缩/解压工具
HTML 压缩/解压工具

在线压缩/解压 HTML 代码

SHA 加密
SHA 加密

SHA 加密工具

XML、JSON 在线转换
XML、JSON 在线转换

在线XML、JSON转换工具