Правильна ли моя реализация арифметики с фиксированной запятой? - PullRequest
Новая
       0

Правильна ли моя реализация арифметики с фиксированной запятой?

1 голос
/ 17 марта 2011

Некоторое время назад я создал кучу макросов 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, потому что у меня нет доступа к целевому оборудованию на данный момент

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

Ответы [ 4 ]

5 голосов
/ 17 марта 2011

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

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

4 голосов
/ 17 марта 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, только идентичный язык ассемблерной инструкции.

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

2 голосов
/ 17 марта 2011

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

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

Эффективно убивает некоторые мифы.

2 голосов
/ 17 марта 2011

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

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

и т. Д.

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

...