Re: [SLUG] Error in Time() command
On 24 May 2010 03:41, Glen Turner g...@gdt.id.au wrote: On Sun, 2010-05-23 at 17:02 +0800, tenz...@iinet.net.au wrote: I'm seeking a preferably citeable reference to the amount of error in the returned result from a Time() command. I want to be able to quote the level of error in timing the execution speed of my project. Why don't you use http://www.eclipse.org/tptp/ if this is for java... -- SLUG - Sydney Linux User's Group Mailing List - http://slug.org.au/ Subscription info and FAQs: http://slug.org.au/faq/mailinglists.html
Re: [SLUG] Error in Time() command
On Sun, May 23, 2010 at 2:02 AM, tenz...@iinet.net.au tenz...@iinet.net.au wrote: I'm seeking a preferably citeable reference to the amount of error in the returned result from a Time() command. I want to be able to quote the level of error in timing the execution speed of my project. A reference that probably doesn't apply to you wouldn't really convince me; I would think simply showing a sane standard deviation over a reasonable number of runs would be better. You could find a lot of papers that wouldn't even give this. [1] is an example of a paper written with several timing-based results with what I think is quite readable stats (IMHO:) -i [1] ftp://ftp.cse.unsw.edu.au/pub/doc/papers/UNSW/0307.pdf -- SLUG - Sydney Linux User's Group Mailing List - http://slug.org.au/ Subscription info and FAQs: http://slug.org.au/faq/mailinglists.html
Re: [SLUG] Error in Time() command
Pretty much based on the knowledge that the MCU program counter is clocked on a 16MHz crystal (according to http://en.wikipedia.org/wiki/Quartz_clock they are generally good for 6 parts per million for standard grade crystals, whatever that is). You can use this in a number of ways. If you program it using a standard loop to read inputs, calculate and write out to say a LCD display, you should have a loop-length of known number of CPU cycles. (This is quite possible with a microcontroller as everything is in memory and as long you aren't waiting for random DMA interrupts should be quite feasible. A general purpose CPU running a mega operating system with lots of peripherals would make this task pretty much impossible). Another option is to use the built-in timer/counters (one 8 bit and one 16 bit are available) on the AVR ATmega MCU. Again clocked against the same crystal, and using a configurable frequency divider mechanism. And finally there are various dedicated real-time chips, such as DS1307, which combined with a crystal (usually 32.768KHz) can be easily interfaced if needed. These chips tend to be human-scale timers so you might have to count lots of repetitions of your loop under test and do the maths to get an average loop time (possibly limiting its usefulness). Regards, Martin martinvisse...@gmail.com On Wed, May 26, 2010 at 3:55 PM, Nick Andrew n...@nick-andrew.net wrote: On Wed, May 26, 2010 at 01:53:27PM +1000, Martin Visser wrote: (And if you don't have a scope or freq. meter) a suitably programmed Arduino or similar microcontroller could do this fairly easily for you - probably with better than 0.01% precision. How do we know the Arduino is so precise? :-) Nick. -- SLUG - Sydney Linux User's Group Mailing List - http://slug.org.au/ Subscription info and FAQs: http://slug.org.au/faq/mailinglists.html
Re: [SLUG] Error in Time() command
On Wed, May 26, 2010 at 05:52:59PM +1000, Martin Visser wrote: Pretty much based on the knowledge that the MCU program counter is clocked on a 16MHz crystal (according to http://en.wikipedia.org/wiki/Quartz_clock they are generally good for 6 parts per million for standard grade crystals, whatever that is). Ok, that's reasonably accurate. If you program it using a standard loop to read inputs, calculate and write out to say a LCD display, you should have a loop-length of known number of CPU cycles. (This is quite possible with a microcontroller as everything is in memory and as long you aren't waiting for random DMA interrupts should be quite feasible. A general purpose CPU running a mega operating system with lots of peripherals would make this task pretty much impossible). That's what I was thinking - apart from wanting to be sure that the timebase is sufficiently accurate. Another option is to use the built-in timer/counters (one 8 bit and one 16 bit are available) on the AVR ATmega MCU. Again clocked against the same crystal, and using a configurable frequency divider mechanism. The arduino language/library includes a millis() function which returns the number of msec of uptime; it's a 32-bit unsigned counter so it overflows after 49.7 days. There's also a microsecond counter with a 4 or 8 uS resolution depending on the CPU clock speed. And finally there are various dedicated real-time chips, such as DS1307, which combined with a crystal (usually 32.768KHz) can be easily interfaced if needed. These chips tend to be human-scale timers so you might have to count lots of repetitions of your loop under test and do the maths to get an average loop time (possibly limiting its usefulness). Depending of course on the timescales being measured either the milli- or microsecond counter should be adequate. Reasons for looping several times would be the counter resolution isn't high enough and the program being tested takes a varying time to run. If run on a desktop operating system, there's a lot of activity going on in the background so looping many times and taking an average is, I think, a necessity. I have an Arduino which I'll be using for temperature monitoring among other things. While running the Thermistor2 program I noticed the reported temperature jumped around almost at random. I did some analysis and a lot of that noise is coming from the ADC itself: I wired it up to fixed value resistor dividers (instead of a resistor and thermistor) and monitored the ADC value twice a second for several days. It turns out the ADC value is approximately Normally distributed with a standard deviation of about 0.7 x LSB. From what I have read this is out of spec and it may be due to noise in the input voltage (USB powered) and can also be reduced by adding a capacitor to the circuit (which I haven't done). I modified the code to take 10 readings at a time and average them; this reduces the standard deviation considerably. So I'm looking forward to hooking it back up to the thermistor and running the revised temperature program. It should show better than 0.1 degree C precision, however it will still need to be calibrated to be at all accurate. Nick. -- PGP Key ID = 0x418487E7 http://www.nick-andrew.net/ PGP Key fingerprint = B3ED 6894 8E49 1770 C24A 67E3 6266 6EB9 4184 87E7 -- SLUG - Sydney Linux User's Group Mailing List - http://slug.org.au/ Subscription info and FAQs: http://slug.org.au/faq/mailinglists.html
Re: [SLUG] Error in Time() command
Risking totally going off-topic but analog thermistors are so old-school! ;-) Check out the DS18B20. Same size as transistor (TO-220) but is digitally (one-wire serial) connected. No need for all that analog stuff and curve-fitting. These are uniquely address, thus polled if need be (dozens on the one bus) and can be metres from the microcontroller. (Well I have one on the end of 30 metre roll of alarm cable). Sure a few bucks versus a few cents, but wow. Regards, Martin martinvisse...@gmail.com On Wed, May 26, 2010 at 11:08 PM, Nick Andrew n...@nick-andrew.net wrote: On Wed, May 26, 2010 at 05:52:59PM +1000, Martin Visser wrote: Pretty much based on the knowledge that the MCU program counter is clocked on a 16MHz crystal (according to http://en.wikipedia.org/wiki/Quartz_clock they are generally good for 6 parts per million for standard grade crystals, whatever that is). Ok, that's reasonably accurate. If you program it using a standard loop to read inputs, calculate and write out to say a LCD display, you should have a loop-length of known number of CPU cycles. (This is quite possible with a microcontroller as everything is in memory and as long you aren't waiting for random DMA interrupts should be quite feasible. A general purpose CPU running a mega operating system with lots of peripherals would make this task pretty much impossible). That's what I was thinking - apart from wanting to be sure that the timebase is sufficiently accurate. Another option is to use the built-in timer/counters (one 8 bit and one 16 bit are available) on the AVR ATmega MCU. Again clocked against the same crystal, and using a configurable frequency divider mechanism. The arduino language/library includes a millis() function which returns the number of msec of uptime; it's a 32-bit unsigned counter so it overflows after 49.7 days. There's also a microsecond counter with a 4 or 8 uS resolution depending on the CPU clock speed. And finally there are various dedicated real-time chips, such as DS1307, which combined with a crystal (usually 32.768KHz) can be easily interfaced if needed. These chips tend to be human-scale timers so you might have to count lots of repetitions of your loop under test and do the maths to get an average loop time (possibly limiting its usefulness). Depending of course on the timescales being measured either the milli- or microsecond counter should be adequate. Reasons for looping several times would be the counter resolution isn't high enough and the program being tested takes a varying time to run. If run on a desktop operating system, there's a lot of activity going on in the background so looping many times and taking an average is, I think, a necessity. I have an Arduino which I'll be using for temperature monitoring among other things. While running the Thermistor2 program I noticed the reported temperature jumped around almost at random. I did some analysis and a lot of that noise is coming from the ADC itself: I wired it up to fixed value resistor dividers (instead of a resistor and thermistor) and monitored the ADC value twice a second for several days. It turns out the ADC value is approximately Normally distributed with a standard deviation of about 0.7 x LSB. From what I have read this is out of spec and it may be due to noise in the input voltage (USB powered) and can also be reduced by adding a capacitor to the circuit (which I haven't done). I modified the code to take 10 readings at a time and average them; this reduces the standard deviation considerably. So I'm looking forward to hooking it back up to the thermistor and running the revised temperature program. It should show better than 0.1 degree C precision, however it will still need to be calibrated to be at all accurate. Nick. -- PGP Key ID = 0x418487E7 http://www.nick-andrew.net/ PGP Key fingerprint = B3ED 6894 8E49 1770 C24A 67E3 6266 6EB9 4184 87E7 -- SLUG - Sydney Linux User's Group Mailing List - http://slug.org.au/ Subscription info and FAQs: http://slug.org.au/faq/mailinglists.html
Re: [SLUG] Error in Time() command
On Thu, May 27, 2010 at 08:04:45AM +1000, Martin Visser wrote: Risking totally going off-topic but analog thermistors are so old-school! ;-) I bought a couple of LM335A (?) at the same time, but I figured I'd get it working as well as possible with the basic thermistor to start. Check out the DS18B20. Same size as transistor (TO-220) but is digitally (one-wire serial) connected. No need for all that analog stuff and curve-fitting. These are uniquely address, thus polled if need be (dozens on the one bus) and can be metres from the microcontroller. (Well I have one on the end of 30 metre roll of alarm cable). Sure a few bucks versus a few cents, but wow. It's on my TODO list. Nick. -- SLUG - Sydney Linux User's Group Mailing List - http://slug.org.au/ Subscription info and FAQs: http://slug.org.au/faq/mailinglists.html
Re: [SLUG] Error in Time() command
Dion, As a soon-to-graduate EE you might consider using a tool such as oscilloscope or frequency counter to help more objectively measure timing. A simple thing to do would be to have your code section run in a repeating loop. At the end of the loop toggle a physical output - say the DTR line on a serial port, or even the Num Lock LED on you keyboard. Connection up your 'scope or meter to that physical interface and measure the frequency. I'm pretty sure these modern time-domain measuring devices are going to have some nice crystal-locked output that should have better than 0.1% or better resolution. Just compare that to your output from time() and see how you go. Regards, Martin martinvisse...@gmail.com On Mon, May 24, 2010 at 1:45 PM, Dion Curchin tenz...@iinet.net.au wrote: On 24/05/2010, at 8:47 AM, Glen Turner wrote: On Mon, 2010-05-24 at 09:02 +1000, Peter Chubb wrote: Actually it doesn't give the whole answer. Wow, thanks heaps Peter. Thank you all. Particularly Peter. That is truly an amazing depth of information to digest. tenzero: so there are 1000 (CONFIG_HZ) samples per second. For each sample your program is one of: not scheduled, running in user, running in system, or has yielded the processor due to a blocking event such as I/O or an explicit sleep(). It is possible that all processes yield and you get scheduled twice in one sample -- I'd note that, and then ignore the possibility. Run an infinite loop in another process if it worries you. That bastard will never yield, and so your process will never be scheduled twice in a tick. If you have multiple CPUs, bind one infinite loop to each CPU. In reality, unless your results are odd, this is a lot of work to exclude an unlikely case. With luck, your program is such that you can use strace to count the blocking events on a single run of your program. Then pretend that the scheduler tick misses every one of these. So if you program has 10 blocking events and runs for 1.00 second then there result has a bound of [1.00, 1.01]. Including the reporting error from the API [0.99, 1.02]. You will save yourself a world of statistics if your better program's range falls completely under the worse program's range. In this case it is. The hardware device dramatically outperforms the software and the error in the hardware device is half a clock cycle or 20ns while the error in the software is in the ms scale. Mostly for completeness, I simply wanted to discuss the error in the software measurement. In your Appendix you acknowledge Peter's contribution with a footnote (eg, Thanks to Dr Peter Chubb of UNSW for explaining the sampling nature of the Linux task accounting). In general, you don't cite these sort of e-mail discussions since they are all care and no responsibility discussions rather than a considered opinion ready for peer review. Of course, where the posting becomes a part of the record (such Linus's announcement of Linux) then you reference. You will see from this discussion the common research hassle that determining the error of an experiment is usually more work than determining the result. Indeed, that's exactly how I'm finding this. Best of luck with your studies, Glen Thanks. All things going to plan, I should graduate in about a month. This is for my final year project in Electronic Engineering. Again, thanks for everyones help. Cheers. D. -- SLUG - Sydney Linux User's Group Mailing List - http://slug.org.au/ Subscription info and FAQs: http://slug.org.au/faq/mailinglists.html -- SLUG - Sydney Linux User's Group Mailing List - http://slug.org.au/ Subscription info and FAQs: http://slug.org.au/faq/mailinglists.html
Re: [SLUG] Error in Time() command
Martin, That is a very good idea. Thank you! What makes this especially helpful and I'm anoyed I didn't think of it myself, is that an empty app or loop with only the output pulse included, can be used to approximate the overhead of the rest of the system. Effectively giving a potentially more precise measure of the speed of my actual code. Cheers. Dion. On 25/05/10 3:11 PM, Martin Visser wrote: Dion, As a soon-to-graduate EE you might consider using a tool such as oscilloscope or frequency counter to help more objectively measure timing. A simple thing to do would be to have your code section run in a repeating loop. At the end of the loop toggle a physical output - say the DTR line on a serial port, or even the Num Lock LED on you keyboard. Connection up your 'scope or meter to that physical interface and measure the frequency. I'm pretty sure these modern time-domain measuring devices are going to have some nice crystal-locked output that should have better than 0.1% or better resolution. Just compare that to your output from time() and see how you go. Regards, Martin martinvisse...@gmail.com mailto:martinvisse...@gmail.com -- Never ascribe to malice that which may adequately be explained by incompetence. - Napoleon Bonaparte -- Never ascribe to malice that which may adequately be explained by incompetence. - Napoleon Bonaparte -- SLUG - Sydney Linux User's Group Mailing List - http://slug.org.au/ Subscription info and FAQs: http://slug.org.au/faq/mailinglists.html
Re: [SLUG] Error in Time() command
Martin, That is a very good idea. Thank you! What makes this especially helpful and I'm anoyed I didn't think of it myself, is that an empty app or loop with only the output pulse included, can be used to approximate the overhead of the rest of the system. Effectively giving a potentially more precise measure of the speed of my actual code. Cheers. Dion. On 25/05/10 3:11 PM, Martin Visser wrote: Dion, As a soon-to-graduate EE you might consider using a tool such as oscilloscope or frequency counter to help more objectively measure timing. A simple thing to do would be to have your code section run in a repeating loop. At the end of the loop toggle a physical output - say the DTR line on a serial port, or even the Num Lock LED on you keyboard. Connection up your 'scope or meter to that physical interface and measure the frequency. I'm pretty sure these modern time-domain measuring devices are going to have some nice crystal-locked output that should have better than 0.1% or better resolution. Just compare that to your output from time() and see how you go. Regards, Martin martinvisse...@gmail.com mailto:martinvisse...@gmail.com -- Never ascribe to malice that which may adequately be explained by incompetence. - Napoleon Bonaparte -- Never ascribe to malice that which may adequately be explained by incompetence. - Napoleon Bonaparte -- SLUG - Sydney Linux User's Group Mailing List - http://slug.org.au/ Subscription info and FAQs: http://slug.org.au/faq/mailinglists.html
Re: [SLUG] Error in Time() command
On Wed, May 26, 2010, Dion wrote: Martin, That is a very good idea. Thank you! What makes this especially helpful and I'm anoyed I didn't think of it myself, is that an empty app or loop with only the output pulse included, can be used to approximate the overhead of the rest of the system. Effectively giving a potentially more precise measure of the speed of my actual code. That won't be true under a variety of reasons. Two things that come to my pre-caffienated mind is the behaviour of your system when it approaches CPU use saturation and task scheduling isn't immediate(er), and saturation of your memory throughput and/or CPU cache capacity. Both may change the overhead of your sampling method, including the time it takes to run the driver code. An idle system, with nothing else running, may have all of the kernel code needed to handle the parallel or serial port IO (via say, /dev/lpt0 or /dev/ttyS0) needed in L2 cache. Thus when you do the syscall, the relevant code pages don't have to be read in from memory. But when you start loading your system up, the probability of those pages being there stops being potentially close to 1 and starts dropping - and every L2 miss will impact on how long it'll take for the sampling to occur. Note it may not be the -same- overhead each pass as whether those cache lines are available depend on a whole lot of possibilities. Now, these effects (L2 cache/memory throughput) may only add fractions of microseconds of jitter under load. It may be enough for you. Scheduling latencies (more related to system HZ settings, as mentioned previously, but there's more to it than just that) may add considerably more. There's other things that may give rise to variance. If microsecond jitter matters, then another source is TLB (in)validation. Although the TLB isn't necessarily flushed when going user-kernel-user (eg, a syscall, or doing a privileged instruction such as speaking to an IO port), it is at least partially flushed when changing processes. Hazarding a somewhat-caffienated guess, you'd see this has multiple clusterings of jitter deltas, rather than it clustering around one mean. Don't even get me started about what happens when the scheduler decides to change the CPU your process is on - or, which may be more annoying, leaves your process/threads on their CPUs, but scheduling other processes/threads on your CPU from time to time. The behaviour of your sampling overhead may thus change. There's a lot going on under the hood in your hardware. Controlling for all of the variance is going to be tricky. Equating the variances (so you can elimiate that constant part from your work) is going to be even trickier. 2c, and I hope I haven't scared you off, Adrian -- SLUG - Sydney Linux User's Group Mailing List - http://slug.org.au/ Subscription info and FAQs: http://slug.org.au/faq/mailinglists.html
Re: [SLUG] Error in Time() command
(And if you don't have a scope or freq. meter) a suitably programmed Arduino or similar microcontroller could do this fairly easily for you - probably with better than 0.01% precision. Regards, Martin martinvisse...@gmail.com On Wed, May 26, 2010 at 10:53 AM, Dion tenz...@iinet.net.au wrote: Martin, That is a very good idea. Thank you! What makes this especially helpful and I'm anoyed I didn't think of it myself, is that an empty app or loop with only the output pulse included, can be used to approximate the overhead of the rest of the system. Effectively giving a potentially more precise measure of the speed of my actual code. Cheers. Dion. On 25/05/10 3:11 PM, Martin Visser wrote: Dion, As a soon-to-graduate EE you might consider using a tool such as oscilloscope or frequency counter to help more objectively measure timing. A simple thing to do would be to have your code section run in a repeating loop. At the end of the loop toggle a physical output - say the DTR line on a serial port, or even the Num Lock LED on you keyboard. Connection up your 'scope or meter to that physical interface and measure the frequency. I'm pretty sure these modern time-domain measuring devices are going to have some nice crystal-locked output that should have better than 0.1% or better resolution. Just compare that to your output from time() and see how you go. Regards, Martin martinvisse...@gmail.com mailto:martinvisse...@gmail.com -- Never ascribe to malice that which may adequately be explained by incompetence. - Napoleon Bonaparte -- Never ascribe to malice that which may adequately be explained by incompetence. - Napoleon Bonaparte -- SLUG - Sydney Linux User's Group Mailing List - http://slug.org.au/ Subscription info and FAQs: http://slug.org.au/faq/mailinglists.html -- SLUG - Sydney Linux User's Group Mailing List - http://slug.org.au/ Subscription info and FAQs: http://slug.org.au/faq/mailinglists.html
Re: [SLUG] Error in Time() command
On Wed, May 26, 2010 at 01:53:27PM +1000, Martin Visser wrote: (And if you don't have a scope or freq. meter) a suitably programmed Arduino or similar microcontroller could do this fairly easily for you - probably with better than 0.01% precision. How do we know the Arduino is so precise? :-) Nick. -- SLUG - Sydney Linux User's Group Mailing List - http://slug.org.au/ Subscription info and FAQs: http://slug.org.au/faq/mailinglists.html
[SLUG] Error in Time() command
Hi everyone, I'm seeking a preferably citeable reference to the amount of error in the returned result from a Time() command. I want to be able to quote the level of error in timing the execution speed of my project. While I have been using this command partly on Ubuntu for my project, I would particularly like to find out the level of this error on Mac OS X. Google and Google scholar have been disapointing. I concede that this is a little off topic and will move it OT if people are unhappy. Cheers. D. :: Never ascribe to malice that which may adequately be explained by incompetence! -- Napoleon Bonaparte -- SLUG - Sydney Linux User's Group Mailing List - http://slug.org.au/ Subscription info and FAQs: http://slug.org.au/faq/mailinglists.html
Re: [SLUG] Error in Time() command
tenzero == tenzero tenz...@iinet.net.au writes: tenzero Hi everyone, I'm seeking a preferably citeable reference to tenzero the amount of error in the returned result from a Time() tenzero command. I want to be able to quote the level of error in tenzero timing the execution speed of my project. Do you mean time(2) ??? Short answer: it depends. Long answer: time(2) returns the number of seconds since the epoch. It's accurate for timing in the absence of leap-seconds, and jumps caused by NTP etc. But it can go backwards, and forwards by more than one step at a time. For details, see time(7). If you want accurate timings, use one of the POSIX monotonic clocks. man 3 clock_gettime and look for CLOCK_MONOTONIC Also, you are aware (I assume) that how long something takes depends not only on its own processing time, but on how much else is happening on the system? You can measure just your own process (and its children's) times using the times() system call; if the kernel has been compiled with CONFIG_VIRT_CPU_ACOUNTING time spent in interrupts will not be included in your times. This isn't such an issue on BSD-derived systems such as MacOSX, because they use separately scheduled threads for interrupts. -- Dr Peter Chubb http://www.gelato.unsw.edu.au peterc AT gelato.unsw.edu.au http://www.ertos.nicta.com.au ERTOS within National ICT Australia -- SLUG - Sydney Linux User's Group Mailing List - http://slug.org.au/ Subscription info and FAQs: http://slug.org.au/faq/mailinglists.html
Re: [SLUG] Error in Time() command
On Sun, 2010-05-23 at 17:02 +0800, tenz...@iinet.net.au wrote: Hi everyone, I'm seeking a preferably citeable reference to the amount of error in the returned result from a Time() command. I want to be able to quote the level of error in timing the execution speed of my project. While I have been using this command partly on Ubuntu for my project, I would particularly like to find out the level of this error on Mac OS X. Google and Google scholar have been disapointing. I concede that this is a little off topic and will move it OT if people are unhappy. I concede I have no idea the actual problem you are having. Can you please explain what the issue is? Subtracting two times or something else, reset on ntpdate. Ta Ken -- SLUG - Sydney Linux User's Group Mailing List - http://slug.org.au/ Subscription info and FAQs: http://slug.org.au/faq/mailinglists.html
Re: [SLUG] Error in Time() command
On 23/05/2010, at 5:40 PM, Peter Chubb wrote: tenzero == tenzero tenz...@iinet.net.au writes: tenzero Hi everyone, I'm seeking a preferably citeable reference to tenzero the amount of error in the returned result from a Time() tenzero command. I want to be able to quote the level of error in tenzero timing the execution speed of my project. Do you mean time(2) ??? Actually I used time(1). This may have been unswise, I'm not certain. What I am trying to do, is simply determine the execution time of a small app I wrote in Java. Like this: time (java mcoption 104 .05859375 0.001129155 0.09765625 64 4) I am simply trying to record for performance testing, how long my java app takes to execute the Monte Carlo Simulation. I will be using it as a performance baseline to compare against my FPGA implementation. In terms of error, I am simply trying to find out the measurement error in the returned value. eg +- 1 millisecond or whatever. Short answer: it depends. Long answer: time(2) returns the number of seconds since the epoch. It's accurate for timing in the absence of leap-seconds, and jumps caused by NTP etc. But it can go backwards, and forwards by more than one step at a time. For details, see time(7). If you want accurate timings, use one of the POSIX monotonic clocks. man 3 clock_gettime and look for CLOCK_MONOTONIC Also, you are aware (I assume) that how long something takes depends not only on its own processing time, but on how much else is happening on the system? Yes I accept that I cannot fully control what else is happening across the entire system. Cheers. D. -- SLUG - Sydney Linux User's Group Mailing List - http://slug.org.au/ Subscription info and FAQs: http://slug.org.au/faq/mailinglists.html
Re: [SLUG] Error in Time() command
On Sun, 2010-05-23 at 17:02 +0800, tenz...@iinet.net.au wrote: I'm seeking a preferably citeable reference to the amount of error in the returned result from a Time() command. I want to be able to quote the level of error in timing the execution speed of my project. man time gives the answer. These statistics consist of (i) the elapsed real time between invocation and termination, (ii) the user CPU time (the sum of the tms_utime and tms_cutime values in a struct tms as returned by times(2)), and (iii) the system CPU time (the sum of the tms_stime and tms_cstime values in a struct tms as returned by times(2)). man 2 times says that these data types are clock_t and times() returns the number of clock ticks that have elapsed since an arbitrary point in the past. and The number of clock ticks per second can be obtained using: sysconf(_SC_CLK_TCK); so #include stdio.h #include unistd.h int main(void) { printf(_SC_CLK_TCK is %ld\n, sysconf(_SC_CLK_TCK)); return 0; } which says for my platform _SC_CLK_TCK is 100 Now the measuring precision may not match the reporting precision. But the quantum of your kernel's task scheduler is somewhere between 100 and 1000 (see the CONFIG_HZ kernel compilation flag), so it is safe to say that the reported precision of the tms API is the source of maximum error. If you need more precise runtimes and more details of consumed resources then see the TASKSSTATS system. The documentation which accompanies the kernel source contains sample code which will print all process exits and the resources used to a high precision. You also have control of the error. If you are lacking precision, then give the program a task which makes it run for 10x or 100x longer. As for citable you've got Buckley's. Shove the argument and program above into an appendix and cross-reference it as you would any other minor experiment or incidental proof. In general, these intermediate results don't contribute to word count, but do check the local policy. -- Glen Turner http://www.gdt.id.au/~gdt/ -- SLUG - Sydney Linux User's Group Mailing List - http://slug.org.au/ Subscription info and FAQs: http://slug.org.au/faq/mailinglists.html
Re: [SLUG] Error in Time() command
Glen == Glen Turner g...@gdt.id.au writes: Glen On Sun, 2010-05-23 at 17:02 +0800, tenz...@iinet.net.au wrote: I'm seeking a preferably citeable reference to the amount of error in the returned result from a Time() command. I want to be able to quote the level of error in timing the execution speed of my project. Glen man time gives the answer. Actually it doesn't give the whole answer. The times reported by the kernel are statistical samples of the process's progress -- at each tick, a sample is taken. the currently process has either its user or system time counter incremented, depending on whether it was running in user or kernel at the time of the interrupt. For processes that do a lot of short sleeps, this can be way out; but processes that are mostly CPU-bound and that run for a long time relative to the tick length can use the times reliably. If you're on a platform that can do CONFIG_VIRT_CPU_ACCOUNTING (Itanium, s390) you can rely on precise results at the cost of about a 3% extra overhead on every context switch and kernel/userspace crossing. Alternatively, the microstate accounting patch can give you precise times on Itanium, x86, x86_64, ARM and MIPS, although the latest version isn't on the sourceforge website yet (it's on my TO-DO LIST) Peter C -- Dr Peter Chubb http://www.gelato.unsw.edu.au peterc AT gelato.unsw.edu.au http://www.ertos.nicta.com.au ERTOS within National ICT Australia -- SLUG - Sydney Linux User's Group Mailing List - http://slug.org.au/ Subscription info and FAQs: http://slug.org.au/faq/mailinglists.html
Re: [SLUG] Error in Time() command
On Mon, 2010-05-24 at 09:02 +1000, Peter Chubb wrote: Actually it doesn't give the whole answer. Wow, thanks heaps Peter. tenzero: so there are 1000 (CONFIG_HZ) samples per second. For each sample your program is one of: not scheduled, running in user, running in system, or has yielded the processor due to a blocking event such as I/O or an explicit sleep(). It is possible that all processes yield and you get scheduled twice in one sample -- I'd note that, and then ignore the possibility. Run an infinite loop in another process if it worries you. That bastard will never yield, and so your process will never be scheduled twice in a tick. If you have multiple CPUs, bind one infinite loop to each CPU. In reality, unless your results are odd, this is a lot of work to exclude an unlikely case. With luck, your program is such that you can use strace to count the blocking events on a single run of your program. Then pretend that the scheduler tick misses every one of these. So if you program has 10 blocking events and runs for 1.00 second then there result has a bound of [1.00, 1.01]. Including the reporting error from the API [0.99, 1.02]. You will save yourself a world of statistics if your better program's range falls completely under the worse program's range. In your Appendix you acknowledge Peter's contribution with a footnote (eg, Thanks to Dr Peter Chubb of UNSW for explaining the sampling nature of the Linux task accounting). In general, you don't cite these sort of e-mail discussions since they are all care and no responsibility discussions rather than a considered opinion ready for peer review. Of course, where the posting becomes a part of the record (such Linus's announcement of Linux) then you reference. You will see from this discussion the common research hassle that determining the error of an experiment is usually more work than determining the result. Best of luck with your studies, Glen -- Glen Turner Australia's Academic Research Network (AARNet) www.gdt.id.au/~gdt -- SLUG - Sydney Linux User's Group Mailing List - http://slug.org.au/ Subscription info and FAQs: http://slug.org.au/faq/mailinglists.html
Re: [SLUG] Error in Time() command
Glen Turner g...@gdt.id.au writes: On Mon, 2010-05-24 at 09:02 +1000, Peter Chubb wrote: Actually it doesn't give the whole answer. Wow, thanks heaps Peter. tenzero: so there are 1000 (CONFIG_HZ) samples per second. 250, on my Debian/sid system running 2.6.32-5-openvz-amd64. FWIW. Daniel -- ✣ Daniel Pittman✉ dan...@rimspace.net☎ +61 401 155 707 ♽ made with 100 percent post-consumer electrons -- SLUG - Sydney Linux User's Group Mailing List - http://slug.org.au/ Subscription info and FAQs: http://slug.org.au/faq/mailinglists.html
Re: [SLUG] Error in Time() command
250, on my Debian/sid system running 2.6.32-5-openvz-amd64. FWIW. Daniel A little off topic, but, I noticed that the CONFIG_HZ variable on openvz systems is often 250. I found 1000 to be a better setting for responsiveness on a heavily loaded openvz box. It felt like being able to schedule more small things more often made sense when you have many containers. Or is that totally not how it works? Dave -- SLUG - Sydney Linux User's Group Mailing List - http://slug.org.au/ Subscription info and FAQs: http://slug.org.au/faq/mailinglists.html
Re: [SLUG] Error in Time() command
Dave == Dave Kempe d...@sol1.com.au writes: 250, on my Debian/sid system running 2.6.32-5-openvz-amd64. FWIW. Daniel Dave A little off topic, but, I noticed that the CONFIG_HZ variable Dave on openvz systems is often 250. I found 1000 to be a better Dave setting for responsiveness on a heavily loaded openvz box. It Dave felt like being able to schedule more small things more often Dave made sense when you have many containers. Or is that totally not Dave how it works? Higher HZ will generally give better responsiveness, lower HZ better throughput. Like all rules of thumb this one doesn't always work, it depends on the workloads. -- Dr Peter Chubb http://www.gelato.unsw.edu.au peterc AT gelato.unsw.edu.au http://www.ertos.nicta.com.au ERTOS within National ICT Australia -- SLUG - Sydney Linux User's Group Mailing List - http://slug.org.au/ Subscription info and FAQs: http://slug.org.au/faq/mailinglists.html
Re: [SLUG] Error in Time() command
On 24/05/2010, at 8:47 AM, Glen Turner wrote: On Mon, 2010-05-24 at 09:02 +1000, Peter Chubb wrote: Actually it doesn't give the whole answer. Wow, thanks heaps Peter. Thank you all. Particularly Peter. That is truly an amazing depth of information to digest. tenzero: so there are 1000 (CONFIG_HZ) samples per second. For each sample your program is one of: not scheduled, running in user, running in system, or has yielded the processor due to a blocking event such as I/O or an explicit sleep(). It is possible that all processes yield and you get scheduled twice in one sample -- I'd note that, and then ignore the possibility. Run an infinite loop in another process if it worries you. That bastard will never yield, and so your process will never be scheduled twice in a tick. If you have multiple CPUs, bind one infinite loop to each CPU. In reality, unless your results are odd, this is a lot of work to exclude an unlikely case. With luck, your program is such that you can use strace to count the blocking events on a single run of your program. Then pretend that the scheduler tick misses every one of these. So if you program has 10 blocking events and runs for 1.00 second then there result has a bound of [1.00, 1.01]. Including the reporting error from the API [0.99, 1.02]. You will save yourself a world of statistics if your better program's range falls completely under the worse program's range. In this case it is. The hardware device dramatically outperforms the software and the error in the hardware device is half a clock cycle or 20ns while the error in the software is in the ms scale. Mostly for completeness, I simply wanted to discuss the error in the software measurement. In your Appendix you acknowledge Peter's contribution with a footnote (eg, Thanks to Dr Peter Chubb of UNSW for explaining the sampling nature of the Linux task accounting). In general, you don't cite these sort of e-mail discussions since they are all care and no responsibility discussions rather than a considered opinion ready for peer review. Of course, where the posting becomes a part of the record (such Linus's announcement of Linux) then you reference. You will see from this discussion the common research hassle that determining the error of an experiment is usually more work than determining the result. Indeed, that's exactly how I'm finding this. Best of luck with your studies, Glen Thanks. All things going to plan, I should graduate in about a month. This is for my final year project in Electronic Engineering. Again, thanks for everyones help. Cheers. D. -- SLUG - Sydney Linux User's Group Mailing List - http://slug.org.au/ Subscription info and FAQs: http://slug.org.au/faq/mailinglists.html