At 01:11 AM 4/28/2007 -0500, I wrote:
>At 06:37 AM 4/27/2007 -0500, William A. Rowe wrote:
>>nope - the proposed change is a bit more expensive. (magnitude % 10 in
>>any case being the unavoidably most expensive bit.)
[snip]
> /* Eat two digits at a time.
> while (magnitude > 9) {
> *(short *)--p = two_digit_lut[magnitude % 100];
> --p, magnitude /= 100;
> }
[snip]
Incidentally, I fixed up this loop (it should be "*(short *)(p -= 2)",
rather than splitting the subtraction like that, and the alignment
comparison should be inverted) and ran a little test, and apparently
Microsoft's compiler does not use an IDIV. Instead, it uses a bizarre
multiplication trick to obtain the values of "magnitude % 100" and
"magnitude / 100":
; magnitude in ecx
mov eax, 1374389535
imul ecx
sar edx, 5
mov eax, edx
shr eax, 31
add eax, edx ; eax is now equal to ecx / 100!
mov edx, eax
imul edx, 100
sub ecx, edx ; ecx is now equal to magnitude % 100
; (magnitude - 100 * (magnitude / 100))
Intuitively, I wouldn't expect this long sequence to be faster, but it must
be or they wouldn't emit it. (I guess I'm underestimating the cost of a
division significantly!) They apparently use it whenever they see both
"value % n" and "value / n" near to one another. Also note how in this
case, since it is in a loop where the LCV is overwritten, their register
allocator has no qualms about overwriting the original magnitude value in
ecx, since it already has (magnitude / 100) for the next loop in eax. I'm
not sure how the magic number 1374389535 is computed, but I'm sure it's not
rocket science once you know the trick.
If this is significantly faster than an IDIV or two, then other parts of
the loop become more significant.
Jonathan Gilbert
