[Bug math/13932] New: x86_64 pow unexpectedly slow for some inputs

[Bug math/13932] New: x86_64 pow unexpectedly slow for some inputs

[ppluzhnikov at google dot com]

http://sourceware.org/bugzilla/show_bug.cgi?id=13932

             Bug #: 13932
           Summary: x86_64 pow unexpectedly slow for some inputs
           Product: glibc
           Version: unspecified
            Status: NEW
          Severity: normal
          Priority: P2
         Component: math
        AssignedTo: unassigned@sourceware.org
        ReportedBy: ppluzhnikov@google.com
    Classification: Unclassified


Created attachment 6310
  --> http://sourceware.org/bugzilla/attachment.cgi?id=6310
test case

Attached test case shows that pow is over 10,000 slower for some inputs
than for other (nearby) inputs.

This was first noticed with eglibc-2.11, and reproduced with current
git trunk.

Results:

32-bit build:

./elf/ld.so --library-path .:math:dlfcn ./a.out
pow(0.562500, 1.5): 13.644814 calls/usec
pow(0.563250, 1.5): 13.647048 calls/usec
ratio:      1

64-bit build:

./elf/ld.so --library-path .:math:dlfcn ./a.out
pow(0.562500, 1.5): 0.000982 calls/usec
pow(0.563250, 1.5): 13.574397 calls/usec
ratio:  13828


perf shows:

# Events: 15K cycles
#
# Overhead  Command      Shared Object                               Symbol
# ........  .......  .................  ...................................
#
    63.31%    ld.so  libm.so            [.] __mul
    18.44%    ld.so  libm.so            [.] __ieee754_pow_sse2
    13.81%    ld.so  libm.so            [.] __exp1
     1.20%    ld.so  libm.so            [.] __pow
     1.09%    ld.so  libm.so            [.] sub_magnitudes
     0.43%    ld.so  a.out              [.] main
     0.38%    ld.so  libm.so            [.] __cpy
     0.21%    ld.so  libm.so            [.] add_magnitudes
     0.19%    ld.so  libm.so            [.] @plt

-- 
Configure bugmail: http://sourceware.org/bugzilla/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are on the CC list for the bug.

[Bug math/13932] x86_64 pow unexpectedly slow for some inputs

[manu at gcc dot gnu.org]

http://sourceware.org/bugzilla/show_bug.cgi?id=13932

Manuel López-Ibáñez <manu at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |manu at gcc dot gnu.org

--- Comment #1 from Manuel López-Ibáñez <manu at gcc dot gnu.org> 2012-12-13 16:44:21 UTC ---
I can still reproduce it with 2.12

GNU C Library stable release version 2.12, by Roland McGrath et al.
Copyright (C) 2010 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.
There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A
PARTICULAR PURPOSE.
Compiled by GNU CC version 4.4.6 20120305 (Red Hat 4.4.6-4).
Compiled on a Linux 2.6.32 system on 2012-07-18.
Available extensions:
        The C stubs add-on version 2.1.2.
        crypt add-on version 2.1 by Michael Glad and others
        GNU Libidn by Simon Josefsson
        Native POSIX Threads Library by Ulrich Drepper et al
        BIND-8.2.3-T5B
        RT using linux kernel aio
libc ABIs: UNIQUE IFUNC
For bug reporting instructions, please see:
<http://www.gnu.org/software/libc/bugs.html>.

A testcase:

#include <math.h>
#ifndef POW
#define POW pow
#endif
#define N 1500
int total[N][N];
double alpha = 2.81;
int n = N;

int main(int argc, char *argv[])
{
    int x = 30976397;
    x += 0;
    double trail = 1. / ( (double) N * (double) x) ;
    long i,j;
    for ( i = 0 ; i < N ; i++ ) {
        for ( j = 0 ; j < i ; j++ ) {
            total[i][j] = POW(trail, alpha);
        }
    }
    return 0;
}

$ gcc -o slowpow slowpow.c -lm
$ /usr/bin/time ./slowpow
213.75user 0.04system 3:34.27elapsed 99%CPU (0avgtext+0avgdata
12784maxresident)k
0inputs+0outputs (0major+838minor)pagefaults 0swaps

(Interrupted, it was running forever)

$ gcc -DPOW=powl  -o slowpow slowpow.c -lm
$ /usr/bin/time ./slowpow 
0.20user 0.01system 0:00.22elapsed 98%CPU (0avgtext+0avgdata 35040maxresident)k
0inputs+0outputs (0major+2229minor)pagefaults 0swaps

$ gcc -DPOW=powf  -o slowpow slowpow.c -lm
$ /usr/bin/time ./slowpow 
0.23user 0.01system 0:00.25elapsed 95%CPU (0avgtext+0avgdata 35088maxresident)k
160inputs+0outputs (1major+2231minor)pagefaults 0swaps


At least, it would be nice if the man page mentioned this issue and what kind
of inputs may lead to it. It causes a lot of frustration:
http://entropymine.com/imageworsener/slowpow/

-- 
Configure bugmail: http://sourceware.org/bugzilla/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are on the CC list for the bug.

[Bug math/13932] x86_64 pow unexpectedly slow for some inputs

[ppluzhnikov at google dot com]

http://sourceware.org/bugzilla/show_bug.cgi?id=13932

Paul Pluzhnikov <ppluzhnikov at google dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
               Host|                            |x86_64-linux-gnu

--- Comment #2 from Paul Pluzhnikov <ppluzhnikov at google dot com> 2012-12-13 18:57:52 UTC ---
(In reply to comment #1)
> I can still reproduce it with 2.12

2.12 is ancient history. Current git trunk:

# i686:
Could not get the test to work. Something appears to be broken with my
toolchain, or with trunk in i686 mode.

# x86_64:
./elf/ld.so --library-path .:math:dlfcn /tmp/test_pow64
pow(0.562500, 1.5): 0.000990 calls/usec
pow(0.563250, 1.5): 12.753271 calls/usec
ratio:  12887

-- 
Configure bugmail: http://sourceware.org/bugzilla/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are on the CC list for the bug.

[Bug math/13932] x86_64 pow unexpectedly slow for some inputs

[siddhesh at redhat dot com]

http://sourceware.org/bugzilla/show_bug.cgi?id=13932

Siddhesh Poyarekar <siddhesh at redhat dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |siddhesh at redhat dot com
         AssignedTo|unassigned at sourceware    |siddhesh at redhat dot com
                   |dot org                     |

--- Comment #3 from Siddhesh Poyarekar <siddhesh at redhat dot com> 2013-01-04 11:33:13 UTC ---
Assigning this to me since I'm working on cleaning up the mp code, which should
make this better.

-- 
Configure bugmail: http://sourceware.org/bugzilla/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are on the CC list for the bug.

[Bug math/13932] x86_64 pow unexpectedly slow for some inputs

[herve at guillemet dot org]

http://sourceware.org/bugzilla/show_bug.cgi?id=13932

Hervé Guillemet <herve at guillemet dot org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |herve at guillemet dot org

-- 
Configure bugmail: http://sourceware.org/bugzilla/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are on the CC list for the bug.

[Bug math/13932] x86_64 pow unexpectedly slow for some inputs

[manu at gcc dot gnu.org]

http://sourceware.org/bugzilla/show_bug.cgi?id=13932

--- Comment #4 from Manuel López-Ibáñez <manu at gcc dot gnu.org> 2013-03-08 14:07:29 UTC ---
(In reply to comment #3)
> Assigning this to me since I'm working on cleaning up the mp code, which should
> make this better.

Thanks for working on this. As I said above, it would be nice if for the time
being, a note was added to the man page of pow warning about this issue. If you
happen to know what kind of inputs trigger it, that would be interesting
information.

-- 
Configure bugmail: http://sourceware.org/bugzilla/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are on the CC list for the bug.

[Bug math/13932] x86_64 pow unexpectedly slow for some inputs

[siddhesh at redhat dot com]

http://sourceware.org/bugzilla/show_bug.cgi?id=13932

--- Comment #5 from Siddhesh Poyarekar <siddhesh at redhat dot com> 2013-03-11 06:29:10 UTC ---
If we did, we wouldn't have had to do all those iterations at different
precision levels and the result would have been much faster :)

Nevertheless, I've added patches to master that ought to improve performance by
at least 4x in the worst case, bringing it close to mpfr performance (still
about 2x slower though).  There's still scope to make it faster, which is why I
haven't closed this bug yet.

The man pages are not part of glibc, they're a separate project by themselves. 
There could be a case for adding a note explaining the multiprecision fallback
(why it's there, overview, impact, etc.) in the glibc manual though.

-- 
Configure bugmail: http://sourceware.org/bugzilla/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are on the CC list for the bug.

[Bug math/13932] x86_64 pow unexpectedly slow for some inputs

[siddhesh at redhat dot com]

http://sourceware.org/bugzilla/show_bug.cgi?id=13932

--- Comment #6 from Siddhesh Poyarekar <siddhesh at redhat dot com> 2013-03-11 06:35:44 UTC ---
Created bug 15267 to track the documentation fix.

-- 
Configure bugmail: http://sourceware.org/bugzilla/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are on the CC list for the bug.

[Bug math/13932] x86_64 pow unexpectedly slow for some inputs

[manu at gcc dot gnu.org]

http://sourceware.org/bugzilla/show_bug.cgi?id=13932

--- Comment #7 from Manuel López-Ibáñez <manu at gcc dot gnu.org> 2013-03-11 09:07:17 UTC ---
(In reply to comment #5)
> Nevertheless, I've added patches to master that ought to improve performance by
> at least 4x in the worst case, bringing it close to mpfr performance (still
> about 2x slower though).  There's still scope to make it faster, which is why I
> haven't closed this bug yet.


Hi, thanks for your work. Personally, I would be interested to have a pow
version that is perhaps less precise but that does not have  such nasty
corner-cases. A 4x improvement is nice, but given that the worst-case may be
12,000x slower, it is not a definitive solution.

There are some implementations on the net that perhaps could be used when
-ffast-math is given?

http://jrfonseca.blogspot.be/2008/09/fast-sse2-pow-tables-or-polynomials.html

http://www.dctsystems.co.uk/Software/power.html

http://martin.ankerl.com/2012/01/25/optimized-approximative-pow-in-c-and-cpp/

I am no expert in IEEE floating-point arithmetic, so it may well be that those
implementations produce extremely bad approximations for some inputs. Is that
the case?

-- 
Configure bugmail: http://sourceware.org/bugzilla/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are on the CC list for the bug.

[Bug math/13932] x86_64 pow unexpectedly slow for some inputs

[siddhesh at redhat dot com]

http://sourceware.org/bugzilla/show_bug.cgi?id=13932

--- Comment #8 from Siddhesh Poyarekar <siddhesh at redhat dot com> 2013-03-11 10:19:19 UTC ---
(In reply to comment #7)
> Hi, thanks for your work. Personally, I would be interested to have a pow
> version that is perhaps less precise but that does not have  such nasty
> corner-cases. A 4x improvement is nice, but given that the worst-case may be
> 12,000x slower, it is not a definitive solution.
> 
> There are some implementations on the net that perhaps could be used when
> -ffast-math is given?
> 
> http://jrfonseca.blogspot.be/2008/09/fast-sse2-pow-tables-or-polynomials.html
> 
> http://www.dctsystems.co.uk/Software/power.html
> 
> http://martin.ankerl.com/2012/01/25/optimized-approximative-pow-in-c-and-cpp/
> 
> I am no expert in IEEE floating-point arithmetic, so it may well be that those
> implementations produce extremely bad approximations for some inputs. Is that
> the case?

They're all in a way subsets of what the fast phase of libm does, so we don't
really need to reimplement libm to take advantage of those ideas.

That said, there is indeed a strong case for fast and (for some inputs)
imprecise computations of transcendentals.  That probably won't be the default
in glibc, but I won't rule out the possibility of having an alternate library
or configuration, provided there is consensus in the glibc community for it.

-- 
Configure bugmail: http://sourceware.org/bugzilla/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are on the CC list for the bug.

[Bug math/13932] x86_64 pow unexpectedly slow for some inputs

[vz-sourceware at zeitlins dot org]

https://sourceware.org/bugzilla/show_bug.cgi?id=13932

Vadim Zeitlin <vz-sourceware at zeitlins dot org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |vz-sourceware at zeitlins dot org

-- 
You are receiving this mail because:
You are on the CC list for the bug.

[Bug math/13932] x86_64 pow unexpectedly slow for some inputs

[jsm28 at gcc dot gnu.org]

https://sourceware.org/bugzilla/show_bug.cgi?id=13932

Joseph Myers <jsm28 at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|normal                      |enhancement

-- 
You are receiving this mail because:
You are on the CC list for the bug.

[Bug math/13932] dbl-64 pow unexpectedly slow for some inputs

[jsm28 at gcc dot gnu.org]

https://sourceware.org/bugzilla/show_bug.cgi?id=13932

Joseph Myers <jsm28 at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|x86_64 pow unexpectedly     |dbl-64 pow unexpectedly
                   |slow for some inputs        |slow for some inputs

-- 
You are receiving this mail because:
You are on the CC list for the bug.

[Bug math/13932] dbl-64 pow unexpectedly slow for some inputs

[jsm28 at gcc dot gnu.org]

https://sourceware.org/bugzilla/show_bug.cgi?id=13932

Joseph Myers <jsm28 at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |stefani at seibold dot net

--- Comment #9 from Joseph Myers <jsm28 at gcc dot gnu.org> ---
*** Bug 16898 has been marked as a duplicate of this bug. ***

-- 
You are receiving this mail because:
You are on the CC list for the bug.

[Bug math/13932] dbl-64 pow unexpectedly slow for some inputs

[fweimer at redhat dot com]

https://sourceware.org/bugzilla/show_bug.cgi?id=13932

Florian Weimer <fweimer at redhat dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
              Flags|                            |security-

-- 
You are receiving this mail because:
You are on the CC list for the bug.

[Bug math/13932] dbl-64 pow unexpectedly slow for some inputs

[mtk.manpages at gmail dot com]

https://sourceware.org/bugzilla/show_bug.cgi?id=13932

Michael Kerrisk <mtk.manpages at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |mtk.manpages at gmail dot com

--- Comment #25 from Michael Kerrisk <mtk.manpages at gmail dot com> ---
Fix documented for man-pages-5.07.

diff --git a/man3/pow.3 b/man3/pow.3
index 2f8b340bb..91b9a9562 100644
--- a/man3/pow.3
+++ b/man3/pow.3
@@ -329,9 +329,10 @@ The variant returning
 also conforms to
 SVr4, 4.3BSD, C89.
 .SH BUGS
-On 64-bits,
+Before glibc 2.28,
 .\"
 .\" https://sourceware.org/bugzilla/show_bug.cgi?id=13932
+on some architectures (e.g., x86-64)
 .BR pow ()
 may be more than 10,000 times slower for some (rare) inputs
 than for other nearby inputs.
@@ -341,6 +342,9 @@ and not
 .BR powf ()
 nor
 .BR powl ().
+This problem was fixed
+.\" commit c3d466cba1692708a19c6ff829d0386c83a0c6e5
+in glibc 2.28.
 .PP
 In glibc 2.9 and earlier,
 .\"

-- 
You are receiving this mail because:
You are on the CC list for the bug.

[Bug math/13932] dbl-64 pow unexpectedly slow for some inputs

[vincent-srcware at vinc17 dot net]

https://sourceware.org/bugzilla/show_bug.cgi?id=13932

--- Comment #26 from Vincent Lefèvre <vincent-srcware at vinc17 dot net> ---
(In reply to Michael Kerrisk from comment #25)
> Fix documented for man-pages-5.07.
[...]
> -On 64-bits,
> +Before glibc 2.28,
>  .\"
>  .\" https://sourceware.org/bugzilla/show_bug.cgi?id=13932
> +on some architectures (e.g., x86-64)
>  .BR pow ()
>  may be more than 10,000 times slower for some (rare) inputs
>  than for other nearby inputs.
[...]

The problematic values are uncommon, but not so rare, in the sense that they
are close to simple values, i.e. are likely to occur in practice. An example
given above: pow(0.999999999999999889, 1.5)

1 and 1.5 are very simple values, which are more likely to occur in practice
than some fixed random value. Then it suffices to have a small rounding error
on 1...

For instance, this is very different from hard-to-round cases of exp, which are
also very slow IMHO, but unless one writes a specific program for them, no-one
should notice the slowness because such a case would typically occur only once
among billions (I don't remember the accuracy before the slowest path in this
library).

-- 
You are receiving this mail because:
You are on the CC list for the bug.

[Bug math/13932] dbl-64 pow unexpectedly slow for some inputs

[mtk.manpages at gmail dot com]

https://sourceware.org/bugzilla/show_bug.cgi?id=13932

--- Comment #27 from Michael Kerrisk <mtk.manpages at gmail dot com> ---
(In reply to Vincent Lefèvre from comment #26)
> (In reply to Michael Kerrisk from comment #25)
> > Fix documented for man-pages-5.07.
> [...]
> > -On 64-bits,
> > +Before glibc 2.28,
> >  .\"
> >  .\" https://sourceware.org/bugzilla/show_bug.cgi?id=13932
> > +on some architectures (e.g., x86-64)
> >  .BR pow ()
> >  may be more than 10,000 times slower for some (rare) inputs
> >  than for other nearby inputs.
> [...]
> 
> The problematic values are uncommon, but not so rare, in the sense that they
> are close to simple values, i.e. are likely to occur in practice. An example
> given above: pow(0.999999999999999889, 1.5)
> 
> 1 and 1.5 are very simple values, which are more likely to occur in practice
> than some fixed random value. Then it suffices to have a small rounding
> error on 1...
> 
> For instance, this is very different from hard-to-round cases of exp, which
> are also very slow IMHO, but unless one writes a specific program for them,
> no-one should notice the slowness because such a case would typically occur
> only once among billions (I don't remember the accuracy before the slowest
> path in this library).

Vincent

Thanks for your reply.

So, I should just remove "(rare)", do you think?

Thanks,

Michael

-- 
You are receiving this mail because:
You are on the CC list for the bug.

[Bug math/13932] dbl-64 pow unexpectedly slow for some inputs

[vincent-srcware at vinc17 dot net]

https://sourceware.org/bugzilla/show_bug.cgi?id=13932

--- Comment #28 from Vincent Lefèvre <vincent-srcware at vinc17 dot net> ---
(In reply to Michael Kerrisk from comment #27)
> So, I should just remove "(rare)", do you think?

Yes, I think that "rare" can be misleading. The sentence "[...] more than
10,000 times slower for some inputs than for other nearby inputs." would be OK,
as "some" implies that these are particular inputs, which may affect some
programs. This is exactly what we had before glibc 2.28.

-- 
You are receiving this mail because:
You are on the CC list for the bug.

[Bug math/13932] dbl-64 pow unexpectedly slow for some inputs

[mtk.manpages at gmail dot com]

https://sourceware.org/bugzilla/show_bug.cgi?id=13932

--- Comment #29 from Michael Kerrisk <mtk.manpages at gmail dot com> ---
(In reply to Vincent Lefèvre from comment #28)
> (In reply to Michael Kerrisk from comment #27)
> > So, I should just remove "(rare)", do you think?
> 
> Yes, I think that "rare" can be misleading. 

Okay. Done. Thanks for your input!

-- 
You are receiving this mail because:
You are on the CC list for the bug.