Welcome! Log In Create A New Profile

Advanced

[PHP-DEV] Re: cvs: php-src(PHP_5_3) /ext/standard math.c

Posted by Christian Seiler 
Christian Seiler
[PHP-DEV] Re: cvs: php-src(PHP_5_3) /ext/standard math.c
October 30, 2008 11:00AM
Hi,

> Modified files: (Branch: PHP_5_3)
> /php-src/ext/standard math.c
> Log:
> Fixed bug #42294 (Unified solution for round() based on C99 round)
> [DOC] New implementation of round() to work-around inconsistencies for win32
> and 64 bit platforms.
>
> This solution is very roughly based on BSD's implmentation of round(), which
> itself is an implementation of C99 standard. We take the absolute value of number
> we want to round time the 10 to the power of the number of decimal spaces we are
> rounding to. The resulting value is rounded up and the pre-rounded value is
> subtracted from it. If the difference is greater then 0.5000000001 we round up,
> otherwise we round down.

Apparently, nobody reads internals anymore. :-(

I made my initial comment on the bug report over a year ago. Since then
I've dug quite a bit into floating point arithmetics and the actual
problems behind round(). This lead to:

http://wiki.php.net/rfc/rounding

Which I posted quite a while ago and nearly nobody was interested:

http://news.php.net/php.internals/40070

[Now please don't simply apply the patch there, I've done some
additional research since.]

The solution I proposed over a year ago is actually wrong and it does
not solve all the problems of round()'s g, see my RFC for that.

The general problems with round are actually:

1) Internal FPU precision on x86.
2) Specification problem (which rounding mode should actually be used?)
3) Dividing/multiplying by >= 10^23 is not exact.
4) round (1.255, 2) should give 1.26 but gives 1.25. The FUZZ stuff
tries to resolve this issue (but not the other three) but I've
come to the conclusion that the FUZZ is actually the wrong solution
for the problem.

Since I didn't get any reaction on the RFC on internals, I pinged Lukas
and Johannes (as they are RMs for PHP 5.3) in private in order to ask
whether it was possible to include my proposal in 5.3 (I don't have ZE2
Karma and my patch also needs to change zend_strtod).

Lukas and Johannes were concerned about the interopability of my
solution of problem (1). So I did some tests on different platforms and
operating systems and Lukas and Johannes asked around for other people
to do tests, too. I've summarized results of these tests and proposed
solution for correct cross-platform floating point arithmetics here:

http://www.christian-seiler.de/projekte/fpmath/

I've mailed patches for PHP 5.3 and HEAD to Johannes and Lukas for
ZendEngine2 that only address the above issue (1) and do the following:

1) Define some macros for math-related functions that will ensure the
function itself always uses double precision. Add configure checks for
these macros.

2) Modified zend_strtod and the add/sub/div/mul functions in
zend_operators.c to make use of those macros. This ensures that PHP will
always use double precision for calculations and math is thus portable.

3) Added a test that determines if the calculations precision is
actually correct.

The patches for 5.3 and HEAD are found here:

http://www.christian-seiler.de/temp/php/2008-10-28-fpu/php-float-precision-5.3.patch
http://www.christian-seiler.de/temp/php/2008-10-28-fpu/php-float-precision-6.patch

My next step (as discussed with Johannes and Lukas) would have been to
apply the Non-ZE2-part of my patch to ext/standard/math.c in 5.3 and
HEAD (I don't have separate patches for that yet but they are quite
trivial to adapt to the new macros).

Now the question is: Where do we go from here? Your commit does not
solve all the problems of PHP's round but is at least better than the
previous implementation since at least the platform-dependency on
whether or not to use the FUZZ is removed. The other problems, however,
remain.

Christian

--
PHP Internals - PHP Runtime Development Mailing List
To unsubscribe, visit: http://www.php.net/unsub.php
Marcus Boerger
Re: [PHP-DEV] Re: cvs: php-src(PHP_5_3) /ext/standard math.c
October 30, 2008 01:20PM
Hello Christian,

Thursday, October 30, 2008, 10:55:48 AM, you wrote:

> Hi,

>> Modified files: (Branch: PHP_5_3)
>> /php-src/ext/standard math.c
>> Log:
>> Fixed bug #42294 (Unified solution for round() based on C99 round)
>> [DOC] New implementation of round() to work-around inconsistencies for win32
>> and 64 bit platforms.
>>
>> This solution is very roughly based on BSD's implmentation of round(), which
>> itself is an implementation of C99 standard. We take the absolute value of number
>> we want to round time the 10 to the power of the number of decimal spaces we are
>> rounding to. The resulting value is rounded up and the pre-rounded value is
>> subtracted from it. If the difference is greater then 0.5000000001 we round up,
>> otherwise we round down.

> Apparently, nobody reads internals anymore. :-(

> I made my initial comment on the bug report over a year ago. Since then
> I've dug quite a bit into floating point arithmetics and the actual
> problems behind round(). This lead to:

> http://wiki.php.net/rfc/rounding

> Which I posted quite a while ago and nearly nobody was interested:

> http://news.php.net/php.internals/40070

> [Now please don't simply apply the patch there, I've done some
> additional research since.]

> The solution I proposed over a year ago is actually wrong and it does
> not solve all the problems of round()'s g, see my RFC for that.

> The general problems with round are actually:

> 1) Internal FPU precision on x86.
> 2) Specification problem (which rounding mode should actually be used?)
> 3) Dividing/multiplying by >= 10^23 is not exact.
> 4) round (1.255, 2) should give 1.26 but gives 1.25. The FUZZ stuff
> tries to resolve this issue (but not the other three) but I've
> come to the conclusion that the FUZZ is actually the wrong solution
> for the problem.

> Since I didn't get any reaction on the RFC on internals, I pinged Lukas
> and Johannes (as they are RMs for PHP 5.3) in private in order to ask
> whether it was possible to include my proposal in 5.3 (I don't have ZE2
> Karma and my patch also needs to change zend_strtod).

> Lukas and Johannes were concerned about the interopability of my
> solution of problem (1). So I did some tests on different platforms and
> operating systems and Lukas and Johannes asked around for other people
> to do tests, too. I've summarized results of these tests and proposed
> solution for correct cross-platform floating point arithmetics here:

> http://www.christian-seiler.de/projekte/fpmath/

> I've mailed patches for PHP 5.3 and HEAD to Johannes and Lukas for
> ZendEngine2 that only address the above issue (1) and do the following:

> 1) Define some macros for math-related functions that will ensure the
> function itself always uses double precision. Add configure checks for
> these macros.

> 2) Modified zend_strtod and the add/sub/div/mul functions in
> zend_operators.c to make use of those macros. This ensures that PHP will
> always use double precision for calculations and math is thus portable.

> 3) Added a test that determines if the calculations precision is
> actually correct.

> The patches for 5.3 and HEAD are found here:

> http://www.christian-seiler.de/temp/php/2008-10-28-fpu/php-float-precision-5.3.patch
> http://www.christian-seiler.de/temp/php/2008-10-28-fpu/php-float-precision-6.patch

> My next step (as discussed with Johannes and Lukas) would have been to
> apply the Non-ZE2-part of my patch to ext/standard/math.c in 5.3 and
> HEAD (I don't have separate patches for that yet but they are quite
> trivial to adapt to the new macros).

> Now the question is: Where do we go from here? Your commit does not
> solve all the problems of PHP's round but is at least better than the
> previous implementation since at least the platform-dependency on
> whether or not to use the FUZZ is removed. The other problems, however,
> remain.

Imo you should still go ahead with 5.3 and HEAD, ignoring the issue on 5.2.
It is pretty sad that your patch is necessary, but lets face reality, it is
necessary. The only thing I am wondering about is whether the configure
time resolution is a good idea. People will still switch processors,
wouldn't that break the whole idea? Not that it would ever affect me or
most developers. But users who typically install rpms might get affected.


Best regards,
Marcus


--
PHP Internals - PHP Runtime Development Mailing List
To unsubscribe, visit: http://www.php.net/unsub.php
Ilia Alshanetsky
[PHP-DEV] Re: cvs: php-src(PHP_5_3) /ext/standard math.c
October 30, 2008 02:05PM
On 30-Oct-08, at 5:55 AM, Christian Seiler wrote:
> 1) Internal FPU precision on x86.

Do you have any test cases show the error?

>
> 2) Specification problem (which rounding mode should actually be
> used?)
> 3) Dividing/multiplying by >= 10^23 is not exact.
> 4) round (1.255, 2) should give 1.26 but gives 1.25. The FUZZ stuff
> tries to resolve this issue (but not the other three) but I've
> come to the conclusion that the FUZZ is actually the wrong solution
> for the problem.

The current implementation does return 1.26

The proposed solution seems fairly complex and wide-reaching to me, I
am also concerned with the overheads it introduces as that was a
problem with many in-C implementation libc folks have tried and
rejected.

> Since I didn't get any reaction on the RFC on internals, I pinged
> Lukas
> and Johannes (as they are RMs for PHP 5.3) in private in order to ask
> whether it was possible to include my proposal in 5.3 (I don't have
> ZE2
> Karma and my patch also needs to change zend_strtod).
>
> Lukas and Johannes were concerned about the interopability of my
> solution of problem (1). So I did some tests on different platforms
> and
> operating systems and Lukas and Johannes asked around for other people
> to do tests, too. I've summarized results of these tests and proposed
> solution for correct cross-platform floating point arithmetics here:
>
> http://www.christian-seiler.de/projekte/fpmath/
>
> I've mailed patches for PHP 5.3 and HEAD to Johannes and Lukas for
> ZendEngine2 that only address the above issue (1) and do the
> following:
>
> 1) Define some macros for math-related functions that will ensure the
> function itself always uses double precision. Add configure checks for
> these macros.
>
> 2) Modified zend_strtod and the add/sub/div/mul functions in
> zend_operators.c to make use of those macros. This ensures that PHP
> will
> always use double precision for calculations and math is thus
> portable.
>
> 3) Added a test that determines if the calculations precision is
> actually correct.
>
> The patches for 5.3 and HEAD are found here:
>
> http://www.christian-seiler.de/temp/php/2008-10-28-fpu/php-float-precision-5.3.patch
> http://www.christian-seiler.de/temp/php/2008-10-28-fpu/php-float-precision-6.patch
>
> My next step (as discussed with Johannes and Lukas) would have been to
> apply the Non-ZE2-part of my patch to ext/standard/math.c in 5.3 and
> HEAD (I don't have separate patches for that yet but they are quite
> trivial to adapt to the new macros).
>
> Now the question is: Where do we go from here? Your commit does not
> solve all the problems of PHP's round but is at least better than the
> previous implementation since at least the platform-dependency on
> whether or not to use the FUZZ is removed. The other problems,
> however,
> remain.
>
> Christian

Ilia Alshanetsky





--
PHP Internals - PHP Runtime Development Mailing List
To unsubscribe, visit: http://www.php.net/unsub.php
Christian Seiler
Re: [PHP-DEV] Re: cvs: php-src(PHP_5_3) /ext/standard math.c
October 30, 2008 04:00PM
Hi Stefan,

>> 1) Define some macros for math-related functions that will ensure the
>> function itself always uses double precision. Add configure checks for
>> these macros.
>
> Do you know what the rationale behind the standard compiler behaviour is?
> Because trying to outsmart the compiler is usually not a good idea.

The only time when I try to outsmart the compiler is the "volatile
return variable" trick - and volatile guarantees according to the C
standard the intended behaviour.

The main use of these macros is to correctly set a processor flag to a
certain value (either via other macros defined in system C headers or by
functions provided by the runtime of the OS - and as a fallback inline
assembly [1] if nothing of the above works). I don't actually want to
outsmart the compiler (the volatile trick is only necessary because some
GCC versions optimize at the wrong time) but simply make sure the FPU
environment is in a specifically defined state. Compilers typically
don't care about the FPU environment itself.

Anyway, I've spent quite a lot of time documenting different compiler
behaviours (with and without optimization) and I am extremely sure that
there are no more surprises on x86 platforms. (on other platforms, the
macros expand to /* NOP */ anyway)

If you want to take a look at my documentation, see:

http://www.christian-seiler.de/projekte/fpmath/

I believe I have been thorough enough in my research.

[1] Which is simple enough and glibc on Linux basically does the same
(just with a more generic approach). Also, I tested the inline assembly
with GCC and Sun's CC on OpenSolaris and GCC and Intel's CC on Linux and
those worked as expected.

Also, PHP already uses inline assembly for certain tasks - just look at
the ZEND_SIGNED_MULTIPLY_LONG definition in zend_multiply.h.

Finally, my configure checks test if inline assembly actually works (not
only if it compiles but actually does the expected).

Regards,
Christian



--
PHP Internals - PHP Runtime Development Mailing List
To unsubscribe, visit: http://www.php.net/unsub.php
Christian Seiler
Re: [PHP-DEV] Re: cvs: php-src(PHP_5_3) /ext/standard math.c
October 30, 2008 04:50PM
Hi,

[For conclusive proposal, see below.]

>> 1) Internal FPU precision on x86.
>
> Do you have any test cases show the error?

Sure. Consider the following C code:

#include <stdio.h>
int main (int argc, char **argv) {
volatile double v = 1000000.0;
printf ("%.35f\n%.35f\n", 0.002877, 2877.0 / v);
return 0;
}

According to the C standard, both values should give
0.00287699999..something (the closest double representation of 0.002877).

On most x86 platforms without SSE, the above code will give:

0.00287699999999999978320119886632256
0.00287700000000000021688206786052433

The first is the closest double representation of 0.002877, the second
is the closest double-extended representation of 0.002877 trucated back
to double.

Current PHP (5.2.6) gives me (on my Linux platform):

php -r 'printf ("%.35f\n%.35f\n", 0.002877, 2877.0 / 1000000.0);'
0.00287700000000000021688206786052433
0.00287700000000000021688206786052433

This is due to the fact that PHP has an own implementation of strtod() -
which uses double-extended instead of double for the entire internal
calculation and just returns a double.

PHP 5.2.6 on Windows on the other hand gives me the correct double
representation (because MSVC/Windows always sets the FPU into double
precision mode anyway).

PHP on x86_64 or PHP on x86 Macs (where the compiler defaults to SSE) or
PHP on PPC or Sparc etc. also have the correct double representation.

Thus, FP semantics of PHP are highly platform and (!) compiler
dependent. Worse, since PHP only exposes the double data type, the
internal precision of x87 FPUs can never actually be profited from in
PHP itself - consider $a * $b / $c. This will first calculate $a * $b
(with double-extended precision), truncate that to double and store it
in a temp var. Then it will calculate temp var / $c (double-extended)
and truncate that. So the extra precision is never actually used within
PHP and programmers can never actually take advantage of it (unlike in C
where the variables remain in FPU registers by default [2]).

On the other hand, having the above situation where the division of two
exactly representable (!) FP numbers does not yield the closest FP
representation of the actual result is problematic in my eyes.

[1] http://www.wrcad.com/linux_numerics.txt
[2] And even that is problematic in C, since for example before function
calls, FPU registers are stored back to memory and loaded again after
the function call returns, so one can't even be sure when extended
precision is used and when not.

>> 4) round (1.255, 2) should give 1.26 but gives 1.25. The FUZZ stuff
>> tries to resolve this issue (but not the other three) but I've
>> come to the conclusion that the FUZZ is actually the wrong solution
>> for the problem.
>
> The current implementation does return 1.26

Errr, yes, of course. Wrong grammar. I meant »gave 1.25« on certain
platforms. Your solution works for the cases discussed here and is
certainly much better than the previous code.

But it doesn't always work: Take 32769.255 for example. The FUZZ version
gives 32769.25 where 32769.26 would be expected behaviour (previous PHP
versions were of course never better).

> The proposed solution seems fairly complex and wide-reaching to me, I am
> also concerned with the overheads it introduces as that was a problem
> with many in-C implementation libc folks have tried and rejected.

The libc folks didn't have that many problems. C's round() function
doesn't accept a precision parameter, thus *always* rounds to integer.

This means, if you have a look at my previous points:

1) Internal FPU precision
2) Spec problem (rounding mode)
3) Dividing/multiplying by >= 10^23 inexact
4) round(1.255, 2)

1, 3 and 4 immediately disappear because they ONLY applie if you
actually have a precision parameter (FPU precision is irrelevant for
rounding to integer - if the original number with integer and fraction
part could be represented, the integer part alone can also be
represented - and no division / multiplication is necessary for integer
rounding, so 3 is irrelevant. Since there's no precision parameter,
rounding 1.255 to two places with C's round is irrelevant anyway).

2 also disappears since the C 99 standard defines round() to behave like
arithmetic rounding (round-to-nearest, round-half-up).

On the other hand, PHP has this precision parameter. We can't just drop
it. The best thing would probably have been to never add it but we are
about 8 years or so late for that. So we have to live with it.

My proposal adresses all the four problems. 1 is addressed by the FPU
precision macros (my two patches for ZE2 alone), 3 and 4 are also
addressed (and my implementation correctly handles the above example I
provided) - for implementation details see my RFC.

2 is addressed by the mere fact that I add a third optional parameter to
round() that specifies the rounding mode. Thus the user of the round
function can decide if he/she wants arithmetic or banker's rounding (and
for completeness I've added two others).

As for performance, I've already done some tests. With compiler
optimization, my implemetation is about 14% slower than the previous
implementation for the VAST majority of the use cases. This is certainly
a speed setback but on my laptop (Pentium M 2 GHz) I can still achieve
nearly 1.4 million rounding operations per second with PHP (previously
neraly 1.6 million). I don't really see a problem with this slowdown.

For special cases where somebody wants to round to 23 or 24 digits
precision (i.e. forcing to-string-and-back conversion in the proposed
algorithm), my algorithm is actually about 5 times slower. But I
honestly believe that somebody who writes round ($num, 30) is by far
more interested in results as exact as possible than execution speed.

----------------------------- snip ------------------------------------

Anyway, could we agree that we use your implementation for PHP 5.2.7
(it's better than the current situation and although it isn't perfect it
doesn't change the entire logic in just a bugfix-only revision) and have
my proposal used for PHP >= 5.3?

Regards,
Christian

--
PHP Internals - PHP Runtime Development Mailing List
To unsubscribe, visit: http://www.php.net/unsub.php
Sorry, only registered users may post in this forum.

Click here to login