Calling hotshot coders: NFS code challenge

[xenon]

Speed improvement. Readable assembly code.
Still for Visual C++ compiler only. Please tell whether you have compilation problems.

   modulus      asm      C
   1048583      254     349
   2097169      266     365
   4194319      279     395
   8388617      293     401
  16777259      305     418
  33554467      318     436

[R.D. Silverman]

Originally Posted by xenon

Speed improvement. Readable assembly code.
Still for Visual C++ compiler only. Please tell whether you have compilation problems.

   modulus      asm      C
   1048583      254     349
   2097169      266     365
   4194319      279     395
   8388617      293     401
  16777259      305     418
  33554467      318     436

Query 1:

It appears that the routine assumes a __fastcall. Correct? And that
the inputs are already in registers ecx,edx.

If the calling code is: int __fastcall eegcd(a,modulus) will VC++
automatically put the arguments into ecx & edx?


Query 2:

Done_Ans_1 seems quite a bit away from the jump instruction. Would it
help to move it closer?

???

Also, how much time is saved by __fastcall as opposed to (say) __cdecl?

I prefer not to rely upon arguments being in spcific registers.
With yourOK, I would like to change this to:

int single_modinv(int a, int modulus)

{
_asm {
mov ecx, a
mov edx, modulus
... your code
etc.
}
}
The routine then no longer needs to save a copy of modulus in [esp-4].
The code after Done_mebx can replace

mov eax, [esp-4]

with

mov eax, modulus

and does not need to save modulus at [esp-4] at the top.

We can also eliminate all the push/pops etc.

[xenon]

You may do anything to my code.

Yes, that is fastcall calling convention, arguments are put by compiler into registers.
According to Agner, both Microsoft and GNU use the same registers (ecx and edx) for fastcall. Therefore, now you can use my code just like library. It should always work as long as the same compiler is used.

ebp, ebx, esi, edi must be preserved. So, that's the reason push and pops are there.

fastcall is faster than other calls which put arguments on stack, but I could be wrong here. Actually I used stdcall before this and then found information about fastcall.

For Done_Ans_1, you can experiment yourself if you have MASM32. I've tried moving codes around and find this to be fast. Maybe I missed some arrangement.

[xenon]

Got it run on Linux. I run the code on my other computer which is also a Pentium III. Now I see that maybe I don't know how to use Visual C++ to compile properly. This gcc can compile codes faster than VC++. Anyway, I tried both -O2 switch and -O3 switch on Linux. Nevertheless, hand-tuned code wins. Keep in mind that my assembly code is derived from akruppa's code.

   modulus    asm(O2)  C(O2)   asm(O3)  C(O3)
   1048583      260     320     258      279
   2097169      273     336     271      295
   4194319      287     351     284      310
   8388617      300     367     298      324
  16777259      313     383     311      339
  33554467      327     398     325      354

I was wrong about fastcall that uses registers ecx and edx. In VC++, it's true. But for gcc, the registers are eax, edx, ecx. I was thinking that it'll be easier to use the link method for asm-C interface. But now, I've learn gcc inline asm AT&T syntax. So I can do both method. Both linking method and inlining method requires rewriting every line of assembly code for peak performance. Actually, by using linking method, we can be a bit lazy and use a few mov at the beginning to get the input registers in the right position. So what do you choose? link or inline?

I assume we only need to take care Windows and Linux on x86, right?
For the file I attach, asm folder is meant for Windows (because I use MASM32 assembler, then convert using emxaout). xi2_gcc directory is meant for linux.

[Wacky]

Originally Posted by xenon

I assume we only need to take care Windows and Linux on x86, right?

It would certainly be nice to include FreeBSD, Slowlaris, and MacOS.

Is anything that you are doing particular to Linux (rather than gcc)?

modulus asm c
1048583 423 475
2097169 385 473
4194319 407 490
8388617 425 517
16777259 439 546
33554467 462 552

I did get a warning:

--------------------Configuration: inverse3 - Win32 Release--------------------
Compiling...
inverse3.cpp
C:\Documents and Settings\MyAcount\Desktop\xenon\xi_vc2\benchmark\inverse3.cpp(14) : warning C4101: 'temp' : unreferenced local variable
Linking...

inverse3.exe - 0 error(s), 1 warning(s)

[xenon]

Originally Posted by Wacky

It would certainly be nice to include FreeBSD, Slowlaris, and MacOS.

Is anything that you are doing particular to Linux (rather than gcc)?

No doing anything particular to Linux, but asm code is for x86 only.

Originally Posted by TTn

I did get a warning:

Yes, it is intended. I was too lazy to write #ifdef code there.

[Ken_g6]

Here's a theoretical (meaning I haven't tested it) fast LSB function. It does a binary search for the LSB! In theory you could do the same for the MSB (I think you'd just check if lowpart != 0, but that might be off by one). And the conditionals should produce CMOVs in the assembly.

int lsb(unsigned int n) {
	unsigned int lowpart;
	int lsb = 0;
	int bits;

	for(bits=sizeof(unsigned int)/2; bits != 0; bits >>= 1) {
		lowpart = (1<<bits)-1;
		lowpart = n & lowpart;
		n = (lowpart==0)?(n>>bits):n;
		lsb += (lowpart==0)?bits:0;
	}
	
}

I hope this helps.

[cjohnsto]

Here is a recursive version of LSB algorithm. I have tested it using a simple wrapper. It does not handle the input of 0 well (I consider this undefined). This may be better or worse than what you are currently doing for 32 bit numbers however it should scale to 64bit better.
I tried to make it easy to convert to ASM. Also mine probably requires more registers than yours.

Also maybe you can combine them to get both at once (if that helps you).

int LSB(unsigned int x)
{
	unsigned int a, b, c;
	
	a = x;
	b = 0;
	c = 16;
	do
	{
		a <<= c;
		if (a)
			b |= c;
		else
			a = x << b;
		c >>= 1;
	}	while (c);
	b = 31 - b;
	return b;
}

int MSB(unsigned int x)
{
	unsigned int a, b, c;
	
	a = x;
	b = 0;
	c = 16;
	do
	{
		a >>= c;
		if (a)
			b |= c;
		else
			a = x >> b;
		c >>= 1;
	}	while (c);
	return b;
}

[Ken_g6]

I knew I had a better MSB code lying around here somewhere. It turns out that my LSB algorithm is useless because only 1 in 2^n numbers has an LSB of n or greater. So this takes about twice as long as the naive method.

For MSB it's somewhat more useful, but there's another better method I found here. Pick any one of those methods for MSB.

For LSB, a similar table approach takes 1/4 the time of the naive approach. I couldn't get the compiler to inline my function, so I inlined it myself in my test:

	const char LsbTable256[] = 
	{
		0, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
		4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
		5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
		4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
		6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
		4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
		5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
		4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
		7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
		4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
		5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
		4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
		6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
		4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
		5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
		4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
	};

	unsigned int i, n, lsb1;
	for(i=1; i < 1000000000; ++i) {
		n = i;
		lsb1 = 0;
		while((n&0xFF) == 0) {
			n >>= 8;
			lsb1 += 8;
		}
		lsb1 |= LsbTable256[n];
	}

As in cjohnsto's code, passing 0 is undefined. I haven't actually checked that this table is correct, but I think it is.

If a table's too much for you, here's an intermediate LSB method that's about 70% faster than naive:

	unsigned int i, n, lsb1;
	for(i=1; i < 1000000000; ++i) {
		n = i;
		lsb1 = 0;
		while((n&3) == 0) {
			n >>= 2;
			lsb1 += 2;
		}
		lsb1 |= ((~n)&1);
	}

[Ken_g6]

Now that I look at that page again, there's another algorithm here that's about 15% faster than my table algorithm on my Athlon, and has no shifts so it's probably faster on P4. But it uses a modulus, so I don't know for sure whether it's better.