Weird code output by GCC, what's faster?

Index > High Level Languages > Weird code output by GCC, what's faster?

Author

Thread

Daedalus

Joined: 25 Mar 2007
Posts: 52

Daedalus 12 Jun 2008, 20:25

Hi guys,

I had some problems today with "speeding up" my algorithm. I figured you guys of all people would know best what the fastest code is, so I'm hoping you can help me.

I had this C code:

Code:

  for(i = 0; i < 8; i++){
    curPos[0] = knightPos[0] + horizontal[i];
    if(curPos[0] > 7){
      continue;
    }
    else{
      curPos[1] = knightPos[1] + vertical[i];
      if(curPos[1] > 7){
        continue;
      }
      else{
        if(board[curPos[0] + curPos[1]*8] == 0){

And I figured I could replace it with this:

Code:

  for(i = 0; i < 8; i++){
    curPos[0] = knightPos[0] + horizontal[i];
    if(curPos[0] < 8){
      curPos[1] = knightPos[1] + vertical[i];
      if(curPos[1] < 8){
        if(board[curPos[0] + curPos[1]*8] == 0){

The below one is a lot slower (about 30% on my system), and the code generated by GCC for it is really really really different from the code generated for the top piece of code.

I've attached the outputted ASM (dissembled copy past from ollydbg). I was hoping you could take a look at it and explain to me why one piece of assembly is faster than another in this specific case and in general. I tried some googling, but found it quite hard to pinpoint information on speeding up algorithms.

I still now a few things, but I'm not sure if they are obsolete by now. One thing I can think of is branch prediction. How can I predict when branch prediction will be bad? When generated C code will be slower than C code that looks a lot like it?

I've also posted on a C forum asking this question, in case you're wondering.

In a nutshell:

Thanks In Advance,

Description:	Included is: Original Sources (complete, program for solving Knights Tour using brute force on purpose) And the main loop dissembled in Olly is also in 2 files. FastCode.asm belongs to KnightsTourVier.c, SlowCode.asm to KnightsTourVijf.c C source c	Download
Filename:	Code.rar
Filesize:	3.58 KB
Downloaded:	847 Time(s)

12 Jun 2008, 20:25

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20445
Location: In your JS exploiting you and your system

revolution 12 Jun 2008, 20:53

Daedalus wrote:

What makes code fast?

That is a big question, and it does not have a simple answer.

For some reading I highly recommend Agner Fogg's stuff AND the Intel Optimisation Manual AND the AMD Optimisation Manual. All three are essential knowledge to understand the internal architectures and reasons why some code is faster and other code is not.

For a majority of code that is heavily optimised for speed it goes through many many iterations. A tweak here, a unrolled loop there, an elimination of a branch elsewhere etc.

It is almost impossible to look at a piece of code and make a judgement about if it is going to be fast or not. There are just too many variables to consider. The only reliable way I know of is the good old test and compare on the target system to see if it gives you the performance you need.

12 Jun 2008, 20:53

Daedalus

Joined: 25 Mar 2007
Posts: 52

Daedalus 12 Jun 2008, 21:13

Thank you for the reference to Agner Fog. I'll finish my C++ course and then take a look at his books for sure. Maybe the other ones as well. I'm afraid the best test is indeed compiling and checking but it was rather frustrating to code for an hour an notice the code I have with caching is actually slower than the code without all the fancy "optimizations" I had coded. Life sucks. Sad

12 Jun 2008, 21:13

kohlrak

Joined: 21 Jul 2006
Posts: 1421
Location: Uncle Sam's Pad

kohlrak 13 Jun 2008, 06:20

No more giving back...

Last edited by kohlrak on 07 Aug 2008, 14:34; edited 1 time in total

13 Jun 2008, 06:20

bitRAKE

Joined: 21 Jul 2003
Posts: 4072
Location: vpcmpistri

bitRAKE 13 Jun 2008, 15:17

Use a bit lookup table to reduce the code to a single branch and minimize memory usage. Complex unpredictable branching is very slow on the processor, and should be worked out of the design. Google for "bit board chess".

_________________
¯\(°_o)/¯ “languages are not safe - uses can be” Bjarne Stroustrup

13 Jun 2008, 15:17

AlexP

Joined: 14 Nov 2007
Posts: 561
Location: Out the window. Yes, that one.

AlexP 14 Jun 2008, 17:21

The Agner Fog manuals as well as the Intel Optimization Manual have been a life-saver for me also Smile

. It all depends on which processor you're using to get the most speed out of it.

14 Jun 2008, 17:21

dap

Joined: 01 Dec 2007
Posts: 61
Location: Belgium

dap 14 Jun 2008, 19:35

Just found this : http://developer.amd.com/documentation/videos/pages/SoftwareOptimizationVideoSeries.aspx

_________________
(French only) http://dap.developpez.com

14 Jun 2008, 19:35

bitRAKE

Joined: 21 Jul 2003
Posts: 4072
Location: vpcmpistri

bitRAKE 15 Jun 2008, 01:23

In the video he says, "...family ten.." for the text "family 10h". Laughing

_________________
¯\(°_o)/¯ “languages are not safe - uses can be” Bjarne Stroustrup

15 Jun 2008, 01:23

eskizo

Joined: 22 Nov 2005
Posts: 59

eskizo 02 Jul 2009, 06:33

at least 'curPos[1]*8' --> 'curPos[1] << 3'

02 Jul 2009, 06:33

< Last Thread | Next Thread >

Forum Rules:

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum