python教程—简单的Python挑战:数据缓冲区上最快的位XOR-Python实用宝典

python教程—简单的Python挑战:数据缓冲区上最快的位XOR

挑战:在两个大小相等的缓冲区上执行位XOR。缓冲区必须是python str类型,因为这是python中数据缓冲区的传统类型。返回结果值为str。请尽快这样做。

<强>挑战:< /强>

在两个大小相等的缓冲区上执行位XOR。缓冲区必须是python str类型,因为这是python中数据缓冲区的传统类型。返回结果值为str。请尽快这样做。

输入是两个1兆字节(2**20字节)的字符串。

挑战在于实质上击败了我使用python或现有第三方python模块的低效算法(放松规则:或者创建自己的模块)。边际增长是无用的。

    from os import urandom from numpy import frombuffer,bitwise_xor,byte def slow_xor(aa,bb): a=frombuffer(aa,dtype=byte) b=frombuffer(bb,dtype=byte) c=bitwise_xor(a,b) r=c.tostring() return r aa=urandom(2**20) bb=urandom(2**20) def test_it(): for x in xrange(1000): slow_xor(aa,bb)

回答

第一次尝试

使用scipy。weaveSSE2 intrinsics给出了一个微小的改进。第一次调用稍微慢一点,因为代码需要从磁盘加载和缓存,后续调用更快:

    import numpy import time from os import urandom from scipy import weave SIZE = 2**20 def faster_slow_xor(aa,bb): b = numpy.fromstring(bb, dtype=numpy.uint64) numpy.bitwise_xor(numpy.frombuffer(aa,dtype=numpy.uint64), b, b) return b.tostring() code = """ const __m128i* pa = (__m128i*)a; const __m128i* pend = (__m128i*)(a + arr_size); __m128i* pb = (__m128i*)b; __m128i xmm1, xmm2; while (pa < pend) { xmm1 = _mm_loadu_si128(pa); // must use unaligned access xmm2 = _mm_load_si128(pb); // numpy will align at 16 byte boundaries _mm_store_si128(pb, _mm_xor_si128(xmm1, xmm2)); ++pa; ++pb; } """ def inline_xor(aa, bb): a = numpy.frombuffer(aa, dtype=numpy.uint64) b = numpy.fromstring(bb, dtype=numpy.uint64) arr_size = a.shape[0] weave.inline(code, ["a", "b", "arr_size"], headers = ['"emmintrin.h"']) return b.tostring()

第二次尝试

考虑到这些注释,我重新访问了代码,以确定是否可以避免复制。原来我读错了string对象的文档,所以我又试了一次:

    support = """ #define ALIGNMENT 16 static void memxor(const char* in1, const char* in2, char* out, ssize_t n) { const char* end = in1 + n; while (in1 < end) { *out = *in1 ^ *in2; ++in1; ++in2; ++out; } } """ code2 = """ PyObject* res = PyString_FromStringAndSize(NULL, real_size); const ssize_t tail = (ssize_t)PyString_AS_STRING(res) % ALIGNMENT; const ssize_t head = (ALIGNMENT - tail) % ALIGNMENT; memxor((const char*)a, (const char*)b, PyString_AS_STRING(res), head); const __m128i* pa = (__m128i*)((char*)a + head); const __m128i* pend = (__m128i*)((char*)a + real_size - tail); const __m128i* pb = (__m128i*)((char*)b + head); __m128i xmm1, xmm2; __m128i* pc = (__m128i*)(PyString_AS_STRING(res) + head); while (pa < pend) { xmm1 = _mm_loadu_si128(pa); xmm2 = _mm_loadu_si128(pb); _mm_stream_si128(pc, _mm_xor_si128(xmm1, xmm2)); ++pa; ++pb; ++pc; } memxor((const char*)pa, (const char*)pb, (char*)pc, tail); return_val = res; Py_DECREF(res); """ def inline_xor_nocopy(aa, bb): real_size = len(aa) a = numpy.frombuffer(aa, dtype=numpy.uint64) b = numpy.frombuffer(bb, dtype=numpy.uint64) return weave.inline(code2, ["a", "b", "real_size"], headers = ['"emmintrin.h"'], support_code = support)

区别在于字符串是在C代码中分配的。不可能按照SSE2指令的要求将其对齐到16字节边界,因此,开始和结束时未对齐的内存区域将使用字节访问进行复制。

无论如何,输入数据都是使用numpy数组提交的,因为weave坚持将Python str对象复制到std::string。frombuffer不会复制,所以这很好,但是内存没有对齐到16字节,所以我们需要使用_mm_loadu_si128而不是更快的_mm_load_si128。

我们没有使用_mm_store_si128,而是使用_mm_stream_si128,这将确保任何写入都尽快流到主内存——这样,输出数组就不会耗尽有价值的高速缓存行。

计时

至于计时,第一次编辑中的slow_xor条目引用了我的改进版本(内联位xor, uint64),我消除了这种混淆。slow_xor引用原始问题中的代码。所有计时都是为1000次运行完成的。

  • slow_xor: 1.85 s x (1)
  • faster_slow_xor: 1.25秒(1.48 x)
  • inline_xor: 0.95秒(1.95 x)
  • inline_xor_nocopy: 0.32秒(5.78 x)

代码是使用gcc 4.4.3编译的,我已经验证了编译器实际上使用了SSE指令。

​Python实用宝典 (pythondict.com)
不只是一个宝典
欢迎关注公众号:Python实用宝典

本文由 Python实用宝典 作者:Python实用宝典 发表,其版权均为 Python实用宝典 所有,文章内容系作者个人观点,不代表 Python实用宝典 对观点赞同或支持。如需转载,请注明文章来源。
0

发表评论