Need Help with a program in C

Re: Need Help with a program in C

Post by thetan on Sun Dec 05, 2010 10:43 pm
([msg=50095]see Re: Need Help with a program in C[/msg])

Arameus wrote:When you do print char * i, it doesn't call print 6 times. It means print (char * i), so it evaluates char * i and prints that.

huh? where'd that come from?

Arameus wrote:I'm gonna be honest here, Thetan, you are throwing some pretty big words my way and I don't know what a good portion of them refer to.

What would you like me to elaborate on?

Also, on second though, omitting the IO in the previous benchmark wouldn't be fair either as that is the significant constraint. hmmmm........
"If art interprets our dreams, the computer executes them in the guise of programs!" - SICP

Image

“If at first, the idea is not absurd, then there is no hope for it” - Albert Einstein
User avatar
thetan
Contributor
Contributor
 
Posts: 657
Joined: Thu Dec 17, 2009 6:58 pm
Location: Various Bay Area Cities, California
Blog: View Blog (0)


Re: Need Help with a program in C

Post by Arameus on Sun Dec 05, 2010 10:52 pm
([msg=50097]see Re: Need Help with a program in C[/msg])

huh? where'd that come from?


You were saying that function calls are super expensive, so I assumed you thought the code I posted called print more than if you had used a string.

What would you like me to elaborate on?


You're fine dude, it was just an excuse for if my reply was somehow terribly inapplicable to what you said. I use the "type stuff and hope it works" method in my programming, which actually works a surprising amount of the time. Are you a professional developer btw? Cause I am going to bombard you with questions if you are.
Arameus
New User
New User
 
Posts: 36
Joined: Mon Feb 01, 2010 6:53 pm
Location: Ballston Spa, NY
Blog: View Blog (0)


Re: Need Help with a program in C

Post by thetan on Sun Dec 05, 2010 11:03 pm
([msg=50100]see Re: Need Help with a program in C[/msg])

Arameus wrote:You were saying that function calls are super expensive, so I assumed you thought the code I posted called print more than if you had used a string.

Oh yeah thats not what i was talking about at all. I was referring to having to call printf/print so many times within a tight loop. Function calls aren't super expensive (they're not super cheap though), they're just significantly more expensive then pushing 1 byte of data into memory. As oppose to calling printf/print just once per iteration.


Anyways so i think i got some usable benchmarks now
Code: Select all
joseph@IT:~/Testing/lab$ gcc -o stack stack.c
joseph@IT:~/Testing/lab$ gcc -o loopdeloop loopdeloop.c
joseph@IT:~/Testing/lab$ time ./loopdeloop

real   0m1.113s
user   0m0.760s
sys   0m0.040s
joseph@IT:~/Testing/lab$ time ./stack

real   0m0.109s
user   0m0.060s
sys   0m0.000s
joseph@IT:~/Testing/lab$


Sources are as follows:
Code: Select all
#include <stdio.h>
#include <stdlib.h>

void loopdeloop(char c, int m)
{
    int i, j, k;
   
    for (i = 0; i < m; i++)
    {
        for (j = -1; j < i; j++) k += 1;
    }
}

int main (int argc, char *argv[])
{
    int i;
   
    for (i = 0; i < 99999; i++) loopdeloop('a', 75);
   
    return 0;
}

&&
Code: Select all
#include <stdio.h>
#include <stdlib.h>

void stack(char c, int m)
{
    char s[512];
    int i, j;
   
    // impose arbitrary stack limit
    if (m >= 512) return;
   
    for (i = 0; i < m;)
    {
        s[i] = c;
        s[++i] = '\0';
    }
}

int main (int argc, char *argv[])
{
    int i;
   
    for (i = 0; i < 99999; i++) stack('a', 75);
   
    return 0;
}


So as i predicted, the looping in a loop is significantly slower.

Why is it slower though? because looping (and any kind of conditional branching) is somewhat of a slow operation. CPUs have fairly advanced branch prediction algorithms these days, however, when the algorithm slips (which is easy to do when you have tight loops within tight loops) the CPU basically has to discard it's pipeline of already computed operations (yeah CPUs actually perform operations out of order in a predictive manner)

EDIT:
Are you a professional developer btw? Cause I am going to bombard you with questions if you are.

Yes i am.
"If art interprets our dreams, the computer executes them in the guise of programs!" - SICP

Image

“If at first, the idea is not absurd, then there is no hope for it” - Albert Einstein
User avatar
thetan
Contributor
Contributor
 
Posts: 657
Joined: Thu Dec 17, 2009 6:58 pm
Location: Various Bay Area Cities, California
Blog: View Blog (0)


Re: Need Help with a program in C

Post by Arameus on Sun Dec 05, 2010 11:14 pm
([msg=50104]see Re: Need Help with a program in C[/msg])

OOO HEEYYY YOU COULD APPEND TO THE STRING AND THEN PRINT IT OUT AAFFFTTEERRR THE LOOP MAN SHIT also you did "int main (int argc, char *argv[])" instead of int main(void), but then you never do anything with argc or argv. That could be making it run slightly slower?
Arameus
New User
New User
 
Posts: 36
Joined: Mon Feb 01, 2010 6:53 pm
Location: Ballston Spa, NY
Blog: View Blog (0)


Re: Need Help with a program in C

Post by thetan on Sun Dec 05, 2010 11:16 pm
([msg=50107]see Re: Need Help with a program in C[/msg])

Arameus wrote:OOO HEEYYY YOU COULD APPEND TO THE STRING AND THEN PRINT IT OUT AAFFFTTEERRR THE LOOP MAN SHIT

huh?

Arameus wrote:also you did "int main (int argc, char *argv[])" instead of int main(void), but then you never do anything with argc or argv. That could be making it run slightly slower?

Nope, that has nothing to do with performance.
"If art interprets our dreams, the computer executes them in the guise of programs!" - SICP

Image

“If at first, the idea is not absurd, then there is no hope for it” - Albert Einstein
User avatar
thetan
Contributor
Contributor
 
Posts: 657
Joined: Thu Dec 17, 2009 6:58 pm
Location: Various Bay Area Cities, California
Blog: View Blog (0)


Re: Need Help with a program in C

Post by Arameus on Sun Dec 05, 2010 11:23 pm
([msg=50109]see Re: Need Help with a program in C[/msg])

huh?


I just realized why what I said makes no sense nevermind. How are jobs for software engineers in the bay area? I am currently in school trying to get good education stuff so I can move there with my fiancee. Its our dream city :D :D

This thread is already at the top so no guilt in pointless posts.


RAKJWAKJKJDSKFRJKSDJF POINTLESS POSTS BLLAAARRRNEEEHHHHHHOOOOOOO

I AM ELZOR
Arameus
New User
New User
 
Posts: 36
Joined: Mon Feb 01, 2010 6:53 pm
Location: Ballston Spa, NY
Blog: View Blog (0)


Re: Need Help with a program in C

Post by thetan on Mon Dec 06, 2010 12:54 am
([msg=50113]see Re: Need Help with a program in C[/msg])

Ok, next to highlight my point about the overhead of function calls, i implemented a dummy_io() function thats only purpose is to do as little as possible so it highlights the overhead of function overcall and i placed it wherever an IO call was in the first implementation as it would if it were real world IO ...... just without the IO ;)

Benchmark is as follows:
Code: Select all
joseph@IT:~/Testing/lab$ gcc -o stack stack.c
joseph@IT:~/Testing/lab$ gcc -o loopdeloop loopdeloop.c
joseph@IT:~/Testing/lab$ time ./stack

real   0m0.163s
user   0m0.072s
sys   0m0.008s
joseph@IT:~/Testing/lab$ time ./loopdeloop

real   0m2.065s
user   0m1.692s
sys   0m0.016s


Wow, yeah you're reading that right, the additional function overhead added aprox 2 whole seconds (real & user) of wait time in the loopdeloop implementation.

Code is as follows:
Code: Select all
#include <stdio.h>
#include <stdlib.h>

void dummy_io(int *i)
{
    *i++;
}

void loopdeloop(char c, int m)
{
    int i, j, k;
   
    for (i = 0; i < m; i++)
    {
        for (j = -1; j < i; j++) dummy_io(&k); //print char
        dummy_io(&k); //print new line
    }
}

int main (int argc, char *argv[])
{
    int i;
   
    for (i = 0; i < 99999; i++) loopdeloop('a', 75);
   
    return 0;
}

&&
Code: Select all
#include <stdio.h>
#include <stdlib.h>

void dummy_io(int *i)
{
    *i++;
}

void stack(char c, int m)
{
    char s[512];
    int i, j;
   
    // impose arbitrary stack limit
    if (m >= 512) return;
   
    for (i = 0; i < m;)
    {
        s[i] = c;
        s[++i] = '\0';
        dummy_io(&j);
    }
}

int main (int argc, char *argv[])
{
    int i;
   
    for (i = 0; i < 99999; i++) stack('a', 75);
   
    return 0;
}



Conclusions:
+ Take advantage of IO buffering
+ Minimize nesting of loops whenever you can
+ Function calls aren't free in terms of performance
"If art interprets our dreams, the computer executes them in the guise of programs!" - SICP

Image

“If at first, the idea is not absurd, then there is no hope for it” - Albert Einstein
User avatar
thetan
Contributor
Contributor
 
Posts: 657
Joined: Thu Dec 17, 2009 6:58 pm
Location: Various Bay Area Cities, California
Blog: View Blog (0)


Re: Need Help with a program in C

Post by fabianhjr on Mon Dec 06, 2010 7:17 am
([msg=50127]see Re: Need Help with a program in C[/msg])

Thanks thetan. It is good to have you by here. :D
Donate bitcoins to me! [1DhRP3hHgmSLQdRTZyT8VPTmzAj7Z2rsGA]
Dunno what bitcoins are? BitcoinMe
fabianhjr
Poster
Poster
 
Posts: 286
Joined: Tue Sep 21, 2010 7:48 pm
Blog: View Blog (0)


Re: Need Help with a program in C

Post by tgoe on Tue Dec 07, 2010 9:18 pm
([msg=50279]see Re: Need Help with a program in C[/msg])

I hate to be that guy again but this does really bother me. If you're doing 99999 iterations of useful work, function call overhead is the least of your worries. By your posts, thetan, the cost of those function calls in terms of time is approx: 2.00002 * 10 ** -5s. So if you have a chunk of code that takes 1 second to run, turning it into a function would make that same code take about 1.00002 seconds to run with the bonus of being reusable to boot. Worrying about 0.00002 seconds is a waste of time and is premature optimization.

Code: Select all
>>> 99999 * 1
99999
>>> 99999 * 1.00002
100000.99997999999
>>> (99999 * 1.00002) - (99999 * 1)
1.9999799999932293 # about 2 seconds difference


The bigger the chunk of code is, the more likely you'll make it a function. As the chunk of code grows, function call overhead means less and less. Optimizing small functions is the job of inline and macros.
User avatar
tgoe
Contributor
Contributor
 
Posts: 639
Joined: Sun Sep 28, 2008 2:33 pm
Location: q3dm7
Blog: View Blog (0)


Re: Need Help with a program in C

Post by thetan on Tue Dec 07, 2010 11:16 pm
([msg=50283]see Re: Need Help with a program in C[/msg])

tgoe wrote:I hate to be that guy again but this does really bother me. If you're doing 99999 iterations of useful work, function call overhead is the least of your worries. By your posts, thetan, the cost of those function calls in terms of time is approx: 2.00002 * 10 ** -5s.

Some one hasn't done much work with big data and map reduce jobs that take entire days to finish .....
enough said.

tgoe wrote:So if you have a chunk of code that takes 1 second to run, turning it into a function would make that same code take about 1.00002 seconds to run with the bonus of being reusable to boot. Worrying about 0.00002 seconds is a waste of time and is premature optimization.

....
....
....

The bigger the chunk of code is, the more likely you'll make it a function. As the chunk of code grows, function call overhead means less and less. Optimizing small functions is the job of inline and macros.

the first point there is that a function makes it reusable, then you say that optimizing small functions is the job of inline keywords and macros ... which by definition aren't functions and are just abstractions for .... inlining code.

So in perfect English you're saying, don't inline code it makes code less DRY (don't repeat yourself), instead use inline abstractions. I would have to agree with that. However, this further proves my points because at the end of the day, it is inline.

Also, inline is a recommendation to the compiler, nothing more, nothing less. It's more common then not that even good optimizing compilers will disregard such keywords and forcefully not inline functions, especially in the case of recursion even when you compile with force inlining flags. Which is why i'm a fan of and avid user of macros instead.
"If art interprets our dreams, the computer executes them in the guise of programs!" - SICP

Image

“If at first, the idea is not absurd, then there is no hope for it” - Albert Einstein
User avatar
thetan
Contributor
Contributor
 
Posts: 657
Joined: Thu Dec 17, 2009 6:58 pm
Location: Various Bay Area Cities, California
Blog: View Blog (0)


PreviousNext

Return to C and C++

Who is online

Users browsing this forum: No registered users and 0 guests