[ GSoC ] Bit Iterators, trivial relocatability, and performance

[Thomas Rodgers]

Jonathan Wakely writes:

> 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.
>
I would also be willing to co-mentor.

>>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.
>
>
> # 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)