Могут ли пользовательские классы С++ реплицировать производительность встроенных типов?
Я пытаюсь создать класс С++, который ведет себя точно так же, как встроенный тип int с одним исключением: везде, где вызывается оператор * (или оператор * =), вместо этого вызывается добавление.
Во-первых, производительность моего класса была очень плохой (по сравнению с встроенным типом int), но я заметил, что это было потому, что я забыл включить конструктор копирования ниже:
struct AlmostInt {
AlmostInt () { }
AlmostInt (const AlmostInt &a) : val(a.val) { } // forgetting this killed
// performance
AlmostInt operator+(const AlmostInt &a) const { AlmostInt result = *this;
result.val += a.val;
return result; }
AlmostInt operator-(const AlmostInt &a) const { AlmostInt result = *this;
result.val -= a.val;
return result; }
AlmostInt operator*(const AlmostInt &a) const { AlmostInt result = *this;
result.val = result.val + a.val;
return result; }
AlmostInt &operator+=(const AlmostInt &a) { this->val += a.val;
return *this; }
AlmostInt &operator-=(const AlmostInt &a) { this->val -= a.val;
return *this; }
AlmostInt &operator*=(const AlmostInt &a) { this->val = this->val + a.val);
return *this; }
private:
int val;
};
К сожалению, моя программа остается на 25% медленнее, чем она должна быть. Изучая сборку, сгенерированную для двух разных версий программы (одна использует int, а другая - с помощью AlmostInt), я вижу, что существует одинаковое количество операций + и -, поэтому вещи "работают" на некотором уровне.
Проблема заключается в том, что в коде есть значительно больше операций загрузки и хранения, используя класс AlmostInt, а не встроенную операцию int.
Есть ли у кого-нибудь идеи о том, откуда могут возникать эти накладные расходы? Единственное предположение
У меня было то, что, возможно, компилятор не понимает, что AlmostInt имеет все
те же свойства int (например, ассоциативность, коммутативность), но если это действительно
проблема, я бы ожидал, что в коде будет несколько команд "+" или "-", и этого не произойдет.
Я подозреваю, что дополнительные нагрузки и хранилища связаны с дополнительной активностью стека, но
все, что я могу сказать в этот момент, - это не просто несколько дополнительных нагрузок и хранилищ стека на
сверху и снизу каждой функции, но дополнительные нагрузки и хранилища происходят во всем коде.
Любые идеи? Интересно, может ли кто-нибудь указать мне на компилятор, который позволяет
один для достижения уровня производительности int с помощью пользовательского класса.
UPDATE:
Вот простая функция, которую вы можете вырезать и вставить, чтобы увидеть, что происходит для вас. На x86-64 Linux (g++ 4.3, 4.4), AIX6 xlC и на нескольких других платформах, изменив строки "CHOOSE ONE..." ниже, должен привести к созданию того же кода (или, по крайней мере, кода с одинаковой производительностью), но на практике код раздувается значительно. Может ли кто-нибудь объяснить, что происходит (для какой-либо конкретной платформы/компилятора) или как его исправить?
class AlmostInt
{
int value;
public:
AlmostInt& operator+=(AlmostInt that)
{
value += that.value;
return *this;
}
AlmostInt& operator-=(AlmostInt that)
{
value -= that.value;
return *this;
}
AlmostInt& operator*=(AlmostInt that)
{
value *= that.value;
return *this;
}
};
AlmostInt operator+(AlmostInt lhs, AlmostInt rhs)
{
lhs += rhs;
return lhs;
}
AlmostInt operator-(AlmostInt lhs, AlmostInt rhs)
{
lhs -= rhs;
return lhs;
}
AlmostInt operator*(AlmostInt lhs, AlmostInt rhs)
{
lhs *= rhs;
return lhs;
}
// CHOOSE ONE OF THE FOLLOWING TWO LINES:
//typedef int real;
typedef AlmostInt real;
typedef struct {
real re;
real im;
} complex;
#define R(a0,a1,b0,b1,wre,wim) { \
t1 = a0 - a1; t2 = b0 - b1; \
t5 = t1 * wim; t6 = t2 * wim; \
t3 = a0; t1 *= wre; \
t3 += a1; t2 *= wre; \
t1 -= t6; t4 = b0; \
t2 += t5; t4 += b1; \
a0 = t3; b1 = t2; \
a1 = t4; b0 = t1; \
}
#define RZERO(a0,a1,b0,b1) { \
t1 = a0 - a1; t2 = b0 - b1; \
t3 = a0 + a1; t4 = b0 + b1; \
b0 = t1; a0 = t3; \
b1 = t2; a1 = t4; \
}
void rpass(real *a, const complex *w, unsigned int n)
{
real t1, t2, t3, t4, t5, t6, t7, t8;
real *b;
unsigned int k;
b = a + 4 * n;
k = n - 2;
RZERO(a[0],a[1],b[0],b[1]);
R(a[2],a[3],b[2],b[3],w[0].re,w[0].im);
R(a[4],a[5],b[4],b[5],w[1].re,w[1].im);
R(a[6],a[7],b[6],b[7],w[2].re,w[2].im);
for (;;) {
R(a[8],a[9],b[8],b[9],w[3].re,w[3].im);
R(a[10],a[11],b[10],b[11],w[4].re,w[4].im);
R(a[12],a[13],b[12],b[13],w[5].re,w[5].im);
R(a[14],a[15],b[14],b[15],w[6].re,w[6].im);
if (!(k -= 2)) break;
a += 8;
b += 8;
w += 4;
}
}
(Кредит, причитающийся за кредит: этот маленький ориентир исходит из библиотеки djbfft Дэна Бернштейна)
Ответы
Ответ 1
Одна из наиболее частых причин потери производительности в подобных случаях
возвращает значения из функций. Теоретически компилятор должен быть
способный оптимизировать это, и делать то же самое, что если бы вы вернули int
(при условии, что все соответствующие функции включены); на практике все
компиляторы, которые я знаю, вернут int в регистр, но для класса
type, передаст дополнительный скрытый аргумент с адресом
временно, и вернуть значение в память по этому адресу. Причина
заключается в том, что такие вещи, как конструктор или присвоение копии, требуют
адрес (этот указатель, ссылка на то, что копируется), и
компилятор, похоже, не признает, что после того, как он включил все
функций, адрес больше не понадобится. (Там также
факт, что бинарный API говорит, чтобы сделать это таким образом, но бинарный API
обычно относится только к структурам, а не к типам нетривиальных
конструкторы, деструкторы и операторы присваивания.)
Ответ 2
Я бы избавился от конструкторов, заменил вызов ссылкой-на-const с вызовом по значению (потому что объекты AlmostInt действительно малы) и реализовать немодифицирующие операторы в виде бесплатных функций:
class AlmostInt
{
int value;
public:
AlmostInt& operator+=(AlmostInt that)
{
value += that.value;
return *this;
}
AlmostInt& operator-=(AlmostInt that)
{
value -= that.value;
return *this;
}
AlmostInt& operator*=(AlmostInt that)
{
value *= that.value;
return *this;
}
};
AlmostInt operator+(AlmostInt lhs, AlmostInt rhs)
{
lhs += rhs;
return lhs;
}
AlmostInt operator-(AlmostInt lhs, AlmostInt rhs)
{
lhs -= rhs;
return lhs;
}
AlmostInt operator*(AlmostInt lhs, AlmostInt rhs)
{
lhs *= rhs;
return lhs;
}
Это должно иметь потенциал, чтобы избавиться от лишних накладных расходов.
Ответ 3
Возможно, вместо вашего собственного класса вы можете делать вещи с коллекцией #define, поэтому:
// For normal operations
#define specialplus +
#define specialmultiple *
// And a separate compilation with
#define specialplus min
#define specialmultiple +
Может быть, лучше как:
// normalmath.c
#define plus(a,b) (a)+(b)
#define star(a,b) (a)*(b)
#define FUNCTYPE normal
#include "yourcode.c"
// tropicalmath.c
#define plus(a,b) min((a),(b))
#define star(a,b) (a)+(b)
#define FUNCTYPE tropical
#include "yourcode.c"
// yourcode.c
int FUNCTYPE_opp(int x, int y)
{
// for example
return star(plus(x,y),52);
}
(по крайней мере, если я не испортил свой код препроцессора C).
Или, по крайней мере, что-то из этой формы? Возможно, с некоторой хитрой функцией именования, позволяющей одновременно использовать оба типа этих типов?
Ответ 4
Основываясь на комментариях Фумийо:
Проверьте, работает ли AlmostInt так же быстро, как обычный int на обычной машине:
Вот код, который я запускал:
Это матричное умножение (или попытки быть, я не уверен, что правильно понял). Но в любом случае он много размножается и дополняет то, что мы хотим проверить. Он скомпилирован просто с -O3
В функции main() я запускаю умножение 10 000 раз.
Результат:
AlmostInt: 10093876
int 10320511
В моих книгах, которые совпадают с нашим пределом погрешности.
#include <vector>
#include <iostream>
#include <time.h>
#ifdef ALMOST_INT
class AlmostInt
{
int value;
public:
explicit AlmostInt(int i): value(i) {}
AlmostInt(): value(0) {}
AlmostInt& operator+=(AlmostInt const& that)
{
value += that.value;
return *this;
}
AlmostInt& operator-=(AlmostInt const& that)
{
value -= that.value;
return *this;
}
AlmostInt& operator*=(AlmostInt const& that)
{
value *= that.value;
return *this;
}
};
AlmostInt operator+(AlmostInt lhs, AlmostInt const& rhs) { return lhs += rhs; }
AlmostInt operator-(AlmostInt lhs, AlmostInt const& rhs) { return lhs -= rhs; }
AlmostInt operator*(AlmostInt lhs, AlmostInt const &rhs) { return lhs *= rhs; }
#else
typedef int AlmostInt;
#endif
typedef std::vector<AlmostInt> Vector;
typedef std::vector<Vector> Matrix;
void mult(Matrix const& a, Matrix const& b, Matrix& r)
{
for(int x =0; x < 100; ++x)
{
for(int y =0; y < 100; ++y)
{
AlmostInt sum(0);
for(int s = 0;s < 100; ++s)
{
sum += a[s][y] * b[x][s];
}
r[x][y] = sum;
}
}
}
int main()
{
Matrix a(100, Vector(100));
Matrix b(100, Vector(100));
Matrix r(100, Vector(100));
clock_t t = 0;
for(int loop=0;loop < 10000; ++loop)
{
if ((loop % 100) == 0) std::cout << "Time: " << t << "\n";
clock_t s = clock();
mult(a, b, r);
clock_t e = clock();
t += (e-s);
}
}
