Re: [boost] Add an adapter to cover fast bit functions

Subject: Re: [boost] Add an adapter to cover fast bit functions
From: Steven Watanabe (watanabesj_at_[hidden])
Date: 2018-08-27 00:36:41

AMDG

On 08/26/2018 05:32 PM, Evgeny Shulgin via Boost wrote:
> Hi all, some days ago I opened a thread about DynamicBitset[1] (where I
> noted that a small piece of code may double the speed of a function), which
> received some interesting answers (you guys rock!)
> 
> I looked deeper and realized that Boost doesn't have functionality to do
> common bit operations *really* fast.<snip>
> 
> So, what do you think of an adapter header in Boost, covering all these
> operation of all integer types (and maybe some other one-liners like
> `is_bit_set(x, pos)` ), which keeps programmers out of platform specifics?
> It may look as smth like this [8] (I wrote only 3 functions, but it's
> enough to show the potential).
> 

- Please don't #include <iostream> in headers, if you can avoid it.
- You're using C++14 constexpr, so BOOST_CXX14_CONSTEXPR
  would be the correct macro.
- You might need to think about whether/how to support
  signed integers.  In particular, I'm thinking about
  swap and rotate.
- For unit tests, it's better to use a prng instead of random_device.
  non-deterministic tests make it more difficult to reproduce
  test failures.
- It's better to separate benchmarks from unit tests.  In particular,
  storing the elements in a vector is necessary for benchmarking,
  since you don't want to benchmark the generation of the
  values, but for tests, it artificially limits the maximum
  number of values you can check.
- For char and short, testing every possible input is easy.
  You can do int, too, if you're willing to wait a bit for
  it to finish.
- s/runned/ran/

> I guess it can be placed somewhere to *Boost.Algorithm*, and supported with
> CI build tests of different platforms.
> 

Or Boost.Integer.

> P.S. The (incomplete) list of bit functions, that will give a *notable*
> better performance compared with naive algos and even some "smart" (because
> of precalc/intrinsics):
> - count of bits
> - parity of bit count
> - first 1-bit
> - last 1-bit (aka integer_log2(x))
> - leading zeros
> - trailing zeros
> - swap(x) - returns x with the order of the bytes reversed; for example,
> 0xaabb becomes 0xbbaa. (bytes here are 8 bits exactly)
> - rotate_left(x, shift)
> - rotate_right(x, shift)
> Other functions may look like `is_set(x, pos) -> return x & (1 << pos)` and
> aren't so interesting.
> 

In Christ,
Steven Watanabe