Ting

• Predicted hours: 5
• Actual hours: 6

• Predicted hours: 5
• Actual hours: 6

• Predicted hours: 4
• Actual hours: 4

• Predicted hours: 4
• Actual hours: 6
• Execution time: 0.936s
• Rank: 281

gprof is a useful profiling utility to help speed up your program by telling how how many calls to each function and how long each call lasts.

If you’re on a Linux machine you already have gprof installed, and can always refer to the man pages for more info.

The concise version:

1. When compiling code use the -pg option.

g++ main.cpp -o main.app -pg -O2

2. Run the program piping input and output.

./main.app <in >/dev/null

3. Run gprof to analyze the results.

gprof ./main.app

More after the break.

Continue reading ‘gprof Primer’

• Predicted hours: 5
• Actual hours: 10
• Execution time: 0.016 - 0.024s
• Rank: 31

Since we’ve already done this project in Software Engineering last semester, it was just a matter of redoing it in C++.

One major difference is in the Python version my partner and I just cached 10M primes into memory from a file for fast lookup, but the 40KB UVA constraints limit this.  I tried adding in a small, pre-cached primes array but I was unable to get any meaningful cache size into 40KB outside of the first 3612 primes.  I eventually worked around it by implementing my on bit vector.

• Predicted hours: 4
• Actual hours: 6
• Execution time: 0.040s
• Rank: 1106

Progress went something like this:

1. naive (recursion): 0.892
2. naive (iteration): 0.736
3. naive + math tweaks: 0.716
4. lazy cache: 0.224
5. lazy + meta cache: 0.128
6. eager: 0.040

Had I known UVA would only test again the first 150k numbers or so I would’ve started with eager to begin with.  I started with the lazy cache because I had anticipated an extremely sparse cache with fairly randomized hits.

Raleigh implemented the meta-cache initially at 1000-sized slices.  He reduced the slice down to 200 or so before not seeing any performance increases.

With the eager cache it was just a matter of playing with the cache size.  I started at 1M (0.364s) and worked down to 100k (0.040s) before the times started increasing again.