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 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:

    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: 751 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: 20175
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.
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 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

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 13 Jun 2008, 06:20
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: 3959
Location: vpcmipstrm
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
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 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.
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 14 Jun 2008, 19:35

_________________
(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: 3959
Location: vpcmipstrm
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
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 02 Jul 2009, 06:33
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-2024, Tomasz Grysztar. Also on GitHub, YouTube.

Website powered by rwasa.