Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #16737

Re: Optimisation questions

Show all headers | View raw

Raj Pashwar <raj121190@hotmail.NOSPAM.com> writes:
> On Sun, 05 Feb 2012 23:24:33 +1100, Zoltan Kocsi wrote:
>> On Sun, 5 Feb 2012 10:51:57 +0000 (UTC) Raj Pashwar
>> <raj121190@hotmail.NOSPAM.com> wrote:
>> 
>>> Thanks for all the answers, x&8 looks like a good one for efficiency.
>>> 
>>> I also had another idea while sleeping - amazing how that helps :)  At
>>> program startup, maybe in another thread, I can build an array of all
>>> x/8, x%8 for x's that might occur, then just look up in this array
>>> instead of doing the division every time. I will try this today also.
>> 
>> Chances are, your table will be slower, especially if it is decent size.
>> A table look up means an address calculation and a memory fetch, which
>> even with superscalar architectures and large caches is likely to cost
>> you more than a single instruction register-register AND or shift.
>> 
>> By the way, why would you need to build the table in a different thread?
>> To waste memory and cycles?
>> 
>> You'd be better off with listening to what the others replied to your
>> question. Unless x must be signed, change it to unsigned and the
>> compiler will merrily optimise your division away.
>
> Unfortunately x must be signed because -1 is used to denote "invalid 
> value". So I cannot take full advantage of people's suggestions.

Most people were suggesting dividing by 8 and letting the compiler
generate the best possible code.

> I have tried these out. I find that the program speed does not seem to 
> change much, if I use x%8 or x&7 or x=-(x>>3)<<3 : disappointing! I did 
> not try the table yet, but it stands to reason that it will be quicker 
> just to look up a result, than to do a computation every time.

No, it does not stand to reason.  A table lookup requires performing
computations to determine the location of the desired entry, as well as
a memory access to retrieve it.  Do not depend on your intuition to tell
you what micro-optimizations will make your code faster.

> I have two other optimisation questions I am looking at.
>
> In one loop called many times, I need to swap 2 variables. Currently I do 
> this with a temporary variable:
> tmp=a; a=b; b=tmp;
> I think it will save overhead to avoid this extra variable. I found on 
> the internet an "XOR trick", b^=a; a^=b; b^a=a; but the article said it 
> can be dangerous in some cases i.e. overflow.
>
> I was thinking of this and I invented an alternative version which I 
> believe will work correctly in 100% of cases (uses SUM not XOR):
> b+=a; a=b-a; b-=a;
> Has anyone thought of this idea before? Would you say it will be cheaper 
> than the temporary variable?

Yes, it's been thought of.  It's probably even less reliable than the
xor trick; any of the computations can overflow or underflow, producing
undefined behavior.

The way to swap two variables is to use a temporary

    const int old_a = a;
    a = b;
    b = old_a;

What makes you think that copying values *and* performing arithmetic on
them is going to be faster than just copying them?

> Also program start up is very slow. It must read in 10 million data 
> points from a text file - access is slow (network file). There are 2 
> unsigned long integers (x,y) on each line (represented by strings) that I 
> read into a 10000000x2 array.
>
> Right now I am using fgets() and atol. I don't have any good ideas to 
> optimise this except maybe setting up 100 threads to read different 
> sections of the file. Are there any faster ways to convert integers than 
> atol?
>
> while(fgets(strg,999,fp))
> { ary[ln][0]=atol(strtok(strg," "));
> ary[ln][1]=atol(strtok((char*)NULL,"\n"));
> ln++; } 

The time spent reading data from the file is likely to greatly exceed
the time spent converting it to integers.  10 million data points isn't
all that many.  Can you cache the file locally?

Incidentally, formatting your code for legibility has no performance cost:

    while (fgets(strg, 999, fp)) {
        ary[ln][0] = atol(strtok(strg, " "));
        ary[ln][1] = atol(strtok((char*)NULL, "\n"));
        ln++;
    }

There are probably better approaches than using strtok(); a solution
using strtol() is likely to be cleaner if not faster.

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
    Will write code for food.
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Optimisation questions Raj Pashwar <raj121190@hotmail.NOSPAM.com> - 2012-02-04 22:30 +0000
  Re: Optimisation questions Ian Collins <ian-news@hotmail.com> - 2012-02-05 11:44 +1300
    Re: Optimisation questions Keith Thompson <kst-u@mib.org> - 2012-02-04 14:52 -0800
      Re: Optimisation questions Ian Collins <ian-news@hotmail.com> - 2012-02-05 11:55 +1300
      Re: Optimisation questions Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2012-02-21 18:41 +0200
  Re: Optimisation questions "BartC" <bc@freeuk.com> - 2012-02-04 22:44 +0000
    Re: Optimisation questions "BartC" <bc@freeuk.com> - 2012-02-04 23:41 +0000
  Re: Optimisation questions Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-02-04 17:51 -0500
  Re: Optimisation questions Keith Thompson <kst-u@mib.org> - 2012-02-04 14:52 -0800
  Re: Optimisation questions James Kuyper <jameskuyper@verizon.net> - 2012-02-04 18:44 -0500
    Re: Optimisation questions Stephen Sprunk <stephen@sprunk.org> - 2012-02-04 18:00 -0600
      Re: Optimisation questions James Kuyper <jameskuyper@verizon.net> - 2012-02-04 21:18 -0500
        Re: Optimisation questions Kaz Kylheku <kaz@kylheku.com> - 2012-02-05 03:04 +0000
          Re: Optimisation questions Dann Corbit <dcorbit@connx.com> - 2012-02-06 09:40 -0800
            Re: Optimisation questions Willem <willem@toad.stack.nl> - 2012-02-06 18:51 +0000
            Re: Optimisation questions Markus Wichmann <nullplan@gmx.net> - 2012-02-07 14:19 +0100
              Re: Optimisation questions Dann Corbit <dcorbit@connx.com> - 2012-02-07 14:25 -0800
          Re: Optimisation questions Stephen Sprunk <stephen@sprunk.org> - 2012-02-06 17:29 -0600
            Re: Optimisation questions Kaz Kylheku <kaz@kylheku.com> - 2012-02-06 23:52 +0000
            Re: Optimisation questions pete <pfiland@mindspring.com> - 2012-02-06 19:10 -0500
    Re: Optimisation questions Raj Pashwar <raj121190@hotmail.NOSPAM.com> - 2012-02-05 10:51 +0000
      Re: Optimisation questions Ian Collins <ian-news@hotmail.com> - 2012-02-06 00:08 +1300
        Re: Optimisation questions Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-02-05 08:13 -0500
      Re: Optimisation questions "BartC" <bc@freeuk.com> - 2012-02-05 11:33 +0000
      Re: Optimisation questions Zoltan Kocsi <zoltan@bendor.com.au> - 2012-02-05 23:24 +1100
        Re: Optimisation questions Raj Pashwar <raj121190@hotmail.NOSPAM.com> - 2012-02-05 22:28 +0000
          Re: Optimisation questions Kaz Kylheku <kaz@kylheku.com> - 2012-02-05 22:37 +0000
          Re: Optimisation questions Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-02-05 17:48 -0500
          Re: Optimisation questions Keith Thompson <kst-u@mib.org> - 2012-02-05 15:57 -0800
      Re: Optimisation questions "BartC" <bc@freeuk.com> - 2012-02-05 12:53 +0000
  Re: Optimisation questions Geoff <geoff@invalid.invalid> - 2012-02-04 16:07 -0800
  Re: Optimisation questions "christian.bau" <christian.bau@cbau.wanadoo.co.uk> - 2012-02-04 15:37 -0800
    Re: Optimisation questions Nick Keighley <nick_keighley_nospam@hotmail.com> - 2012-02-05 04:26 -0800
      Re: Optimisation questions lawrence.jones@siemens.com - 2012-02-07 10:56 -0500
  Re: Optimisation questions Nick Keighley <nick_keighley_nospam@hotmail.com> - 2012-02-05 04:29 -0800
  Re: Optimisation questions Michael Angelo Ravera <maravera@prodigy.net> - 2012-02-05 23:24 -0800

csiph-web