4 ms·
Of course if you are looking to see whether a lower-case letter is one of a set, you use a bitmap: bool isvowel(char c){ return (1<<c-'a')&0x104111; } Often
by ncmncm 6y ago
Of course if you are looking to see whether a lower-case letter is one of a set, you use a bitmap:
bool isvowel(char c){ return (1<<c-'a')&0x104111; }
Often O(1) is better than O(n) even for small n.
Often O(1) is better than O(1).
Modern compilers will turn
bool isvowel(char c){
switch(c){
case'a':case'e':case'i':case'o':case'u':
return true;
}
return false;
}
into sort-of the same code (after a range check).
https://godbolt.org/z/aMcdY6 https://godbolt.org/z/aMcdY6
Looking at the code actually produced, the compiler has noticed that all the vowels are even-numbered characters
(0,4,8,14,20), so combined the range check with a "rotate-right" so it can compress 0x104111 down to 0x495, and shift that right and check the low bit of the result instead of doing a "bt", or bit-test. It's anybody's guess why that is considered better; shifts are supposed to be constant-time; but checking the low bit is a byte-sized operation. So, maybe
bool isvowel(char c){ return (0x104111>>c-'a')&1; }
is better: https://godbolt.org/z/M784cK https://godbolt.org/z/M784cK
- fluffything 6y ago> So, maybe [...] is better You were one click away of using LLVM's Machine Code Analyzer (MCA) within godbolt to see why one of the two isvowel one-liners is objectively better than the other: https://godbolt.org/z/fGEv3c https://godbolt.org/z/fGEv3c This version: bool isvowel(char c){ return (0x104111>>c-'a')&1; } puts way more pressure on Port 2 on skylake, reducing the number of IPC that can be scheduled. The first version is therefore a bit better. ;)
- ncmncm 6y agoToday I learned six new things: - Clang thinks compressing 0x104111 to 0x495 is a good idea - Clang thinks 0x495>>((c-'a')>>1)&1 is better than 1<<c-'a'&0x104111 - LLVM has a machine code analyzer - Godbolt has a button to apply it - Clang is wrong about that - Gcc-9 and newer prefers to index into a jump table, instead of bitmasking. (!) Yet another reason to set up a periodic contribution to Godbolt.
- fluffything 6y agoWhile deprecated, intel has also an opensource machine code analyzer called IACA. It is also worth pointing out that these "analyzers" are just tools that simulate particular CPU architectures. Their models are just approximations and aren't perfect, so don't take them as a source of truth.
- hairtuq 6y agoSince the shift count is implicitly modulo 32, you don't even need the subtraction: bool isvowel(char c) { return (1u << (c&31)) & 0x208222; }
- ncmncm 6y agoThe result is unspecified, if you don't mask off the high bits. Some chips will do it implicitly, and give you the right answer anyway, unportably. This is why testing is not a substitute for correctness. Sometimes you get the right answer by accident. But it's good enough for code golf.