Потеря производительности при использовании функтора для предоставления функции или оператора в качестве параметра шаблона C ++?

Question

У меня есть семейство сложных функций, выполняющих очень похожие задачи, за исключением одного оператора прямо в середине функции. Упрощенная версия моего кода может выглядеть примерно так:

#include <assert.h>

static void memopXor(char * buffer1, char * buffer2, char * res, unsigned n){
    for (unsigned x = 0 ; x < n ; x++){
        res[x] = buffer1[x] ^ buffer2[x];
    }
};

static void memopPlus(char * buffer1, char * buffer2, char * res, unsigned n){
    for (unsigned x = 0 ; x < n ; x++){
        res[x] = buffer1[x] + buffer2[x];
    }
};

static void memopMul(char * buffer1, char * buffer2, char * res, unsigned n){
    for (unsigned x = 0 ; x < n ; x++){
        res[x] = buffer1[x] * buffer2[x];
    }
};


int main(int argc, char ** argv){
    char b1[5] = {0, 1, 2, 3, 4};
    char b2[5] = {0, 1, 2, 3, 4};

    char res1[5] = {};
    memopXor(b1, b2, res1, 5);

    assert(res1[0] == 0);
    assert(res1[1] == 0);
    assert(res1[2] == 0);
    assert(res1[3] == 0);
    assert(res1[4] == 1);

    char res2[5] = {};
    memopPlus(b1, b2, res2, 5);

    assert(res2[0] == 0);
    assert(res2[1] == 2);
    assert(res2[2] == 4);
    assert(res2[3] == 6);
    assert(res2[4] == 8);

    char res3[5] = {};
    memopMul(b1, b2, res3, 5);

    assert(res3[0] == 0);
    assert(res3[1] == 1);
    assert(res3[2] == 4);
    assert(res3[3] == 9);
    assert(res3[4] == 16);
}

Выглядит хорошим примером использования шаблонов C ++, чтобы избежать дублирования кода, поэтому я искал способ изменить свой код на что-то вроде ниже (псевдокод):

#include <assert.h>

template <FUNCTION>
void memop<FUNCTION>(char * buffer1, char * buffer2, char * res, size_t n){
    for (size_t x = 0 ; x < n ; x++){
        res[x] = FUNCTION(buffer1[x], buffer2[x]);
    }
}

int main(int argc, char ** argv){
    char b1[5] = {0, 1, 2, 3, 4};
    char b2[5] = {0, 1, 2, 3, 4};

    char res1[5] = {};
    memop<operator^>(b1, b2, res1, 5);

    assert(res1[0] == 0);
    assert(res1[1] == 0);
    assert(res1[2] == 0);
    assert(res1[3] == 0);
    assert(res1[4] == 0);

    char res2[5] = {};
    memop<operator+>(b1, b2, res2, 5);

    assert(res2[0] == 0);
    assert(res2[1] == 2);
    assert(res2[2] == 4);
    assert(res2[3] == 6);
    assert(res2[4] == 8);

    char res3[5] = {};
    memop<operator*>(b1, b2, res3, 5);

    assert(res3[0] == 0);
    assert(res3[1] == 1);
    assert(res3[2] == 4);
    assert(res3[3] == 9);
    assert(res3[4] == 16);
}

Сложность в том, что я не готов принять какое-либо замедление в результате кода. Это означает, что решения, подразумевающие косвенные вызовы (либо через vtable, либо через указатели функций), не подходят.

Обычное решение C ++ для этой проблемы, по-видимому, заключает в себе оператор для вызова внутри метода operator () класса функторов. Как правило, чтобы получить что-то вроде кода ниже:

#include <assert.h>

template <typename Op>
void memop(char * buffer1, char * buffer2, char * res, unsigned n){
    Op o;
    for (unsigned x = 0 ; x < n ; x++){
        res[x] = o(buffer1[x], buffer2[x]);
    }
};


struct Xor
{
    char operator()(char a, char b){
        return a ^ b;
    }
};

struct Plus
{
    char operator()(char a, char b){
        return a + b;
    }
};

struct Mul
{
    char operator()(char a, char b){
        return a * b;
    }
};

int main(int argc, char ** argv){
    char b1[5] = {0, 1, 2, 3, 4};
    char b2[5] = {0, 1, 2, 3, 4};

    char res1[5] = {};
    memop<Xor>(b1, b2, res1, 5);

    assert(res1[0] == 0);
    assert(res1[1] == 0);
    assert(res1[2] == 0);
    assert(res1[3] == 0);
    assert(res1[4] == 0);

    char res2[5] = {};
    memop<Plus>(b1, b2, res2, 5);

    assert(res2[0] == 0);
    assert(res2[1] == 2);
    assert(res2[2] == 4);
    assert(res2[3] == 6);
    assert(res2[4] == 8);

    char res3[5] = {};
    memop<Mul>(b1, b2, res3, 5);

    assert(res3[0] == 0);
    assert(res3[1] == 1);
    assert(res3[2] == 4);
    assert(res3[3] == 9);
    assert(res3[4] == 16);
}

Есть ли какое-либо снижение производительности?

Answer 1

Код, который вы раскрываете, бесполезен с точки зрения бенчмарка.

char cversion() {
    char b1[5] = {0, 1, 2, 3, 4};
    char b2[5] = {0, 1, 2, 3, 4};

    char res1[5] = {};
    memopXor(b1, b2, res1, 5);

    return res1[4];
}

char cppversion() {
    char b1[5] = {0, 1, 2, 3, 4};
    char b2[5] = {0, 1, 2, 3, 4};

    char res1[5] = {};
    memop<Xor>(b1, b2, res1, 5);

    return res1[4];
}

компилируется в такой LLVM IR:

define signext i8 @cversion()() nounwind uwtable readnone {
  ret i8 0
}

define signext i8 @cppversion()() nounwind uwtable readnone {
  ret i8 0
}

То есть компилятор выполняет все вычисления во время компиляции.

Итак, я позволил себе определить новую функцию:

void cppmemopXor(char * buffer1,
                 char * buffer2,
                 char * res,
                 unsigned n)
{
  memop<Xor>(buffer1, buffer2, res, n);
}

и удалил квалификатор static на memopXor, а затем повторил опыт:

define void @memopXor(char*, char*, char*, unsigned int)(i8* nocapture %buffer1, i8* nocapture %buffer2, i8* nocapture %res, i32 %n) nounwind uwtable {
  %1 = icmp eq i32 %n, 0
  br i1 %1, label %._crit_edge, label %.lr.ph

.lr.ph:                                           ; preds = %.lr.ph, %0
  %indvars.iv = phi i64 [ %indvars.iv.next, %.lr.ph ], [ 0, %0 ]
  %2 = getelementptr inbounds i8* %buffer1, i64 %indvars.iv
  %3 = load i8* %2, align 1, !tbaa !0
  %4 = getelementptr inbounds i8* %buffer2, i64 %indvars.iv
  %5 = load i8* %4, align 1, !tbaa !0
  %6 = xor i8 %5, %3
  %7 = getelementptr inbounds i8* %res, i64 %indvars.iv
  store i8 %6, i8* %7, align 1, !tbaa !0
  %indvars.iv.next = add i64 %indvars.iv, 1
  %lftr.wideiv = trunc i64 %indvars.iv.next to i32
  %exitcond = icmp eq i32 %lftr.wideiv, %n
  br i1 %exitcond, label %._crit_edge, label %.lr.ph

._crit_edge:                                      ; preds = %.lr.ph, %0
  ret void
}

И версия C ++ с шаблонами:

define void @cppmemopXor(char*, char*, char*, unsigned int)(i8* nocapture %buffer1, i8* nocapture %buffer2, i8* nocapture %res, i32 %n) nounwind uwtable {
  %1 = icmp eq i32 %n, 0
  br i1 %1, label %_ZL5memopI3XorEvPcS1_S1_j.exit, label %.lr.ph.i

.lr.ph.i:                                         ; preds = %.lr.ph.i, %0
  %indvars.iv.i = phi i64 [ %indvars.iv.next.i, %.lr.ph.i ], [ 0, %0 ]
  %2 = getelementptr inbounds i8* %buffer1, i64 %indvars.iv.i
  %3 = load i8* %2, align 1, !tbaa !0
  %4 = getelementptr inbounds i8* %buffer2, i64 %indvars.iv.i
  %5 = load i8* %4, align 1, !tbaa !0
  %6 = xor i8 %5, %3
  %7 = getelementptr inbounds i8* %res, i64 %indvars.iv.i
  store i8 %6, i8* %7, align 1, !tbaa !0
  %indvars.iv.next.i = add i64 %indvars.iv.i, 1
  %lftr.wideiv = trunc i64 %indvars.iv.next.i to i32
  %exitcond = icmp eq i32 %lftr.wideiv, %n
  br i1 %exitcond, label %_ZL5memopI3XorEvPcS1_S1_j.exit, label %.lr.ph.i

_ZL5memopI3XorEvPcS1_S1_j.exit:                   ; preds = %.lr.ph.i, %0
  ret void
}

Как и ожидалось, они структурно идентичны, поскольку код функтора был полностью встроен (, который виден даже без понимания ИК ).

Обратите внимание, что это не результат изоляции. Например, std::sort выполняет в два-три раза быстрее, чем qsort, потому что он использует функтор вместо косвенного вызова функции. Конечно, использование шаблонной функции и функтора означает, что каждая отдельная реализация будет генерировать новый код, как если бы вы кодировали функцию вручную, но в любом случае это именно то, что вы делали вручную.

Answer 2

Единственная проблема, с которой я столкнулся в приведенном выше коде, это то, что у компилятора будут проблемы с псевдонимами операций с памятью при вызове memop, см .: C ++ правила псевдонимов .

Помните также, что в версии шаблона компилятор будет генерировать отдельный объект для каждого передаваемого уникального аргумента шаблона, что означает, что за три вызова memop с тремя различными операциями вы получите три реализации в двоичном файле. Это должно привести к коду, который почти идентичен вашему исходному коду.

Я согласен с другим комментатором, что функции должны быть встроены. Однако, если производительность критична, вы должны тестировать свой код до и после предложенных изменений, просто чтобы быть в безопасности, все, что нужно, это неправильный флаг компилятора, чтобы взорвать все.

Answer 3

Только вы можете сказать, достаточно ли быстро что-то для ваших нужд.Но я пошел дальше и запустил ваш код в своем собственном окне, чтобы посмотреть, что произойдет.

int main(int argc, char ** argv){
  char b1[5] = {0, 1, 2, 3, 4};
  char b2[5] = {0, 1, 2, 3, 4};

  int ans = 0;

  for (int i = 0; i < 100000000; i++) {
    char res1[5] = {};
    memopXor(b1, b2, res1, 5);
//    memop<Xor>(b1, b2, res1, 5);

    char res2[5] = {};
    memopPlus(b1, b2, res2, 5);
//    memop<Plus>(b1, b2, res2, 5);

    char res3[5] = {};
    memopMul(b1, b2, res3, 5);
//    memop<Mul>(b1, b2, res3, 5);

    ans += res1[0] + res2[1] + res3[2];  // prevents optimization
  }

  std::cout << ans << std::endl;

  return 0;
}

Я скомпилировал обе версии с -O3 на g ++.time возвращает 2,40 секунды для версии с ручным кодированием и 2,58 секунды для версии шаблона.

(Кстати, мне пришлось исправить ваш memopMul(), чтобы фактически выполнить умножение.)