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

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

efficient or clever way

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

Contents

  efficient or clever way "dr.oktopus" <blindwilly@freeonline.zzn.com> - 2011-06-06 01:29 -0700
    Re: efficient or clever way China Blue Angels <chine.bleu@yahoo.com> - 2011-06-06 02:12 -0700
      Re: efficient or clever way Chris H <chris@phaedsys.org> - 2011-06-06 12:50 +0100
        Re: efficient or clever way "Kleuskes & Moos" <kleuske@xs4all.nl> - 2011-06-06 11:38 -0700
      Re: efficient or clever way Anand Hariharan <mailto.anand.hariharan@gmail.com> - 2011-06-08 13:48 -0700
        Re: efficient or clever way China Blue Angels <chine.bleu@yahoo.com> - 2011-06-08 16:16 -0700
        Re: efficient or clever way "christian.bau" <christian.bau@cbau.wanadoo.co.uk> - 2011-06-12 01:10 -0700
    Re: efficient or clever way pete <pfiland@mindspring.com> - 2011-06-06 08:21 -0400
      Re: efficient or clever way Voice Of Truth <oops@uhm.wow> - 2011-06-06 20:48 +0200
        Re: efficient or clever way Keith Thompson <kst-u@mib.org> - 2011-06-06 11:55 -0700
          Re: efficient or clever way Voice Of Truth <oops@uhm.wow> - 2011-06-06 20:58 +0200
        Re: efficient or clever way pete <pfiland@mindspring.com> - 2011-06-06 19:10 -0400
          Re: efficient or clever way Voice Of Truth <oops@uhm.wow> - 2011-06-07 05:54 +0200
    Re: efficient or clever way cri@tiac.net (Richard Harter) - 2011-06-06 15:13 +0000
    Re: efficient or clever way Keith Thompson <kst-u@mib.org> - 2011-06-06 09:35 -0700
    Re: efficient or clever way Jorgen Grahn <grahn+nntp@snipabacken.se> - 2011-06-08 20:34 +0000

#5548 — efficient or clever way

Hello,
walking an array is a common construct in programming.
In C language, I see two common practises.

1:

for (p = array, pend = array + size ; p < pend ; ++p)
/* do something */

2:

count = size;
p = array;
while (count--) {
/* do something here */
++p;
}

In complex contests, keeping a count variable could
be more readable (IMO) than having a variable acting
as a sentinel for the array bound (I'm speking of pieces
of codes where array navigation is not from the start
to the end, or inside Duff's devices, for example).
My question is: is this code really inefficient than
first approach (since it has to dec a variable every
cycle, more than test it) or current cpus could handle a sort
of decrement and test instr that do it all at the same time?
Thanks,
                  wily

[toc] | [next] | [standalone]

#5552

> My question is: is this code really inefficient than
> first approach (since it has to dec a variable every
> cycle, more than test it) or current cpus could handle a sort
> of decrement and test instr that do it all at the same time?

Think of it these terms: the difference is maybe one cycle per loop, or a few 
more if it goes to cache. Your post has been propagated on millions of computers 
using a considerable number of cycles worldwide. In all likelihood the possible 
savings from a correct answer will never be more than fraction of the cost of 
asking the question.

For code like this far more energy will be spent on other people trying to 
figure out why you did that than actually executing it. So you should choose the 
clearest, most obvious coding.

The place where you should put your work are in things like converting an O(n^2) 
program to O(n log n) or even O(n). These kinds of changes are more likely to 
have a long term pay off.

Compilers are good at scrubbing out extraneous cycles from the code you wrote. 
They're really bad at rewriting an algorithm to save an order of 
complexity--that's for humans to do.

-- 
I remember finding out about you,  |              I survived XYZZY-Day.
Everyday my mind is all around you,|     I'm whoever you want me to be.
Looking out from my lonely room    |Annoying Usenet one post at a time.
Day after day.                     |  At least I can stay in character.

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

#5556

In message <chine.bleu-C1538A.02122706062011@news.eternal-
september.org>, China Blue Angels <chine.bleu@yahoo.com> writes
>> My question is: is this code really inefficient than
>> first approach (since it has to dec a variable every
>> cycle, more than test it) or current cpus could handle a sort
>> of decrement and test instr that do it all at the same time?
>
>Think of it these terms: the difference is maybe one cycle per loop, or a few
>more if it goes to cache. Your post has been propagated on millions of
>computers
>using a considerable number of cycles worldwide. In all likelihood the
>possible
>savings from a correct answer will never be more than fraction of the cost of
>asking the question.

I like that thought.

>Compilers are good at scrubbing out extraneous cycles from the code you wrote.
>They're really bad at rewriting an algorithm to save an order of
>complexity--that's for humans to do.

This is also true....

I find a lot of programmers spend time shaving cycles off functions
whereas the problem is the higher level design.

-- 
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
\/\/\/\/\ Chris Hills  Staffs  England     /\/\/\/\/
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/

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

#5576

On Jun 6, 1:50 pm, Chris H <ch...@phaedsys.org> wrote:
> In message <chine.bleu-C1538A.02122706062...@news.eternal-
> september.org>, China Blue Angels <chine.b...@yahoo.com> writes
>
> >> My question is: is this code really inefficient than
> >> first approach (since it has to dec a variable every
> >> cycle, more than test it) or current cpus could handle a sort
> >> of decrement and test instr that do it all at the same time?
>
> >Think of it these terms: the difference is maybe one cycle per loop, or a few
> >more if it goes to cache. Your post has been propagated on millions of
> >computers
> >using a considerable number of cycles worldwide. In all likelihood the
> >possible
> >savings from a correct answer will never be more than fraction of the cost of
> >asking the question.
>
> I like that thought.

"premature optimization is the root of all evil", Donald Knuth.

But i might steal the above quote, too.

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

#5658

On Jun 6, 4:12 am, China Blue Angels <chine.b...@yahoo.com> wrote:
(...)
> The place where you should put your work are in things like converting an O(n^2)
> program to O(n log n) or even O(n). These kinds of changes are more likely to
> have a long term pay off.
>

Do you know of instances where a program that had a quadratic
complexity was changed/rewritten to have a linear complexity?

- Anand

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

#5667

In article <7c9ca0fa-22da-4090-addd-aaef443f715c@r35g2000prj.googlegroups.com>,
 Anand Hariharan <mailto.anand.hariharan@gmail.com> wrote:

> On Jun 6, 4:12 am, China Blue Angels <chine.b...@yahoo.com> wrote:
> (...)
> > The place where you should put your work are in things like converting an 
> > O(n^2)
> > program to O(n log n) or even O(n). These kinds of changes are more likely 
> > to
> > have a long term pay off.
> >
> 
> Do you know of instances where a program that had a quadratic
> complexity was changed/rewritten to have a linear complexity?

Do you mean like Tarjan's strongly connected regions?

-- 
I remember finding out about you,  |              I survived XYZZY-Day.
Everyday my mind is all around you,|     I'm whoever you want me to be.
Looking out from my lonely room    |Annoying Usenet one post at a time.
Day after day.                     |  At least I can stay in character.

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

#5892

On Jun 8, 9:48 pm, Anand Hariharan <mailto.anand.hariha...@gmail.com>
wrote:

> Do you know of instances where a program that had a quadratic
> complexity was changed/rewritten to have a linear complexity?

I recently changed some code from O (n^3) to O (n). Nobody had noticed
until I tried instances with n = 500.

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

#5557

dr.oktopus wrote:
> 
> Hello,
> walking an array is a common construct in programming.
> In C language, I see two common practises.
> 
> 1:
> 
> for (p = array, pend = array + size ; p < pend ; ++p)
> /* do something */
> 
> 2:
> 
> count = size;
> p = array;
> while (count--) {
> /* do something here */
> ++p;
> }
> 
> In complex contests, keeping a count variable could
> be more readable (IMO) than having a variable acting
> as a sentinel for the array bound (I'm speking of pieces
> of codes where array navigation is not from the start
> to the end, or inside Duff's devices, for example).
> My question is: is this code really inefficient than
> first approach (since it has to dec a variable every
> cycle, more than test it) or current cpus could handle a sort
> of decrement and test instr that do it all at the same time?
> Thanks,
>                   wily

It all depends on the cpu.
Comparing two variables against each other 
may or may not be slower 
than a decrement plus a comparison against constant zero.

A decrement plus a comparison against constant zero,
is a single instruction in Microchip assembly.

-- 
pete

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

#5578

pete wrote:

> It all depends on the cpu.
> Comparing two variables against each other
> may or may not be slower
> than a decrement plus a comparison against constant zero.
>
> A decrement plus a comparison against constant zero,
> is a single instruction in Microchip assembly.


Pete, your answers are always as short as irritating. You must be
a great pole in the ass for everyone. Just for once at least, take your
answer and put it up your ass (and you are still lucky 'cause it's short).

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

#5579

Voice Of Truth <oops@uhm.wow> writes:
> pete wrote:
>> It all depends on the cpu.
>> Comparing two variables against each other
>> may or may not be slower
>> than a decrement plus a comparison against constant zero.
>>
>> A decrement plus a comparison against constant zero,
>> is a single instruction in Microchip assembly.
>
> Pete, your answers are always as short as irritating. You must be
> a great pole in the ass for everyone. Just for once at least, take your
> answer and put it up your ass (and you are still lucky 'cause it's short).

I found pete's response to be accurate, informative, and to the point.

You, on the other hand, appear to have a posting history consisting of
this one unjustified insult.  You're not getting off to a good start.

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

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

#5580

Keith Thompson wrote:

> I found pete's response to be accurate, informative, and to the point.
>
> You, on the other hand, appear to have a posting history consisting of
> this one unjustified insult.  You're not getting off to a good start.

Love you Keith, as brother of course.

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

#5590

Voice Of Truth wrote:
 
> Pete, your answers are always as short as irritating.

sfsort is my latest microoptimization of
a Leapfrogging Samplesort function
with a qsort type interface.

http://www.springerlink.com/content/p70564506802n575/

/* BEGIN sfsort.h */

#ifndef H_SFSORT_H
#define H_SFSORT_H

#include <stddef.h>

void sfsort(void *base, size_t nmemb, size_t size, 
            int (*compar)(const void *, const void *));

#endif

/* END sfsort.h */



/* BEGIN sfsort.c */

#include "sfsort.h"

static void sfrog(size_t s1, 
                  size_t ss, 
                  unsigned char *A, 
                  size_t u,
                  size_t size, 
                  int (*compar)(const void *, const void *));

void            
sfsort(void *base, size_t nmemb, size_t size, 
       int (*compar)(const void *, const void *))
{
    size_t s;

    if (nmemb > 1) {
        for (s = 1; nmemb - s > s; s += s + 1) {
            sfrog(0, s - 1, base, s + s, size, compar);
        }
        sfrog(0, s - 1, base, nmemb - 1, size, compar);
    } 
}

static void 
sfrog(size_t s1, size_t ss, 
     unsigned char *A, size_t u, size_t size, 
     int (*compar)(const void *, const void *))
{
    if (s1 - ss != 1) {
        if (u > ss) {
            unsigned char *p1, *p2, *end, swap;
            const size_t  sm = (ss - s1) / 2 + s1;
            const size_t sms = sm * size;
                  size_t   j = (u + 1) * size;
                  size_t   i = ss * size;

            do {
                i += size;
            } while (j > i && compar(A + sms, A + i) > 0);
            do {
                j -= size;
            } while (j > i && compar(A + j, A + sms) > 0);
            while (j > i) {
                p1  = A + j;
                p2  = A + i;
                end = p2 + size;
                do {
                    swap  = *p1;
                    *p1++ = *p2;
                    *p2++ = swap;
                } while (p2 != end);
                do {
                    i += size;
                } while (j > i && compar(A + sms, A + i) > 0);
                do {
                    j -= size;
                } while (j > i && compar(A + j, A + sms) > 0);
            } 
            if (j == i) {
                j -= size;
            }        
            i = ss * size;
            if (j > i) {
                end = A + sms;
                p1  = A + j + size;
                p2  = A + i + size;
                do {
                    swap = *--p2;
                    *p2  = *--p1;
                    *p1  = swap;
                } while (p2 != end);
                j /= size;
                i = sm + j - ss + 1;
                sfrog(s1, sm - 1, A, i - 2, size, compar);
            } else {
                j = ss;
                i = sm + 1;
            }
            sfrog(i, j, A, u, size, compar);
        }
    } else {
        sfsort(A + s1 * size, u - ss, size, compar);
    }
}

/* END sfsort.c */


-- 
pete

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

#5596

pete wrote:
> Voice Of Truth wrote:
>
>> Pete, your answers are always as short as irritating.
>
> sfsort is my latest microoptimization of
> a Leapfrogging Samplesort function
> with a qsort type interface.
>
> http://www.springerlink.com/content/p70564506802n575/
>
> /* BEGIN sfsort.h */
>
...
>
> /* END sfsort.c */

That is not an answer to the original poster, that's an article,
and you just proved you can copy and paste. But, I love you Pete.
Don't feed me, I'm a troll with suicidal tendencies.

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

#5563

On Mon, 6 Jun 2011 01:29:11 -0700 (PDT), "dr.oktopus"
<blindwilly@freeonline.zzn.com> wrote:

>Hello,
>walking an array is a common construct in programming.
>In C language, I see two common practises.
>
>1:
>
>for (p = array, pend = array + size ; p < pend ; ++p)
>/* do something */
>
>2:
>
>count = size;
>p = array;
>while (count--) {
>/* do something here */
>++p;
>}
>
>In complex contests, keeping a count variable could
>be more readable (IMO) than having a variable acting
>as a sentinel for the array bound (I'm speking of pieces
>of codes where array navigation is not from the start
>to the end, or inside Duff's devices, for example).
>My question is: is this code really inefficient than
>first approach (since it has to dec a variable every
>cycle, more than test it) or current cpus could handle a sort
>of decrement and test instr that do it all at the same time?

In ye olde days of yore the second form would have been more efficient
than the first.  Decrement, increment, and test against zero are all
much simpler instructions, than the compare of two pointers, which
requires a subtraction.  Many machines had a one instruction decrement
and test against zero.  In these days with modern machines and modern
compilers it's almost certainly a wash.  If there is a difference it
could be either way.

All of that said, I would write your second form like this:

for (count=size,p=array;count--;++p) {/* body */}

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

#5572

"dr.oktopus" <blindwilly@freeonline.zzn.com> writes:
> walking an array is a common construct in programming.
> In C language, I see two common practises.
>
> 1:
>
> for (p = array, pend = array + size ; p < pend ; ++p)
> /* do something */
>
> 2:
>
> count = size;
> p = array;
> while (count--) {
> /* do something here */
> ++p;
> }

There's also this:

    const size_t array_len = sizeof array / sizeof array[0];
    for (size_t i = 0; i < array_len; i ++) {
        /* do something with array[i] */
    }

An optimizing compiler is likely to generate equally good code for
any of them.

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

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

#5656

On Mon, 2011-06-06, dr.oktopus wrote:
> Hello,
> walking an array is a common construct in programming.
> In C language, I see two common practises.
>
> 1:
>
> for (p = array, pend = array + size ; p < pend ; ++p)
> /* do something */
>
> 2:
>
> count = size;
> p = array;
> while (count--) {
> /* do something here */
> ++p;
> }

Those are not common in my experience. Are you excluding the more
common forms because you believe they are less efficient?

1b:
for (Foo* p=array; p!=array+size; p++) { ... }

2b:
for (int i=0; i<size; i++) { ... }

I prefer 1b if the index is really irrelevant inside the loop. Mostly
because I use C++ a lot -- it's a common idiom there.

/Jorgen

-- 
  // Jorgen Grahn <grahn@  Oo  o.   .  .
\X/     snipabacken.se>   O  o   .

[toc] | [prev] | [standalone]

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

csiph-web