flat assembler
Message board for the users of flat assembler.

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

Author
Thread Post new topic Reply to topic
Daedalus



Joined: 25 Mar 2007
Posts: 52
Daedalus
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:

    What makes code fast?
    How can I be semi-sure that some code ASM or C is going to be fast?


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: 382 Time(s)

Post 12 Jun 2008, 20:25
View user's profile Send private message MSN Messenger Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 17636
Location: In your JS exploiting you and your system
revolution
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.
Post 12 Jun 2008, 20:53
View user's profile Send private message Visit poster's website Reply with quote
Daedalus



Joined: 25 Mar 2007
Posts: 52
Daedalus
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

Wink
Post 12 Jun 2008, 21:13
View user's profile Send private message MSN Messenger Reply with quote
kohlrak



Joined: 21 Jul 2006
Posts: 1421
Location: Uncle Sam's Pad
kohlrak
No more giving back...


Last edited by kohlrak on 07 Aug 2008, 14:34; edited 1 time in total
Post 13 Jun 2008, 06:20
View user's profile Send private message Visit poster's website AIM Address Yahoo Messenger MSN Messenger Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 3025
Location: vpcmipstrm
bitRAKE
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)/¯ unlicense.org
Post 13 Jun 2008, 15:17
View user's profile Send private message Visit poster's website Reply with quote
AlexP



Joined: 14 Nov 2007
Posts: 561
Location: Out the window. Yes, that one.
AlexP
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.
Post 14 Jun 2008, 17:21
View user's profile Send private message Visit poster's website Reply with quote
dap



Joined: 01 Dec 2007
Posts: 61
Location: Belgium
dap

_________________
(French only) http://dap.developpez.com
Post 14 Jun 2008, 19:35
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 3025
Location: vpcmipstrm
bitRAKE
In the video he says, "...family ten.." for the text "family 10h". Laughing

_________________
¯\(°_o)/¯ unlicense.org
Post 15 Jun 2008, 01:23
View user's profile Send private message Visit poster's website Reply with quote
eskizo



Joined: 22 Nov 2005
Posts: 59
eskizo
at least 'curPos[1]*8' --> 'curPos[1] << 3'
Post 02 Jul 2009, 06:33
View user's profile Send private message Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  


< 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


Copyright © 1999-2020, Tomasz Grysztar. Also on GitHub, YouTube, Twitter.

Website powered by rwasa.