Posted on 2008-10-02
Medium Priority
Last Modified: 2013-12-10
Q1) What is exact meaning of CPU time and Wall time? When I am checking for the performance of the algorithm which one should be used?

Q2) For example in the below code,

//partial code begins here
before_time = (long) time(NULL);
before_clock = (double) clock();

//Matrix Multiplication
for (i = 0; i < ROW_A ; i++){
        for (j = 0; j < COL_B; j++){
           sum = 0;
                for (k = 0; k < COL_A; k++)
                        sum += A[i][k] *B[k][j];
                C[i][j] = sum;
after_time = (long) time(&before_time);
after_clock = (double) clock();

is that
CPU time = after_clock - before_clock
Wall time = after_time - before_time

kindly clarify me.
Question by:thirst4truth
  • 3
  • 3
LVL 85

Expert Comment

ID: 22627091
LVL 18

Accepted Solution

Jose Parrot earned 1000 total points
ID: 22627202
To measure the algorithm performance you should use CPU time by calling clock().
Wall time is the total time including other things not related to the algorithm, most related to the Operating System and services around: refreshing, pooling, window looping, graphics pipeline, swapping, garbage collection.
This is why Wall Time > CPU time.
LVL 111

Assisted Solution

by:Ray Paseur
Ray Paseur earned 1000 total points
ID: 22642005
CPU time is typically processor-only time - ie: the time spent executing code.  Wall clock time is just that - watch the program run and time it with an external clock.

In the code example you posted, if the processor is relatively lightly loaded, the CPU time and Wall Clock time (also called Elapsed Time) are likely to be nearly the same.  Wall clock time will tend to exceed CPU time when the processor is heavily loaded, and gives your programs only small slices of the available CPU.  Wall time will also exceed CPU time when the algorithm does lots of I/O operations.  Whereas CPU time is measured in nanoseconds, I/O service time is measured in milliseconds.

Best regards, ~Ray
Free Tool: Subnet Calculator

The subnet calculator helps you design networks by taking an IP address and network mask and returning information such as network, broadcast address, and host range.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

LVL 18

Expert Comment

by:Jose Parrot
ID: 22646370
Some few clarifications:
1. Wall clock does'nt tend to surpass CPU time. The first is allways bigger than CPU time, despite the computing load.
2. The CPU gives small slices of availabity only if there are others running heavy programs. The common condition in Windows PCs is the CPU to be 90% or more available to be used by your own program. Check it by doing Ctrl-Alt-Del and see at  Process tab how much is the System Idle Process. So the CPU gives most of its slices of time to the program.
3. CPU time isn't measured in nanoseconds. The motherboard circuitry isn't capable of so small time resolution.
4. The clock() function, used to measure CPU time, returns a determinated number of ticks to complete 1 second. The CLOCKS_PER_SEC macro result is such number. If you need CPU time in milliseconds, should find the difference of two clock() results, divide by CLOCKS_PER_SEC and multiply by 1000.
5. If the algorithm does lots of I/O operations which are part of the algorithm, they should be considered in the algorithm time. If I/O operations are performed without explicit calling by your algorithm then it must be not considered. Example: your program works with huge arrays, you don't have enough memory to store them and the the Operating System is forced to map some memory in the disk. In this example, CPU time and wll time will be considerably different.
6. I/O services aren't measured in milliseconds. Disk R/W operations are measured in MB/s; ethernet operations are measured in Mbps, serial port I/O is measured in baud. In any of these cases, the time is calculated in function of the rates and the amount of Bytes, bits or blocks, dependindg on the protocol.
LVL 111

Expert Comment

by:Ray Paseur
ID: 22650047
Jose: Very exhaustive explanation, thanks.  It includes a lot of assumptions, as must any answer to such a broad question.  

To your point 1, one's ability to discern whether wall clock time exceeds CPU time will be dependent on the method and accuracy of measurement.  It may be noticeably different or imperceptibly different.  It may also be not meaningfully different, as in an algorithm that does nothing but loop the CPU.  

To your point 3, the motherboard's ability to resolve time has nothing to do with cycle speed.  Modern processors work within nanosecond tolerances.  You can look it up.

To your point 6, you might want to go back to my post that "I/O service time" - which is not the same as data transfer - is measured in milliseconds, at least by those who understand measurement of these things.  The point is that data access from even the fastest disk is orders of magnitude slower than data access from processor cache or electronic memory.
LVL 18

Expert Comment

by:Jose Parrot
ID: 22654338
In overview, I agree with all 3 points you have post a comment to.
What I have noticed is that all the author seeks is for an understanding on these two measurement methods and what is the adequate one to check the performance of an algorithm.
About point 1, yes, the times can be so closer that seems to be equal. But in absolute terms, the time spent by the operating system (including the clock() system call itself) isn't part of the algorithm, so should be discounted from wall time.
About point 3, we must consider that different computers and operating systems vary wildly in how they keep track of CPU time. Anyway, clock() function isn't a time counter, but a tick counter instead, say, how many clock cycles occurred between calls to it. Example: in a 2 GHz Pentium there are 2*10^9 clocks per second, or 0.5 nanoseconds period. But such frequency is nominal, so two clocks aren't precisely 1 nanosecond. That is why POSIX determines such precision to 1 microsecond, or 1000 nanoseconds.
About point 6, if the I/O is part of the algorithm, must be considered, despite being disk or pendrive. If I/O service time is spent by the O.S., should not be considered in the time of the algorithm.
What I think the author waits for is:
"To measure the algorithm performance you should use CPU time by calling clock()".
When we look for time complexity, as in big O notation, the absolute time isn't relevant, what matters is how much a given algorithm time grows: O(n)? O(log n)? O(2^n)?
To such purpose, the number of tick clocks is good enough.
LVL 111

Expert Comment

by:Ray Paseur
ID: 22863422
@compfixer101: I think Jose and I answered the original question.  Any reason why we should not have a split of the points?  No big deal, just asking. Thanks, ~Ray

Featured Post

Free Tool: SSL Checker

Scans your site and returns information about your SSL implementation and certificate. Helpful for debugging and validating your SSL configuration.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

Join & Write a Comment

Article by: Nadia
Suppose you use Uber application as a rider and you request a ride to go from one place to another. Your driver just arrived at the parking lot of your place. The only thing you know about the ride is the license plate number. How do you find your U…
On Beyond Tools A conversation I recently had with the DevOps manager of a major online retailer really made me think about DevOps monitoring tools (https://www.onpage.com/devops-incident-management-tool/). The manager and I discussed how sever…
I've attached the XLSM Excel spreadsheet I used in the video and also text files containing the macros used below. https://filedb.experts-exchange.com/incoming/2017/03_w12/1151775/Permutations.txt https://filedb.experts-exchange.com/incoming/201…
Watch the video to learn how one can deal with PST file corruption issue with an outstanding Kernel for Outlook PST Repair Tool easily. Using this tool, non-technical users can swiftly perform the repair process to restore their essential data witho…

589 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question