8 ms·
Converting integers to decimal strings faster with AVX-512
- jeffbee 5y agoI'd be curious about use cases where this does or does not make sense. On the one hand, you saved a few nanoseconds on the integer-to-string encoder. But on the other hand you're committed to storing and transferring up to 15 leading zeros, and there must be some cost on the decoder to consuming the leading zeros. So this clearly makes sense on a write-once-read-never application but there must also be a point at which the full lifecycle cost crosses over and this approach is worse.
- aqrit 5y agorelated to IEEE 754 double-precision floating-point round-trips?
- dzaima 5y agoThe article compares padded length 15 output for both cases; removing leading zeroes would have cost for both AVX-512 and regular code.
- jeffbee 5y agoYeah, that's the "this approach" to which I refer though. This is a micro-optimization of an approach that I'm not sure has many beneficial applications.
- dzaima 5y agoAh. The article, as I see it, is primarily about AVX-512 vs scalar code, not the 15 digits though. The fixed-length restriction is purely to simplify the challenge. To remove leading zeroes, you'd need to use one of bsf/lzcnt/pcmpistri, and a masked store, which has some cost, but still stays branchless and will probably easily be compensated by the smaller cache/storage/network usage & shorter decoding.
- celrod 5y agoAVX512 has a compressed store which might be a bit easier than a normal masked store?
- dzaima 5y agocompress has less throughput, and probably a decent bit more latency. It would save offsetting the result pointer by the leading zero count, but I don't think that'd be enough to compensate for the slower compress. I don't know where regular masked store is done in the pipeline though, so maybe it has its own latency comparable to that of compress, but I doubt it.
- celrod 5y agoYeah, 2p5 (two uops on port 5) for a compressed store vs 1p05 (1 uop on either port 0 or port 5) for a masked move. For throughput's sake, shifting the pointer is better.
- Aardwolf 5y agoAnd meanwhile after 9 years of existing intel is still not reliably adding avx 512 to flagship desktop/gaming cpu's, first because of 5+ years of using the same old architecture and process, now because I don't know why they disabled it when it was there. Why was it not a problem for Intel to add mmx, several sse iterations, avx, avx 2, but now 9 years of nothing, even though parallel computing in annoying to program for and depend on gpu's is only gaining in importance?
- ceeplusplus 5y agoIt costs a lot of area for something that's doesn't move the needle for the majority of desktop applications (browsers, games, office apps). The AVX512 units on Skylake-SP for example are a substantial portion of the area of each core. At some point you have to consider how many cores you could fit in the area used for vector extensions and make a trade-off.
- aseipp 5y agoThis argument IMO is rather overblown. A quick die shot of Skylake-X indicates to me that even if you completely nerfed every AVX-512 unit appropriately (including the register files) on say, an 8-core or 10-core processor, you're going to get what? 1 or 2 more cores at maximum?[1] People make it sound like 70% of every Skylake-X die just sits there and you could have 50x more cores, when it's not that simple. You can delete tons of features from a modern microprocessor to save space but that isn't always the best way forward. In any case, I think this whole argument really misses another important thing, which is that the ISA and the vector width are separate here different. If Intel would just give us AVX-512 with 256b or 128b vectors, it would lead to a very big increase in use IMO, without having to have massive register files and vector data paths complicate things. The instruction set improvements are good enough to justify this IMO. (Alder Lake makes it a more complex case since they'd need to do a lot of work to unify Gracemont/Golden Cove before they could even think about that, but I still think it would be great.) They could even just half the width of the vector load/store units relative to the vector size like AMD did with Zen 2 (e.g. 256b vecs are split into 2x128b ops.) I'll still take it [1] https://twitter.com/GPUsAreMagic/status/1256866465577394181/photo/2 https://twitter.com/GPUsAreMagic/status/1256866465577394181/...
- nitwit005 5y ago> The code is a bit technical, but remarkably, it does not require a table. Those constants being used look a lot like a table.
- dzaima 5y agoThe list of arguments to _mm512_setr_epi64 are just reciprocals of powers of 10, multiplied by 2^52. The scalar code uses division by powers of 10, which'd compile down to similar multiplication constants; you just don't see them because the compiler does that for the scalar code, but you have to do so manually for AVX-512. And permb_const is a list of indices for the result characters within the vector register - the algorithm works on 64-bit integers, but the result must be a list of bytes, so it picks out every 8th one.
- adrian_b 5y agoI assume that he referred to the fact that the code does not need an array in memory, with constant values that must be accessed with indexed loads. Using such a table in memory can be relatively slow, as proven by the benchmarks for this method. There are constants, but they are used directly as arguments for the AVX-512 intrinsics. They must still be loaded into the AVX-512 registers from memory, but they are loaded from locations already known at compile-time and the loads can be scheduled optimally by the compiler, because they are not dependent on any other instructions. For a table stored in an array in memory, the loads can be done only after the indices are computed and the loads may need to be done in a random order, not in the sequential order of the memory locations. When the latencies of the loads cannot be hidden, they can slow a lot any algorithm.
- orlp 5y agoIf your program is sufficiently large and diverse the constants embedded in the instructions are no better than a table load/lookup. The jump to the conversion routine is unpredictable, and the routine will not be in the instruction cache, causing the CPU to stall while waiting for the instructions to load from RAM. This will never show up in a microbenchmark where the function's instructions are always hot. In fact, a lot of microbenchmarking software "warms up" the code by calling it a bunch of times before starting to time it, to maximize the chances of them being able to ignore this reality.
- bumblebritches5 5y ago
- thebiss 5y agoIf you're curious what gets generated, Godbolt maps the C code to ASM, and provides explanations of the instructions on hover. Link below processes the source using CLANG, providing a cleaner result than GCC. [0] https://godbolt.org/z/78KodqxaP https://godbolt.org/z/78KodqxaP
- cosmiccatnap 5y ago
- MrYellowP 5y agoThat memcopy version is hilariously bad. He could at least have made a proper assembly version for a proper comparison.
- dzaima 5y agothe memcopies will of course be compiled to unaligned loads & stores. Clang even seems to simplify the multiplications based on the size of the current portion of the argument, so I don't see much that could be improved. Maybe you could squeeze out a dozen or two percent more speed, but not 3.5x faster.