[Bug c++/61621] New: Normal enum switch slower than test case.

[Bug c++/61621] New: Normal enum switch slower than test case.

[holger.seelig at yahoo dot de]

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

            Bug ID: 61621
           Summary: Normal enum switch slower than test case.
           Product: gcc
           Version: 4.8.2
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: holger.seelig at yahoo dot de

I detected that a normal enum switch is 1.5 up to 3 times slower than a
'double' enum switch. Below I created a test case for you. Unkomment the marked
lines to get better performace results.


### Compiler options
/usr/bin/g++ -O3 -Wall -std=c++11 test-case.cpp

###  test-case.cpp

#include <iostream>
#include <vector>
#include <chrono>


enum InstructionType
{
   UNDEFINED,
   INT32,
   UINT32,
   NUMBER,
   STRING,
   NULL_OBJECT,
   OBJECT,
   BOOLEAN_OBJECT,
   NUMBER_OBJECT,
   STRING_OBJECT,
   ARRAY_OBJECT,
   DATE_OBJECT,
   REGEX_OBJECT,
   FUNCTION_OBJECT,
   ADDRESS,
   NOP,
   RESULT,
   JUMP_IF_ZERO,
   MULTIPLICATION_EXPRESSION,
   DIVISION_EXPRESSION,
   REMAINDER_EXPRESSION,
   ADDITION_EXPRESSION,
   SUBTRACTION_EXPRESSION,
   LESS_EXPRESSION,
   RETURN_STATEMENT,

};

int
run (const std::vector <InstructionType> & instructions)
{
   int value = 0;

   for (size_t i = 0, size = instructions .size (); i < size; ++ i)
   {
      switch (instructions [i])
      {
         case UNDEFINED:
         case INT32:
         case UINT32:
         case NUMBER:
         case STRING:
         case NULL_OBJECT:
         case OBJECT:
         case BOOLEAN_OBJECT:
         case NUMBER_OBJECT:
         case STRING_OBJECT:
         case ARRAY_OBJECT:
         case DATE_OBJECT:
         case REGEX_OBJECT:
         case FUNCTION_OBJECT:
         case ADDRESS:
            value += 1;
            break;
// UNCOMMENT THE FOLLOWING LINES TO GET BETTER PERFORMANCE
//         default:
//         {
//            switch (instructions [i])
//            {
               case NOP:
                  break;
               case RESULT:
                  value += 2;
                  break;
               case JUMP_IF_ZERO:
                  value ++;
                  break;
               case MULTIPLICATION_EXPRESSION:
                  value += 3;
                  break;
               case DIVISION_EXPRESSION:
                  value += 4;
                  break;
               case REMAINDER_EXPRESSION:
                  value += 5;
                  break;
               case ADDITION_EXPRESSION:
                  value += 6;
                  break;
               case SUBTRACTION_EXPRESSION:
                  value += 7;
                  break;
               case LESS_EXPRESSION:
                  value += 8;
                  break;
               case RETURN_STATEMENT:
                  value += 9;
                  break;
// UNCOMMENT THE FOLLOWING LINES TO GET BETTER PERFORMANCE
//               default:
//                  break;
//            }
//         }
      }
   }

   return value;
}

inline
double
now ()
{
   using namespace std::chrono;

   return duration_cast <duration <double>> (high_resolution_clock::now ()
.time_since_epoch ()) .count ();
}

int
main (int argc, char **argv)
{
   std::cout << "Enum switch performance test!" << std::endl;

   std::vector <InstructionType> instructions = {
      UNDEFINED,
      INT32,
      UINT32,
      NUMBER,
      STRING,
      NULL_OBJECT,
      OBJECT,
      BOOLEAN_OBJECT,
      NUMBER_OBJECT,
      STRING_OBJECT,
      ARRAY_OBJECT,
      DATE_OBJECT,
      REGEX_OBJECT,
      FUNCTION_OBJECT,
      ADDRESS,
      NOP,
      RESULT,
      JUMP_IF_ZERO,
      MULTIPLICATION_EXPRESSION,
      DIVISION_EXPRESSION,
      REMAINDER_EXPRESSION,
      ADDITION_EXPRESSION,
      SUBTRACTION_EXPRESSION,
      LESS_EXPRESSION,
      RETURN_STATEMENT,
   };

   int  value = 0;
   auto t0    = now ();

   for (int i = 0; i < 100000000; ++ i)
      value += run (instructions);

   std::cout << "value: " << value << std::endl;
   std::cout << "time:  " << now () - t0 << " s" << std::endl;

   return 0;
}


################

holger@qualle:~$ gcc -v
Using built-in specs.
COLLECT_GCC=gcc
COLLECT_LTO_WRAPPER=/usr/lib/gcc/x86_64-linux-gnu/4.8/lto-wrapper
Target: x86_64-linux-gnu
Configured with: ../src/configure -v --with-pkgversion='Ubuntu 4.8.2-19ubuntu1'
--with-bugurl=file:///usr/share/doc/gcc-4.8/README.Bugs
--enable-languages=c,c++,java,go,d,fortran,objc,obj-c++ --prefix=/usr
--program-suffix=-4.8 --enable-shared --enable-linker-build-id
--libexecdir=/usr/lib --without-included-gettext --enable-threads=posix
--with-gxx-include-dir=/usr/include/c++/4.8 --libdir=/usr/lib --enable-nls
--with-sysroot=/ --enable-clocale=gnu --enable-libstdcxx-debug
--enable-libstdcxx-time=yes --enable-gnu-unique-object --disable-libmudflap
--enable-plugin --with-system-zlib --disable-browser-plugin
--enable-java-awt=gtk --enable-gtk-cairo
--with-java-home=/usr/lib/jvm/java-1.5.0-gcj-4.8-amd64/jre --enable-java-home
--with-jvm-root-dir=/usr/lib/jvm/java-1.5.0-gcj-4.8-amd64
--with-jvm-jar-dir=/usr/lib/jvm-exports/java-1.5.0-gcj-4.8-amd64
--with-arch-directory=amd64 --with-ecj-jar=/usr/share/java/eclipse-ecj.jar
--enable-objc-gc --enable-multiarch --disable-werror --with-arch-32=i686
--with-abi=m64 --with-multilib-list=m32,m64,mx32 --with-tune=generic
--enable-checking=release --build=x86_64-linux-gnu --host=x86_64-linux-gnu
--target=x86_64-linux-gnu
Thread model: posix
gcc version 4.8.2 (Ubuntu 4.8.2-19ubuntu1)

[Bug c++/61621] Normal enum switch slower than test case.

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |WAITING
   Last reconfirmed|                            |2014-06-27
     Ever confirmed|0                           |1

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
Well, you manually made the first case covering many cases fast by
grouping the rest of the cases.

Did you try using profile-feedback to give GCC a chance to see what
cases are executed more frequently?

[Bug c++/61621] Normal enum switch slower than test case.

[holger.seelig at yahoo dot de]

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

--- Comment #2 from Holger Seelig <holger.seelig at yahoo dot de> ---
To my understanding and what I know is that a switch like the following:

switch (i)
{
   case 10:
      func_a();
      break;
   case 11:
      func_b();
      break;
   case 12:
      func_c();
      break;
}

Should become something like this:

// N.B.: This is not C++ code
static address jump_table[] = { case_a, case_b, case_c, end };
unsigned int index = i - 10;
if (index > 3) goto end;
goto jump_table [index];
case_a: func_a(); goto end;
case_b: func_b(); goto end;
case_c: func_c();
end:

and with this code a switch should handle many enum cases very efficiently
regardless if a case is executed more frequently.  (With a normal enum type the
second line »unsigned int index = i - 10;« could be omitted).
>From gcc-bugs-return-455133-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org Fri Jun 27 13:06:48 2014
Return-Path: <gcc-bugs-return-455133-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org>
Delivered-To: listarch-gcc-bugs@gcc.gnu.org
Received: (qmail 24842 invoked by alias); 27 Jun 2014 13:06:48 -0000
Mailing-List: contact gcc-bugs-help@gcc.gnu.org; run by ezmlm
Precedence: bulk
List-Id: <gcc-bugs.gcc.gnu.org>
List-Archive: <http://gcc.gnu.org/ml/gcc-bugs/>
List-Post: <mailto:gcc-bugs@gcc.gnu.org>
List-Help: <mailto:gcc-bugs-help@gcc.gnu.org>
Sender: gcc-bugs-owner@gcc.gnu.org
Delivered-To: mailing list gcc-bugs@gcc.gnu.org
Received: (qmail 24789 invoked by uid 48); 27 Jun 2014 13:06:44 -0000
From: "mustrumr97 at gmail dot com" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug tree-optimization/60899] undef reference generated with -fdevirtualize-speculatively
Date: Fri, 27 Jun 2014 13:06:00 -0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: changed
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: tree-optimization
X-Bugzilla-Version: 4.10.0
X-Bugzilla-Keywords: wrong-code
X-Bugzilla-Severity: normal
X-Bugzilla-Who: mustrumr97 at gmail dot com
X-Bugzilla-Status: NEW
X-Bugzilla-Priority: P3
X-Bugzilla-Assigned-To: hubicka at gcc dot gnu.org
X-Bugzilla-Target-Milestone: ---
X-Bugzilla-Flags:
X-Bugzilla-Changed-Fields: cc
Message-ID: <bug-60899-4-Q2XFfhtPiS@http.gcc.gnu.org/bugzilla/>
In-Reply-To: <bug-60899-4@http.gcc.gnu.org/bugzilla/>
References: <bug-60899-4@http.gcc.gnu.org/bugzilla/>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: 7bit
X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/
Auto-Submitted: auto-generated
MIME-Version: 1.0
X-SW-Source: 2014-06/txt/msg02215.txt.bz2
Content-length: 450

https://gcc.gnu.org/bugzilla/show_bug.cgi?id`899

Hristo Venev <mustrumr97 at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |mustrumr97 at gmail dot com

--- Comment #11 from Hristo Venev <mustrumr97 at gmail dot com> ---
This bug also affects gcc 4.9.1. It causes LLVM to fail to build.

[Bug middle-end/61621] Normal enum switch slower than test case.

[pinskia at gcc dot gnu.org]

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

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
          Component|c++                         |middle-end
           Keywords|                            |missed-optimization

--- Comment #3 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Note I think this might have been improved already.

Also I think there is an issue here which is not mentioned, in the case of
"instructions", there might be most used ones which can be pulled out of the
case table.
Also in the below test function could even be using a constant table and a load
from that based on the instructions [i] (and then added to value).