Broken millis(), broken PWM on pins 5 and 6

Cool, thanks for doing the calculation. It certainly seems worth sacrificing half a percent (or so) of processing power to provide a longer-lived and easier to handle millis() value. This (or similar) will probably go in Arduino 0012.

It certainly seems worth sacrificing half a percent (or so) of processing power to provide a longer-lived and easier to handle millis() value.

I see where you are coming from...

Changing the clock_ticks variable from unsigned long to unsigned int (which should always work, as 1 millisecond is 16,000 clock ticks, below the 32,767 max that an unsigned int can take) reduces the time the ISR takes to 38 clock cycles when millis isn't incremented (i.e. the same as the current ISR), and 77 clock cycles when millis is incremented. So it's an extra 39 clock cycles over and above what's already there every millisecond, or about 0.25%.

Still, I think it's a good idea to have timer0 overflow at least twice every millisecond. If it were to overflow 4 times a millisecond, the total hit on performance would be 191 clock ticks per millisecond, or 1.2%.

What's the advantage of having it overflow more than once per millisecond? Better accuracy?

What's the advantage of having it overflow more than once per millisecond? Better accuracy?

You get less jitter.

If it overflows 0.95 times per millisecond, then once every 20 milliseconds it will take two overflows to increment millis() - i.e. the time interval between two increments will be 1.9 milliseconds - almost twice what it should be. If it overflows 0.15 times per millisecond, the worst that can happen is (I think) 1.1 milliseconds between increments.

If it overflows 0.95 times per millisecond...

Even worse is if it overflows 0.55 times per millisecond - once every 20 milliseconds, the interval between increments will be 0.55 milliseconds - about half what it should be. This could break some peripherals that need at least a millisecond delay.

Makes sense. Any thoughts on the best balance between minimizing jitter and minimizing CPU usage?

Anyone else have any use cases in which the accuracy or jitter of the millis() function is particularly important?

Any thoughts on the best balance between minimizing jitter and minimizing CPU usage?

Hmmm - looking at the datasheet, it looks like the best we can do is to set a prescale of 8 - this means that timer0 would overflow every 2,048 clock cycles, which gives an average of 7.8 overflows per millisecond. The next higher prescale is 64, which gives less than one overflow per millisecond, meaning that millis() could jump by two in just over one millisecond.

Timer 2 isn't much better - it has a prescale of 32, giving a dangerous 1.95 overflows per millisecond, which would mean that there would be times where the return value of millis() would increment in just over 0.5 milliseconds.

So it looks like timer0 with a prescale of 8, giving 2,048 clock cycles per overflow, is the best we can achieve. Using the code below, the time penalty goes to about 318 clock cycles per millisecond, or just under 2%.

volatile unsigned long millis;
unsigned int clock_ticks;

SIGNAL(SIG_OVERFLOW0)
{
clock_ticks += 2048;
if (clock_ticks >= 16000) {
millis++;
clock_ticks -= 16000;
}
}

I'm sure if someone wants to attempt to hand-write the ISR in assembly language, that time penalty can be brought down, possibly drastically. I haven't done any assembly language for the Atmel microcontrollers yet - I might consider this to be a good time and place to start!

Anyone else have any use cases in which the accuracy or jitter of the millis() function is particularly important?

Well, nothing totally critical, but the accuracy of the delay() function depends on millis(). Currently a delay(1) could vary from .2 to 1.9 msec. While I don't know of any code that relies on the accuracy of delay(), it would be better to make it work as advertised.

Oh, there were some people trying to build an RTC using arduino. I would guess that they used millis(). More accurate millis() might mean less RTC drift.

Just some ideas...

Makes sense. Any thoughts on the best balance between minimizing jitter and minimizing CPU usage?

Anyone else have any use cases in which the accuracy or jitter of the millis() function is particularly important?

I'm working on a timer project where millis() robustness is important since it requires millisecond resolution. In my particular case I'm certainly happy to cede a bit more CPU for this accuracy.

I've noticed the PWM being broken on the project that I am currently working on. Thanks for the tip! (pin, LOW) it is!

Chris

I updated the timer 0 overflow and millis() with the basic strategy you suggested: updating the millis count inside interrupt handler, so it overflows nicely. I didn't change the timer 0 prescale factor because I didn't want the PWM frequency on pins 5 and 6 to differ from those on the other PWM pins. The new code is below. There's still more to do on this, so suggestions are welcome.

volatile unsigned long timer0_clock_cycles = 0;
volatile unsigned long timer0_millis = 0;

SIGNAL(SIG_OVERFLOW0)
{
      // timer 0 prescale factor is 64 and the timer overflows at 256
      timer0_clock_cycles += 64UL * 256UL;
      while (timer0_clock_cycles > clockCyclesPerMicrosecond() * 1000UL) {
            timer0_clock_cycles -= clockCyclesPerMicrosecond() * 1000UL;
            timer0_millis++;
      }
}

unsigned long millis()
{
      unsigned long m;
      uint8_t oldSREG = SREG;
      
      cli();
      m = timer0_millis;
      SREG = oldSREG;
      
      return m;
}

I didn't change the timer 0 prescale factor because I didn't want the PWM frequency on pins 5 and 6 to differ from those on the other PWM pins.

I would suggest that a better solution would be to up the frequency on the other pins - otherwise you end up with a millis that can jump by 2ms in just over 1ms. But I don't see what problem you are trying to solve by keeping the frequencies of the PWM pins the same - off the top of my head I cannot think of a project that would need those frequencies to be the same.

volatile unsigned long timer0_clock_cycles = 0;

I think you can get away with an unsigned int here - doing so not only saves two bytes of memory, but it also makes the code smaller and run faster.

I think that some motors (motor drivers?) have trouble with faster frequencies. What's the problem with having millis() sometimes increment by two?

I think that some motors (motor drivers?) have trouble with faster frequencies.

A motor driver that runs at 1KHz? That sounds a bit fast for pretty much any physical process I can think of - except sound generation. But sound generation requires the frequency to be programmable - having just the duty cycle modifiable isn't any good for sound generation.

What's the problem with having millis() sometimes increment by two?

If you try and implement a delay of 2 milliseconds, you may end up pausing for only (just over) one millisecond. An attempt to delay by 3 milliseconds may be completed in just over 2 etc. I'm pretty sure there are peripherals which would have a problem with that.

I came accross this post while I was trying to figure out why millis() seemed to be busted.

I think that millis() should be part of a bigger strategy to implement a RTC as well as the basic foundation for a Real Time OS.

It does not matter if you get one or two ticks, as long as you maitain RTC integrity. Simplicity in processing and low overhead are desirable goals.

The system tic should be selected based on the best value and OS goals. (i.e. will vary with developement over the years pending on hardware capability and application needs). The system tic does not have to be one millisec. The RTC function calls and the millis() function have to be accurate. It is not possible to guarentee one millsec granularity with the overheads in a typical system.

I have not studied the internals very carefully, so I can not recommend a fix.

I am looking for a mini RTOS, that allows me to schedule tasks on a one second or greater time interval over several hours at least, preferably days.

I am looking for a mini RTOS, that allows me to schedule tasks on a one second or greater time interval over several hours at least, preferably days.

I believe my YAVRTOS http://www.chris.obyrne.com/yavrtos/index.html works on the Arduino.

Yes, YAVRTOS is worth looking at. FreeRTOS is too big.

IMO it would be better to add RTC functionality, date, time and a wait functions to the processing/wiring framework.

People want to program at a high level and use one stop shopping. Processing/wiring framework is close. Look at some of the new features in the XMega.

Ardruino 0012 Alpha appears to fix the bug.

Studying this thread and pondering the famous rollover event, I decided to do an experiment. Curious to see if I could catch the rollover in progress, I wrote the following simple program:

long int oldt, newt;

void setup()
{
  Serial.begin(9600);
  Serial.println("Hello, world!");
  oldt = millis();
}

void loop()
{
  newt = millis();
  
  // Filter out expected deltas of 0, 1, or 2 ms
  if (newt != oldt && newt != oldt + 1 && newt != oldt + 2)
  {
    Serial.print("Discontinuity event: Old time = ");
    Serial.print(oldt);
    Serial.print("ms, New time = ");
    Serial.print(newt);
    Serial.print(" ms, Delta = ");
    Serial.println(newt - oldt);
    
    if (newt < oldt)
      Serial.println("Rollover??!  New time is less than old time!");
  }

  oldt = millis();
}

The code simply loops repeatedly, comparing successive (and rapid) calls to millis(). Because I expected these successive calls to usually be the same, occasionally differing by 1 or perhaps 2 ms, the code flags any other delta to be a "rollover". But when I run the program I get some results I don't understand too well. Once in a while you get a largish jump of about 262ms, that I write off as some sort of bookkeeping interrupt(?) But the interesting part is I find that occasionally the millis() clock seems to go backwards (well before the expected rollover). I haven't studied the millis() implementation well enough to understand why this might be, but it's very reproducible, and I'm pretty sure there isn't any error in my simple test. For example, here are the results of running the program above for about 10 minutes:

Hello, world!
Discontinuity event: Old time = 91487ms, New time = 91749 ms, Delta = 262
Discontinuity event: Old time = 182713ms, New time = 182975 ms, Delta = 262
Discontinuity event: Old time = 206044ms, New time = 205783 ms, Delta = -261
Rollover??!  New time is less than old time!
Discontinuity event: Old time = 315358ms, New time = 315097 ms, Delta = -261
Rollover??!  New time is less than old time!
Discontinuity event: Old time = 412089ms, New time = 412351 ms, Delta = 262
Discontinuity event: Old time = 550239ms, New time = 550501 ms, Delta = 262
Discontinuity event: Old time = 566492ms, New time = 566231 ms, Delta = -261
Rollover??!  New time is less than old time!
Discontinuity event: Old time = 599260ms, New time = 598999 ms, Delta = -261
Rollover??!  New time is less than old time!

I can understand and tolerate the jitter and accuracy issues mentioned below, but I'll bet that there are applications that depend on consecutive calls to millis() predictably increasing (until the rollover at least). How can I better understand this behavior?

Mikal

Aha! I have figured out what the problem is. Millis() occasionally returns an incorrect value, and I understand why and how to fix it! I will discuss this in a new thread, since it is sufficiently different from the original discussion.

Mikal