In German, we have the word Schwuppdizität (perhaps "snappiness") to describe the perceived operating speed of a computer. Very important to distinguish from actual FLOP/s number or similar measures.
335 karma · joined September 13, 2023
This is acceptable if you see the point of inline assembly in writing long code sections, but that's not what inine assembly is meant to solve. If you want to write long sections of assembly code, just put the whole thing into an assembly source file and link it into your binary.
gcc-style inline assembly on the other hand is designed to solve the problem of augmenting code generation with individual instructions the compiler doesn't know about. Correctly used, gcc-style asm statements typically only hold one or two instructions that are then integrated into a complex function with little to no overhead. And for this usage, the syntax and model provided by gcc is perfectly fine. It only fails if you misuse it for writing long chunks of assembly code, something for which you should have used an assembly file in the first place.
It's part of simdutf.
The one in the parent comment does not; it's basically a black box and the compiler has to save and restore the entire state of the function around it. Total performance killer unless you write large chunks of code in inline assembly (and then you're probably better off just using an assembly file).
The main advantage of pcmpistrm is that it doesn't need preprocessing. You can beat its raw speed just fine, e.g. using the Muła/Langdale algorithm (http://0x80.pl/articles/simd-byte-lookup.html), but that algorithm requires costly preprocessing of the set to be matched. For string functions, input strings are usually very short and algorithms have to be optimised for that case; the steady state of a tight main loop is rarely reached and not the primary goal of optimisation. So as a result, any preprocessing before we can get started walking down the string gets really expensive.
In fact, the benchmarks I wrote and whose results the Phoronox page has shamelessly ripped off use strings of just 64 bytes on average, which I believe is more representative for real-world cases than the very long strings other implementations seemed to have been optimised for. This is also the reason why I ended up using just SSE: not only do the instructions provided by SSE2 largely suffice for the job, but also is the advantage of longer vectors severely reduced when your input is unlikely to be longer than one or two of them. Plus for AVX and later, we have to do a VZEROUPPER before return (to ensure other SSE code in the user's program is not impacted), further reducing performance for such short-running string functions.
> I'm also curious if you looked into the difference of asm vs intrinsics, where the compiler was going wrong, and/or how long ago that was?
That was last year. Mainly, the code in question does unusually complex things with mask registers, constantly shuffling data back and forth between general purpose and mask registers. Gcc and clang do a really poor job deciding which operations to do in GPRs and which to do in mask registers. They also fail hard at hoisting constant loads out of hot loops. Finally, register allocation fails to find a solution that keeps everything in registers (which the asm code does just fine with 2 GPRs to spare), instead spilling to the stack.
> As to careful loads and movmskb, Highway does have LoadN and Find(Known)FirstTrue which is still quite decent on Arm. You might find it useful if/when porting?
Maybe, but keep in mind that strings are nul-terminated. So each loop trying to find something in a string must at the same time look for the nul terminator and be careful not to cross page boundaries while doing so. These aspects cannot be separated unless you want to sacrifice performance by reading the string twice at prohibitive cost.
And we don't actually want to do masked loads. Instead, I load with junk before the beginning of the string and mask this junk out off the bitmask when testing if the mask has the desired contents. This moves the µops for computing the mask down the dependency chain to after comparison, improving ILP.
I recommend you try and implement some of these functions yourself. strchr() and strcpy() are good starting points. You can use my benchmark framework (https://github.com/clausecker/strperf) to check the performance. I'm interested in seeing what you come up with.
* about half the code deals with reading the beginning and end of strings by doing elaborate, careful unaligned loads and masking * the other half is straightforward byte-wise comparison following by pmovmskb to inspect where matches were found. This is very performance sensitive and different strategies have to be used on different platforms. For example, NEON doesn't have an instruction like that, so you need to work around the shortcoming in various painful ways.
* some functions currently use the x86-only pcmpistrm instruction and would need a complete redesign for other platforms
I have so far not had any good experience with SIMD libraries for this kind of code. Even C++ + instrinsics delivers poor performance in this sort of setup. For example, when we ported our UTF-8 <-> UTF-16 kernels (AVX-512) from assembly to C++ with intrinsics, performance dropped by 25%.
Also there are two other important constraints:
* we're working far outside the rules of the C language, overreading buffers here and there. It is unknown if the C compiler would miscompile our code.
* similarly, we don't want any C++ in libc, so using a C++-based library is out.
I'm also looking for anybody willing to sponsor a port of this work to other architectures or x86-64-v3/v4 (i.e. AVX2/AVX-512).
Is there anything I can about what Intel planned for their x86 extension to 64 bits? I'm curious about this road not taken.
> Itanium chips were targeted only for high-end systems needing lots of ILP concurrency. There was no economic way to make chips with less ILP (or much more ILP), so no Itanium chips cheap and low-power enough to be packaged as development boxes for individual open-source programmers like Torvalds. This was only going to market via top-down corporate edicts, not bottom-up improvements.
One wonders why they have not learned from this mistake. They continue to make it again and again (AVX-512 and NVRAM are some more recent examples). If the ordinary joe can't get his hands on a box with the new stuff, he's not going to port his software to it or make use of its special features.
> The first-gen Itanium chip, Merced, included a modest processor for directly executing x86 32-bit code. This ran much slower than Intel's contemporary cheap x86 chips, so no one wanted that migration route. It also ran slower than using static translation from x86 assembler code to Itanium native code. So HP dropped that x86 portion from future Itanium chips. Itanium had to make it on its own via its own native-built software. The large base of x86 software was of no help. In contrast, DEC designed Alpha and migration tools so that Alpha could efficiently run VAX object code at higher speeds than on any VAX.
Seems like Apple learned from that. Both generations of Rosetta have top-notch performance. Hard to emulate bits were circumvented by just adding extra features to the CPU that directly implement missing functionality (e.g. there's an x86-like parity flag on the Apple M1).
Thanks, that makes sense. I did not understand the intent of the stop bits correctly. However, it still seems like the design wouldn't scale super well: if you have less ports, you want to schedule dependent instructions on the critical path as early as possible, even if other independent (but not latency-critical) instructions could be scheduled earlier, incurring extra stop bits. So while some degree of performance-portability is designed into the hardware, the compiler may have a hard time generating code that is scheduled well on both 3 port and possible future 6 port machines.
This reminds me of macro-fusion, where there's a similar contradiction: macro fusion only triggers if the fusable instructions are issued back to back. But when optimising for a multi-issue-in-order design, you usually want to interleave dependency chains (i.e. not issue dependet instructions back to back) such that all the pipelines are kept busy. So unless the pairs that fuse are the same on all of them, it's very hard to generate code that performs well on a variety of microarchitectures.
As a quick recap, superscalar processors have multiple execution units, each of which can execute one instruction each cycle. So if you have three execution units, your CPU can execute up to three instructions every cycle. The conventional way to make use of the power of more than one execution unit is to have an out-of-order design, where a complicated mechanism (Tomasulo algorithm) decodes multiple instructions in parallel, tracks their dependencies and dispatches them onto execution units as they can be executed. Dependencies are resolved by having a large physical register file, which is dynamically mapped onto the programmer-visible logical register file (register renaming). This works well, but is notoriously complex to implement and requires a couple of extra pipeline stages before decode and execution, increasing the latency of mispredicted branches.
The idea of VLIW architectures was to improve on this idea by moving the decision which instruction to execute on which port to the compiler. The compiler, having prescient knowledge about what your code is going to do next, can compute the optimal assignment of instructions to execution units. Each instruction word is a pack of multiple instructions, one for each port, that are executed simultaneously (these words become very wide, hence VLIW for Very Long Instruction Word). In essence, all the bits of the out-of-order mechanism between decoding and execution ports can be done away with and the decoder is much simpler, too.
However, things fail in practice:
* the whole idea hinges on the compiler being able to figure out the correct instruction schedule ahead of time. While feasible for Intel's/HP's in house compiler team, the authors of other toolchains largely did not bother, instead opting for more conventional code generation that did not performed all too well.
* This issue was exacerbated by the Itanium's dreadful model for fast memory loads. You see, loads can take a long time to finish, especially if cache misses or page faults occur. To fix that, the Itanium has the option to do a speculative load, which may or may not succeed at a later point. So you can do a load from a dubious pointer, then check if the pointer is fine (e.g. is it in bounds? Is it a null pointer?), and only once it has been validated you make use of the result. This allows you to hide the latency of the load, significantly speeding up typical business logic. However, the load can still fail (e.g. due to to pagefault), in which case your code has to roll back to where the load should be performed and then do a conventional load as a back-up. Understandably, few, if any compilers ever made use of this feature and load latency was dealt with rather poorly.
* Relatedly, the latency of some instructions like loads and division is variable and cannot easily be predicted. So there usually isn't even the one perfect schedule the compiler could find. Turns out the schedule is much better when you leave it to the Tomasulo mechanism, which has accurate knowledge of the latency of already executing long-latency instructions.
* By design, VLIW instruction sets encode a lot about how the execution units work in the instruction format. For example, Itanium is designed for a machine with three execution units and each instruction pack has up to three instructions, one for each of them. But what if you want to put more execution units into the CPU in a future iteration of the design? Well, it's not straightforward. One approach is to ship executables in a bytecode, which is only scheduled and encoded on the machine it is installed on, allowed the instruction encoding and thus number of ports to vary. Intel had chosen a different approach and instead implemented later Itanium CPUs as out-of-order designs, combining the worst of both worlds.
* Due to not having register renaming, VLIW architectures conventionally have a large register file (128 registers in the case of the Itanium). This slows down context switches, further reducing performance. Out-of-order CPUs can cheat by having a comparably small programmer-visible state, with most of the state hidden in the bowels of the processor and consequently not in need of saving or restoring.
* Branch prediction rapidly grew more and more accurate shortly after the Itanium's release, reducing the importance of fast recovery from mispredictions. These days, branch prediction is up to 99% accurate and out-of-order CPUs can evaluate multiple branches per cycle using speculative execution. A feature, that is not possible with a straightforward VLIW design due to the lack of register renaming. So Intel locked itself out of one of the most crucial strategies for better performance with this approach.
* Another enginering issue was that x86 simulation on the Itanium performed quite poorly, giving existing customers no incentive to switch. And those that did decide to switch found that if they invest into porting their software, they might as well make it fully portable and be independent of the architecture. This is the same problem that led to the death of DEC: by forcing their customers to rewrite all the VAX software for the Alpha, the created a bunch of customers that were no longer locked into their ecosystem and could now buy whatever UNIX box was cheapest on the free market.
Other pools have the ropes always installed.