- android - 多次调用 OnPrimaryClipChangedListener
- android - 无法更新 RecyclerView 中的 TextView 字段
- android.database.CursorIndexOutOfBoundsException : Index 0 requested, 光标大小为 0
- android - 使用 AppCompat 时,我们是否需要明确指定其 UI 组件(Spinner、EditText)颜色
这是一个对整数 vector 求和的基本函数。当使用具有第三级优化 (-O3) 的 gcc 编译时,我可以达到 CPE 0.51,这是我们可以获得的最大值。
int sum_basic(int a[], long n)
{
int acc = 0;
for (long i = 0; i < n; i++) {
acc += a[i];
}
return acc;
}
这是此函数的优化版本,它应用4x4 循环展开。我能得到的最好结果是 CPE 0.84。我尝试了其他类型的优化,但无法接近 CPE 0.51。使用整数乘法我可以击败 gcc,使用浮点运算我也可以达到最佳性能,而 gcc 不能。但是整数加法 gcc 打败了我。有什么问题?
int sum_optimized(int a[], long n) {
int acc1 = 0;
int acc2 = 0;
int acc3 = 0;
int acc4 = 0;
for (long i = 0; i < n; i+=4) {
acc1 += a[i];
acc2 += a[i+1];
acc3 += a[i+2];
acc4 += a[i+3];
}
return acc1 + acc2 + acc3 + acc4;
}
我使用此代码来衡量 CPE:
// get CPU cycle counter
static __inline__ unsigned long long rdtsc(void)
{
unsigned hi, lo;
__asm__ __volatile__ ("rdtsc" : "=a"(lo), "=d"(hi));
return ( (unsigned long long)lo)|( ((unsigned long long)hi)<<32 );
}
#define SIZE 10000
int a[SIZE];
int main(void)
{
// cache warm up + initialize array
for (long i = 0; i < SIZE; i++)
a[i] = rand();
long r_begin = rdtsc();
//---------- MEASURE THIS ------------
int res = sum_optimized(a, SIZE);
//------------------------------------
long r_end = rdtsc();
long cycles = r_end - r_begin;
double cpe = cycles / (double)SIZE;
printf("CPE: %.2f \n", cpe);
return res;
}
最佳答案
TL:DR:这可能是一个已知的优化错误错误(gcc 不对带符号的整数进行关联数学优化),再加上普通的老式编译器实际上并不是人工智能并且生成的代码很慢。
首先,RDTSC 测量挂钟时间,不一定是核心时钟周期。使用性能计数器测量微基准测试中的核心时钟周期,这样您就不必担心 CPU 频率缩放。 (除非您的微基准测试涉及 L2 缓存未命中,因为以纳秒为单位的相同时间是更高频率下更多的时钟周期。即高频意味着缓存未命中造成的伤害更大,并且主内存带宽以每个周期的字节数计更低。)
gcc 5.3(没有 -march=nehalem
或 -mtune=haswell
或任何东西)将基本版本自动矢量化为其通常选择的标量,直到对齐边界,然后是向量化的内循环:
# gcc5.3 -O3 -fverbose-asm (-mtune=generic; only SSE2 because no -march used)
sum_basic:
... scalar prologue
.L14: ### inner loop
add rdx, 1 # ivtmp.39,
paddd xmm0, XMMWORD PTR [r9] # vect_acc_10.34, MEM[base: _156, offset: 0B]
add r9, 16 # ivtmp.40,
cmp r8, rdx # bnd.28, ivtmp.39
ja .L14 #,
... horizontal sum and scalar epilogue
所以,愚蠢的 gcc,保留两个独立的循环计数器,而不是仅仅检查 r9
是否到达 a+n
。或者至少使用 dec rdx/jnz
循环以避免 cmp
。但是不,所以循环有 4 个融合域微指令,它们都需要一个 ALU 端口。因此它可以在 Intel Core2 及更高版本上每个时钟迭代一次,但在 Haswell 及更高版本(添加了第 4 个 ALU 端口)上每个时钟只能执行一次迭代。
在 SnB 及更高版本上,具有两个 vector ALU 的展开将使小型阵列的吞吐量翻倍,因为 PADDD
具有一个周期延迟,但每个周期吞吐量有两个(或三个),负载也是如此.在更大的阵列上,您仍然只是内存带宽的瓶颈。
当您手动展开 4 个累加器时,gcc 决定保留这些语义,并且只在内部循环中使用未对齐的加载。不幸的是,gcc 5.3 最终做得非常糟糕:
# gcc5.3 -O3 -fverbose-asm (-mtune=generic, same lack of enabling SSE4/AVX/AVX2)
sum_optimized:
zero xmm0 and some other minor setup
.L3:
mov rdx, rax
add rax, 1
sal rdx, 4 # what the hell gcc? just add 16 instead of copying and shifting a separate instructions. Even if it takes two loop counters like in the basic version.
cmp rcx, rax # cmp not next to ja, can't macro-fuse. (-mtune=haswell fixes this)
movdqu xmm1, XMMWORD PTR [rdi+rdx] # separate load, not folded into paddd because it's unaligned.
paddd xmm0, xmm1
ja .L3
...
A hilarious horizontal sum that uses MOVD on each element separately and sums with scalar integer ops. (With -march=nehalem, it uses PEXTRD)
这是 Intel Nehalem 及更高版本上的 7 个融合域微指令。在 Core2 上,它是 9 uops IIRC。在 Nehalem 之前,movdqu 是多个 uops,运行速度比 movdqa 慢,即使数据在运行时对齐也是如此。
无论如何,假设 Nehalem 或更高版本,这可以每 2 个周期迭代一次,这就是瓶颈。执行每 2 个周期最多可以处理 6 个 ALU 微指令。即使指针未对齐,也不应再减慢它的速度,因为 gcc 的代码已经很慢了。
我的理论是,这是因为 gcc 中一个已知的未优化错误:以不同的顺序添加数字会导致溢出。多亏了 2 的补码,一切最终都会成功,但 gcc 不知道如何利用它。 C 中的有符号溢出是未定义的行为,但在 x86 上不是。
理查德·比纳 (Richard Biener) 对 my gcc bug report about gcc not doing associative-math optimizations on signed-int a+b+c+d+e+f+g+h
的回应,他说:
It's a long-standing issue that reassoc doesn't associate ! TYPE_OVERFLOW_WRAPS chains.It's a long-standing issue that reassoc doesn't associate ! TYPE_OVERFLOW_WRAPS chains. It could do that to a limited extent (only cancelling ops that don't affect overflow) or fully if it re-writes the operation to unsigned arithmetic at commit time. Some way of detecting desired vs. just canonicalization transforms is required to avoid rewriting all signed integer ops into unsigned (well, maybe it's not that bad actually, who knows).
两个版本使用的水平求和算法为这一理论提供了一些分量:sum_basic 使用正常的向下移动高半和 vector 相加。 sum_optimized 分别提取每个 vector 元素。
使用 -march=native
编译,尤其是当您的 CPU 支持 AVX2 时。
正如我之前提到的,多个 vector 累加器可以在 Intel SnB 系列或 AMD K10 或更高版本上为您提供两个负载和每个时钟的两个 128 或 256b vector 加法. (IIRC,AMD K8 可以每个时钟执行两次加载,但没有 128b 宽的执行单元。)
与往常一样,在什么硬件上运行微基准测试以及阵列大小很重要!
关于c - 为什么我无法通过整数加法获得最佳性能?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/39308701/
我正在尝试学习 Fortran,并且看到了很多不同的定义,我想知道他们是否正在尝试完成同样的事情。以下有什么区别? 整数*4 整数(4) 整数(kind=4) 最佳答案 在 Fortran >=90
我以前从未编程过,最近(1 周前)才开始学习!第一门类(class)是函数式编程,使用 Haskell。 我有一项学校作业,我想通过删除一两个步骤来改进它,但我遇到了一个讨厌的错误。 基本上,我创建了
给定以下GraphQL请求和变量: 请求: query accounts($filter:AccountFilter, $first_:String, $skip_:Int) { accounts
我已经搜索了 StackOverflow,但找不到关于如何检查计算器应用程序的数字输入正则表达式的答案,该计算器应用程序将检查每个 keyup 的以下格式(jquery key up): 任何整数,例
类似于我上一篇致歉的文章,但没有那么长篇大论。基本上我想知道当每次重绘调用只重绘屏幕的一小部分时,优化重绘到 JFrame/JPanel 的最佳选择是什么。 此外,除了重绘重载之外,我并不是 100%
所以在我的教科书中有一个使用 f# 的递归函数的例子 let rec gcd = function | (0,n) -> n | (m,n) -> gcd(n % m,m);; 使用此功能,我的教科书
我有一个数据结构,例如表达式树或图形。我想添加一些“测量”功能,例如depth和 size . 如何最好地键入这些函数? 我认为以下三个变体的用处大致相同: depth :: Expr -> Int
这样写比较好 int primitive1 = 3, primitive2 = 4; Integer a = new Integer(primitive1); Integer b = new Inte
我是 Java 8 新手,想根据键对 Map 进行排序,然后在值内对每个列表进行排序。 我试图寻找一种 Java 8 方法来对键和值进行排序。HashMap>映射 map.entrySet().str
这就是我的目标... vector ,int> > var_name (x, pair (y),int>); 其中 x 是 vector var_name 的大小,y 是对内 vector 的大小。
这里是 an answer to "How do I instantiate a Queue object in java?" , Queue is an interface. You can't i
这个问题在这里已经有了答案: Weird Integer boxing in Java (12 个答案) Why are autoboxed Integers and .getClass() val
我们可以使用 C++ STL 做这样的事情吗?如果是,我将如何初始化元素?我试图这样做,但没有成功。 pair,vector>p; p.first[0]=2; 最佳答案 Can we do som
您好,我正在尝试为百分比和整数数组中的数字找到索引。假设 arraynum = ['10%','250','20%','500'] 并且用户发送一个值 15%,这个数字在哪个范围内居住?我可以使用这段
我与三列有关系:ProductName、CategoryID 和 Price。我需要选择仅那些价格高于给定类别中平均产品价格的产品。(例如,当apple(ProductName)是fruit(Cate
我已经坚持了一段时间,我正在尝试将一些数据配对在一起。这是我的代码。 #include #include using namespace std; int main() { pair data(
我收到错误:'(Int, Int)' 与 'CGPoint' 不相同 如何将 (Int, Int) 转换为 CGPoint let zigzag = [(100,100), (100,150)
我在 .cpp 文件中发现了以下代码。我不理解涉及头文件的构造或语法。我确实认识到这些特定的头文件与 Android NDK 相关。但是,我认为这个问题是关于 C++ 语法的一般问题。这些在某种程度上
我将这些输入到 Scala 解释器中: val a : Integer = 1; val b : Integer = a + 1; 我收到消息: :5: error: type mismatch;
C++:vector>v(size);当我试图打印出值时显示 0 作为值,但是当未声明 vector 大小时它显示正确的输出?为什么这样?例如: int x; cin>>x; vector>v(x);
我是一名优秀的程序员,十分优秀!