Oberon Community Platform Forum

Development => Bug Report => Topic started by: Alexey on January 19, 2009, 11:13:18 AM



Title: HUGEINT division bug
Post by: Alexey on January 19, 2009, 11:13:18 AM
Hi!

when I try to compute c := a DIV b; where all a,b,c are HUGEINT I get a TRAP which is in the enclosure. I used the latest WinAos release.

Best regards,

Alexey


Title: Re: HUGEINT division bug
Post by: negelef on January 19, 2009, 12:01:49 PM
The compiler doesn't really support hugeint multiplication and division. Use Machine.MulH and Machine.DivH for the time being.


Title: Re: HUGEINT division bug
Post by: Alexey on January 19, 2009, 12:06:19 PM
Thanks,

Alexey


Title: Re: HUGEINT division bug
Post by: Alexey on January 19, 2009, 06:32:31 PM
Anyway there is a problem...

when I tried to compute:

a := 0CD1F42EFH;
b := Machine.DivH(a,60);
c := Machine.MulH(b,60);

I get c = CD1F430C which is bigger than a. It looks like Machine.DivH instead of truncation of LONGREAL FPU result does rounding, because
0CD1F42EFH/60 = 57356300.516.

Regards,

Alexey


Title: Re: HUGEINT division bug
Post by: Alexey on January 26, 2009, 09:44:08 AM
Hello,

here is an implementation of HUGEINT multiplication and division for x86 systems based on the code from "AMD Athlon processor x86 Code Optimization Guide". On my Intel PCs it runs 2.4 times faster that current implementation based on the use of FPU, and it gives correct results. FPU based MulH and DivH are very dangerous to use because mantissa in double precision has only 52 bits length, thus for the cases when the result of multiplication or dividend in division require more than 52 bits for their integer representation, you can have an incorrect (rounded) result.

Best regards,

Alexey


Title: Re: HUGEINT division bug
Post by: negelef on January 26, 2009, 10:58:44 AM
Thanks for the implementation and its evaluation. We will replace the FPU version, but is there a reason why your procedures are marked as inline? What's the performance impact of the alternative non-inlined version? As these procedures contain quite a few instructions, their inlined versions could cause some significant code bloat, couldn't they?


Title: Re: HUGEINT division bug
Post by: Alexey on January 26, 2009, 01:43:25 PM
Hi negelef,

I made the procedures inline because Machine.MulH/DivH are inline. In addition I do not know how to access LO/HI of HUGEINT input arguments in non-inline procedures.

Alexey


Title: Re: HUGEINT division bug
Post by: negelef on January 26, 2009, 01:53:29 PM
Non-inlined procedures written in assembly are called like ordinary procedures. Therefore the CALL instruction on the caller site and the RET instruction on the callee site take over the stack management. Additionally, as the call implicitly creates a new stack frame, the parameters have to be access via the frame base pointer. See e.g. Machine.Fill32 hot to accomplish that.

In inlined versions, programmers have to fake a procedure call by manipulating the stack pointers themselves as there actually is no procedure call at all because its replaced by the assembly code. And since there is no new stack frame, parameters have to be accessed via the stack pointer.


Title: Re: HUGEINT division bug
Post by: Alexey on January 26, 2009, 03:42:59 PM
Hi,

here are non-inline assembler procedures. Tests showed decrease of performance by 22% for multiplication and 14% for division, which is not so bad.

Best regards,

Alexey


Title: Re: HUGEINT division bug
Post by: negelef on January 26, 2009, 04:18:38 PM
Decrease of performance with respect to what? It would be most interesting to see the code used for the benchmarks.


Title: Re: HUGEINT division bug
Post by: Alexey on January 26, 2009, 05:01:58 PM
In respect to the performance of inline-procedures. See enclosed test module.

Here are the results for my Intel Quad Q9400 2.6GHz (WinAos)

Machine.MulH:
1560 ms
Hex(HI)=1EABE4BD
Hex(LO)=D7631400

HugeintMulDiv.Mul:
639 ms
Hex(HI)=1EABE4BD
Hex(LO)=D7631388

HugeintMulDiv.Mul1:
796 ms
Hex(HI)=1EABE4BD
Hex(LO)=D7631388

Machine.DivH:
2153 ms
Hex(HI)=00000000
Hex(LO)=0000002C

HugeintMulDiv.Div:
1591 ms
Hex(HI)=00000000
Hex(LO)=0000002B

HugeintMulDiv.Div1:
1841 ms
Hex(HI)=00000000
Hex(LO)=0000002B

Alexey


Title: Re: HUGEINT division bug
Post by: Alexey on January 26, 2009, 10:52:55 PM
Hi!

This is modified test module for testing all branches of the Mul/Div code.

Alexey


Title: Re: HUGEINT division bug
Post by: negelef on January 27, 2009, 01:18:41 PM
I just tried to replace the existing version with yours but unfortunately, the system gets quite unstable. It looks like there is a stack problem. At least with the windows version.


Title: Re: HUGEINT division bug
Post by: BohdanT on January 27, 2009, 02:28:07 PM
Quote
It looks like there is a stack problem.

Code:
S.GETREG(S.ESP, spreg);
Log.String("SP= "); Log.Hex(spreg, 0); Log.Ln;
   
I added before and after each FOR-cycle.
ESP - does not change
 ???


Title: Re: HUGEINT division bug
Post by: negelef on January 27, 2009, 03:11:32 PM
The stack problem was actually my fault, sorry about that. The non-inlined code now works and is available starting from revision 1897. Thank you very much for the contribution!


Title: Re: HUGEINT division bug
Post by: BohdanT on January 27, 2009, 03:19:56 PM
The following modules are used Machine.DivH, IMHO it is necessary to verify of their work.  ???

Quote
I386.BenchInterrupts.Mod    WMPartitions.Mod
WMObjectTracker.Mod         WMPerfMonPluginMemory.Mod
AMD64.Processors.Mod        DiskTests.Mod
Unix.WMPerfMonPlugins.Mod   WMPerfMonPlugins.Mod
OGGUtilities.Mod            OGGVorbisPlayer.Mod


Title: Re: HUGEINT division bug
Post by: negelef on January 27, 2009, 03:55:51 PM
Alexey thankfully corrected the previous implementations and also verified their correctness. I don't think we have to additionally verify the modules you mentioned as long as they do not explicitly depend on the erroneous behaviour of the FPU versions. And this is hardly the case, as Alexey was actually the first to observe that they produce wrong results.