[Bug c/66263] New: Performance regression from gcc-4.8 and up (trivial sudoku program)

[Bug c/66263] New: Performance regression from gcc-4.8 and up (trivial sudoku program)

[bdeyal at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66263

            Bug ID: 66263
           Summary: Performance regression from gcc-4.8 and up (trivial
                    sudoku program)
           Product: gcc
           Version: 4.8.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c
          Assignee: unassigned at gcc dot gnu.org
          Reporter: bdeyal at gmail dot com
  Target Milestone: ---

Created attachment 35605
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=35605&action=edit
Preprocessed source file

I ran the attached simple program with gcc-4.6, 4.7, 4.8, 4.9 and 5.1

This is a simple brute force + recursion program that finds all the solutions
for a given sudoku board. My input file had about half a million different
solutions.

System is fedora 21 with gcc 4.9.2
All other compilers were built locally.

my compilation command line was:

$(CC) -Ofast -W -Wall -DNDEBUG src/sudoku.c -o bin/sudoku


Running time results
====================


gcc-4.6.4   0.483s
gcc-4.7.4   0.496s
gcc-4.8.4   0.749s
gcc-4.9.2   0.762s
gcc-5.1.0   0.776s


Files:
======
Attached preprocessed file to compile.

In addition here's the input file contents for solving:

- - - - - 1 - 3 -
- - 8 - - - - 7 5
- 1 - 9 - - - - -
- - 7 - - - - - 1
- - - 8 - 9 - - -
8 - - - 3 - - - -
- - - - - - - 9 -
9 2 - - - - 3 - -
- - - - - - - - -

to test you should run something like:

time ./sudoku --quiet < input_file.txt

where ./sudoku is the produced executable and input_file.txt is the sudoku
board from above.



Detailed compiler version and configure options:
================================================

$ gcc-4.6 -v
Using built-in specs.
COLLECT_GCC=gcc-4.6
COLLECT_LTO_WRAPPER=/opt/gcc46/libexec/gcc/x86_64-redhat-linux/4.6.4/lto-wrapper
Target: x86_64-redhat-linux
Configured with: ../configure --prefix=/opt/gcc46 --enable-bootstrap
--enable-shared --enable-threads=posix --enable-checking=release
--enable-multilib --with-system-zlib --enable-__cxa_atexit
--disable-libunwind-exceptions --enable-gnu-unique-object
--enable-linker-build-id --with-linker-hash-style=gnu --enable-languages=c,c++
--enable-plugin --enable-initfini-array --with-tune=generic --with-arch_32=i686
--build=x86_64-redhat-linux
Thread model: posix
gcc version 4.6.4 (GCC)


$ gcc-4.7 -v
Using built-in specs.
COLLECT_GCC=gcc-4.7
COLLECT_LTO_WRAPPER=/opt/gcc-4.7.4/libexec/gcc/x86_64-redhat-linux/4.7.4/lto-wrapper
Target: x86_64-redhat-linux
Configured with: ../gcc-4.7.4/configure --prefix=/opt/gcc-4.7.4
--enable-bootstrap --enable-shared --enable-threads=posix
--enable-checking=release --with-system-zlib --enable-__cxa_atexit
--disable-libunwind-exceptions --enable-gnu-unique-object
--enable-linker-build-id --with-linker-hash-style=gnu
--enable-languages=c,c++,fortran --enable-plugin --enable-initfini-array
--disable-dssi --with-tune=generic --with-arch_32=i686
--build=x86_64-redhat-linux
Thread model: posix
gcc version 4.7.4 (GCC)


$ gcc-4.8 -v
Using built-in specs.
COLLECT_GCC=gcc-4.8
COLLECT_LTO_WRAPPER=/opt/gcc48/libexec/gcc/x86_64-redhat-linux/4.8.4/lto-wrapper
Target: x86_64-redhat-linux
Configured with: ../configure --prefix=/opt/gcc48 --enable-bootstrap
--enable-shared --enable-threads=posix --enable-checking=release
--enable-multilib --with-system-zlib --enable-__cxa_atexit
--disable-libunwind-exceptions --enable-gnu-unique-object
--enable-linker-build-id --with-linker-hash-style=gnu
--enable-languages=c,c++,fortran,go,lto --enable-plugin --enable-initfini-array
--with-tune=generic --with-arch_32=i686 --build=x86_64-redhat-linux
Thread model: posix
gcc version 4.8.4 (GCC)


$ gcc -v
Using built-in specs.
COLLECT_GCC=gcc
COLLECT_LTO_WRAPPER=/usr/libexec/gcc/x86_64-redhat-linux/4.9.2/lto-wrapper
Target: x86_64-redhat-linux
Configured with: ../configure --prefix=/usr --mandir=/usr/share/man
--infodir=/usr/share/info --with-bugurl=http://bugzilla.redhat.com/bugzilla
--enable-bootstrap --enable-shared --enable-threads=posix
--enable-checking=release --enable-multilib --with-system-zlib
--enable-__cxa_atexit --disable-libunwind-exceptions --enable-gnu-unique-object
--enable-linker-build-id --with-linker-hash-style=gnu
--enable-languages=c,c++,objc,obj-c++,fortran,ada,go,lto --enable-plugin
--enable-initfini-array --disable-libgcj
--with-isl=/builddir/build/BUILD/gcc-4.9.2-20150212/obj-x86_64-redhat-linux/isl-install
--with-cloog=/builddir/build/BUILD/gcc-4.9.2-20150212/obj-x86_64-redhat-linux/cloog-install
--enable-gnu-indirect-function --with-tune=generic --with-arch_32=i686
--build=x86_64-redhat-linux
Thread model: posix
gcc version 4.9.2 20150212 (Red Hat 4.9.2-6) (GCC)


$ gcc-5.0 -v
Using built-in specs.
COLLECT_GCC=gcc-5.0
COLLECT_LTO_WRAPPER=/opt/gcc5/libexec/gcc/x86_64-redhat-linux/5.1.0/lto-wrapper
Target: x86_64-redhat-linux
Configured with: ../configure --prefix=/opt/gcc5/ --enable-bootstrap
--enable-shared --enable-threads=posix --enable-checking=release
--enable-multilib --with-system-zlib --enable-__cxa_atexit
--disable-libunwind-exceptions --enable-gnu-unique-object
--enable-linker-build-id --with-linker-hash-style=gnu
--enable-languages=c,c++,fortran,go,lto --enable-plugin --enable-initfini-array
--with-tune=generic --with-arch_32=i686 --build=x86_64-redhat-linux
Thread model: posix
gcc version 5.1.0 (GCC)

[Bug c/66263] Performance regression from gcc-4.8 and up (trivial sudoku program)

[bdeyal at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66263

--- Comment #1 from EyalBD <bdeyal at gmail dot com> ---
Created attachment 35606
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=35606&action=edit
Input file for running

[Bug tree-optimization/66263] [4.8/4.9/5/6 Regression] Performance regression from gcc-4.8 and up (trivial sudoku program)

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66263

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |missed-optimization
             Target|                            |x86_64-*-*
          Component|c                           |tree-optimization
   Target Milestone|---                         |4.8.5
            Summary|Performance regression from |[4.8/4.9/5/6 Regression]
                   |gcc-4.8 and up (trivial     |Performance regression from
                   |sudoku program)             |gcc-4.8 and up (trivial
                   |                            |sudoku program)

--- Comment #3 from Richard Biener <rguenth at gcc dot gnu.org> ---
I'd say it might be changes in inlining.  For single-file testcases it's
profitable to add -fwhole-program to -Ofast as well.

[Bug tree-optimization/66263] [4.8/4.9/5/6 Regression] Performance regression from gcc-4.8 and up (trivial sudoku program)

[bdeyal at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66263

--- Comment #4 from EyalBD <bdeyal at gmail dot com> ---
Same results for -fwhole-program too.  gcc-4.6,4.7 around 0.5s, others 0.7-0.8s

[Bug tree-optimization/66263] [4.8/4.9/5/6 Regression] Performance regression from gcc-4.8 and up (trivial sudoku program)

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66263

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.8.5                       |4.9.3

--- Comment #5 from Richard Biener <rguenth at gcc dot gnu.org> ---
The gcc-4_8-branch is being closed, re-targeting regressions to 4.9.3.

[Bug tree-optimization/66263] [4.9/5/6 Regression] Performance regression from gcc-4.8 and up (trivial sudoku program)

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66263

--- Comment #6 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
GCC 4.9.3 has been released.

[Bug tree-optimization/66263] [4.9/5/6 Regression] Performance regression from gcc-4.8 and up (trivial sudoku program)

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66263

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.9.3                       |4.9.4

[Bug tree-optimization/66263] [4.9/5/6 Regression] Performance regression from gcc-4.8 and up (trivial sudoku program)

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66263

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P3                          |P2
             Status|UNCONFIRMED                 |RESOLVED
      Known to work|                            |4.7.4
         Resolution|---                         |DUPLICATE
      Known to fail|                            |4.8.3, 5.1.0

--- Comment #7 from Richard Biener <rguenth at gcc dot gnu.org> ---
Confirmed, for me:

4.7.4: 0.77s
4.8.3: 1.5s
5.1: 1.57s

with -O3, time with -O2 didn't regress.  Even with -fno-inline it regresses:

4.7.4 -O3 -fno-inline: 1.7s
5.1 -O3 -fno-inline: 2.3s

Ok, 4.7 unrolls the 

      for (digit = 1; digit <= N; ++digit) {
         if (can_put_digit(row, col, box, digit)) {
            put_digit(row, col, box, digit);
            solve(square+1);
            pop_digit(row, col, box, digit);
         }
      }

loop, so this looks like a duplicate of PR59967.  It also re-orders
basic-blocks in a way that if can_put_digit returns false (which should
be likely in the end) then it just falls thru to the next can_put_digit call.

With inlining the non-pure call is the recursion to solve ().

*** This bug has been marked as a duplicate of bug 59967 ***