On Mon, Oct 24, 2022 at 5:14 PM Arthur O'Dwyer via Std-Proposals
<std-proposals_at_[hidden]> wrote:
>
> On Mon, Oct 24, 2022 at 1:22 PM Madhur Chauhan <madhur4127_at_[hidden]> wrote:
>>
>> Thanks for the comments Arthur, much appreciated!
>>
>> I think the core problem is absense of an efficient iterator for bitset.
>> Normal random access iterator will still access each bit and that's inefficient so we'll need something different that can process words and then trailing bits.
>> If that fancy iterator exists then we don't need proposed function and <algorithm> can be used instead.
>
>
> That's a great point. I had forgotten (but now I vaguely recall) that libc++ has several algorithms, such as std::find, specifically optimized for bit-iterators. They also have a few algorithms specifically optimized for deque::iterator, because deques are "piecewise contiguous" in a way that's known at compile time. (Sadly, P0447 hive::iterator can't benefit from the same optimizations because a hive's degree of piecewise-contiguity is known only at runtime.)
>
> Double-sadly, `std::bitset` doesn't have iterators! Bit-iterators only exist for `vector<bool>`. I agree that "bitset is not iterable" might be the root of the problem here. But, again, if we think of a bitset as a mapping from small integers to bools (or a set of small integers), then it kind of makes sense that you can't "iterate" it — you'd just be iterating over "false, false, true, false, true, false..." which isn't relevant to the problem domain. (Contrast to vector<bool>, which is a sequence of bools you can iterate.)
> I could see it being hard to convince LEWG that there was a real problem here, unfortunately.
>
> Did you try benchmarking the <algorithm> version of your code, and the hand-rolled version, using `vector<bool>`? How does it compare?
> I tried this version of the code:
> https://godbolt.org/z/9q88qzG4e
>
> GCC+libstdc++ gives these numbers on Godbolt:
>
> -----------------------------------------------------
>
> Benchmark Time CPU Iterations
>
> -----------------------------------------------------
>
> bs_manual 4184 ns 2251 ns 252405
>
> bv_manual 4061 ns 2349 ns 288193
>
> bv_stl 4164 ns 2210 ns 255113
>
> bs_library 130 ns 62.6 ns 14677544
>
>
> Clang+libc++ gives these numbers on my local laptop:
>
> -----------------------------------------------------
>
> Benchmark Time CPU Iterations
>
> -----------------------------------------------------
>
> bs_manual 2186 ns 2180 ns 315701
>
> bv_manual 2115 ns 2112 ns 319833
>
> bv_stl 39.7 ns 39.6 ns 17456620
>
>
>
> Hmm, I had thought C++20 or C++23 was going to give us std::bit_iterator and std::bit_reference... what ever happened to those?

That was P0237, the latest version being R10 (from 2019). There, they
suggested that they should replace `bitset` with a new container
defined around bit iterators/references. The authors don't appear to
have done much since 2019, so the proposal seems abandoned.

> Not that they would be specifically useful in this scenario, since you can't get at the underlying storage of a std::bitset<N> in order to iterate over it, even if you had a std::bit_iterator adaptor.
>
> –Arthur