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

Groups > comp.lang.c > #16688 > unrolled thread

Optimisation questions

Back to article view | Back to comp.lang.c

Contents

  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

Page 2 of 2 — ← Prev page 1 [2]

#16713

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.

Thanks

On Sat, 04 Feb 2012 18:44:25 -0500, James Kuyper wrote:
> On 02/04/2012 05:30 PM, Raj Pashwar wrote:
>> Hello :
>> 
>> My current program runs too slow. It uses x/8 and x%8 many times, where
>> x is an int in both cases.
>> 
>> I have replaced x/8 with x>>3, as this is faster (pretty sure).
>> However, I am not sure whether this is faster than x%8 : x-=(x>>3)<<3;
> 
> As a general rule, your compiler should generate exactly the same code
> for x/8 and x>>3, because they're required to have exactly the same
> behavior. If it doesn't, get a better one. What that code will be may be
> different on different machines, it might be called a division
> instruction on one machine, and a shift instruction on a different
> machine, but you can generally trust the compiler to know which one is
> faster. If it doesn't, get a better one.
> 
> 
>> Is this generally a good optimisation to use?
>> 
>> Also I've got a memory region that I constantly need to access, so I
>> would like it to be in cache. I know that I can use 'register' in
>> variable declarations, to speed up it's access.
> 
> That's unlikely to be the case; if putting it in a register would speed
> up, you can be reasonably sure the compiler already puts it in a
> register, even if you don't specifically tell it to do so. If it didn't
> put it in a register, it probably had a good reason for not doing so; in
> that case, if it paid attention to your "register" declaration, it could
> actually slow your program down. For precisely this reason, most
> compilers ignore the keyword "register", and the way the standard is
> written, this is perfectly acceptable behavior.

[toc] | [prev] | [next] | [standalone]

#16714

On 02/ 5/12 11:51 PM, Raj Pashwar wrote:
> Thanks for all the answers, x&8 looks like a good one for efficiency.

Efficiency for what?  Did you actually read what we wrote about the 
futility of such silly optimisations?  Did you measure the performance 
of your code?

-- 
Ian Collins

[toc] | [prev] | [next] | [standalone]

#16719

On 2/5/2012 6:08 AM, Ian Collins wrote:
> On 02/ 5/12 11:51 PM, Raj Pashwar wrote:
>> Thanks for all the answers, x&8 looks like a good one for efficiency.
>
> Efficiency for what? Did you actually read what we wrote about the
> futility of such silly optimisations? Did you measure the performance of
> your code?

     He didn't even read with enough attention to get the mask right.

-- 
Eric Sosman
esosman@ieee-dot-org.invalid

[toc] | [prev] | [next] | [standalone]

#16715

"Raj Pashwar" <raj121190@hotmail.NOSPAM.com> wrote in message 
news:jgln0d$jj2$1@speranza.aioe.org...
> Thanks for all the answers, x&8 looks like a good one for efficiency.

You might find x&7 more useful, it you want the last 3 bits.

-- 
Bartc
 

[toc] | [prev] | [next] | [standalone]

#16717

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.

Zoltan

[toc] | [prev] | [next] | [standalone]

#16734

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.

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.

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?

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++; } 

Thank You to everyone who has helped so far.

[toc] | [prev] | [next] | [standalone]

#16735

On 2012-02-05, Raj Pashwar <raj121190@hotmail.NOSPAM.com> wrote:
> 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.

The astute reader must now come to this conclusion: troll.

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

Oh yeah 100 threads: that will make bytes come down faster from the network.

What a hoot.

[toc] | [prev] | [next] | [standalone]

#16736

On 2/5/2012 5:28 PM, Raj Pashwar wrote:
> [...]it stands to reason that it will be quicker
> just to look up a result, than to do a computation every time.

     Two questions for the astute reasoner:

     1) At full throttle, how many instructions can your computer's
CPU execute in one second?

     2) At full throttle, how many fetches can your computer's RAM
satisfy in one second?

     Since you've already mentioned "cache" you are presumably aware
of it.  Does the mere existence of cache memory suggest anything
about the answers to (1) and (2)?

-- 
Eric Sosman
esosman@ieee-dot-org.invalid

[toc] | [prev] | [next] | [standalone]

#16737

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"

[toc] | [prev] | [next] | [standalone]

#16718

"Raj Pashwar" <raj121190@hotmail.NOSPAM.com> wrote in message 
news:jgln0d$jj2$1@speranza.aioe.org...

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

If the range of x is small enough (8 or 16 bits), that it would make the 
table viable, then you don't need a separate thread to set it up. But if 
it's so big (32 bits for example), then such a huge table will likely make 
your machine grind to a halt.

And a table-lookup will almost certainly take longer than a shift or mask 
operation.

But, x/8 and x%8 sound like you're doing something with bit pointers. 
Perhaps post more of your code here, so you can get more helpful responses, 
once we know what you're trying to do.

-- 
Bartc 

[toc] | [prev] | [next] | [standalone]

#16701

On Sat, 4 Feb 2012 22:30:54 +0000 (UTC), Raj Pashwar
<raj121190@hotmail.NOSPAM.com> wrote:

>Hello :
>
>My current program runs too slow. It uses x/8 and x%8 many times, where x 
>is an int in both cases.

How slow is too slow? How did you measure it?
Where is your measurement data?

Debug build or release build? 
Which compiler and what version are you using?
What is your target platform?

>
>I have replaced x/8 with x>>3, as this is faster (pretty sure).
>However, I am not sure whether this is faster than x%8 :
>x-=(x>>3)<<3;

To be sure, you must measure.

What if x is negative? Are the results of x/8 vs. x>>3 the same across
your problem space?

>
>Is this generally a good optimisation to use?

Generally, no. 

Generally, the result can depend on the value range of x and the
architecture of your target. Generally, writing code this way is
called 'premature optimization'. Write code to say what you mean, let
the compiler do it's job regarding the details of the translation.
Obtain correct results first, then turn on optimizations and test the
code again.

>
>Also I've got a memory region that I constantly need to access, so I 
>would like it to be in cache. I know that I can use 'register' in 
>variable declarations, to speed up it's access. But if I have a pointer 
>to that mem. region and I declared it 'register' I will get faster access 
>to the pointer, not to the mem. region it points to, isn't it? What is 
>the way out of this paradox?

Declaring 'register' is a hint to the compiler, it's free to disregard
it if it wants. A 'region' can never be in register, you are correct.
Any decent, state-of-the-art compiler will know more than you about
how to optimize for this. What compiler and what version are you
using?

The way out of this paradox is to select a state-of-the-art compiler
for your target platform. What compiler and version are you using?

[toc] | [prev] | [next] | [standalone]

#16797

On Feb 4, 10:30 pm, Raj Pashwar <raj121...@hotmail.NOSPAM.com> wrote:

> Is this generally a good optimisation to use?

Here's the most important thing about optimisation: Any attempt at
optimisation is completely pointless unless you measure first how much
time your program spends in which part of the program. What you are
doing now is based on pure guesswork. And I can promise you that if
your program is too slow now, replacing x / 8 with x >> 3 isn't going
to help you.

Most of the time, programs are made faster by finding the bits where
you are doing completely stupid things that waste time, and stop doing
them. Next, you look for things where you do unnecessary work, and
stop doing that. These things are the most important optimisations,
and you'll never do them unless you _measure_.

Once your program is in a state where it doesn't do anything stupid,
and is still too slow: Google for "cache friendly programming". In
2012, that is the most important thing you need to know to make code
fast. Most important, if your code is not "cache friendly" then no
optimisation is going to make the slightest difference to speed.

[toc] | [prev] | [next] | [standalone]

#16798

On Feb 4, 11:37 pm, "christian.bau" <christian....@cbau.wanadoo.co.uk>
wrote:


> Here's the most important thing about optimisation: Any attempt at
> optimisation is completely pointless unless you measure first how much
> time your program spends in which part of the program.

I known this is the received wisdom, if not the dogma. But it isn't
actually true. Yes it's a good idea to measure. But then pressing the
"run" button and counting heartbeats until the answer appears is a
measurement. And sometimes a good-enough one.

You /can/ improve the performance of a program without measuring all
the different bits. I know I've done it (tweaking a hash calculation
resulted in a massive performance improvement). Sometimes educated
guess-work /is/ good enough.

So, yes, the advice should read "any attempt at optimisation should be
guided by careful measurement of parts of the program". But your
"completly pointless" comment is just hyperbole that does more harm
than good.


> What you are
> doing now is based on pure guesswork. And I can promise you that if
> your program is too slow now, replacing x / 8 with x >> 3 isn't going
> to help you.
>
> Most of the time, programs are made faster by finding the bits where
> you are doing completely stupid things that waste time, and stop doing
> them. Next, you look for things where you do unnecessary work, and
> stop doing that. These things are the most important optimisations,
> and you'll never do them unless you _measure_.
>
> Once your program is in a state where it doesn't do anything stupid,
> and is still too slow: Google for "cache friendly programming". In
> 2012, that is the most important thing you need to know to make code
> fast. Most important, if your code is not "cache friendly" then no
> optimisation is going to make the slightest difference to speed.

[toc] | [prev] | [next] | [standalone]

#16845

Nick Keighley <nick_keighley_nospam@hotmail.com> wrote:
> 
> You /can/ improve the performance of a program without measuring all
> the different bits. I know I've done it (tweaking a hash calculation
> resulted in a massive performance improvement). Sometimes educated
> guess-work /is/ good enough.

Sometimes, but not very often.  I've done a lot of performance
improvement over the years and have found that the bottlenecks
are very rarely where you expect them to be.
-- 
Larry Jones

When I want an editorial, I'll ASK for it! -- Calvin

[toc] | [prev] | [next] | [standalone]

#16799

On Feb 4, 10:30 pm, Raj Pashwar <raj121...@hotmail.NOSPAM.com> wrote:

> My current program runs too slow.

how do you know?


> It uses x/8 and x%8 many times, where x
> is an int in both cases.
>
> I have replaced x/8 with x>>3, as this is faster (pretty sure).

and? Does it go any faster. I'd bet not.

> However, I am not sure whether this is faster than x%8 :
> x-=(x>>3)<<3;

measure it

> Is this generally a good optimisation to use?

dunno. What does your measurement tell you?

> Also I've got a memory region that I constantly need to access, so I
> would like it to be in cache. I know that I can use 'register' in
> variable declarations, to speed up it's

that's "its"

> access. But if I have a pointer
> to that mem. region and I declared it 'register' I will get faster access
> to the pointer, not to the mem. region it points to, isn't it? What is
> the way out of this paradox?

I see no paradox. Look up what "paradox" means. It doesn't mean "I
wish the laws of physics were different"

[toc] | [prev] | [next] | [standalone]

#16805

On Saturday, February 4, 2012 2:30:54 PM UTC-8, Raj Pashwar wrote:
> Hello :
> 
> My current program runs too slow. It uses x/8 and x%8 many times, where x 
> is an int in both cases.
> 
> I have replaced x/8 with x>>3, as this is faster (pretty sure).
> However, I am not sure whether this is faster than x%8 :
> x-=(x>>3)<<3;

"x & 7" and "x % 8" are logically equivalent for unsigned integers. The former has a chance of being faster. I need to check the definition for the residue of a negative number of a positive one, but, a reasonable definition makes "x & 7" work for one's complement implementations of negative numbers as well. It would be very reasonable to define -1 % 8 as === 7.

[toc] | [prev] | [standalone]

Page 2 of 2 — ← Prev page 1 [2]

Back to top | Article view | comp.lang.c

csiph-web