3 ms·
This article is kind of fine overall but gets so many specifics wrong. I guess this is to be expected from someone just beginning to verse in assembly, but stil
by purplesyringa 2y ago
This article is kind of fine overall but gets so many specifics wrong. I guess this is to be expected from someone just beginning to verse in assembly, but still.
if '0' <= x && x <= '9' || 'a' <= x && x <= 'z' || 'A' <= x && x <= 'Z' {
...
}
Go is garbage, but GCC and LLVM compile this to branchless code. If the goal was to redo the book in Zig and Rust, perhaps it would've been a good idea to profile the implementations under Zig and Rust.
If you really want to optimize code like `a <= x && x <= b` by hand, you can rewrite it to `x - a <= b - a`, where the comparison is unsigned; GCC and LLVM do that for you. Next, you can optimize the case-insensitive check by masking out the case bit:
void f();
void test(char x) {
if ((unsigned char)(x - '0') < 10 || (unsigned char)((x & 0x5f) - 'A') < 26) {
f();
}
}
compiles to just
lea eax, [rdi - 48]
cmp al, 10
jb f
and dil, 95
add dil, -65
cmp dil, 25
jbe f
ret
This is still not as fast as a memory read, but IMO this should've been the first thing to try. However, a) GCC and LLVM can autovectorize this, whereas memory reads can't be (although I admit the resulting codegen makes me uneasy), b) you can go on and vectorize this by hand, parsing an identifier in just one iteration of a loop, which you can't do with a LUT. I might have made a bug, but something along the lines of
unsigned short test(__m128i x) {
return _mm_movemask_epi8(_mm_or_si128(
_mm_cmplt_epi8(_mm_sub_epi8(x, _mm_set1_epi8(0xb0)), _mm_set1_epi8(0x8a)),
_mm_cmplt_epi8(_mm_sub_epi8(_mm_and_si128(x, _mm_set1_epi8(0x5f)), _mm_set1_epi8(0xc1)), _mm_set1_epi8(0x9a))
));
}
should work. This has 5x more throughput than a LUT and should have better branch prediction characteristics, although it consumes 16 bytes at a time, slightly limiting the applications.
The section about bitvectors is fine.
x86 processors don't have 128-bit MMX registers and 256-bit MMY registers. They have legacy 64-bit MMX registers, modern 128-bit XMM registers, and modern 256-bit YMM registers. This MMX/XMM duality sure does confuse people, so I don't blame the author. But come on, at least read the article before publishing; broken GitHub URLs without `blob/master` and broken ()[] Markdown syntax is not funny.
To those trying to make sense of Zig output, don't forget `-O ReleaseFast`. The codegen here is very simple, just a 128-bit integer simulated with two 64-bit ones.
- jesse__ 2y agoExcellent nitpicks, hopefully the author reads this and does a follow up :)
- selimthegrim 2y agoHow good is Hacker’s Delight on this stuff?
- purplesyringa 2y agoThe main problem with Hacker's Delight is its age. It has lots of bit tricks and optimization guidelines you'll find useful, but you have to understand that a big part of it doesn't apply on modern devices. But as long as you treat it as a collection of snippets and benchmark the code on modern devices (or, if you have built some intuition, that works too), it's an invaluable resource.
- selimthegrim 2y agoThanks, I stumbled across a copy in a local coffee shop by happenstance that had been remaindered out of a University of Alaska library.
- boris-smidt 2y agoI'll have another try in Zig later on and indeed the XMM/MMX and MMY really is confusing, couldn't they just cal it V128, V256 and V512 ...