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

[Michael Sommerville]

On Thu, May 10, 2012 at 4:02 PM, Howard Hinnant <hhinnant at apple.com> wrote:
> 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

Thank you very much for the quick fix and the lesson! :-)

-Michael