How to make my “custom integer type” perform better?

Question

During a project at my work I needed a convenient way to store values taking up the smallest amount of bits necessary, not in memory but later when they're serialized into an array of unsigned short ints. For instance, a value that could be between 0 and 7 was only supposed to be 3 bits long. I ended up developing my own solution based on std::bitset with some additional code in order to make it work with signed values. Another goal was to make it work as close to a regular integer type as possible. This is the code (https://github.com/AndersHogqvist/custom_int):

#include <bitset>
#include <type_traits>

template<size_t Size>
class TypeBase {
public:
  size_t size() const {
    return data_.size();
  }

  unsigned long to_ulong() const {
    return data_.to_ulong();
  }

  unsigned long long to_ullong() const {
    return data_.to_ullong();
  }

  std::bitset<Size> data() const {
    return data_;
  }

  std::string to_string() const {
    return data_.to_string();
  }

  template<typename T,
      typename std::enable_if<std::is_integral<T>::value, T>::type* = nullptr>
  TypeBase<Size> &operator=(const T value) {
    data_ = std::bitset<Size>(value);
    return *this;
  }

  bool operator==(const TypeBase<Size> &other) const {
    return data_ == other.data();
  }

  template<typename T,
      typename std::enable_if<std::is_integral<T>::value, T>::type* = nullptr>
  bool operator==(const T value) const {
    return data_.to_ullong() == value;
  }

  bool operator!=(const TypeBase<Size> &other) const {
    return !(*this == other);
  }

  template<typename T,
      typename std::enable_if<std::is_integral<T>::value, T>::type* = nullptr>
  bool operator!=(const T value) const {
    return data_ != std::bitset<Size>(value);
  }

  bool operator<(const TypeBase<Size> &other) const {
    if (data_ == other.data_) {
      return false;
    }
    return less_than_(other.data_);
  }

  template<typename T,
      typename std::enable_if<std::is_integral<T>::value, T>::type* = nullptr>
  bool operator<(const T value) const {
    return less_than_(std::bitset<Size>(value));
  }

  bool operator<=(const TypeBase<Size> &other) const {
    if (data_ == other.data_) {
      return true;
    }
    return less_than_or_eq_(other.data_);
  }

  template<typename T,
      typename std::enable_if<std::is_integral<T>::value, T>::type* = nullptr>
  bool operator<=(const T value) const {
    return less_than_or_eq_(std::bitset<Size>(value));
  }

  bool operator>(const TypeBase<Size> &other) const {
    if (data_ == other.data_) {
      return false;
    }
    return greater_than_(other.data_);
  }

  template<typename T,
      typename std::enable_if<std::is_integral<T>::value, T>::type* = nullptr>
  bool operator>(const T value) const {
    return greater_than_(std::bitset<Size>(value));
  }

  bool operator>=(const TypeBase<Size> &other) const {
    if (data_ == other.data_) {
      return true;
    }
    return greater_than_or_eq_(other.data_);
  }

  template<typename T,
      typename std::enable_if<std::is_integral<T>::value, T>::type* = nullptr>
  bool operator>=(const T value) const {
    return greater_than_or_eq_(std::bitset<Size>(value));
  }

  TypeBase<Size> &operator+(const TypeBase<Size> &other) {
    bool carry = false;
    for (size_t ix = 0; ix < Size; ++ix) {
      data_[ix] = add_(data_[ix], other.data_[ix], carry);
    }
    return *this;
  }

  TypeBase<Size> &operator+(const std::bitset<Size> &other) {
    bool carry = false;
    for (size_t ix = 0; ix < Size; ++ix) {
      data_[ix] = add_(data_[ix], other[ix], carry);
    }
    return *this;
  }

  template<typename T,
      typename std::enable_if<std::is_integral<T>::value, T>::type* = nullptr>
  TypeBase<Size> &operator+(const T value) {
    bool carry = false;
    std::bitset<Size> other(value);
    for (size_t ix = 0; ix < Size; ++ix) {
      data_[ix] = add_(data_[ix], other[ix], carry);
    }
    return *this;
  }

  TypeBase<Size> &operator+=(const TypeBase<Size> &other) {
    bool carry = false;
    for (size_t ix = 0; ix < Size; ++ix) {
      data_[ix] = add_(data_[ix], other.data_[ix], carry);
    }
    return *this;
  }

  TypeBase<Size> &operator+=(const std::bitset<Size> &other) {
    bool carry = false;
    for (size_t ix = 0; ix < Size; ++ix) {
      data_[ix] = add_(data_[ix], other[ix], carry);
    }
    return *this;
  }

  template<typename T,
      typename std::enable_if<std::is_integral<T>::value, T>::type* = nullptr>
  TypeBase<Size> &operator+=(const T value) {
    bool carry = false;
    std::bitset<Size> other(value);
    for (size_t ix = 0; ix < Size; ++ix) {
      data_[ix] = add_(data_[ix], other[ix], carry);
    }
    return *this;
  }

  TypeBase<Size> &operator++(int) {
    bool carry = false;
    std::bitset<Size> other(1);
    for (size_t ix = 0; ix < Size; ++ix) {
      data_[ix] = add_(data_[ix], other[ix], carry);
    }
    return *this;
  }

  TypeBase<Size> &operator-(const TypeBase<Size> &other) {
    subtract_(other.data_);
    return *this;
  }

  TypeBase<Size> &operator-(const std::bitset<Size> &other) {
    subtract_(other);
    return *this;
  }

  template<typename T,
      typename std::enable_if<std::is_integral<T>::value, T>::type* = nullptr>
  TypeBase<Size> &operator-(const T value) {
    subtract_(std::bitset<Size>(value));
    return *this;
  }

  TypeBase<Size> &operator-=(const TypeBase<Size> &other) {
    subtract_(other.data_);
    return *this;
  }

  TypeBase<Size> &operator-=(const std::bitset<Size> &other) {
    subtract_(other);
    return *this;
  }

  template<typename T,
      typename std::enable_if<std::is_integral<T>::value, T>::type* = nullptr>
  TypeBase<Size> &operator-=(const T value) {
    subtract_(std::bitset<Size>(value));
    return *this;
  }

  TypeBase<Size> &operator--(int) {
    subtract_(std::bitset<Size>(1));
    return *this;
  }

  TypeBase<Size> &operator*(const TypeBase<Size> &other) {
    multiply_(other.data_);
    return *this;
  }

  TypeBase<Size> &operator*(const std::bitset<Size> &other) {
    multiply_(other);
    return *this;
  }

  template<typename T,
      typename std::enable_if<std::is_integral<T>::value, T>::type* = nullptr>
  TypeBase<Size> &operator*(const T value) {
    multiply_(std::bitset<Size>(value));
    return *this;
  }

  TypeBase<Size> &operator*=(const TypeBase<Size> &other) {
    multiply_(other.data_);
    return *this;
  }

  template<typename T,
      typename std::enable_if<std::is_integral<T>::value, T>::type* = nullptr>
  TypeBase<Size> &operator*=(const T value) {
    multiply_(std::bitset<Size>(value));
    return *this;
  }

  TypeBase<Size> &operator/(const TypeBase<Size> &other) {
    data_ = data_.to_ullong() / other.to_ullong();
    return *this;
  }

  TypeBase<Size> &operator/(const std::bitset<Size> &other) {
    data_ = data_.to_ullong() / other.to_ullong();
    return *this;
  }

  template<typename T,
      typename std::enable_if<std::is_integral<T>::value, T>::type* = nullptr>
  TypeBase<Size> &operator/(const T value) {
    data_ = data_.to_ullong() / value;
    return *this;
  }

  TypeBase<Size> &operator/=(const TypeBase<Size> &other) {
    data_ = data_.to_ullong() / other.to_ullong();
    return *this;
  }

  template<typename T,
      typename std::enable_if<std::is_integral<T>::value, T>::type* = nullptr>
  TypeBase<Size> &operator/=(const T value) {
    data_ = data_.to_ullong() / value;
    return *this;
  }

  template<size_t S>
  friend std::ostream &operator <<(std::ostream &out, const TypeBase<S> &u);
protected:
  TypeBase() = default;
  ~TypeBase() = default;

  std::bitset<Size> data_;

  bool add_(bool b1, bool b2, bool &carry) {
    bool sum = (b1 ^ b2) ^ carry;
    carry = (b1 && b2) || (b1 && carry) || (b2 && carry);
    return sum;
  }

  void subtract_(const std::bitset<Size> &other) {
    bool borrow = false;
    for (int i = 0; i < Size; i++) {
      if (borrow) {
        if (data_[i]) {
          data_[i] = other[i];
          borrow = other[i];
        }
        else {
          data_[i] = !other[i];
          borrow = true;
        }
      }
      else {
        if (data_[i]) {
          data_[i] = !other[i];
          borrow = false;
        }
        else {
          data_[i] = other[i];
          borrow = other[i];
        }
      }
    }
  }

  void multiply_(const std::bitset<Size> &other) {
    std::bitset<Size> tmp = data_;
    data_.reset();
    if (tmp.count() < other.count()) {
      for (int i = 0; i < Size; i++) {
        if (tmp[i]) {
          operator+=(other << i);
        }
      }
    }
    else {
      for (int i = 0; i < Size; i++) {
        if (other[i]) {
          operator+=(tmp << i);
        }
      }
    }
  }

  bool less_than_or_eq_(const std::bitset<Size> &other) const {
    for (int i = Size - 1; i >= 0; i--) {
      if (data_[i] && !other[i]) {
        return false;
      }
      if (!data_[i] && other[i]) {
        return true;
      }
    }
    return true;
  }

  bool less_than_(const std::bitset<Size> &other) const {
    for (int i = Size - 1; i >= 0; i--) {
      if (data_[i] && !other[i]) {
        return false;
      }
      if (!data_[i] && other[i]) {
        return true;
      }
    }
    return false;
  }

  bool greater_than_or_eq_(const std::bitset<Size> &other) const {
    for (int i = Size - 1; i >= 0; i--) {
      if (data_[i] && !other[i]) {
        return true;
      }
      if (!data_[i] && other[i]) {
        return false;
      }
    }
    return true;
  }

  bool greater_than_(const std::bitset<Size> &other) const {
    for (int i = Size - 1; i >= 0; i--) {
      if (data_[i] && !other[i]) {
        return true;
      }
      if (!data_[i] && other[i]) {
        return false;
      }
    }
    return false;
  }
};

template<size_t Size>
class Int : public TypeBase<Size> {
public:
  Int() = default;

  template<typename T,
      typename std::enable_if<std::is_integral<T>::value, T>::type* = nullptr>
  Int(const T value) {
    TypeBase<Size>::operator=(value);
  }

  ~Int() = default;

  Int<Size> &operator=(const TypeBase<Size> &other) {
    if (this->data_ == other.data()) {
      return *this;
    }
    this->data_ = other.data();
    return *this;
  }

  long long to_int() const {
    if (this->data_[Size - 1]) {
      std::bitset<Size> tmp = this->data_;
      tmp.flip();
      return tmp.to_ullong() * -1 - 1;
    }
    return this->data_.to_ullong();
  }

  Int<Size> &operator/(const TypeBase<Size> &other) {
    this->data_ = to_int() / other.to_ullong();
    return *this;
  }

  Int<Size> &operator/(const std::bitset<Size> &other) {
    this->data_ = to_int() / other.to_ullong();
    return *this;
  }

  template<typename T,
      typename std::enable_if<std::is_integral<T>::value, T>::type* = nullptr>
  Int<Size> &operator/(const T value) {
    this->data_ = to_int() / value;
    return *this;
  }

  Int<Size> &operator/=(const TypeBase<Size> &other) {
    this->data_ = to_int() / other.to_ullong();
    return *this;
  }

  template<typename T,
      typename std::enable_if<std::is_integral<T>::value, T>::type* = nullptr>
  Int<Size> &operator/=(const T value) {
    this->data_ = to_int() / value;
    return *this;
  }
};

template<size_t Size>
std::ostream &operator<<(std::ostream &out, const Int<Size> &u) {
  out << u.to_int();
  return out;
}

template<size_t Size>
class UInt : public TypeBase<Size> {
public:
  UInt() = default;

  template<typename T,
      typename std::enable_if<std::is_integral<T>::value, T>::type* = nullptr>
  UInt(const T value) {
    TypeBase<Size>::operator=(value);
  }

  ~UInt() = default;

  UInt<Size> &operator=(const TypeBase<Size> &other) {
    if (this->data_ == other.data()) {
      return *this;
    }
    this->data_ = other.data();
    return *this;
  }

  unsigned long long to_int() const {
    return this->data_.to_ullong();
  }
};

template<size_t Size>
std::ostream &operator<<(std::ostream &out, const UInt<Size> &u) {
  out << u.to_ullong();
  return out;
}

Here are some examples on how it's supposed to be used:

#include <iostream>

#include "custom_int.h"

using namespace std;

int main() {
  Int<13> test1 = 1;
  UInt<5> test2;

  cout << "test1: " << test1 << endl;
  cout << "test2: " << test2 << endl;

  test1++;
  cout << "test1: " << test1 << endl;

  test1--;
  cout << "test1: " << test1 << endl;

  test1 -= 10;
  cout << "test1: " << test1 << endl;

  auto test3 = test1;

  cout << "test3: " << test3 << endl;

  test3 /= 3;

  cout << "test3: " << test3 << endl;

  test2 += 20;

  cout << "test2: " << test2 << endl;

  test2 = test2 / 10;

  cout << "test2: " << test2 << endl;
}

I'm by no means a seasoned C++ developer, so even if I believe it's working the way it should I would love to have some input on what can be improved.

What I'm mostly concerned about is the performance (unnecessary copying etc). It's supposed to be used in a real time application so I need it to be as fast as possible.

Is it intended to work for integers wider than unsigned long long? — user555045
– user555045, Commented Sep 15, 2019 at 15:00
@harold, in my project I was handling up to 64 bit unsigned ints, so i haven't really thought about anything larger than that. — Zenit_swe
– Zenit_swe, Commented Sep 15, 2019 at 15:14
I rolled back your last edit. Editing code after the answer was posted is against the CR policy, because it invalidates the answer. — vnp
– vnp, Commented Sep 15, 2019 at 17:32
Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. If your code has significantly improved, preferably with edits of yourself as well, you could ask a new question, a follow-up. — Mast
– Mast ♦, Commented Sep 15, 2019 at 17:50

user555045 · Accepted Answer · 2019-09-15 15:34:42Z

5

A significant performance drain is bit-by-bit computation loops such as

  TypeBase<Size> &operator+=(const TypeBase<Size> &other) {
    bool carry = false;
    for (size_t ix = 0; ix < Size; ++ix) {
      data_[ix] = add_(data_[ix], other.data_[ix], carry);
    }
    return *this;
  }

Unfortunately, at this time such constructs are not recognized by major compilers, and probably also not by various embedded compilers (which if I recall correctly you mentioned earlier).

For small Size it could be implemented with plain old arithmetic operators,

  TypeBase<Size> &operator+=(const TypeBase<Size> &other) {
    data_ = std::bitset<Size>(to_ullong() + other.to_ullong());
    return *this;
  }

Which unsurprisingly compiles to normal addition.

Larger Size is trickier to support efficiently this way.

answered Sep 15, 2019 at 15:34

user555045

12.4k1 gold badge19 silver badges39 bronze badges

\$\begingroup\$ This is exactly why I posted it here! Thank you for your input, much appreciated. Would it be sufficient if I added a control statement that implements your solution if Size <= 64 and if not use the current bit-by-bit function? \$\endgroup\$

Zenit_swe
– Zenit_swe

2019-09-15 15:42:03 +00:00
Commented Sep 15, 2019 at 15:42
1

\$\begingroup\$ @Zenit_swe that would do it, though it's a very sharp performance discontinuity between 64 and 65 bits then \$\endgroup\$

user555045
– user555045

2019-09-15 15:46:28 +00:00
Commented Sep 15, 2019 at 15:46

Add a comment |

Stack Exchange Network

How to make my “custom integer type” perform better?

1 Answer 1

You must log in to answer this question.

Hot Network Questions

How to make my “custom integer type” perform better?

1 Answer 1

You must log in to answer this question.

Related

Hot Network Questions