Subject: Re: [boost] Add an adapter to cover fast bit functions
From: Steven Watanabe (watanabesj_at_[hidden])
Date: 2018-08-27 00:36:41
On 08/26/2018 05:32 PM, Evgeny Shulgin via Boost wrote:
> Hi all, some days ago I opened a thread about DynamicBitset (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  (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
- 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.
> I guess it can be placed somewhere to *Boost.Algorithm*, and supported with
> CI build tests of different platforms.
> 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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk