ali*_*i_m 18 python performance numpy logarithm glibc
在玩这个问题时,我注意到一些我无法解释的关于相对表现的事情np.log2,np.log并且np.log10:
In [1]: %%timeit x = np.random.rand(100000)
....: np.log2(x)
....:
1000 loops, best of 3: 1.31 ms per loop
In [2]: %%timeit x = np.random.rand(100000)
np.log(x)
....:
100 loops, best of 3: 3.64 ms per loop
In [3]: %%timeit x = np.random.rand(100000)
np.log10(x)
....:
100 loops, best of 3: 3.93 ms per loop
np.log2比np.log和和快约3倍np.log10.或许甚至更直观地np.log1p(x)计算ln(x + 1),与以下内容相同np.log2:
In [4]: %%timeit x = np.random.rand(100000)
np.log1p(x)
....:
1000 loops, best of 3: 1.46 ms per loop
我在numpy v1.10.1和v1.8.2中获得了几乎相同的时间.
对运行时性能的这些差异有直观的解释吗？
Reb*_*que 10
我发现你的问题非常有趣,所以我花了几个小时做了一些研究; 我认为我已经找到了性能差异的解释,因为它适用于整数(感谢Matteo Italia的注释) - 目前还不清楚这种推理如何扩展到浮点数:
计算机使用基数2 - 根据参考文献中链接的文章,log2的计算是4个处理器周期过程 - log10的计算需要将log2(val)乘以1/log2(10),这又增加了5个周期.
查找log2是找到值的最低有效位的索引的问题. (视频大约在第23分钟开始).
bit hacks:查找整数的整数对数10
bit hacks:在O(lg(N))中找到N位整数的对数库2
通过首先使用上述技术之一来查找日志库2来计算整数对数库10.通过关系log10(v)= log2(v)/ log2(10),我们需要将其乘以1/log2( 10),大约是1233/4096,或1233,然后右移12.需要添加一个,因为IntegerLogBase2向下舍入.最后,由于值t只是一个可能偏离1的近似值,因此通过减去v <PowersOf10 [t]的结果得到精确值.
此方法比IntegerLogBase2多运行6次.通过修改上面的log base 2 table-lookup方法,可以加速(在具有快速内存访问的机器上),以便条目保存为t计算的内容(即pre-add,-mulitply和-shift).这样做将需要总共仅9次操作来找到日志库10,假设使用了4个表(对于v的每个字节一个表).
值得注意的是:使用DeBruijn序列查找和位移技术来计算此MIT视频中的 log2 :Lec 2 | 麻省理工学院6.172软件系统性能工程,2010年秋季(视频在第36分钟开始).
值得注意的是,这个StackOverflow帖子演示了一种方法,可以使高效的log2计算真正与C++交叉平台
警告:我没有检查过numpy源代码来验证它确实实现了类似的技术,但它确实没有.事实上,根据OP的帖子中的评论,Fermion Portal已经检查过:
实际上numpy使用glibc中的math.h,如果你使用math.h/cmath.h,你会在C/C++中看到相同的区别.你可以找到两个函数的评论很好的源代码,例如 ic.unicamp.br/~islene/2s2008-mo806/libc/sysdeps/ieee754/dbl-64/...和 ic.unicamp.br/~islene/2s2008-mo806/libc/sysdeps/ieee754/dbl-64/... - Fermion Portal [9]
这只是一个注释,但比评论更长.显然,这与您的特定安装有关:
import numpy as np
import numexpr as ne
x = np.random.rand(100000)
我从conda和使用icc编译的版本得到了与numpy 1.10相同的时序:
%timeit np.log2(x)
1000 loops, best of 3: 1.24 ms per loop
%timeit np.log(x)
1000 loops, best of 3: 1.28 ms per loop
我认为抓住MKL VML包可能有些东西,但看起来不是这样:
%timeit ne.evaluate('log(x)')
1000 loops, best of 3: 218 µs per loop
看起来你的numpy安装从两个不同的地方抓取它的log/log2实现是奇怪的.
免责声明：我既不是可信的也不是官方消息来源。
我几乎可以肯定，任何基于 e 函数的 log 实现都可以像 log2 函数一样快，因为要将一个函数转换为另一个函数，您需要除以常数。这当然是假设单个除法运算是其他计算的一小部分；这在对数的准确实现中是正确的。
在大多数情况下，numpy 使用math.hfrom glibc，如果您使用math.h/ ，您将在 C/C++ 中看到相同的差异cmath.h。在评论中，有些人观察到np.log和 的速度相同np.log2；我怀疑这可能来自不同的构建/平台。
你可以找到两个函数的很好的注释的源代码文件e_log.c，e_log2.c，e_logf.c，e_log2f.c在dbl-64/和flt-32/子目录这个GitHub库。
对于双精度，in glibc，该log函数正在实现与log2IBM完全不同的算法（与2001相比），该算法包含在他们的libultim库中。而log2来自大约 1993 年的 Sun Microsystems。仅查看代码就可以看到正在实现两种不同的近似值。相反，对于单精度，两者的功能log和log2是相同的距除以ln2在log2的情况下，因此具有相同的速度。
有关基础算法的更多背景、替代方案和glibc将来要包含的讨论，请参见此处。