[ GSoC ] Bit Iterators, trivial relocatability, and performance

[Jonathan Wakely]

On 04/02/19 11:59 +0100, Marc Glisse wrote:
>On Mon, 4 Feb 2019, JeanHeyd Meneide wrote:
>
>>Dear libstdc++-dev Community,
>>
>>    I hope this e-mail finds you all doing well. My name is JeanHeyd
>>Meneide and I am interested in participating in the Google Summer of Code,
>>2019.
>>
>>    I have put together a preliminary proposal for working on
>>_Bit_iterator and overloading several standard algorithms to improve their
>>performance characteristics, following the wisdom of the 7 year old Howard
>>Hinnant writeup on vector<bool> (
>>https://howardhinnant.github.io/onvectorbool.html). I also want to look
>>into algorithmic performance improvements related to
>>is_trivially_relocatable. The proposal can be found at:
>>https://github.com/ThePhD/gsoc-2019-bit/blob/master/proposal/gsoc-2019.pdf
>>
>>    I know the student application section for GSoC isn't open yet, but I
>>wanted to gain early feedback on this and was advised by people to post
>>here. (If this is the wrong place, I can post it elsewhere, such as the
>>typical gcc-dev list?)

Hi JeanHeyd, this is definitely the right place, thanks for the email
and your interest in contributing to libstdc++!

>I am not available enough during the summer to co-mentor, but the 
>topic is interesting and if you post to this list I'll likely be able 
>to help sometimes.

I would be willing to co-mentor, if somebody else is as well. It's
possible I could be the sole mentor, but I am always desperately short
of time just for existing work, and I might not do a good job as
mentor by myself.

>Some comments:
>
>2§1 it is good to test against preexisting tests, but it wouldn't hurt 
>to add some new ones. The pitfalls will not be exactly the same, and 
>while the existing tests are fine for a naive implementation, they may 
>not include large consecutive groups of false (where some intrinsics 
>have undefined behavior), etc.

Absolutely agreed. We have the following tests:

testsuite/25_algorithms/stable_sort/3.cc
testsuite/25_algorithms/adjacent_find/vectorbool.cc
testsuite/25_algorithms/find/vectorbool.cc
testsuite/25_algorithms/is_permutation/vectorbool.cc
testsuite/25_algorithms/heap/vectorbool.cc
testsuite/25_algorithms/find_end/vectorbool.cc
testsuite/25_algorithms/find_if_not/vectorbool.cc
testsuite/25_algorithms/iter_swap/20577.cc
testsuite/25_algorithms/find_first_of/vectorbool.cc
testsuite/25_algorithms/find_if/vectorbool.cc
testsuite/25_algorithms/sort/vectorbool.cc

But they all work on tiny data sets (usually fewer than 8 bits) so
won't hit any edge cases likely to matter with smarter
implementations. Naïve tests are OK for a naïve implementation, but a
smarter implementation will need more tests.

>I never tried to run the llvm checks on 
>libstdc++, but trying it once (without spending weeks on it if it is 
>hard) could be a nice sanity check.

Running the libc++ tests is trivial, you just need a lit.site.cfg like
the one attached, to tell the test harness to use g++.

>2§3 code review really happens on the list, bugzilla is for reporting bugs

Yup.


>2.2 it isn't clear what you would optimize about iter_move/iter_swap, 
>which handle a single bit. If there is work to be done here, it is 
>more likely in the optimizers.
>
>3 Don't oversell Arthur's proposal. It was one amongst several that 
>appeared along the years, and it doesn't seem to have been received 
>much better (i.e. people are interested but it isn't clear the 
>approach is the one we want).

Agreed.

I think an implementation of P0237 might be more valuable than the
trivially-relocatable topic (and closer to the vector<bool> part of
the proposal).

N.B. as I think Ville mentioned previously, we do have a
dynamic_bitset in libstdc++. <tr2/dynamic_bitset> is an implementation
of N2050, but has only been minimally maintained since it was added.
There are no specialized algorithms for it, so there is definitely
room for improvement.

>The remark above about optimizers is one I think is interesting when 
>contributing to a compiler, although others may find it less relevant: 
>it is good to tweak the library to improve performance, but when 
>possible it is even better to tweak the optimizers to generate the 
>same good asm from the old readable code. The second is often harder 
>or even impossible, so it is worth doing the first, but it should be 
>kept in mind when you see a low hanging fruit. And for this, it may be 
>good to take a look at what the compiler (with -O2 or -O3) writes with 
>-fdump-tree-optimized. It is good anyway because you will have a 
>clearer picture of what your code does, you will notice if popcount is 
>surrounded by tons of tests or in a tight loop, etc.

Yes, if research done for such a GSoC project results in
"missed-optimization" bug reports for the compiler, so that the
optimizers can improve, then that's a good outcome too. Source-level
optimizations in the library code do not have to be the only goal.


-------------- next part --------------
# This file belogs in libcxx/test/lit.site.cfg

# Configure the testsuite for libstdc++.
config.cxx_stdlib_under_test    = 'libstdc++'

local_gcc_path = "/home/jwakely/gcc/latest"
# The compiler used to test. Set this to your prefered default. You
# can use --param=cxx_under_test=<comp> to override it on the command line.
config.cxx_under_test           = "%s/bin/g++" % local_gcc_path

# The directory containing libstdc++.so. This will add '-L<path>'
# and '-rpath <path>'
config.cxx_library_root         = "%s/lib64" % local_gcc_path

# Enable/Disable testing certain features. These should be the right defaults
# for ToT libstdc++
config.enable_exceptions        = "True"
config.enable_experimental      = "True"
config.enable_filesystem        = "True"
config.enable_rtti              = "True"
config.enable_shared            = "True"
config.enable_32bit             = "False"

# Misc GCC configuration options
config.target_triple            = ""
config.sysroot                  = ""

# This path will be used when generating temporary files when running the tests.
config.project_obj_root         = '/tmp/libcxx-testsuite-output'
config.libcxx_obj_root          = '/tmp/libcxx-testsuite-output'

# Let the main config do the real work.
import os
cfg_path = os.path.join(os.path.dirname(os.path.realpath(__file__)), 'lit.cfg')
config.loaded_site_config = True
lit_config.load_config(config, cfg_path)