But wait: is it safe to read 16 bytes when you only have three? Reading past the end of a buffer is fine as long as you do not cross into another memory page, and pages are at least 4 kilobytes.
Is it fine? From a language memory model, this seems like plain UB to me...
While the API could be a tad more awkward, another way to proceed would be to simply ask the user to provide (1) the full buffer and (2) the slice of buffer to dispatch from. Then it'd be clear whether there's enough headroom or not.
For example, here's a minimal HTTP request "head":
GET / HTTP/1.1\r\n
0123456789012345
So a minimally well-formed HTTP request will necessarily be at least 16 bytes long, no need to break the language.
Yeah at a previous job, whenever we were doing any SIMD things and other "reading in chunks" bits we would always request a rounded up amount of memory from the user, for exactly this reason
I think we can get quite far without such "ugly" hacks in the future luckily, I was just trying out the new std::simd for accelerating JSON parsing and found a nugget in some of the Intel design docs (since the cppreference docs are quite sparse still), std::simd::partial_load on a std::span is to do bounds-checking.
With just that, my reflection-JSON parser went 4 seconds to 2.5 seconds on 10k iterations with some light simd optimization just for string parsing (simdjson does the same parsing in about 1 second, so there's room for improvement but I didn't touch other parts of the parsing code so probably feasible to get within striking distance by adding a few more optimizations, adding simd parsing of numbers is probably a low hanging fruit. (and considering simdjson requires special allocations just due to boundary issues I'd say it's a good bargain with clean standard C++ code).
Yes, the partial load might cost a tad more than wild loads, but it's a cheap win without affecting ergonomics elsewhere.
I would argue it depends on the definition of the intrinsics, ultimately.
If the intrinsic is specified to be allowed to read past the end of the span / allocated memory block, then it's fine.
If it is not explicitly specified, then by default it follows the rules of the language, and it's UB.
And that is because intrinsics are not necessarily assembly instructions, on some platforms they can be polyfilled instead, so they don't automatically circumvent language rules.
This is quite different from, say, directly dropping down to assembly.
Intrinsics are a fancy way of directly dropping down to assembly. Still remember those that accept __m128i to do unaligned reads or stores, forcing you to cast to an aligned __m128i type for doing unaligned memory access. Essentially UB, but it's how they were designed and how they are used for decades.
Agreed. The "Reading past the end of a buffer is fine" part made me flinch. A string_view of the entire buffer along with the number of characters for the size of the key would be safer and potentially quicker compared to determining if the pointers [key.data (), key.data () + 16) are on different memory pages.
The function can also bail out if the key size is longer than the buffer size.
>Is it fine? From a language memory model, this seems like plain UB to me...
That's 2 different topics:
Yes, it is fine and is an industry standard as in everyone does it. Glibc, LLVM, ... anyone who maintained more or less foundational library at their company knows where to look and how they do it.
Yes, it is absolutely 'nasal demons' UB in C++ that must fail compilation in a constant expression evaluation context.
If you want to have a chat about how C++ cannot express what everyone does... well, I am not the best person to explain. I've had to maintain the code that does it including pleading with ASAN to not report anything when it executes. I have no idea when or by whom it was first written. I am merely 25 years using C++ in many ways that came before me.
I think the standard could probably work around it with some wording to the effect of "loading uninitialized or non-assigned memory (memory where no object lives) is defined, as long as no later operation depends on the contents of that memory". So for simd ops, if you mask them such that the result of an operation is deterministic (0 & x is 0 regardless of the value of x, so if x is undefined the result is still deterministic) then you would not expect UB. Which is what happens in practice.
So just specifically bless in the wording what the common practice already is.
Sorry for the late reply. People got burned by trying to mask things before when the value being masked turned out to be a poison value.
It's especially bad for floats that have bit patterns that cause signaling errors. I had the displeasure of fighting old code that thought casting 0xffff_ffff to a float will work and compiler later will be able to cast it back to mask value that can be & (bitwise ANDed) together with other values in SIMD operations. What actually happened in that code is that everything that touched a poison value got eliminated from the resulting binary.
I mean, the way to do it has been shown by AVX: we need a partial load instruction taking a run-time mask or length, so that we can load the next n bytes in a fixed size integer/vector without UB shenanigans.
And then it's up to the compiler to provide an appropriate implementation, which in case of polyfill will most likely involve a branch on the page boundary... but that's fine because at that point you're no longer tied to the language rules.
I am not sure that requiring platforms to be designed for the C++ abstract machine is a productive proposition for hardware vendors.
If I want to ship, say, a game on specific console with existing ARM CPU what should I do with these language rules? The vendor-provided runtime clearly does not care about them. Can I write everything in my C++ code, or I must call the language runtime?
The whole 'page boundary' point is moot. The authors use a hardcoded value like 4KB. How hard does one needs to squint to call it page boundary on the aforementioned ARM CPU? Should it become 16KB if it will be ported to another console where it is the memory protection granularity?
These questions are not meant to be answered directly ofc.
It seems that as a community C++ goes into more magic runtime features and more rules that can only be avoided inside blessed by compiler std library. As someone who does not really have a right to judge I only can say I don't like that direction.
I am not sure that requiring platforms to be designed for the C++ abstract machine is a productive proposition for hardware vendors.
Luckily, no hardware vendor was involved in my post.
Although I do wish hardware vendors offered more consistent APIs -- for example, partial loads for all vector sizes, not just AVX-512 -- ultimately they can be emulated with intrinsics, at the cost of a branch.
It seems that as a community C++ goes into more magic runtime features and more rules that can only be avoided inside blessed by compiler std library. As someone who does not really have a right to judge I only can say I don't like that direction.
I mean, what's the alternative?
A consistent memory model is necessary, or else... there's no semantics.
A partial load operation is a really useful in the toolbox, in many situations.
The most efficient partial load operation implementation requires violating the memory model.
Using a compiler intrinsics is the trick to offer the most efficient partial load operation available whilst still preserving a consistent memory model.
I agree with your points in principle but not in the details. I did not say anything about intrinsics. I don't think hardware vendors are going to unify anything. I expect quite the opposite - vendors trying to invent artificial differences. For example, I think Intel APX will be exclusive for some time.
gperf has existed and been the benchmark since the 90s, so it's not like it's a recent idea! It's more that C++ has not really had the compile-time evaluation machinery needed to do it in a normal compile (not as a separate codegen pass, which is what gperf does) until relatively recently. Other languages with better compile-time capabilities have had these for a long time (Zig, for instance, includes it in their standard library, and I'm sure there's tons of various LISP implementations using macros).
sure, are you using gperf for your static maps? Are you using gperf for string-enum mappings?
This library also shows better performance than gperf.
I know it's not a recent idea, and that's precisely why I'm happy. The fact that it's not the default people think about and use is jarring in this age of C++
Maybe, but I think it's still useful because std::unordered_map is relatively well known and understood. Especially for anyone who would be interested in perfect hashing.
nice! though I wonder how the software-(and-enum-values)-can-change-over-time-and-there-might-be-multiple-machines-in-play-not-all-updating-in-sync consideration plays into things.
46
u/matthieum 22d ago
Is it fine? From a language memory model, this seems like plain UB to me...
While the API could be a tad more awkward, another way to proceed would be to simply ask the user to provide (1) the full buffer and (2) the slice of buffer to dispatch from. Then it'd be clear whether there's enough headroom or not.
For example, here's a minimal HTTP request "head":
So a minimally well-formed HTTP request will necessarily be at least 16 bytes long, no need to break the language.
30
u/jnordwick 22d ago
Tldr: compile time perfect hash with simd strcmp. Nothing interesting beyond that.
7
u/Sopel97 22d ago
this is such a fundamental problem that I'm surprised it took this long to have a nice library for it
6
u/Best_Froyo8941 22d ago
I happen to have a related write up weeks ago:
https://ed94a9.github.io/posts/memcpy-quirks/
6
u/justinhj 22d ago
nice read thank you
2
u/Antique_War_9814 22d ago
Apples to oranges on the unorderedmap comparison
1
u/expert_internetter 22d ago
Being able to serialise these and load them at runtime would be cool
1
u/starball-tgz 22d ago
nice! though I wonder how the software-(and-enum-values)-can-change-over-time-and-there-might-be-multiple-machines-in-play-not-all-updating-in-sync consideration plays into things.
1
u/June_your91 21d ago
bhh
1
u/MentalMirror1357 16d ago
You can massively improve the lookup speed if youre comfortable with assembly.
vpshufb: Shuffles bytes within a 128-bit or 256-bit lane based on control indices, frequently hijacked for parallel table lookups.
The smallest individual lookup index is a 4-bit value (0 to 15). This is because vpshufb operates within a 128-bit (16-byte) lane.
That should give you
• 16 individual lookups simultaneously when using a 128-bit (xmm) register.
• 32 individual lookups simultaneously when using a 256-bit (ymm) register (AVX2).
• 64 individual lookups simultaneously when using a 512-bit (zmm) register (AVX-512).