Quantcast

Got Homework?

Connect with other students for help. It's a free community.

  • across
    MIT Grad Student
    Online now
  • laura*
    Helped 1,000 students
    Online now
  • Hero
    College Math Guru
    Online now

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

agdgdgdgwngo Group Title

So I've got a simple C program that runs in 40 milliseconds on my x86 (1.6GHz Intel Atom). 40 milliseconds is not fast enough for me; I want it to happen in under 10 milliseconds. How do I optimize my C code? What are the sequence of steps that a programmer takes when optimizing code? How do I profile my program and find out what parts I need to refactor/ use a better algorithm, etc.

  • 2 years ago
  • 2 years ago

  • This Question is Closed
  1. agdgdgdgwngo Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    so far all i've done is use gcc -O2 . what else can i do to optimize my program to run in my calculator?

    • 2 years ago
  2. nick67 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    did you try with this ? -Ofast "Disregard strict standards compliance. -Ofast enables all -O3 optimizations. It also enables optimizations that are not valid for all standard compliant programs. It turns on -ffast-math and the Fortran-specific -fno-protect-parens and -fstack-arrays."

    • 2 years ago
  3. adhokshaj Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Will you please provide the source code, so that I can have a look on it? You should not depend blindly on optimizations provided by compilers. Before optimizations, know when to optimize, what to optimize, and how to optimize. To answer first problem, if performance improvement is significant without TOOOOOOOOOO MUCH headach, go for it! To answer second problem, use a profiler. It will show you where most of the processing time is consumed in your program. Optimize that part first. For third one, you may use a better algorithm, or employ some *trikcy* fast solutions. It depends upon the case.

    • 2 years ago
  4. agdgdgdgwngo Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    I just tried -Ofast with no luck :( still giving me about 40 milliseconds. here is th e source: #include "prog.h" int main(int argc, char *argv[]) { switch (argc) { case 1: solve_from_stdin(); break; default: return -1; break; } return 0; }

    • 2 years ago
  5. adhokshaj Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Please provide prog.h as well! In case you are working on some secret project, you may use profiler(s) or ask other project members.

    • 2 years ago
  6. nick67 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    which way are you measuring the time ?

    • 2 years ago
  7. agdgdgdgwngo Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    bash's builtin time command

    • 2 years ago
  8. nick67 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    did you try removing anything else but the pure main to have the minimum execution time ?

    • 2 years ago
  9. agdgdgdgwngo Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    this is what prog.h looks like #ifndef _PROG_H_ #define _PROG_H_ unsigned int a(int *, int *, const unsigned int, const unsigned int); unsigned int b(int *, int *, const unsigned int, const unsigned int, const unsigned int); unsigned int c(int *, const unsigned int); void solve_from_stdin(void); #endif /* ifndef _PROG_H_ */ what prfiler should i use?

    • 2 years ago
  10. adhokshaj Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    AMD APP Profiler is a free C/C++ Profiler

    • 2 years ago
  11. adhokshaj Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Intel Parallel Studio also contains a profiler.

    • 2 years ago
  12. nick67 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    In the header file you just have declarations, not definitions, so nobody can understand what the code really does; but could you try to execute a main() without the function call and report the measured execution time ? #include "prog.h" int main(int argc, char *argv[]) { switch (argc) { case 1: // solve_from_stdin(); break; default: return -1; break; } return 0; }

    • 2 years ago
  13. agdgdgdgwngo Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    but those kits are both exclusive to Windows/visual studio :( without the solve_from_stdin(), time outputs 0.000 :-D so that one routine is taking 99.9% of cpu time :D

    • 2 years ago
  14. adhokshaj Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Intell Parallel Studio is available for LINUX as well.

    • 2 years ago
  15. agdgdgdgwngo Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    that's awesome I'll check my package manager then

    • 2 years ago
  16. agdgdgdgwngo Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    alright I have intel parallel studio xe in my package manager

    • 2 years ago
  17. nick67 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    ok, now reactivate the call to the function but eliminate any action in the function body, then go on reactivating part of the code in the function body until you can understand which part is taking more execution time

    • 2 years ago
  18. nick67 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    old times profiling style :-)

    • 2 years ago
  19. agdgdgdgwngo Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    okay I deactivated procedure a() and I'm also getting 0.000 from bash

    • 2 years ago
  20. agdgdgdgwngo Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    but procedure a() calls procedure b()

    • 2 years ago
  21. nick67 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    then reactivate procedure a() but not procedure b()

    • 2 years ago
  22. agdgdgdgwngo Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    that decreased my time from 40 to 22 ms

    • 2 years ago
  23. nick67 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    does procedure a() do anything else apart calling procedure b() ?

    • 2 years ago
  24. agdgdgdgwngo Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    procedure a also calls itself before calling procedure b

    • 2 years ago
  25. nick67 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    it sounds strange, it should loop forever, unless there is some kind of counter to avoid it

    • 2 years ago
  26. agdgdgdgwngo Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    yeah at the start it tests for the value of (const int $1 + const int $2) / 2

    • 2 years ago
  27. nick67 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    is the function solve_from_stdin() recursive ?

    • 2 years ago
  28. agdgdgdgwngo Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    here's procedure b() void merge_int(int* left, unsigned int len_left, int* right, unsigned int len_right, int* end) { unsigned int i, j, k; for (i = j = k = 0; i < len_left && j < len_right; ++k) { if (left[i] < right[j]) { end[k] = left[i]; ++i; } else { end[k] = right[j]; ++j; } } for (; i < len_left; ++i, ++k) { end[k] = left[i]; } for (; j < len_right; ++j, ++k) { end[k] = right[j]; } }

    • 2 years ago
  29. nick67 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    is the b() procedure called just once in the a() procedure ?

    • 2 years ago
  30. agdgdgdgwngo Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    right just once

    • 2 years ago
  31. agdgdgdgwngo Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    but since a() calls itself recursively, it ends up calling b quite a lot of times :)

    • 2 years ago
  32. nick67 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    if so you could try to directly write the b() procedure's content into the a() procedure body, so that you save one function call time (context saving time into the stack)

    • 2 years ago
  33. agdgdgdgwngo Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    I got a seg fault :(

    • 2 years ago
  34. nick67 Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    did you use correct types for left, right, end variables ?

    • 2 years ago
  35. agdgdgdgwngo Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    alright I'm going to refurbish my code and use a different data structure and see how it goes...

    • 2 years ago
    • Attachments:

See more questions >>>

Your question is ready. Sign up for free to start getting answers.

spraguer (Moderator)
5 → View Detailed Profile

is replying to Can someone tell me what button the professor is hitting...

23

  • Teamwork 19 Teammate
  • Problem Solving 19 Hero
  • You have blocked this person.
  • ✔ You're a fan Checking fan status...

Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.