562653 - modulo op (%) is slow

Status: RESOLVED WONTFIX

(Tamarin Graveyard :: Baseline JIT (CodegenLIR), defect, P3)

Description

[Felix S. Klock II [:pnkfelix, :fklock]]

From the lego mailing list: 
"Quick question for the player engineers: Any ideas why the performance of the modulus operator is so poor? For example:

a = i%5;
b = i-(i/5|0)*5;
// b is about 50% faster"

Comment 1

[Steven Johnson]

Perhaps because the modulo call generates a function call (with associated overhead) vs inlined SSE2 instructions for the latter?

Comment 2

[Edwin Smith]

Plenty of room for specialization of % (nonzero-int rhs, in this case for example)

Comment 3

[Werner Sharp]

Attachment: Add integer specialized mod call, tweak Win32 mod routine

Added code in Specializer to handle int(fmod(double(a), double(b)) where a and b are integers.  Integer modulo is over 10x faster than FP.  Tweaked MathUtils::mod so it does not have to call modInternal.  About 10% faster.  Also added constant folding to Specializer code...my first experiments to get in there were constant folding away a subtract operation but still leaving the int->double->int roundtrip.

Further support would be to inline mod routine directly:  if (b = 0) result=0 else load a, cdq, idiv b, get mod result from x86 register directly.

Comment 4

[Lars T Hansen]

This is cool, but I'm not sure C++ '%' always (ie on all platforms and compilers) has the same semantics as ActionScript '%'.  That needs investigation.  Specifically, the C++ spec says that if either operand is negative then the sign of the remainder is implementation-defined (C++ 1998 5.6 subsection 4).  In ECMAScript, "the sign of the result equals the sign of the dividend" (ES5 11.5.3).  The ES5 spec also makes the point that the semantics of remainder are those of fmod() in the C library, and of Java.  If we've been using fmod() for % up until now then ActionScript probably has those semantics in fact, as well.

I think the C++ rule comes from C.  I don't have a copy of the C rationale but I believe the rule is what it is to cater to different behavior on different CPUs.  The compiler also figures into it; SPARC has a divide operation that does not provide the remainder, for example.  x86 follows the ES spec.

Comment 5

[Werner Sharp]

What is the process for verifying results on all supported platforms?

1. Get QE (or myself) to write a test case for negative mod values?
2. Run a buildbot verifying correct results on all platforms?
3. Add the change to a user depot?
4. Run buildbot on my user depot?

Simple test with x86 result with and without changelist applied:

function modTest(a:int,b:int)
{
	var c:int = a % b;
	trace(a + " % " + b + " = " + c);
}
modTest(-12,-5); // -2
modTest(12,-5); // 2
modTest(-12,5); // -2
modTest(12,5); // 2
modTest(-10,3); // -1
modTest(10,3); // 1
modTest(10,-3) // 1
modTest(-10,-3) // -1

Comment 6

[Edwin Smith]

(In reply to comment #5)
> What is the process for verifying results on all supported platforms?
> 
> 1. Get QE (or myself) to write a test case for negative mod values?
> 2. Run a buildbot verifying correct results on all platforms?
> 3. Add the change to a user depot?
> 4. Run buildbot on my user depot?

basically, yes.  If you review the test suite and find that all the necessary tests are already done, then super.  but odds are they won't be and its probably more expedient to write them.

While you're at it, consider adding tests with fractions on the lhs and rhs.

> 
> Simple test with x86 result with and without changelist applied:
> 
> function modTest(a:int,b:int)
> {
>     var c:int = a % b;
>     trace(a + " % " + b + " = " + c);
> }
> modTest(-12,-5); // -2
> modTest(12,-5); // 2
> modTest(-12,5); // -2
> modTest(12,5); // 2
> modTest(-10,3); // -1
> modTest(10,3); // 1
> modTest(10,-3) // 1
> modTest(-10,-3) // -1

Comment 7

[Edwin Smith]

Comment on attachment 449319 [details] [diff] [review]
Add integer specialized mod call, tweak Win32 mod routine

Switching primary reviewer to Bill since he's working on similar optimizations for other operators.  Steven - feedback/review welcome of course.

Comment 8

[Steven Johnson]

Patch uses naked "int" types for the new function, rather than C99 types; new code should always use C99 types unless there's a compelling reason otherwise.

Comment 9

[Edwin Smith]

Comment on attachment 449319 [details] [diff] [review]
Add integer specialized mod call, tweak Win32 mod routine

cancelling my SR until cross-platform issues of C++ % are addressed.

Comment 10

[Werner Sharp]

Lars/Ed, I'd like to push this patch to my sandbox and run the tryserver on all platforms to version cross-platform C++ issues.  Do you have any specific integer mod tests should I test besides the following?

> function modTest(a:int,b:int)
> {
>     var c:int = a % b;
>     trace(a + " % " + b + " = " + c);
> }
> modTest(-12,-5); // -2
> modTest(12,-5); // 2
> modTest(-12,5); // -2
> modTest(12,5); // 2
> modTest(-10,3); // -1
> modTest(10,3); // 1
> modTest(10,-3) // 1
> modTest(-10,-3) // -1

Comment 11

[Lars T Hansen]

It's always good to toss in maximal and minimal int values, and zeroes just to make sure they work (they need to) - both with and without an explicit type annotation on 'c'.  And test uint in addition to int, perhaps.

Comment 12

[Werner Sharp]

Attachment: updated patch including inlining mod on x86

Interestingly, inlining the modi(div(a,b)) call for x86 is no faster than calling out to a helper function to perform the same thing.  NJ is not quite as efficient because of the two sti() calls which write the intermediate result from a register to memory.

FASTCALL is also no faster because it puts the registers in the wrong location for the x86 DIV instruction.

Calling int helper is still 3x faster than float variant.

Comment 13

[William Maddox]

(In reply to comment #12)

R-, mostly because the patch is seriously stale.

> Interestingly, inlining the modi(div(a,b)) call for x86 is no faster than
> calling out to a helper function to perform the same thing. 

This is a bit surprising, as the arguments have to go to memory for the helper, but perhaps we're seeing x86 microarchitectural trickery.

In any case, we should remove the code in the '#if 0' branch if not useful.

The patch will not apply against the current TR due to significant reorganization of the specialization code, including some changes made to keep specialization from breaking CSE.  In the new design, it is awkward to specialize on both arguments and results simultaneously.  Instead, we should specialize on the integer arguments in inlineBuiltinFunctions(), producing a double result, and then specialize the resulting call on the integer result in coerceNumberToInt().  This may be improve peformance as well in cases where a Number result is needed, as doing an integer modulo and then converting the result to double gives the correct answer in this case.

A comment is in order in MathUtils::modInteger() explaining the result of zero when the divisor is zero.  The reason is that the specialization is taking place in a context where the result is coerced to int, hence the actual modulus result NaN is coerced to zero.

Comment 14

[Sylvestre Ledru [:Sylvestre]]

Tamarin is a dead project now. Mass WONTFIX.

Comment 15

[Sylvestre Ledru [:Sylvestre]]

Tamarin isn't maintained anymore. WONTFIX remaining bugs.