C++ Logo

std-proposals

Advanced search

Re: [std-proposals] [bitset] find first set bit after a position pos

From: Madhur Chauhan <madhur4127_at_[hidden]>
Date: Tue, 25 Oct 2022 13:15:27 +0530
Hey Arthur,

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 kinda like the standard's description:

 The class template bitset<N> describes an object that can store a sequence
> consisting of a fixed number of bits, N


Then bitset is similar to vector<bool> the same way std::array is to
std::vector. Bitset and array are stack-based unlike their heap
counterparts.

Did you try benchmarking the <algorithm> version of your code, and the
> hand-rolled version, using `vector<bool>`? How does it compare?
>

yes, I did and the terrible performance motivated me to write this proposal.

Run on (8 X 2400.01 MHz CPU s)
CPU Caches:
  L1 Data 32 KiB (x4)
  L1 Instruction 32 KiB (x4)
  L2 Unified 256 KiB (x4)
  L3 Unified 8192 KiB (x1)
Load Average: 0.12, 0.13, 0.09

# Clang 15.0.3 (-O3 + libstdc++)
-----------------------------------------------------
Benchmark Time CPU Iterations
-----------------------------------------------------
bs_manual 1734 ns 1733 ns 388946
bv_manual 1716 ns 1716 ns 399920
bv_stl 3390 ns 3390 ns 202435
bs_library 26.7 ns 26.7 ns 25967329

# GCC 12.1 (-O3 + libstdc++)
-----------------------------------------------------
bs_manual 2561 ns 2561 ns 258898
bv_manual 2538 ns 2538 ns 277357
bv_stl 2391 ns 2391 ns 291598
bs_library 45.9 ns 45.9 ns 15333493

Source file attached

-- 
Sincerely,
Madhur Chauhan
*β€œTo live is the rarest thing in the world. Most people exist, that is
all.”*
*- **Oscar Wilde*

Received on 2022-10-25 07:46:04