CppCon 2016: “From Numerical Cosmology to Efficient Bit Abstractions for the Standard Library"

http://CppCon.org — Presentation Slides, PDFs, Source Code and other presenter materials are available at: https://github.com/cppcon/cppcon2016 — Efficient bit abstractions for the standard library, or how to beat vector＜bool＞ performances by three orders of magnitude. Can you imagine a perfect world? A world of unicorns. A world of double rainbows. A world of candy mountains. A world in which vector＜bool＞ would not even have existed. As the first three aspects are easy to imagine, I will mostly focus on the last one. For about 20 years now, vector＜bool＞ has been regarded as a bad design decision. There is no problem with the functionality provided by a dynamic vector of bits, but specializing vector for boolean data types was not the best idea ever. In this talk, I will present a radically new approach, generalizing existing implementation practices and experimentations, to achieve both genericity and performances for bit manipulation. I will describe how we designed a minimalist set of abstractions to access and manipulate bits and to serve as a common basis for bit oriented data structures, algorithms and arbitrary precision arithmetic. This presentation echoes a standardization work that will hopefully make bit utilities available in a future revision of the C++ standard library. Bit manipulation is used as a fundamental building block of a wide range of applications including arithmetic of big integers, cryptography, hash tables, compression, fast Fourier transforms and bioinformatics. We started this work while investigating... the expansion of the Universe. Cosmological simulations on supercomputers require fast data structures, and in our case bit manipulation was a bottleneck. A common problem with bit abstractions is that they need a double standard: an easy to use interface for users, and a full access to low level instructions and compiler intrinsics to make the most of modern architectures. I will review our approach and give examples on how to use our library. I will also explain how to use bit values, bit references, bit pointers and bit iterators to design algorithms that outperform bit vectors by factors varying between 100 an 3500. I will conclude this talk by discussing how the bit abstraction proposal may affect the future of the standard library and particularly how it will be interfaced with standard algorithms, standard containers, ranges and arbitrary precision arithmetic. — Vincent Reverdy University of Illinois at Urbana-Champaign Astrophysicist Urbana-Champaign, Illinois Area Vincent has been working as a post-doctoral researcher at the University of Illinois at Urbana-Champaign (USA) since he obtained his PhD at the Paris observatory (France) in november 2014. His main scientific interests are related to cosmology and general relativity. He his particularly interested in the study of relativistic effects at cosmological scales using high performance simulations run on supercomputers. Because these simulations rely on tree data structures, he started investigating ways to optimize them. He now leads a research team working on tree data structures with main applications in simulations, machine learning, and data science. He also participates into the C++ standardization process and regularly submits proposals to improve the C++ language. — Videos Filmed & Edited by Bash Films: http://www.BashFilms.com Work at Hudson River Trading (HRT): https://tinyurl.com/safxfctf