Comparing std::vector<bool> to std::vector<char>

Question

A recent comment to an answer of mine here on Code Review brought up an interesting point. The comment was that one should use std::vector<char> over std::vector<bool> in most cases because the standard requires std::vector<bool> to actually pack bits. I replied that for small vector sizes, the speed wouldn't matter much and for large ones, cache locality would give the advantage to bool vectors.

However somewhere in between "small" and "large" is a lot of numbers! I wanted to do a test to characterize any std::vector<bool> advantage. The method I used is fairly simple. I wrote a program that takes 3 arguments:

• minsize = the smallest vector size to test
• maxsize = the largest vector size to test
• steps = the number of steps between those two

Since I wanted to test a large range quickly, and guessing how the vectors would scale, I chose to step through the range logarithmically. Using the output from the test, and normalizing the speed advantage of std::vector<bool> over std::vector<char> by subtracting the two times and dividing by the size of the vector yielded this chart on my machine (an older 64-bit Linux machine, using g++ version 5.3.1 for x86_64).

It seems that for a range of sizes in the 2000 to 75000 range, the advantage is with std::vector<char> but for all other ranges, the two were either identical (to the resolution of my timer) or the std::vector<bool> had the advantage.

I'm interested in comments on the code or the test method.

booltest.cpp

#include <iostream>
#include <vector>
#include <cstdlib>
#include <cmath>
#include "stopwatch.h"

template <typename F>
struct testfunc {
    F *fn;
    const char *name;
};

#define TEST(x) { x, #x }
template <typename T>
void vectest(unsigned n)
{
    std::vector<T> arr(n, false);
    unsigned remaining = n;
    static constexpr unsigned incr = 13;

    for (unsigned j = 0; j < incr; ++j) {
        for (unsigned i = j; i < n && remaining; i += incr) {
            if (!arr[i]) {
                arr[i] = true;
                --remaining;
            }
        }
    }
}

#define SHOW(x) std::cerr << #x << " = " << x << "\n"

int main(int argc, char *argv[])
{
    const testfunc<decltype(vectest<bool>)> test[]{
        TEST(vectest<char>),
        TEST(vectest<bool>),
    };

    if (argc < 4) {
        std::cerr << "Usage: booltest minsize maxsize steps\n";
        return 0;
    }

    unsigned min = std::stod(argv[1]);
    unsigned max = std::stod(argv[2]);
    unsigned steps = std::stod(argv[3]);
    double logmin = std::log10(min);
    double logmax = std::log10(max);
    double step = (logmax - logmin)/steps;

    SHOW(min);
    SHOW(max);
    SHOW(steps);

    // print header data
    std::cout << "\"n\"";
    for (const auto t : test) {
        std::cout << ", \"" << t.name << "\"";
    }
    std::cout << "\n";

    for (unsigned i = 0; i < steps; ++i) {
        unsigned val = std::pow(10, logmin + i * step);
        std::cout << val;
        for (const auto t : test) {
            std::cout << ", " << timeit<>(t.fn, val);
        }
        std::cout << std::endl;
    }
}

Answer 1

I'm going to intersperse bits of code with my comments on them:

template <typename F>
struct testfunc {
    F *fn;
    const char *name;
};

testfunc isn't an entirely self-explanatory name (especially given that it's a template, so F could be pretty much anything. A comment about the basic intent would be quite helpful.

#define TEST(x) { x, #x }
template <typename T>

I'd rather see a blank link after the end of TEST to make it clear that the subsequent template isn't particularly closely related. Other than that, the same comment as previously applies: the name TEST doesn't tell us much, so a comment (or more explanatory name, or both) might be helpful here.

static constexpr unsigned incr = 13;

Two points here. First, I'm not entirely excited about the name: the value is used as an increment in one place (which seems to fit well with the name) but as the upper limit on a loop in another place (which doesn't fit quite so well).

Second, I'm left wondering exactly what (if any) significance the value 13 has. Is it arbitrary, or does it matter that it happens to be odd, or perhaps it matters that it's prime. Or maybe it's really a carriage return in disguise (oh, but only some crusty old assembly language programmer would notice that; no wonder it never occurred to you:-) !)

std::cout << std::endl;

It seems likely that this is one of the (rare) times that somebody is using std:endl because they really want what it does. Personally, I'd rather do that a bit more explicitly with std::cout << "\n" << std::flush; though. Otherwise, some busybody might conclude you're part of the crowd that routinely uses endl when they really just want a carriage return, and change it to the latter.

As far as the test method goes, it only tests one very specific pattern. It fits well with the Sieve of Eratosthenes, but doesn't tell you much about (for example) repeated manipulations of the same parts of the vector. If that fits closely with your intended usage pattern, that's fine--but there are clearly a lot of other possible uses about which this is likely to tell us little or nothing.