这个答案试图给出一个估计,平行化版本可以获得多少加速。然而,由于这个任务受到内存带宽的限制(Python整数对象至少占用32个字节,并且可能散布在内存中,因此会有许多缓存未命中),我们不应该期望太多。
第一个问题是如何处理错误(元素不是整数或值过大)。我将采用以下策略/简化:当对象
时,它将被转换为一个特殊数字(
-1
),表示发生了错误。只允许非负整数
<2^30
可以使我的工作更容易,因为我必须重新实现
PyLong_AsLongAndOverflow
而不引发错误,否则检测溢出通常很麻烦(但请参见答案末尾的更复杂方法)。
Python整数对象的内存布局可以在
这里找到:
struct _longobject {
PyObject_VAR_HEAD
digit ob_digit[1];
};
成员变量ob_size
/宏Py_SIZE
告诉我们在整数的表示中使用了多少个30位数字(对于负整数,ob_size
为负数)。
因此,我的简单规则可以转换为以下C代码(我使用C而不是Cython,因为它是使用Python C-API的更简单/更自然的方式):
#include <Python.h>
int to_int(PyObject *vv){
if (PyLong_Check(vv)) {
PyLongObject * v = (PyLongObject *)vv;
Py_ssize_t i = Py_SIZE(v);
if(i==0){
return 0;
}
if(i==1){
return v->ob_digit[0];
}
return -1;
}
return -1;
}
现在,给定一个列表,我们可以使用以下的C函数并行地将其转换为
int
缓冲区,该函数使用omp:
void convert_list(PyListObject *lst, int *output){
Py_ssize_t n = Py_SIZE(lst);
PyObject **data = lst->ob_item;
#pragma omp parallel for
for(Py_ssize_t i=0; i<n; ++i){
output[i] = to_int(data[i]);
}
}
没有太多可说的 - PyListObject
-API 用于并行访问列表中的元素。这可以实现,因为 to_int
函数中没有引用计数/竞争条件。
现在,通过Cython将所有内容捆绑在一起:
%%cython -c=-fopenmp --link-args=-fopenmp
import cython
cdef extern from *:
"""
#include <Python.h>
int to_int(PyObject *vv){
... code
}
void convert_list(PyListObject *lst, int *output){
... code
}
"""
void convert_list(list lst, int *output)
@cython.boundscheck(False)
@cython.wraparound(False)
def pack_ints_ead(list int_col):
cdef char[::1] int_buf = bytearray(4*len(int_col))
convert_list(int_col, <int*>(&int_buf[0]))
return int_buf.base
一个重要的细节是:
convert_list
不能是nogil(因为它不是)!Omp线程和受GIL影响的Python线程是完全不同的东西。
可以(但不一定)在使用具有
缓冲区协议的对象时释放GIL以进行omp操作 - 因为这些对象通过缓冲区协议被锁定,不能从不同的Python线程更改。列表没有这样的锁定机制,因此,如果释放了GIL,则列表可能会在另一个线程中更改,并且所有指针都可能无效。
现在来看下时间(使用稍大的列表):
amount = 5*10**7
ints = list(range(amount))
%timeit pack(f'{amount}i', *ints)
%timeit pack_ints_DavidW(ints)
%timeit pack_ints_ead(ints)
顺便提一句,关闭pack_ints_ead
的并行化会使运行时间为209毫秒。
因此,考虑到约33%的小幅改进,我会选择更健壮的DavidW的方案。
这里是使用略有不同的方式来表示错误值的实现:
- 非整数对象的结果为
-2147483648
(即 0x80000000
)- 32位整数可以存储的最小负值。
- 大于等于
2147483647
(即 >=0x7fffffff
)的整数将被映射/存储为 2147483647
- 32位整数可以存储的最大正数。
- 小于等于
-2147483647
(即 <=0x80000001
)的整数将被映射/存储为 -2147483647
- 所有其他整数都映射到其正确的值。
主要优点是它可以正确地处理更大范围的整数值。该算法的运行时间几乎与第一种简单版本相同(可能比第一种慢2-3%):
int to_int(PyObject *vv){
if (PyLong_Check(vv)) {
PyLongObject * v = (PyLongObject *)vv;
Py_ssize_t i = Py_SIZE(v);
int sign = i<0 ? -1 : 1;
i = abs(i);
if(i==0){
return 0;
}
if(i==1){
return sign*v->ob_digit[0];
}
if(i==2 && (v->ob_digit[1]>>1)==0){
int add = (v->ob_digit[1]&1) << 30;
return sign*(v->ob_digit[0]+add);
}
return sign * 0x7fffffff;
}
return 0x80000000;
}
@nogil
。 - JayPyLong_AsLong
的实现。您需要调整实现方式,使其不使用GIL(即不能引发异常)。 - DavidW