So with the following code, changing the type of the parameter x from const ull to const ull& (with typedef unsigned long long ull) results in a roughly 25% speedup when compiled with gcc 4.7.2 and flags -O3 -std=c++11 -g, and I can't figure out why this would make such a big difference.
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;
}
It is called in the following function (for doing schoolbook long multiplication)
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;
}
}
The timing is done by calling clock() around a loop to measure how long it takes. Not the most accurate/precise way, but I figured a consistent 25% difference meant the difference was statistically significant.
Full working code block:
#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;
}
And runtimes (I named the file that passes the value value.cpp and reference 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.
