\documentclass{wg21}

\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{xcolor}
\usepackage{soul}
\usepackage{ulem}
\usepackage{fullpage}
\usepackage{cite}
\usepackage{parskip}
\usepackage{hyperref}
\usepackage{csquotes}
\usepackage{listings}
\usepackage{minted}
\usepackage{enumitem}
\usepackage{minted}

\begin{document}

\title{7 Years Later: On \tcode{vector<bool>} and optimized Standard Algorithms in libstdc++ for Google Summer of Code 2019}
\audience{Free Software Foundation, libstdc++-dev}
\author{<NAME>}{<EMAIL>}{Columbia University}
\date{February 3rd 2019}

\maketitle

In 2012, <NAME> wrote a blog post about the performance characteristics and qualities of not only \tcode{vector<bool>} but the standard algorithms that underpin all containers\cite{hinnant_on_vector_bool}. By this time, libc++ added internal overloads to optimize \tcode{std::vector<bool>}'s iterator for various algorithms\cite{libc++_bit_iterator} including \tcode{std::find}, \tcode{std::fill(_n)}, \tcode{std::find}, \tcode{std::equal} and others. Things are not as far along in libstdc++. Only \tcode{std::fill}\cite{libstdc++_bit_iterator} has an overload in libstdc++'s library for \tcode{_Bit_iterator}s. Performance data captured in statistically rigorous benchmarks for various Standard Libraries -- including VC++ and libstdc++ -- show that \tcode{vector<bool>} and its bit iterators are not as optimized as they ought to be\cite{bit_proposal_gsoc2019}.

With the coming revival of bit utilities paper for the C++ Standard and the potential of a new suite of bit utilities coming from a header \tcode{<bit>}\cite{p0237}, the goal of this \textsc{Google Summer of Code 2019} project will be to identify existing algorithms where libstdc++ will benefit from additional overloads based on using the bit iterators. This proposal also explores the fundamental appeal of broadening this class of optimizations to types that are not only represented by bit iterators or \tcode{std::vector<bool>}, but any type whose bits are trivially relocatable under the upcoming work of <NAME> that is gaining both LLVM Clang\cite{relocatable_clang} and the GNU Compiler Collection (GCC)\cite{relocatable_gcc} implementation traction, as well as broader C++ community exposure\cite{odwyer_cppchat}.


\section[background]{Background}

I am a student at Columbia University who spends their free time working on high-quality C++ libraries\cite{sol2} and participating in C++ Standardization\cite{c++_standardization}. After engaging in a Library Working Group "Issues Processing" session during the 2018 Rapperswil-Jona C++ Standards Meeting\cite{c++_rapperswil_2018} at the HSR Hochschule für Technik Rapperswil, I realized that I could help contribute to the Standard Libraries that make C++ both fast and easy to use.

I also wanted to try implementing the newer bits of the C++ Proposal for Bit Utilities, P0237\cite{p0237}. But before I do that, I realized that getting real-world experience with the existing bit utilities in an actual C++ Standard Library would give me a much greater perspective in helping to move those utilities forward and push a much more complete product into the C++ Standard.

My résumé is available upon request.


\section[phase1]{Phase 1: Updating tr2::dynamic_bitset using accumulated knowledge based on an updated P0237}

Initial communication with P0237's author -- Dr. <NAME> -- has yielded that P0237 is likely to receive an update before GSoC 2019 comes out with a new approach to greatly expand the utilities of a \tcode{<bit>} header.

libstdc++ has a minimally-maintained dynamic bitset in <tr2/dynamic_bitset>, but needs to be more thoroughly tested and updated.

The new direction for P0237 -- as has been explained -- will be to allow for a container adapter which might sit on top of any container, allowing the user to pick the necessary underlying container which will provide for the (primitive) type that bit operations will be performed on. An early implementation of \tcode{std::dynamic_bitset<Container} will prove instrumental in vetting design decisions and optimization opportunities for C++, and prevent having to write Yet Another Owning Container With Slightly Different Conflated Semantics for Standard Library developers.

The full deliverable for Phase 1 will be an implementation and discussion of \tcode{template <typename Container> class std::dynamic_bitset;} for libstdc++.

\begin{enumerate}
	\item Week 1 will be spent identifying the necessary requirements to place on Container (e.g., should it work with just \tcode{ContiguousSequenceContainer}, or with things like \tcode{std::list} that are just bidirectional sequences?). It will also be spent considering whether \tcode{std::dynamic_bitset<std::span<T>>} should be possible, and whether other non-owning ranges can be put into \tcode{std::dynamic_bitset} or if \tcode{template <typename Range> std::bitset_view<Range>} might be a valuable addition to the library.
	\item Weeks 2-3 will be spent implementing the container, taking advantage of the requirements identified in Week 4.
	\item Week 4 will be locating and potentially acting on optimization opportunities inside of \tcode{dynamic_bitset}.
\end{enumerate}

The reason this portion is worked on first is because we will need to finalize and update \tcode{_Bit_iterator} and \tcode{_Bit_reference} to be shared between this implementation and \tcode{vector<bool>} for Phase 2.


\section[phase2]{Phase 2: Library Algorithms}

At this stage, verification of the work done begins and iteration over the previous functions while we look to the standard library algorithms for optimization opportunities will begin. Because we will have a common bit iterator and bit reference nomenclature, we can specialize and overload C++ Standard Library algorithms to take advantage of both contiguous iterator and bit iterator structures. Verification will include:

\begin{enumerate}  
	\item Correctness - Algorithms will be tested against libstdc++'s preexisting tests for these algorithms to ensure that adding these overloads does not break the correctness of the algorithm's implementations;
	\item Benchmarks - performance is correctness. Currently, there is a harness of benchmarks created specifically for this proposal. Hooking into libstdc++'s testing infrastructure will be vital in ensuring the longevity of these changes (and if not, a test suite with benchmark data is available at\cite{bit_proposal_gsoc2019}); and,
	\item Code review - the general quality review process that happens through mailing list discussion.
\end{enumerate}

Notably, tests that we must pass are contained in the following files, as of the time of writing:

\begin{itemize}
	\item testsuite/25_algorithms/stable_sort/3.cc
	\item testsuite/25_algorithms/adjacent_find/vectorbool.cc
	\item testsuite/25_algorithms/find/vectorbool.cc
	\item testsuite/25_algorithms/is_permutation/vectorbool.cc
	\item testsuite/25_algorithms/heap/vectorbool.cc
	\item testsuite/25_algorithms/find_end/vectorbool.cc
	\item testsuite/25_algorithms/find_if_not/vectorbool.cc
	\item testsuite/25_algorithms/iter_swap/20577.cc
	\item testsuite/25_algorithms/find_first_of/vectorbool.cc
	\item testsuite/25_algorithms/find_if/vectorbool.cc
	\item testsuite/25_algorithms/sort/vectorbool.cc
\end{itemize}

As stated in early communication\cite{bit_proposal_libstdc++_initial_mailing}, many of the bitset tests only deal with a small number of bits. Expanding this test suite will be part of the deliverable value of this proposal.

\subsection{Phase 2 \textsc{MVP}: improved libstdc++ \tcode{std::find}, \tcode{std::equal}, \tcode{std::copy} and \tcode{std::count}}

Improving these algorithms will follow in the same vein of the improvements hinted at in Howard Hinnant's 2012 article: we will use specialized built-in functions from GCC and Clang in order to provide several orders of magnitude speedup to many of these algorithms to help the standard library remain competitive with hand-rolled implementation.

This will take up weeks 5 through 7 of Phase 2, spending about one week per two algorithm with additional tuning for the last week.

\subsection{Phase 2 \textsc{Stretch Goal}s: enhanced libstdc++ \tcode{std::swap_ranges}, \tcode{std::rotate}, \tcode{std::is_sorted}, \tcode{iter_move}/\tcode{iter_swap} and \tcode{std::is_sorted_until}}

These algorithms are a bit more complicated than the above algorithms and require a degree of additional finesse to ensure correctness. While I am familiar with the intrinsic functions required to make the Phase 1 Deliverables possible, the built-ins used here will undoubtedly be similar but require some research. There are also search patterns and other optimizations that can be applied even at this level, and delivering on these algorithms will be more of a stretch goal.

Note that optimizations will not be applied to \tcode{iter_move} and \tcode{iter_swap}, just changes to make sure they behave properly for all the standard algorithms (albeit it seems like libstdc++ already specializes one of them: ranges work will allow specializing the second for bit iterators).

This will take up any additional time leftover from implementing the Phase 2's \textsc{mvp}.


\section[phase3]{Phase 3: Research and Guideline development for \tcode{is_trivially_relocatable} usage in algorithms}

\tcode{is_trivially_relocatable<T>} is a trait that is seen as the current logical evolution of wanting to support what has been typically referred to as "destructive move": types whose bits can be taken from one place to another and who (effectively) end the lifetime of their source. \tcode{std::is_trivial_v<T>} gave us the legal definition of a type that should be trivially relocatable (and thus bit-blast-able) from one memory location to another. The current rendition of \tcode{is_trivially_relocatable<T>} being worked on by <NAME> and <NAME> in libstdc++ gives us a trait that identifies whether the physical layout of a type is also bit-blast-able from one place to another. In libstdc++, the patch remains for a strictly internal library trait. Early work suggests it is a good area for future-looking library improvements.

Phase 3 will be all about analyzing where and how in the Standard Library -- in particular, algorithms such as \tcode{std::equal}, \tcode{std::find}, \tcode{std::fill}, \tcode{std::copy}, etc. can use this information to perhaps work down to either using intrinsic functions for copy operations or directly applying \tcode{std::memcmp}, \tcode{std::memchr}, \tcode{std::memcpy}, and other high-performance bit-based functions and intrinsic functions.

Should this proposal be accepted, Phase 3 will consist of:

\begin{enumerate}
	\item Research - contacting <NAME> and engaging other Standard Library maintainers to help identify places where \tcode{is_trivially_relocatable<T>} can bring benefit to libstdc++;
	\item Implementation - attempting proof of concept code rewritten to take advantage of \tcode{is_trivially_relocatable<T>} for various primitive types in libstdc++'s internal mechanisms; and
	\item Review - provide feedback (possibly integrated into P1144 \cite{p1144} and a new revision of P0237 \cite{p0237}) that lays out the merits and usefulness of \tcode{is_trivially_relocatable<T>} for Standard Library implementations.
\end{enumerate} 

This is the most research-heavy portion of the proposal. A significant amount of proof of concept work has already been performed by <NAME> and <NAME> in this area for some standards containers: extending it and recognizing when it could apply to algorithms with ranges and iterators seems to be the next logical step for ensuring maximal performance in the Standard Library (if the compiler doesn't optimize such already).

Phase 3's \textsc{mvp} will be showing proof of communication and feedback with <NAME>, <NAME> and the chosen mentors about the benefits this can bring to the Standard Library. The \textsc{stretch goal} will be having the feedback incorporated into respective Standards papers and information left in libstdc++'s documentation about the research efforts, particularly places of useful or interesting design expansion not identified in the early weeks of Phase 1.

Any leftover work from Phase 2 will be checked here for correctness and performance, and tests will be enhanced.


\section[summary]{Summary}

Summarizing, this proposal seeks to:

\begin{enumerate}
	\item Improve libstdc++'s handling of bit utilities to be on part with libc++'s while also teaching myself what a real-world usable Standard Library would require for bit utilities;
	\item Produce an implementation of an adaptable P0237;
	\item Research more closely additional places that the potential trait \tcode{std::is_trivially_relocatable} might bring to the standard library; and,
	\item Use that information to help guide libstdc++'s future optimization development and to provide proper feedback to C++ Standardization with real-world implementation and usage experience.
\end{enumerate}

I humbly request the opportunity to work on this for the greater C++ and open source communities as part of the \textsc{Google Summer of Code 2019}.

\bibliographystyle{unsrt}
\bibliography{thephd-gsoc-2019}

\end{document}
