Верна ли моя реализация арифметики с фиксированной точкой?

Некоторое время назад я создал набор макросов C для манипулирования значениями с фиксированной точкой. Воодушевленный несколькими вопросами и ответами по SO, я надеялся получить прирост производительности в той части моей программы, которая требует интенсивных вычислений. Хотя код, кажется, дает правильные результаты, мне интересно, не слишком ли он наивен / упрощен, потому что на самом деле он работает для меня медленнее, чем обычные версии моих подпрограмм с плавающей запятой (я выполняю бикубическую интерполяцию изображений в Wintel). Не могли бы вы взглянуть на этот небольшой фрагмент кода, содержащий мои макросы, и предложить некоторые улучшения, особенно в отношении производительности? Спасибо.

// these are architecture-dependent
typedef short int fixed16;
typedef int fixed32;
typedef __int64 fixed64;

// value of 2^n
#define POW2(n) (1 << n)

// create 16bit integer-based fixed point value from a floating point value, n is the number of bits reserved for the fractional part
#define FP_MAKE16(x, n) ((x) > 0.0 ? static_cast<fixed16>(floor((x) * POW2(n) + 0.5)) : static_cast<fixed16>(ceil((x) * POW2(n) - 0.5)))
// the same, 32bit
#define FP_MAKE32(x, n) ((x) > 0.0 ? static_cast<fixed32>(floor((x) * POW2(n) + 0.5)) : static_cast<fixed32>(ceil((x) * POW2(n) - 0.5)))
// and 64bit
#define FP_MAKE64(x, n) ((x) > 0.0 ? static_cast<fixed64>(floor((x) * POW2(n) + 0.5)) : static_cast<fixed64>(ceil((x) * POW2(n) - 0.5)))

// convert a fixed-point integer from one (n) format to another (m) assuming n < m
#define FP_CONVERT_UP(x, n, m) ((x) << (m-n))
// same for n > m
#define FP_CONVERT_DOWN(x, n, m) ((x) >> (n-m))

// convert floating-point value back to float
#define FP_FLOAT(x, n) (static_cast<float>(x) / POW2(n))
// same for double 
#define FP_DOUBLE(x, n) (static_cast<double>(x) / POW2(n))
// and for int. fractional part will be discarded! 
#define FP_INT(x, n) ((x) >> n)

// arithmetic operations for same-format numbers 
#define FP_NEG(a) ((~a)+1)
#define FP_ADD(a, b) ((a) + (b))
#define FP_SUB(a, b) ((a) + FP_NEG(b))
#define FP_MUL(a, b, n) (((a) * (b)) >> n)
#define FP_DIV(a, b, n) (((a) << n) / (b))
#define FP_POW2(a, n) (((a) * (a)) >> n)
#define FP_POW3(a, n) (((((a) * (a)) >> n)*(a)) >> n)

// arithmetic for different-format numbers, assuming n is the target (result) format and n > m
#define FP_ADD_UP(a, b, n, m) ((a) + ((b) << (n-m)))
#define FP_SUB_UP(a, b, n, m) ((a) + FP_NEG((b) << (n-m)))
#define FP_MUL_UP(a, b, n, m) (((a) * (b)) >> m)
#define FP_DIV_UP(a, b, n, m) (((a) << m) / (b))

// same for n < m
#define FP_ADD_DOWN(a, b, n, m) ((a) + ((b) >> (m-n)))
#define FP_SUB_DOWN(a, b, n, m) ((a) + FP_NEG((b) >> (m-n)))
#define FP_MUL_DOWN(a, b, n, m) (((a) * (b)) >> m)
#define FP_DIV_DOWN(a, b, n, m) (((a) << m) / (b))

РЕДАКТИРОВАТЬ: В основном ответы и комментарии касались этих двух пунктов:

  • Код ужасен, его сложно использовать и поддерживать: Я полностью согласен и найду время, чтобы инкапсулировать его внутри класса. У меня были некоторые опасения по поводу производительности, которые были решены, и я был убежден, что они были необоснованными, и я пошел на все зря. :)
  • С фиксированной точкой в ​​любом случае не стоит беспокоиться: Хотя это может быть правдой на моей платформе, я создавал ее, чтобы повысить скорость выполнения моего кода на платформе, где не было оборудования с плавающей точкой. Там операции с плавающей запятой занимали слишком много времени, и было решено исправить это. Я тестировал это только на Intel, потому что в данный момент у меня нет доступа к целевому оборудованию.

Хотя я чрезвычайно благодарен за предоставленное до сих пор понимание, я надеялся услышать от кого-то, кто действительно сделал некоторые вычисления с фиксированной точкой, чтобы сказать мне, действительно ли эти арифметические операции действительно подходят. Возможно, есть какие-то дополнительные хитрые биты, о которых я не знаю, которые имеют значение в отношении производительности или точности? Другими словами, если мне нужно инкапсулировать этот код, могу ли я сохранить те же арифметические инструкции во встроенных операторных функциях в основном такими же, как сейчас, или мне следует как-то их изменить?


person neuviemeporte    schedule 17.03.2011    source источник
comment
Удален тег C, так как это не C код.   -  person Puppy    schedule 17.03.2011
comment
Код, написанный для использования этих макросов, будет жестоким. Зачем вам нужно это сделать? Честно говоря, если бы я когда-нибудь увидел #define FP_ADD(a, b) ((a) + (b)) в коде, который был вынужден поддерживать, я был бы глубоко обеспокоен.   -  person meagar    schedule 17.03.2011
comment
Я рассчитывал избежать накладных расходов, если откажусь от всего объектно-ориентированного подхода. Я мог бы обернуть все это в класс и перегрузить арифметические операторы, но поскольку AFAIK они фактически реализованы как функции, которые имеют накладные расходы на вызовы, я надеялся получить некоторую производительность, делая это таким образом. Небольшая навязчивая идея, которую я испытываю в последнее время. Кроме того, я подумал, может быть, компилятору будет легче оптимизировать это.   -  person neuviemeporte    schedule 17.03.2011
comment
@neuviemeporte: классы без иерархии типов не являются объектно-ориентированными, и они равны структурам в C с точки зрения вводимых накладных расходов.   -  person Tugrul Ates    schedule 17.03.2011
comment
@neuviemeporte: Это полное заблуждение. Компилятор будет встраивать такие небольшие функции. То, что C компиляторы идиотски относились к функциям, не означает, что C++ компиляторы таковыми. Класс с арифметическими операторами вообще не будет иметь дополнительных накладных расходов на разумный современный компилятор. И это будет в миллиард раз безопаснее и правильнее.   -  person Puppy    schedule 17.03.2011
comment
@junjanes: Вы уверены? Не могли бы вы указать мне на какие-нибудь документы, подтверждающие это? Кроме того, даже если это так - я предполагаю, что на члены структуры также нужно ссылаться с помощью какого-то указателя; от этого никуда не деться. И разыменование указателя тоже стоит денег, не так ли? Я знаю, что это глупо, но мы говорим здесь о микрооптимизациях.   -  person neuviemeporte    schedule 17.03.2011
comment
@neuviemeporte: То же самое и с локальными переменными - на них ссылается указатель стека. Вы упускаете суть - компилятор удалит все это из конечного результата. Фактическая сборка будет выглядеть так, как будто вы сгенерировали ее с помощью макроса.   -  person Puppy    schedule 17.03.2011
comment
@DeadMG: Я этого не осознавал, это многое прояснило для меня. Спасибо.   -  person neuviemeporte    schedule 17.03.2011


Ответы (4)


Встроенные функции. Используй их. Не макросы. Используйте класс, перегрузите его операторами. И static_cast не существует в C. Этот код настолько ужасен, что если бы вы разместили образец кода, используя его, он был бы совершенно нечитаемым.

Помните, что операции с плавающей запятой реализованы аппаратно, а операции с фиксированной запятой, которые вы реализовали, - программно. За это изменение будет штраф, и вполне может случиться так, что ваш код просто недостаточно быстр на алгоритмическом уровне, чтобы преодолеть это изменение.

person Puppy    schedule 17.03.2011
comment
Я на самом деле написал код, чтобы использовать это, поэтому я знаю, что вы правы, и я практически убежден, что нужно обернуть это внутри класса для удобства чтения и поддержки. Тем не менее, некоторые сомнения в производительности, но я думаю, мне просто нужно измерить, есть ли еще какие-то успехи. Я просто не понимаю, что вы имеете в виду под дихотомией аппаратного и программного обеспечения. Конечно, оборудование также выполняет целочисленные операции. И я полагаю, что процессору требуется больше времени для умножения двух чисел с плавающей запятой, чем для умножения двух целых чисел и сдвига результата? - person neuviemeporte; 17.03.2011
comment
@neuviwmeporte: Умножение с плавающей запятой - это одна аппаратная операция. Умножение int-int, а затем int-shift - это больше регистров (три операнда, а не два), и вы дважды вызываете оборудование. Если int-int mul быстрее, чем float-float mul, во многих случаях он бесполезен, потому что вы ждете дополнительной памяти или время тратится, пока ЦП ожидает следующего цикла для выполнения следующей операции. Вы также выдуваете больше кеша инструкций. Никогда ничего не придумывайте, профилируйте это и подтвердите свои предположения, прежде чем писать код, основанный на них. - person Puppy; 17.03.2011

Это ответ на комментарии @ neuviemeporte о производительности. Я делаю это как ответ вместо комментария, чтобы упростить форматирование кода.

Вы сказали: «AFAIK, они фактически реализованы как функции, которые имеют накладные расходы на вызовы», и «Я предполагаю, что на члены структуры также нужно ссылаться с помощью какого-то указателя; вы не можете избежать 'this'». Оба эти опасения справедливы на первый взгляд, но давайте рассмотрим подробнее.

Я использую gcc в Linux / x86. Рассмотрим эту программу:

typedef int fixed32;
#define FP_ADD(a,b) ((a)+(b))
#define FP_NEG(a) ((~a)+1)
#define FP_SUB(a,b) ((a)+FP_NEG(b))
#define FP_INT(x,n) ((x)>>n)
#define FP_MUL(a,b,n) (((a)*(b))>>n)
#define FP_DIV(a,b,n) (((a)<<n)/(b))

template<class T, unsigned n>
struct Fixed {
private:
    T theBits;

public:
    Fixed(T t = T()) : theBits(t) {}

    Fixed operator+(const Fixed& rhs) const {
        return Fixed(theBits + rhs.theBits);
    }

    Fixed operator-(const Fixed& rhs) const {
        return Fixed(theBits - rhs.theBits);
    }

    Fixed operator~() const {
        return Fixed(~theBits);
    }

    Fixed operator*(const Fixed& rhs) const {
        return Fixed((theBits*rhs.theBits)>>n);
    }

    Fixed operator/(const Fixed& rhs) const {
        return Fixed((theBits<<n)/rhs.theBits);
    }

    operator T() const {
        return theBits >> n;
    }
};

int DoFpAdd(const fixed32 a, const fixed32 b) {
     fixed32 result = FP_ADD(a, b);
     return FP_INT(result, 16);
}

int DoFixedAdd(const Fixed<int, 16> a, const Fixed<int, 16> b) {
    return a+b;
}


int DoFpSub(const fixed32 a, const fixed32 b) {
     fixed32 result = FP_SUB(a, b);
     return FP_INT(result, 16);
}

int DoFixedSub(const Fixed<int, 16> a, const Fixed<int, 16> b) {
    return a-b;
}

int DoFpMul(const fixed32 a, const fixed32 b) {
     fixed32 result = FP_MUL(a, b, 16);
     return FP_INT(result, 16);
}

int DoFixedMul(const Fixed<int, 16> a, const Fixed<int, 16> b) {
    return a*b;
}

int DoFpDiv(const fixed32 a, const fixed32 b) {
     fixed32 result = FP_DIV(a, b, 16);
     return FP_INT(result, 16);
}
int DoFixedDiv(const Fixed<int, 16> a, const Fixed<int, 16> b) {
    return a/b;
}

Я скомпилировал его с помощью этой командной строки g++ -O4 -Wall -pedantic -ansi -S x.cc && c++filt <x.s > x.S.

Вы можете удивиться, узнав, что функции с одинаковыми именами производят идентичный язык ассемблера. Да, FP_ADD () и Fixed ‹> :: operator + - это одно и то же. Никаких вызовов функций (все встроено) нет указателя this, просто инструкция на идентичном языке ассемблера.

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

person Robᵩ    schedule 17.03.2011
comment
Спасибо, что потрудились и предоставили эту информацию раньше, чем я смог. :) - person neuviemeporte; 17.03.2011

Вы можете узнать это, написав модульный тест для своей реализации. Простая реализация может быть достигнута с помощью последовательных утверждений:

assert(FP_ADD(7, 5) == 12)
assert(FP_SUB(7, 5) == 2)

и Т. Д.

Рассмотрите достаточное количество вариантов использования, пока не будете уверены в своем коде. Кроме того, не забудьте сравнить doubles и floats в пределах небольшого эпсилона. Равенство может не работать должным образом из-за ограничений их битового представления.

person Tugrul Ates    schedule 17.03.2011
comment
Я так и поступил, и я убежден, что это дает правильные результаты. Мне просто интересно, так ли быстро, насколько это возможно. - person neuviemeporte; 17.03.2011

Вам, вероятно, следует прочитать этот документ комитета C ++ - «Технический отчет о производительности C ++».

http://www.open-std.org/jtc1/sc22/wg21/docs/TR18015.pdf

Это эффективно развеивает некоторые мифы.

person Bo Persson    schedule 17.03.2011