StephanTLavavej

Yep, that's my pull request. :-) At the moment, it's usable if you build the microsoft/STL repo with VS 2022 17.4 Preview 3 or later. When VS 2022 17.5 Preview 1 ships (in the very near future; can't say when exactly), it will be "in box" without the need to build our GitHub repo.

It will still be necessary to build the std.ixx source file (to produce std.ifc and std.obj for consumption; we will never ship prebuilt IFCs/OBJs for the standard modules). It takes maybe 3-5 seconds and doesn't need to be rebuilt until you change your compiler options or upgrade your toolset. Build system support for doing this automatically is a work in progress.

Although we have test coverage running that exercises every header of the Standard Library through `import std;`, we're still working on fixing various compiler bugs, especially in complicated scenarios (e.g. using Ranges through modules). My hope is that the experience will be solid by the time that VS 2022 17.5 is released for production.

Note that the O-rings were 12 feet in diameter - they encircled the entire solid rocket booster. They definitely didn't cost less than a dollar.

I'm glad you liked my charconv talk! Here's a complete list of my recorded conference talks:

BoostCon/C++Now 2012: Regex In C++11 And Boost: https://youtu.be/mUZL-PRWMeg

GoingNative 2012: STL11: Magic && Secrets: https://docs.microsoft.com/en-us/events/goingnative-2012/stl...

GoingNative 2013: Don't Help The Compiler: https://docs.microsoft.com/en-us/events/goingnative-2013/don...

GoingNative 2013: rand() Considered Harmful: https://docs.microsoft.com/en-us/events/goingnative-2013/ran...

CppCon 2014: STL Features And Implementation Techniques: https://youtu.be/dTeKf5Oek2c

CppCon 2015: functional: What's New, And Proper Usage: https://youtu.be/zt7ThwVfap0

CppCon 2016: tuple: What's New, And How It Works: https://youtu.be/JhgWFYfdIho

CppCon 2018: Class Template Argument Deduction for Everyone: https://youtu.be/-H-ut6j1BYU

CppCon 2019: Floating-Point charconv: Making Your Code 10x Faster With C++17's Final Boss: https://youtu.be/4P_kbF0EbZM

CppCon 2020: C++20 STL Features: 1 Year of Development on GitHub: https://youtu.be/8kjRx8vo6y4

Pure Virtual C++ 2022: MSVC C++20/23 Update: https://youtu.be/DAl37n2XOwk

std::format is available, with all C++20 Defect Reports implemented, in VS 2019 16.11.14 (and all later 16.11.x) and VS 2022 17.2 (and all later 17.x).

It’s actually inverse cube for magnets - see https://en.wikipedia.org/wiki/Force_between_magnets : “One characteristic of a dipole field is that the strength of the field falls off inversely with the cube of the distance from the magnet's center.”

Here’s what we do in MSVC’s STL:

    constexpr bool test_is_even() {
        assert(is_even(0));
        assert(!is_even(1));
        // … more test coverage
        return true;
    }
    int main() {
        test_is_even(); // runtime coverage
        static_assert(test_is_even()); // compile-time coverage

This lets us run all test cases at both runtime and compiletime. (The static_assert performs constant evaluation, and if an assert within test_is_even would fail, it won’t be a constant expression.)

> I'm curious if anybody is working to make C++ faster to compile.

Yes - C++20 added support for modules to the Core Language (both "header units" and "named modules"; header units are an intermediate step between classic includes and named modules), and support for header units to the Standard Library. Compiler/library support is a work in progress (MSVC's STL, which I work on, is the furthest along - see https://github.com/microsoft/STL/issues/1694 for status), but header units are showing significant improvements in compiler throughput (build speed). This looks like `import <vector>;` in your source code (with significant build system changes to build vector as a header unit, producing vector.ifc and vector.obj).

There's a proposal under review for C++23 to add named modules for the Standard Library, see https://wg21.link/p2465r2 . If this is accepted, `import std;` (or `import std.compat;`) will be the one-line way to use the entire C++ Standard Library with (what we hope will be) even better compiler throughput.

The primary limitation of header units and especially named modules is macros: neither can be influenced by macros defined in the source file, and named modules can't emit macros at all. Thus, one will still need to `#include <cassert>` in addition to `import std;` if you want the `assert()` macro.

Can you expand on how Roll breaks down when the players are trying to win?

Thank you!

I opened the spreadsheet, and now I can't remove it from my list of Google Sheets (unlike most shared spreadsheets). Am I missing some obscure way to remove it, despite the Remove option being grayed out? (It does respect the "Owned by me" filter so this isn't the end of the world.)

MSVC has /O1 and /O2 (and /Os), but not /O3. See https://docs.microsoft.com/en-us/cpp/build/reference/compile... . (I work on MSVC's STL.)

Modern processors have integrated “firmware” TPMs, so you shouldn’t need a discrete module. See https://arstechnica.com/gadgets/2021/06/heres-what-youll-nee... for some details. I was able to enable mine in my BIOS.

(I work for MS, but in Visual C++, not Windows, and I don’t speak for them.)

Well beyond exploring - microsoft/STL runs libc++’s test suite for every PR, skipping a set of known failures (for product bugs, test bugs, etc.), see https://github.com/microsoft/STL/blob/main/tests/libcxx/expe... . (I work on MSVC’s STL.)

On the "How Was It Typed" page, Note 6 and beyond are using the same image, and link to an "http://xxxx" placeholder. Different images appear to have been intended (e.g. a Roman Numeral technique is described in the text).

Thanks for this writeup and fascinating analysis - I hope more of the mystery can be solved!

https://www.planetary.org/articles/08190630-curiosity-wheel-... explains the root cause.

That “weirdness” is just scientific notation, which the Ryu implementation always emits. It is “superficial” in the sense that it’s separate from the core algorithm. When I adapted it for C++17 charconv in MSVC, I implemented fixed, general, and “plain shortest” notation, which will print 0.3 there. (General notation follows C printf %g’s rules for switching between fixed and scientific; “plain shortest” notation selects the one that’s fewer characters, tiebreaking to prefer fixed).

We actually do use libc++'s test suite, which has found several bugs, but not this one (apparently because they don't yet have std::boyer_moore_searcher).

> you're guaranteed to have some bugs when implementing BM. Writing your own string search function seems nearly on the same level as implementing your own cryptographic functions, though.

And that’s the Curse Of The Standard Library Implementers: we’re the ones that have to implement Boyer-Moore, floating-point string conversions, etc. so everyone else can use them :-)

Very interesting, thanks!

Indeed, the randomized test in this PR uses alphabets from AB to ABCDEF, because I noticed the same thing - small alphabets make repetitions more likely, which are the tricky cases.

Apparently there are multiple fixes, some of which are said to be simpler. See https://github.com/microsoft/STL/issues/727 and the cited comments within, which quote Knuth. (I'm learning a lot by having this PR appear on HN!)

I conclude that usage of std::boyer_moore_searcher is relatively low, despite this C++17 feature shipping in VS 2017 15.3 (August 2017).

"www" triggers the bug like all 3-character repeats, but Boyer-Moore manages to find it in "http://www.example.com/" despite the damaged delta2 table, because the incorrect shift value is never exercised. However, a haystack of "https://www.example.com/" triggers the bug, because now the "www" is at an offset of 8.

This sounds like the vector<list<unique_ptr<T>>> fiasco, where a vector contains elements that are movable-only (you can't copy a list<unique_ptr<T>>, only move it), yet with throwing move constructors (as MSVC's list, set, and other node-based containers dynamically allocate sentinel nodes when default/move-constructed - this is a behavior difference from GCC's libstdc++ and Clang's libc++, where both dynamically-allocated and container-internal sentinel nodes are permitted by the Standard). The doom begins when STL containers like list (also vector itself) don't have "constrained copy constructors" - that is, list(const list&) always appears to be available, as far as type traits like is_copy_constructible are concerned, even if that copy constructor can't actually compile. The doom accelerates when vector<Elem> needs to ask the question "are you nothrow-movable? If so, I can move you efficiently. Otherwise, are you copyable? If so, I can fall back to copying you during reallocation, in order to preserve the strong exception guarantee. Otherwise, you're throwing movable-only, so I'll move you and you get the basic guarantee". The doom is complete when list<unique_ptr<T>> correctly reports that it isn't nothrow-move-constructible (it would throw due to allocating a sentinel), yet incorrectly claims to be is_copy_constructible. Therefore the vector tries to copy the list<unique_ptr<T>> and that fails to instantiate, resulting in an epic compiler error.

This situation is a fiasco because there is no good way out of it (constraining container copy constructors isn't possible because the Standard permits incomplete element types for many containers, and users use them for other containers even though they technically shouldn't, weakening EH guarantees is potentially problematic, changing the nature of sentinel nodes is ABI-breaking and affects iterator invalidation guarantees). It is also highly memorable, which is why I can guess what it was :-)

I believe that fuzz testing would have found it, yes. I'm not sure if fuzz testing would have been guided towards highly repetitive patterns, given the relative lack of branches in the table construction code, but the incorrectly handled patterns can be very short so fuzz testing should have stumbled upon them (given a pattern that generated an incorrect table, finding a haystack which doesn't work is merely a matter of having the needle occur at a specific offset).

Currently we don't fuzz test MSVC's STL, but that is an extremely interesting area to explore in the future. I played around with this a little while working on std::from_chars() (and found no bugs), but it involved actually porting the code to Linux to be compiled with American Fuzzy Lop, so I didn't permanently add such test coverage to our repo.

After comparing the outputs of the old and new algorithms, I believe that a needle needs more than two repeats in order to trigger the bug. That is, "aa" and "abab" don't trigger the bug, but "aaa" and "ababa" do, the last one having a partial third repeat (needle "ababa" with haystack "WXYZababa" was definitely wrong). I tested the table output for "aa" for completeness (and just in case we manage to damage it in the future).

Disclaimer: I don't understand the algorithms deeply enough to write them from scratch, and I'm writing this at 6 AM.

And this works because I have `using namespace std;` in the test, which makes all of the Standard Library's "user"-defined literals available. So does `using namespace std::literals;` (without dragging in other names). There's also the extremely fine-grained `using namespace std::chrono_literals;` (no need to type `using namespace std::literals::chrono_literals;` due to how inline namespaces work) which drags in just the chrono duration literals. Finally, `using namespace std::chrono;` drags in all of the chrono names and the chrono literals.

The reason that a using-directive of some kind is necessary is that UDLs are provided by operators, and directly spelling out the operator in order to namespace-qualify it would be self-defeating. (Many people dislike `using namespace std;` and I understand their point, but when one works on the STL all day every day, this using-directive is sure nice for test code.)

My exhaustive test case for this is (demonstrating all the different ways that chrono literals can be accessed): https://github.com/microsoft/STL/blob/31419650d472932dd24b9c...

The smallest test case appears to be a needle of "aaa" and a haystack of "xxaaa", where VS 2019 16.5's boyer_moore_searcher will report "not found", while the corrected code finds the needle at offset 2 in the haystack.

Legends of Caltech, page 69 has the story and a photograph (looking at my copy right now). It was a valve package plate on the Voyagers ink-stamped with “DEI/FEIF”.

And that's only quadratic growth, not exponential.

Dark mode is still incompatible with monospace code regions, as reported several times in the ApolloApp subreddit; I tried using Apollo yesterday but couldn’t get past this bug (as I read a lot of code on reddit). Please fix this and I’ll buy the app!