3 ms·
Re: "fast" parity code in article. I always preferred the parity example from the (pre-ansi) K&R C Programming Language book: #include <stdio.h> main( argc,
by anonymousiam 6y ago
Re: "fast" parity code in article. I always preferred the parity example from the (pre-ansi) K&R C Programming Language book:
#include <stdio.h>
main( argc, argv )
int argc;
char *argv[];
{
unsigned source;
int parity;
if ( argc > 1 )
{
if ( sscanf( argv[1], "%d", &source ) == 1 )
{
printf( "%d = ", source );
for ( parity = 0; source; parity++ )
source &= ( source - 1 );
printf( "%d\n", parity & 1 );
}
}
}
The function in the article is faster for > 8-bit values when there are more than eight ones in the value being checked. Also, I suppose theirs is better than K&R because it always executes in the same number of cycles.
- juxhindb 6y agoThanks for sharing that, love the simplicity behind it which is more intuitive than the example I had gone with. I think the reason why I chose that particular one was to show how thinking about a problem from an entirely different angle can yield great (and rewarding) results.
- saagarjha 6y agoIdeally, you'd want your compiler to use the hardware population count instructions though. So this might be one of the places where a simpler algorithm might win out because the compiler can recognize it.
- juxhindb 6y agoIn fact that is one of the follow-ups I want to have out of this. Have architecture-specific optimisations (popcnt on x86) either manually through something like the `asm` crate, or by having a simpler algorithm that the compiler can optimise away.
- juxhindb 6y agoAn extension to this infact is the following - https://github.com/llvm-mirror/llvm/blob/f36485f7ac2a8d72ad0e0f2134c17fd365272285/lib/Transforms/Scalar/LoopIdiomRecognize.cpp#L960 https://github.com/llvm-mirror/llvm/blob/f36485f7ac2a8d72ad0... So the original user's comment might infact get detected by this and get optimised down to using popcnt. Will need to try it out. :-)