embedded software boot camp

Efficient C Tips #9 – Use lookup tables

Thursday, May 28th, 2009 by Nigel Jones

This the ninth in a series of tips on how to make your C code more efficient.

(Note if you are looking for basic information on lookup tables, you should read this).

Typically the fastest ways to compute something on a microcontroller is to not compute it all – but to simply read the result from a lookup table. For example this is regularly done as part of CRC calculations. Despite this I’ve noticed over the years what I’ll call the ‘look up tables are boring’ syndrome. What do I mean by this? Well when having to code a solution to a problem, it seems that most of us would rather code something that involves crunching numbers, rather than generate a table where we just look up the result. I’m sure that many of you are thinking that I’m dead wrong and that you use lookup tables all the time. Well I’m sure many of you do. However the question is whether you make full use of this capability?

What started me thinking about this is the person who ended up on this blog looking for an efficient algorithm for determining the day of the year. I have no idea if they were coding for an embedded system or not, nor whether they were looking for a fast solution, a minimal memory solution, or something in between. However, it did make me realize that it would be a simple albeit slightly contrived way of demonstrating my point about look up tables.

First off, I imposed some constraints

  • The Gregorian calendar is to be used.
  • Days, months and years are numbered from 1 and not zero, such that January 1 is day 1 and not day 0.

Here’s my first solution, that makes use of a small lookup table:

#define JAN_DAYS (31)
#define FEB_DAYS (28)
#define LY_FEB_DAYS (29)
...
#define NOV_DAYS (30)
#define MONTHS_IN_A_YEAR (12+1)

uint16_t day_of_year(uint8_t day, uint8_t month, uint16_t year)
{
 static const uint16_t days[2][MONTHS_IN_A_YEAR] =
 {
  { /* Non leap year table */
   0,    /* Padding because first month is not zero */
   0,    /* If month is january, then no days before it */
   JAN_DAYS,  JAN_DAYS + FEB_DAYS,...JAN_DAYS + FEB_DAYS + ... + NOV_DAYS
  },
  { /* Leap year lookup table */
   0,    /* Padding because first month is not zero */
   0,    /* If month is January, then no days before it */
   JAN_DAYS,  JAN_DAYS + LY_FEB_DAYS,  ...JAN_DAYS + LY_FEB_DAYS + ... + NOV_DAYS
  }
 };

 uint16_t day_of_year;

 if ((year % 4 == 0) && (year % 100 != 0) || (year % 400 == 0))
 {
   /* Leap year */
   day_of_year = days[1][month] + day;
 }
 else
 {
  /* Non leap year */
  day_of_year = days[0][month] + day;
 }
 return day_of_year;
}

For most applications I think this is an optimal solution in that it handles a very wide range of dates, uses a small amount of storage for the lookup tables and requires minimal computational effort to achieve the result. (On an ARM7 it requires 128 bytes of code space, 64 bytes for the lookup table and executes in about 40 cycles). However, what about if the code had to run as fast as possible? I’d guess that most folks would work on optimizing the details of the implementation and leave it at that. I’m not sure that many people would consider a gigantic look up table so that the code looks like this:

#define LAST_YEAR (2400 + 1)/* Last year to worry about */
uint16_t day_of_year(uint8_t day, uint8_t month, uint16_t year)
{
 static const uint16_t days[LAST_YEAR][[MONTHS_IN_A_YEAR] =
 {
  {
   /* Padding because first year is not zero */ 0,
   /* Padding because first month is zero */ 0,
   /* If month is January, then no days before it */
   JAN_DAYS,  JAN_DAYS + FEB_DAYS,...JAN_DAYS + FEB_DAYS + ... + NOV_DAYS
  },

  {
    /* Year 1 - non leap year */0,
    /* Padding because first month is zero */0,
    /* If month is January, then no days before it */
    JAN_DAYS,  JAN_DAYS + FEB_DAYS,...JAN_DAYS + FEB_DAYS + ... + NOV_DAYS
  },

 ... 

  {
   /* Last year - a leap year */ 0,
   /* Padding because first month is zero */ 0,
   /* If month is January, then no days before it */
   JAN_DAYS,  JAN_DAYS + LY_FEB_DAYS,...JAN_DAYS + LY_FEB_DAYS + ... + NOV_DAYS
  },
};

return days[year][month] + day;
}

The lookup table would of course require at least 2401 * 13 * 2 = 62426 bytes. Evidently this would likely be unreasonable on an 8 bit processor. On a 32 bit processor with 8 Mbytes of Flash – not so unreasonable. I first learned this lesson many years ago in an application that required an 8051 processor to perform a complicated refresh of multiplexed LEDs at about 1 kHz (a significant load for the 8051). The initial implementation consisted of pure code. Over the next year or so the two of us working on it realized that we could speed it up by using lookup tables. We started off with a small look up table, and by the time we were done, the table was 48K (out of the 64K available to the 8051) while the execution time was a fraction of what it had been before. Thus next time you are faced with making something run faster consider using a look up table – even if it is huge. Sometimes it’s just the best way to go.

Next Tip

Previous Tip

Home

9 Responses to “Efficient C Tips #9 – Use lookup tables”

  1. Uhmmmm says:

    I would just add a comment about blowing the data cache with huge lookup tables. It can happen, and in those cases, the extra calculation may be faster than going to memory. Just like blindly coding the algorithm isn’t optimal, neither is blindly trusting a LUT to be optimal. As always, the code should be benchmarked.

  2. Nigel Jones says:

    Ah yes the good old cache problem. Writing code so as to optimize cache performance is definitely one of the more challenging tasks. For example a common speed optimization is to unravel loops – which of course on some CPUs means the code is no longer completely held in cache and thus runs slower. Having said that, your point is well taken. The proof of the pudding is always in the eating.

  3. GregK says:

    1. Confusing!if ((year % 4 == 0) && (year % 100 != 0) || (year % 400 == 0)){}if ( ((year % 4 == 0) && (year % 100 != 0)) || (year % 400 == 0) ){}2. I would rather cut this: (year % 400 == 0) if we considering only current and future time. Modulo is in most cases extremly costly, and do this with one dimention array: day_of_year = days[month] + day; if (month > 2) { if ( ((year % 4 == 0) && (year % 100 != 0)) || /* (year % 400 == 0) */ ) { ++day_of_year; } }

  4. Yevheniy Soloshenko says:

    Nigel, do we need "+DEC_DAYS" in case of December? It will be already next year.

  5. Nigel Jones says:

    You win the prize for spotting the deliberate mistake! Thanks for paying careful attention – I'll correct the code.

  6. Nigel Jones says:

    Yevheniy diplomatically pointed out to me (by email) that I had allocated 31 days to November. We do a lot of strange things in Maryland but alas this is not one of them.I guess it's been one of those weeks. No doubt I should just take this advice and quit on this post.

  7. Kirk Charles says:

    Nigel, Thanks for this post. I need to consider LUTs more often. Since modulo is slow and a huge table would not fit on a small micro, could we have a leapyear table?

    uint8_t isleapyear(uint16_t year)
    {
    static const uint8_t leapTbl[LAST_YEAR] = {0,0,0,1,0,0 …….}
    return leapTbl[year]; // feed this into the 1st dim of the days array.
    }

    Still crunched for space? A slower but smaller version.
    uint8_t isleapyear(uint16_t year)
    {
    static const uint8_t leapTbl[LAST_YEAR/8] = {B00010001,B00010001, …….}
    uint8_t leapbyte = leapTbl[year/8]; //pick the byte
    uint8_t leapbit = (leapbyte >> ((year <>14) ) && 1; // <>14) is modulo of 4
    return leapbit; // feed this into the 1st dim of the days array.
    }

  8. Kirk Charles says:

    static const uint8_t leapTbl[LAST_YEAR/8] = {B00010001,B00010001, …….} has the bits reversed 🙁

  9. Kirk Charles says:

    REDO (please go easy on the noob)
    Still crunched for space? A slower but smaller version.
    uint8_t isleapyear(uint16_t year)
    {
    static const uint8_t leapTbl[LAST_YEAR/8] = {B1001000,B10001000,B1001000, …….}
    uint8_t leapbyte = leapTbl[year/8]; //pick the byte
    uint8_t leapbit = (leapbyte >> ((year & 3) ) && 1; // &3 is modulo of 4
    return leapbit; // feed this into the 1st dim of the days array.
    }

Leave a Reply

You must be logged in to post a comment.