这个答案试图给出一个估计,并行版本可以产生多少加速。然而,因为这个任务是内存带宽限制的(Python 整数对象至少需要 32 个字节,并且可以分散在内存中,所以会有很多缓存未命中),我们不应该期望太多。
第一个问题是,如何处理错误(元素不是整数或值太大)。我将遵循策略/简化:当对象
它将被转换为一个特殊的数字(-1
)这表明出现了问题。仅允许非负整数<2^30
让我的生活更轻松,因为我必须重新实现PyLong_AsLongAndOverflow https://github.com/python/cpython/blob/5428f48b6308c7fd71636077f2ebc307c9a53d03/Objects/longobject.c#L486没有引发错误并且检测溢出通常很麻烦(但是,请参阅答案末尾的版本以获取更复杂的方法)。
Python整型对象的内存布局可以找到here https://github.com/python/cpython/blob/e42b705188271da108de42b55d9344642170aa2b/Include/longintrepr.h#L85:
struct _longobject {
PyObject_VAR_HEAD
digit ob_digit[1];
};
Member ob_size/macro Py_SIZE https://docs.python.org/3/c-api/structures.html#c.PyObject_VAR_HEAD告诉我们在整数的表示中使用了多少个 30 位数字(ob_size
负整数为负)。
因此,我的简单规则可以转换为以下 C 代码(我使用 C 而不是 Cython,因为它是使用 Python C-API 的更简单/更自然的方式):
#include <Python.h>
// returns -1 if vv is not an integer,
// negative, or > 2**30-1
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){//small enought for a digit
return v->ob_digit[0];
}
//negative (i<0) or too big (i>1)
return -1;
}
return -1;
}
现在给定一个列表,我们可以将其转换为int
-buffer 与以下使用 omp 的 C 函数并行:
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 https://github.com/python/cpython/blob/cd7db76a636c218b2d81d3526eb435cfae61f212/Include/listobject.h#L40用于并行访问列表的元素。这是可以做到的,因为没有裁判计数/竞赛条件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
一定不能是诺吉尔(因为它不是)! Omp 线程和 Python 线程(受 GIL 影响)是完全不同的东西。
在使用对象时,可以(但不是必须)为 omp 操作释放 GIL缓冲协议 https://docs.python.org/3/c-api/buffer.html- 因为这些对象通过缓冲区协议被锁定,并且不能从不同的 Python 线程进行更改。 Alist
没有这样的锁定机制,因此,如果 GIL 被释放,列表可能会在另一个线程中更改,并且我们所有的指针都可能会失效。
现在是时间安排(列表稍大一些):
amount = 5*10**7
ints = list(range(amount))
%timeit pack(f'{amount}i', *ints)
# 1.51 s ± 38.9 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
%timeit pack_ints_DavidW(ints)
# 284 ms ± 3.1 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
%timeit pack_ints_ead(ints)
# 177 ms ± 11.8 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
顺便说一句关闭并行化pack_ints_ead
导致运行时间为 209 毫秒。
因此,考虑到大约的适度改进。 33%,我会选择更强大的 DavidW 解决方案。
以下是用稍微不同的方式发出错误值的实现:
- 不是整数对象会导致
-2147483648
(i.e. 0x80000000
) - 32 位 int 可以存储的最小负值。
- 整数
>=2147483647
(i.e. >=0x7fffffff
)将被映射到/存储为2147483647
- 32 位 int 可以存储的最大正数。
- 整数
<=-2147483647
(i.e. <=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){//small enought for a digit
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;
}