Попытка уменьшить накладные расходы на скорость для класса почти, но не совсем целых чисел.

Question

Я реализовал класс C ++, который ведет себя очень похоже на стандартный тип int.Разница заключается в том, что он имеет дополнительную концепцию «эпсилон», которая представляет собой какое-то крошечное значение, которое намного меньше 1, но больше 0. Один способ думать об этом - это очень широкое число с фиксированной точкой с 32 старшими битами (целое числочастей), 32 LSB (части эпсилона) и огромное море нулей между ними.(Примечание: большая разница между этим классом и обычными числами с фиксированной точкой состоит в том, что есть два знака, а не один: «значение» и «эпсилон» могут быть отрицательными независимо друг от друга, тогда как для фиксированной точки, есть один знак дляцелое число.)

Следующий класс работает, но вводит ~ 2-кратное снижение скорости в общей программе.(Программа включает в себя код, который не имеет ничего общего с этим классом, поэтому фактическое снижение скорости этого класса, вероятно, намного больше, чем в 2 раза.) Я не могу вставить код, который использует этот класс, но я могу сказать следующее:

+, -, +=, <, > и >= являются единственными активно используемыми операторами.Использование setEpsilon() и getInt() крайне редко.* также встречается редко и даже не требует учета значений эпсилона.

Вот класс:

#include <limits>

struct int32Uepsilon {
typedef int32Uepsilon Self;

int32Uepsilon () { _value = 0;
                   _eps   = 0; }
int32Uepsilon (const int &i) { _value = i;
                               _eps   = 0; }
void setEpsilon() { _eps = 1; }
Self operator+(const Self &rhs) const { Self result = *this;
                                      result._value += rhs._value;
                                      result._eps   += rhs._eps;
                                      return result; }
Self operator-(const Self &rhs) const { Self result = *this;
                                      result._value -= rhs._value;
                                      result._eps   -= rhs._eps;
                                      return result; }
Self operator-(               ) const { Self result = *this;
                                      result._value = -result._value;
                                      result._eps   = -result._eps;
                                      return result; }
Self operator*(const Self &rhs) const { return this->getInt() * rhs.getInt(); } // XXX: discards epsilon

bool operator<(const Self &rhs) const { return (_value < rhs._value) ||
                                             (_value == rhs._value && _eps < rhs._eps); }
bool operator>(const Self &rhs) const { return (_value > rhs._value) ||
                                             (_value == rhs._value && _eps > rhs._eps); }
bool operator>=(const Self &rhs) const { return (_value >= rhs._value) ||
                                             (_value == rhs._value && _eps >= rhs._eps); }

Self &operator+=(const Self &rhs) { this->_value += rhs._value;
                                  this->_eps   += rhs._eps;
                                  return *this; }
Self &operator-=(const Self &rhs) { this->_value -= rhs._value;
                                  this->_eps   -= rhs._eps;
                                  return *this; }
int getInt() const { return(_value); }

private:
  int _value;
  int _eps;
};

namespace std {
template<>
struct numeric_limits<int32Uepsilon> {
  static const bool is_signed  = true;
  static int max() { return 2147483647; }
}
};

Приведенный выше код работает, но он довольно медленный,У кого-нибудь есть идеи как улучшить производительность?Я могу дать несколько советов / подробностей, которые могут быть полезны:

• 32 бита определенно недостаточно для хранения как _value, так и _eps.На практике используется до 24 ~ 28 битов _value и используется до 20 битов _eps.
• Я не мог измерить существенную разницу в производительности между использованием int32_t и int64_t, поэтому нехватка памятиСамо по себе, вероятно, здесь не проблема.
• Насыщающее сложение / вычитание на _eps было бы здорово, но на самом деле это не нужно.
• Обратите внимание, что знаки _value и _eps не обязательно совпадают!Это сломало мою первую попытку ускорить этот класс.
• Встроенная сборка не проблема, если она работает с GCC в системе Core i7 под управлением Linux!

Answer 1

Следует попробовать каноническую практику определения, например, operator+ в терминах operator+=:

Self operator+(const Self &rhs) const { return Self(*this) += rhs; }

Это облегчает оптимизацию возвращаемого значения , что исключаетконструктор копирования, который в противном случае был бы необходим для возврата по значению.

Кроме того, это уменьшает обслуживание кода!

Answer 2

2x снижение скорости не кажется необоснованным, поскольку все операции выполняются дважды.

Вы можете использовать инструкции MMX / SSE2 для упаковки значений и эпсилона в два регистра и выполнять две операции параллельно только один раз.В качестве альтернативы, в 64-битной архитектуре вы можете упаковать два значения в один int64, например: [32 bits of value][12 zeros][20 bits of eps].Сравнения будут работать автоматически с одной операцией, сложение и вычитание должны будут маскировать перенос из eps в нули дополнения.Нет никаких препятствий для использования MMX для сложения и вычитания (тогда автоматически происходит маскирование) и обычного целочисленного сравнения для сравнений.

Кстати, ваш оператор - = глючит: в this->_eps -= rhs._eps, this->eps можетстать отрицательным.Разве вы не должны затем отрегулировать как eps, так и уменьшить значение?Каково поведение переполнения eps?Это когда-либо переносится в стоимость?

Answer 3

Мое (частичное) решение использует одну целочисленную операцию вместо два в вашем решении, как указано Оли Чарльзуорт в комментарии.

Вот как вы можете это сделать: используйте int64_t для хранения _eps и _value.В моем примере ниже _value представлен bit0-to-bit31, а _eps представлен bit32-to-bit63.

struct int32Uepsilon 
{

   typedef int32Uepsilon Self;

   int64_t value;

   int32Uepsilon () { value = 0 }
   int32Uepsilon (const int i) {  value = i; }
   void setEpsilon() 
   {  
      //equivent to _eps = 1
      value = ((int64_t)1 << 32) + (value & 0xFFFFFFFF); 
   }
   Self operator+(const Self &rhs) const 
   { 
     Self result = *this;
    //this adds lower 32 bits to lower 32 bits, upper 32 bits to upper 32 bits!
     result.value += rhs.value; 
     return result; 
   }
   //....
   int getValue() { return value & 0xFFFFFFFF; }
   int getEpsilon() { return value >> 32; }
};

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

---

Простая демонстрация сложения.Пожалуйста, прочитайте комментарий

int main() 
{
    int64_t x =  ((int64_t)2 << 32) + 4;     //eps = 2,  value = 4
    int64_t y =  ((int64_t)65 << 32) +7897;  //eps = 65, value = 7897
    int64_t z =  x + y ; //in z, eps = (2+65) = 67, value = (4 + 7897) = 7901 
    cout << (x >> 32) << ", " << (x & 0xFFFFFFFF) << endl;  
    cout << (y >> 32) << ", " << (y & 0xFFFFFFFF) << endl;  
    cout << (z >> 32) << ", " << (z & 0xFFFFFFFF) << endl;  
    return 0;
}

Вывод:

2, 4    
65, 7897   
67, 7901

, как и ожидалось.

Демонстрация на Ideone: http://www.ideone.com/GjSnJ

---

Вместоx + y, вы можете использовать x | y, что даже на более быструю операцию .

Answer 4

Спасибо за вклад, всем.В конце я использовал встроенную сборку для реализации +, - и + =.Удивительно, но GCC не смог векторизовать эти крошечные функции сам по себе, хотя использование встроенной функции __builtin_ia32_paddd() помогло.В конечном итоге общие накладные расходы программы (по сравнению с использованием голых int) были сокращены со 100% до 50%.Глядя на сгенерированную сборку, результат казался оптимальным, по крайней мере там, где я смотрел.Насколько я могу судить по краткому прочтению руководств Intel, в операциях сравнения ничто не поможет.(Есть инструкции для сравнения векторов, но ни одна из них здесь не поможет.)