Is there a better way to benchmark a C program than timing?

Question

I'm coding a little program that has to sort a large array (up to 4 million text strings). Seems like I'm doing quite well at it, since a combination of radixsort and mergesort already cut the original q(uick)sort execution time in less than half.

Execution time being the main point, since this is what I'm using to benchmark my piece of code.

My question is:

Is there a better (i. e. more reliable) way of benchmarking a program than just time the execution? It kinda works, but the same program (with the same background processes running) usually has slightly different execution times if run twice.

This kinda defeats the purpose of detecting small improvements. And several small improvements could add up to a big one...

Thanks in advance for any input!

Results:

I managed to get gprof to work under Windows (using gcc and MinGW). gcc behaves poorly (considering execution time) compared to my normal compiler (tcc), but it gave me quite some insight.

@delnan: yes, because tools for detailed profiling are language-specific. Prolog's `time/1` and IPython's `timeit` don't work their magic on C programs :) — Fred Foo, Sep 17 '11 at 16:23
How to time properly: http://stackoverflow.com/questions/2349776/how-can-i-benchmark-c-code-easily — Ciro Santilli OurBigBook.com, Jun 29 '15 at 14:01
http://stackoverflow.com/questions/375913/what-can-i-use-to-profile-c-code-in-linux — Ciro Santilli OurBigBook.com, Jun 29 '15 at 14:03

score 11 · Accepted Answer · answered Sep 17 '11 at 16:21

11

Try a profiling tool, that will also show you where the program is spending its time. gprof is the classic C profiling tool, at least on Unix.

answered Sep 17 '11 at 16:21

Fred Foo

355,277
75
744
836

2

+1 for the idea. I would recommend Valgrind's Callgrind over gprof. If you're on KDE, Valgrind and Callgrind both have a nice gui front-end but I can't remember the name. – San Jacinto Sep 17 '11 at 16:28
@San: You probably mean `kcachegrind`, and yes, it is an excellent tool. – Benjamin Bannier Sep 17 '11 at 16:31

score 3 · Answer 2 · answered Sep 17 '11 at 16:23

3

Look at the time command. It tracks both the CPU time a process uses and the wall-clock time. You can also use something like gprof for profiling your code to find the parts of your program that are actually taking the most time. You could do a lower-tech version of profiling with timers in your code. Boost has a nice timer class, but it's easy to roll your own.

answered Sep 17 '11 at 16:23

David Nehme

21,379
8
78
117

Is there an equivalent of Linux's time for Windows? – Dennis Sep 17 '11 at 16:53
1

Apparently there is something like that in windows. The first answer to this [question](http://stackoverflow.com/questions/673523/how-to-measure-execution-time-of-command-in-windows-command-line) – David Nehme Sep 17 '11 at 17:18

score 2 · Answer 3 · answered Sep 17 '11 at 16:30

I don't think it's sufficient to just measure how long a piece of code takes to execute. Your environment is a constantly changing thing, so you have to take a statistical approach to measuring execution time.

Essentially you need to take N measurements, discard outliers, and calculate your average, median and standard deviation running time, with an uncertainty measurement.

Here's a good blog explaining why and how to do this (with code): http://blogs.perl.org/users/steffen_mueller/2010/09/your-benchmarks-suck.html

Jens · Answer 4 · 2011-09-17T16:30:09.157

1

What do you use for timing execution time so far? There's C89 clock() in time.h for starters. On unixoid systems you might find getitimer() for ITIMER_VIRTUAL to measure process CPU time. See the respective manual pages for details.

You can also use a POSIX shell's times utility to benchmark the processor time used by a process and its children. The resolution is system dependent, like just anything about profiling. Try to wrap your C code in a loop, executing it as many times as necessary to reduce the "jitter" in the time the benchmarking reports.

edited Sep 17 '11 at 16:30

answered Sep 17 '11 at 16:24

Jens

69,818
15
125
179

I'm using clock(). The odd thing is that it sometimes gives me milliseconds, sometimes it rounds to 10s... – Dennis Sep 17 '11 at 16:56
Do you divide by `CLOCKS_PER_SEC` to get the value in seconds? – Jens Sep 17 '11 at 17:31

Paul R · Answer 5 · 2011-09-17T16:38:01.590

1

Call your routine from a test harness, whereby it executes N + 1 times. Ignore the timing for the first iteration and then take the average of iterations 1..N. The reason for ignoring the first time is that is is often slightly inflated due to various effects, e.g. virtual memory, code being paged in, etc. The reason for averaging N iterations is that you get rid of artefacts caused by other processes, the scheduler, etc.

If you're running on Linux or similar You might also want to use taskset to pin your code to a specific CPU core (assuming it's single-threaded), ideally not core 0, since this tends to handle all interrupts.

edited Sep 17 '11 at 16:38

answered Sep 17 '11 at 16:26

Paul R

208,748
37
389
560

I'll try the iterations. Is there an equivalent of taskset for Windows? – Dennis Sep 17 '11 at 16:58
@Dennis: sorry - I don't do Windows - I believe there's some kind of CPU affinity API in recent versions of Windows but there's probably no command line tool, unless perhaps cygwin or similar has one. – Paul R Sep 17 '11 at 21:10

Is there a better way to benchmark a C program than timing?

5 Answers5

Linked