个人中心
文章发布
退出
作者热门文章
- mongodb - 在 MongoDB mapreduce 中，如何展平值对象？
- javascript - 对象传播与 Object.assign
- html - 输入类型 ="submit"Vs 按钮标签它们可以互换吗？
- sql - 使用 MongoDB 而不是 MS SQL Server 的优缺点
26
4
所以用下面的代码，把参数x的类型从const ull改为const ull&(用typedef unsigned long long ull) 在使用 gcc 4.7.2 和标志 -O3 -std=c++11 -g 编译时导致大约 25% 的加速，我不知道为什么这会产生如此大的影响。
static void inline single_mult(const std::vector<ull>::iterator& data,
const std::vector<ull>::const_iterator& rbegin,
const std::vector<ull>::const_iterator& rend,
const ull x) {
ull tmp=0, carry=0, i=0;
for (auto rhs_it = rbegin; rhs_it != rend; ++rhs_it) {
tmp = x*(*rhs_it) + data[i] + carry;
if (tmp >= imax) {
carry = tmp >> numbits;
tmp &= imax - 1;
} else {
carry = 0;
}
data[i++] = tmp;
}
data[i] += carry;
}
在以下函数中调用(用于做教科书长乘法)
static void naive(std::vector<ull>::iterator data,
std::vector<ull>::const_iterator cbegin,
std::vector<ull>::const_iterator cend ,
std::vector<ull>::const_iterator rbegin,
std::vector<ull>::const_iterator rend) {
for (auto data_it = cbegin;
data_it != cend; ++data_it) {
if (*data_it != 0) {
single_mult(data, rbegin, rend, *data_it);
}
++data;
}
}
计时是通过围绕一个循环调用 clock() 来测量它需要多长时间来完成的。不是最准确/最精确的方法，但我认为一致的 25% 差异意味着差异具有统计学意义。
完整的工作代码块:
#include <vector>
#include <limits>
#include <ctime>
#include <iostream>
typedef unsigned long long ull;
typedef unsigned int uint;
const ull numbits = (ull) std::numeric_limits<uint>::digits;
const ull imax = 1LL << numbits;
static void inline single_mult(const std::vector<ull>::iterator& data,
const std::vector<ull>::const_iterator& rbegin,
const std::vector<ull>::const_iterator& rend,
const ull x) {
ull tmp=0, carry=0, i=0;
for (auto rhs_it = rbegin; rhs_it != rend; ++rhs_it) {
tmp = x*(*rhs_it) + data[i] + carry;
if (tmp >= imax) {
carry = tmp >> numbits;
tmp &= imax - 1;
} else {
carry = 0;
}
data[i++] = tmp;
}
data[i] += carry;
}
static void naive(std::vector<ull>::iterator data,
std::vector<ull>::const_iterator cbegin,
std::vector<ull>::const_iterator cend ,
std::vector<ull>::const_iterator rbegin,
std::vector<ull>::const_iterator rend) {
for (auto data_it = cbegin; data_it != cend; ++data_it) {
if (*data_it != 0) {
single_mult(data, rbegin, rend, *data_it);
}
++data;
}
}
int main() {
int N = 10000;
std::vector<ull> vec(N);
for (int i=0; i<N; ++i) {
vec[i] = i;
}
auto s1 = clock();
int num = 10;
std::vector<ull> result(2*N);
for (int i=0; i<num; ++i) {
//Need to zero out the vector or the result will be different.
std::fill(result.begin(), result.end(), 0);
naive(result.begin(), vec.cbegin(), vec.cend(), vec.cbegin(), vec.cend());
}
s1 = (clock() - s1);
std::cout << "Took " << float(s1)/CLOCKS_PER_SEC << "seconds total." << std::endl;
}
和运行时(我将传递值的文件命名为value.cpp并引用reference.cpp)
$ g++ -O3 -std=c++11 -g -o reference reference.cpp
$ g++ -O3 -std=c++11 -g -o value value.cpp
$ ./reference
Took 1.05seconds total.
$ ./value
Took 1.83seconds total.
最佳答案
我能够重现您对加速的观察，这对我来说更加明显(快了 1.75 倍)。问题似乎在于，当您通过值传递 x 时，它使编译器能够执行原本不会执行的优化，而这些优化适得其反，它们显然会在处理器中引入意外的停顿。编译器生成几个条件移动，背靠背，而不是比较和分支。比较和分支的运行速度比背靠背条件移动快得多。
我可以通过简化编译器遇到问题的代码来避免这种情况，即这个
if (tmp >= imax) {
carry = tmp >> numbits;
tmp &= imax - 1;
} else {
carry = 0;
}
可以简化为
carry = tmp >> numbits;
tmp &= imax - 1;
这是我正在使用的 gcc 版本
g++ --version
g++ (GCC) 4.6.3 20120306 (Red Hat 4.6.3-2)
这些是我使用的命令，perf record 将分析您的代码，perf report 将使用分析结果注释源和反汇编
g++ -std=gnu++0x -O3 -g single_mult.cpp -o single_mult
perf record ./single_mult
perf report
在性能报告中按下 main 上的 enter 并选择 Annotate main，您将看到程序的反汇编以及源代码以及分析器发现您的程序在函数中的每条指令处运行的时间百分比......实际上这些数字必须仅作为提示，通常您会看到计数很大的指令，而实际上它是前一条指令停止，或者错过了缓存，或者有一个错误预测的分支等。所以当你看到一个大计数时，回头看看可能是什么原因造成的。原因是配置文件是统计的，它以恒定的速率中断您的程序并查看指令指针的位置，并且通常在处理器由于缓存未命中或错误预测的分支或某些内部原因而停止时发生中断数据依赖。
我增加了迭代次数，以便为分析器留出更多时间
int N = 20000;
当 x 按值传递时，它 总共花费了 11.58 秒，这就是我所看到的，请注意 cmovbe 指令
: ull tmp=0, carry=0, i=0;
: for (auto rhs_it = rbegin; rhs_it != rend; ++rhs_it) {
: tmp = x*(*rhs_it) + data[i] + carry;
11.10 : 400b40: 4c 89 c9 mov %r9,%rcx
0.00 : 400b43: 48 89 fa mov %rdi,%rdx
0.01 : 400b46: 48 03 14 c6 add (%rsi,%rax,8),%rdx
11.65 : 400b4a: 48 0f af 0c c3 imul (%rbx,%rax,8),%rcx
0.99 : 400b4f: 48 01 ca add %rcx,%rdx
: if (tmp >= imax) {
: carry = tmp >> numbits;
2.25 : 400b52: 48 89 d7 mov %rdx,%rdi
: tmp &= imax - 1;
10.99 : 400b55: 48 89 d1 mov %rdx,%rcx
: const ull x) {
: ull tmp=0, carry=0, i=0;
: for (auto rhs_it = rbegin; rhs_it != rend; ++rhs_it) {
: tmp = x*(*rhs_it) + data[i] + carry;
: if (tmp >= imax) {
: carry = tmp >> numbits;
0.69 : 400b58: 48 c1 ef 20 shr $0x20,%rdi
: tmp &= imax - 1;
9.54 : 400b5c: 83 e1 ff and $0xffffffff,%ecx
9.05 : 400b5f: 4c 39 c2 cmp %r8,%rdx
10.78 : 400b62: 49 0f 46 fb cmovbe %r11,%rdi
: } else {
: carry = 0;
: }
: data[i++] = tmp;
20.73 : 400b66: 48 83 c0 01 add $0x1,%rax
0.02 : 400b6a: 4c 39 c2 cmp %r8,%rdx
0.17 : 400b6d: 48 0f 46 ca cmovbe %rdx,%rcx
: static void inline single_mult(const std::vector<ull>::iterator& data,
: const std::vector<ull>::const_iterator& rbegin,
: const std::vector<ull>::const_iterator& rend,
: const ull x) {
: ull tmp=0, carry=0, i=0;
: for (auto rhs_it = rbegin; rhs_it != rend; ++rhs_it) {
11.47 : 400b71: 4c 39 d0 cmp %r10,%rax
: carry = tmp >> numbits;
: tmp &= imax - 1;
: } else {
: carry = 0;
: }
: data[i++] = tmp;
0.01 : 400b74: 48 89 4c c6 f8 mov %rcx,-0x8(%rsi,%rax,8)
: static void inline single_mult(const std::vector<ull>::iterator& data,
: const std::vector<ull>::const_iterator& rbegin,
: const std::vector<ull>::const_iterator& rend,
: const ull x) {
: ull tmp=0, carry=0, i=0;
: for (auto rhs_it = rbegin; rhs_it != rend; ++rhs_it) {
0.53 : 400b79: 75 c5 jne 400b40 <main+0x250>
: } else {
: carry = 0;
: }
: data[i++] = tmp;
: }
: data[i] += carry;
0.00 : 400b7b: 4a 01 3c d6 add %rdi,(%rsi,%r10,8)
0.01 : 400b7f: 48 83 c5 08 add $0x8,%rbp
当 x 通过引用传递时 总共花了 6.59 秒，这就是我看到的
: ull tmp=0, carry=0, i=0;
: for (auto rhs_it = rbegin; rhs_it != rend; ++rhs_it) {
20.90 : 400b30: 48 8b 17 mov (%rdi),%rdx
: tmp = x*(*rhs_it) + data[i] + carry;
1.38 : 400b33: 49 0f af 14 c1 imul (%r9,%rax,8),%rdx
4.82 : 400b38: 48 03 0c c6 add (%rsi,%rax,8),%rcx
22.41 : 400b3c: 48 01 ca add %rcx,%rdx
: if (tmp >= imax) {
: carry = tmp >> numbits;
: tmp &= imax - 1;
: } else {
: carry = 0;
2.95 : 400b3f: 31 c9 xor %ecx,%ecx
: const std::vector<ull>::const_iterator& rend,
: const ull &x) {
: ull tmp=0, carry=0, i=0;
: for (auto rhs_it = rbegin; rhs_it != rend; ++rhs_it) {
: tmp = x*(*rhs_it) + data[i] + carry;
: if (tmp >= imax) {
0.23 : 400b41: 4c 39 d2 cmp %r10,%rdx
0.00 : 400b44: 76 0a jbe 400b50 <main+0x260>
: carry = tmp >> numbits;
2.27 : 400b46: 48 89 d1 mov %rdx,%rcx
: tmp &= imax - 1;
1.29 : 400b49: 83 e2 ff and $0xffffffff,%edx
: const ull &x) {
: ull tmp=0, carry=0, i=0;
: for (auto rhs_it = rbegin; rhs_it != rend; ++rhs_it) {
: tmp = x*(*rhs_it) + data[i] + carry;
: if (tmp >= imax) {
: carry = tmp >> numbits;
0.26 : 400b4c: 48 c1 e9 20 shr $0x20,%rcx
: tmp &= imax - 1;
: } else {
: carry = 0;
: }
: data[i++] = tmp;
19.67 : 400b50: 48 83 c0 01 add $0x1,%rax
: static void inline single_mult(const std::vector<ull>::iterator& data,
: const std::vector<ull>::const_iterator& rbegin,
: const std::vector<ull>::const_iterator& rend,
: const ull &x) {
: ull tmp=0, carry=0, i=0;
: for (auto rhs_it = rbegin; rhs_it != rend; ++rhs_it) {
0.53 : 400b54: 4c 39 c0 cmp %r8,%rax
: carry = tmp >> numbits;
: tmp &= imax - 1;
: } else {
: carry = 0;
: }
: data[i++] = tmp;
0.39 : 400b57: 48 89 54 c6 f8 mov %rdx,-0x8(%rsi,%rax,8)
: static void inline single_mult(const std::vector<ull>::iterator& data,
: const std::vector<ull>::const_iterator& rbegin,
: const std::vector<ull>::const_iterator& rend,
: const ull &x) {
: ull tmp=0, carry=0, i=0;
: for (auto rhs_it = rbegin; rhs_it != rend; ++rhs_it) {
22.91 : 400b5c: 75 d2 jne 400b30 <main+0x240>
: } else {
: carry = 0;
: }
: data[i++] = tmp;
: }
: data[i] += carry;
0.00 : 400b5e: 4a 01 0c c6 add %rcx,(%rsi,%r8,8)
0.00 : 400b62: 48 83 c7 08 add $0x8,%rdi
关于c++ - 为什么将函数参数中的 `const ull` 更改为 `const ull&` 会导致性能提升？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/14805641/
26
4
0
CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界. 这篇CFSDN的博客文章详解dedecms后台编辑器将回车 改为 的方法由作者收集整理，如果你对
关闭。此题需要details or clarity 。目前不接受答案。 想要改进这个问题吗？通过 editing this post 添加详细信息并澄清问题. 已关闭 6 年前。 Improve th
不是将代码放在正文的头部或末尾(我把它放在正文的末尾)，如果我将代码放在 JS 文件中而不是在 html 中它自己的脚本标记，是否可以？ (我假设它像任何其他代码一样工作正常，但我问以防万一) 最佳答
我尝试执行从\e 命令编写的查询，但现在我无法执行任何查询，但可以在 PSQL 中执行命令。 现在我注意到这一点，我输入的命令现在在\e 中。 当我关闭\e(尝试运行它)时问题开始了。 最佳答案 ps
我有一个这样的字符串($ 字符总是被其他字符包围): a$b c$d e$f 我希望我的字符串方法在 $ 前面放置一个 \ 并删除换行符: a\$bc\$de\$f 我试过了，但它没有放入 \ 字符:
我需要使用 Java 构建一个 XML 文件。问题是我必须使用一些特殊字符，例如“ć”，然后在我的移动应用程序中读取它。 如果我手动更改 ć 就可以正常工作至 ć在我的 XML 文件中的记事
我有一个removeUser 页面，我在其中使用，然后使用submitForm() 函数进行错误处理。这段代码运行得非常好: export default function RemoveUserPag
我在数据库 “2048-05-21” 中有一个看起来像这样的日期 我只想得到年份，在这一年我只想得到两个后面的数字并将两个前面的数字更改为19 example: data : 2048-05-21 1
public class Venus1 { public static void main(String args[]) { int[]x={1,2,3};
我有以下 PHP 脚本，现在我需要在 JavaScript 中做同样的事情。 JavaScript 中是否有类似于 PHP 函数的函数，我已经搜索了好几天但找不到类似的东西？我想做的是计算某个单词在数
这个问题在这里已经有了答案: Is it bad practice to specify an array size using a variable instead of `#define` in
我陷入了一种情况，我必须通过“选中”工具栏中的复选框来“选中”列表中存在的所有复选框。 这是创建复选框列表的代码:- itemTpl: 'checked="checked" /> {groupName
我正在使用Python3。在分析一些网站时，我遇到了一些奇怪的字符并寻找解决方案。我找到了一个，但在找到解决方案之前，我尝试了一些方法，并且知道我无法重置它。当我使用 Jupyter 笔记本将列表 l
我在 http 下有 unity android app 和 site api 的工作基础设施。 最近换了服务器，申请了ssl证书。现在我的 api 在 https 下。 在 unity 应用程序中，
我在 http 下有 unity android app 和 site api 的工作基础设施。 最近换了服务器，申请了ssl证书。现在我的 api 在 https 下。 在 unity 应用程序中，
我在 Objective-C 中有一些代码。我想，我收到了 NSString 类型，但是当我尝试将它保存在核心数据中时，我得到了一个 user.clientID = clientID; 错误，例如:
在表中我有一个名为 CallTime 的字段 (Varchar)。 包括晚上8:00、晚上8:40、上午10:00等时间 我想将字段类型更改为“时间”并更新时间格式。该怎么做？ 谢谢 最佳答案 UPD
这个问题在这里已经有了答案: C# - for Loop Freezes at strange intervals (3 个答案) 关闭 6 年前。 我试图解决 problem #14 from P
我今天在 Pycharm 社区版 5.0.3 中收到了这个错误，想知道这是否只是我做错了/没有意识到，或者是 PyCharm lint 问题。重现错误的代码是 mylist = list() # fi
我的目标是将数据库中的随机文本显示到网页上。首先，我不知道为什么我的数据没有保存，为什么我得到的是[Entity of type sec.helloweb.HelloMessage with id:
我是一名优秀的程序员,十分优秀！