[cfe-dev] [libc++] std::count with bool types

[Howard Hinnant]

On May 10, 2012, at 10:11 AM, Howard Hinnant wrote:

> And it is still wrong.  Sorry.  Working on it...

Ok, fix committed revision 156546.

Sorry about the thrash.  As an attempt to save what little face I have left, I've expanded your example and put some timers on it.  On OS X, compiling with -O3 and in 64 bit mode:

#include <iostream>
#include <algorithm>
#include <chrono>
#include <random>
#include <vector>

int main ()
{
    typedef std::chrono::high_resolution_clock Clock;
    typedef std::chrono::nanoseconds ns;
    std::mt19937_64 eng;
    std::uniform_int_distribution<bool> d;
    const unsigned N = 10000;
    // counting boolean elements in array
    bool bool_array[N];
    for (auto& b : bool_array)
        b = d(eng);
    auto t0 = Clock::now();
    int mycount = (int) std::count (bool_array, bool_array+N, true);
    auto t1 = Clock::now();
    std::cout << "true appears " << mycount  << " times.\n";
    std::cout << "count took " << ns(t1-t0).count() << "ns\n";
    t0 = Clock::now();
    mycount = (int) std::count (bool_array, bool_array+N, false);
    t1 = Clock::now();
    std::cout << "false appears " << mycount  << " times.\n";
    std::cout << "count took " << ns(t1-t0).count() << "ns\n";

    // counting boolean elements in container
    std::vector<bool> bool_vector( bool_array,bool_array+N );
    t0 = Clock::now();
    mycount = (int) std::count (bool_vector.begin(), bool_vector.end(), true);
    t1 = Clock::now();
    std::cout << "true appears " << mycount  << " times.\n";
    std::cout << "count took " << ns(t1-t0).count() << "ns\n";
    t0 = Clock::now();
    mycount = (int) std::count (bool_vector.begin(), bool_vector.end(), false);
    t1 = Clock::now();
    std::cout << "false appears " << mycount  << " times.\n";
    std::cout << "count took " << ns(t1-t0).count() << "ns\n";
}

I get:

true appears 5039 times.
count took 6922ns
false appears 4961 times.
count took 10328ns
true appears 5039 times.
count took 565ns
false appears 4961 times.
count took 537ns

So working with bits instead of bools is both correct and about 15 times faster (if you have enough bools anyway).  This is what the private header <__bit_reference> is all about:  specializing a few of the std::algorithms for bit iterators, used by both bitset and vector<bool>.

Howard