Fast conversion from std::string to std::vector<bool>

user_13759708 0
Viewed 208

Edit: I am leaving the original question below, but the conversion is not as slow as I claimed. There is a bug in my original program that caused the function to be called with a much longer input than I intended. Indeed, converting from a string to a bit vector only takes about 1.5x as long as converting the other way.

I need to convert a string to vector<bool>. The conversion is very slow, however. I understand that vector<bool> is a specialization of vector. I tried using vector<char> instead, but that is just as slow.

This is my code:

std::vector<bool> frombytes(const std::string &bytes)
{
    std::vector<bool> output;

    for (unsigned int i = 0; i < bytes.length(); i++)
    {
        unsigned char byte = bytes[i];
        for (unsigned int j = 0; j < 8; j++)
        {
            output.push_back(byte >> (7 - j) & 1);
        }
    }
}

I am thinking that perhaps by writing 8 bits at a time, I can make this faster. However, I can't figure out a way to do so. Any suggestions would be helpful. Thanks!

More information:

  • I have tried vector::reserve, but that did not make much difference.
  • I am compiling the program using g++ with the "-O3" flag.
optimization c++ performance
2 Answers

I'm not sure that such a conversion is necessary. You can use simple accessor functions to get hold of individual bits, and you can write simple custom iterators that expose bits in a string as if they were individual bools. That completely sidesteps the cost of conversion. The conversion is very wasteful because internally the vector<bool> will be usually implemented as a vector of unsigned chars or integers, with special accessors that twiddle bits of those. It is highly likely that the memory representation of the data in the vector<bool> and std::string will be identical with possible exception of bit and/or byte order. So if you seem to care about performance so much, then skipping the whole brouhaha makes most sense.

The accessors are dead simple:

bool getBit(size_t index, const std::string &str)
{
  assert(index/8 < str.size());
  return (str[index/8] >> (index%8)) & 1;
}

void setBit(size_t const index, bool const val, std::string &str)
{
  assert(index/8 < str.size());
  char c = str[index/8];
  c &= ~(1 << (index%8));
  c |= char(val) << (index % 8);
  str[index/8] = c;
}

If you want to iterate the string as bits, you could use the following iterator adapter (untested):

template <typename Container>
class const_bit_iterator {
  using c_value_type = const Container::value_type;
  using iterator = Container::const_iterator;
  static constexpr size_t modulus = 8u * sizeof(c_value_type );
  size_t index = 0;
  iterator it = {};
  constexpr c_value_type bitmask() const { return c_value_type (1) << (index % modulus); }
public:
  using value_type = const bool;
  struct end_tag_t {};
  static constexpr end_tag_t end_tag = {};
  explicit bit_iterator(const Container &container) : it(container.begin()) {}
  explicit bit_iterator(end_tag_t, const Container &container) :
    index(modulus * container.size()), it(container.end()) {}
  bool operator*() const { return get(); }
  bool get() const { return (*it) & bitmask(); }
  bit_iterator &operator++() {
    ++ index;
    if (!(index % modulus)) ++ it;
    return *this;
  }
  bit_iterator operator++(int) {
    auto it = *this;
    ++ *this;
    return it;
  }
  bit_iterator &operator--() {
    -- index;
    if ((index % modulus) == (modulus - 1)) -- it;
    return *this;
  }
  bit_iterator operator--(int) {
    auto it = *this;
    -- *this;
    return it;
  }
  bool operator==(const bit_iterator &o) const { return index == o.index; }
  bool operator!=(const bit_iterator &o) const { return index != o.index; }
  bool operator<(const bit_iterator &o) const { return index < o.index; }
};

template <typename Container>
class const_bit_adapter
{
  const Container &ref;
public:
  const_bit_adapter(const Container &container) : ref(container) {}
  const_bit_iterator begin() const { return const_bit_iterator(ref); }
  const_bit_iterator end() const { return const_bit_iterator(const_bit_iterator::end_tag, ref); }
};

template <typename Container>
const_bit_adapter<Container> as_const_bits(const Container &container)
{ return {container}; }
template <typename Container>
const_bit_adapter<Container> as_bits(const Container &container)
{ return {container}; }

Example use:

std::vector<int> bits(32);
size_t n = 0;
for (bool b : as_const_bits(bits))
  ++n;
assert(n == bits.size() * 8u * sizeof(decltype(bits)::value_type));
user_13296520

I tried a couple of different ways namely using a table and a switch to make it faster. Here are the results:

  1. Results using switch
  2. Results using table

Results are separate due to character limit in quickbench.

  • Using switch and returning std::array is almost 1.8 times faster than the original version.
  • Using table was about 1.6 - 1.7 times faster than the original version.
  • Using std::vector<bool> is slighty slower than using std::vector<unsigned char>

Code used to generate the table and switch(with a little modification):

std::vector<bool> frombytes(int byte)
{
    std::vector<bool> output;
        for (unsigned int j = 0; j < 8; j++)
        {
            output.push_back(byte >> (7 - j) & 1);
        }
    return output;
}

int main()
{
    std::cout << "{\n";
    for (int i = 0; i <= 255; i++) {  
        auto bits = frombytes(i);
        /* std::cout << "case " << i <<":\n"; */
        std::cout << "    {";
        int cnt = 0;
        for (auto b : bits) {
            cnt++;
            if (cnt == 8)
                std::cout << b;
            else
                std::cout << b << ", ";
        }
        std::cout << "},\n";
    }
    std::cout << "\n};\n";   
    return 0;
}
user_22794220
Related