Look Up Table

22 Aug 2011

Dear all,

I need to use a very large (static) look-up-table (>145K entries) in a real-time control loop.

I know that I can easily read data from a text file, that could have stored the table. However, what I don't know is if this is fast enough to maintain a real-time controller bandwidth of let's say >100Hz?

Is this possible and the best way to use such a large look-up-table? Or are there better alternatives I could consider to use?

Thanks for all your help.

22 Aug 2011

I guess the best solution depends on several factors: How large are the entries in the table, 1 or 2 bytes or much more. Small amounts of data may even fit in the internal program flashmemory (512K) assuming that you dont need much space for your sourcecode. Larger amounts of data will have to be stored externally. Text files stored in the local filesystem will probably be too slow to access and decode. Sequential access is not very fast. I would probably use eeprom or SD cards on the SPI bus (or eeprom on the slower I2C bus). Use entries of constant size to simplify addressing: (eeprom address = (entry index) x (entry size in bytes). You can initialise the eeprom from the local filesystem using a textfile.

Regards, Wim

27 Aug 2011

look up tables are (usually) used to increase speed at the cost of memory. resorting to file access defeats this purpose. Can you approximate your lookup table using a function?

14 Sep 2011

Thanks for the answers! I have been working on it.

I have managed to downsize my Look-Up-Table (LUT) to 363KB, stored in a .txt file, so I am able to store it on the flash memory of mbed itself.

The LUT contains 52998 entries (size 73 x 726). Each data entry is a signed char.

I know how to read data from a file, but here comes the challenge I'm currently facing:

Let's say I know which data entry I want to pick from my LUT, for example entry (y,x). The stored data in the LUT looks like this (small part of it as example) :

-3 -113 -11 -111 +45 -70 -3 -112

-2 -112 -9 -110 +42 -73 -1 -110

So each signed char is tab separated.

I have been trying to use fseek followed by fscanf; calculating based upon y and x where the cursor should be set with fseek, however, as the data entries do not consist of the same number of characters this is not so straightforward, i.e. no solution.

Maybe I should store the data by putting zeros in front to make the entries the same size (Wim is that what you meant?). So that my example then becomes:

-003 -113 -011 -111 +045 -070 -003 -112

-002 -112 -009 -110 +042 -073 -001 -110

This way I can calculate with y and x, i.e. the known table index, where my cursor should be set with use of fseek.

However, there might be a more elegant solution to solve this? Somebody suggestions?

Thank you!

p.s. I saw on the preview that the tab delimited table entries in my examples above don't stay nicely in place, i.e. the tab is removed. But I guess the idea is clear.

14 Sep 2011

If it's only 52998 entries, it should actually fit in your firmware. Here's a possible way to declare it.

const signed char lookuptab[726][73] = {
  {-3, -113, -11, -111, +45, -70, -3, ..., -112, }, // line 1, 73 items
  ...
  {-2, -112, -9, -110, +42, -73, -1, ..., -110},  // line 726, 73 items
};

Then you just access this array as any other variable.

28 Oct 2011

There was some other stuff that needed my attention, but I picked up my struggle with the Look-Up-Table again.

Igor, I followed your advice of trying to put the code in the firmware like you suggest.

Problem 1: As the array is very large I don't want to type it myself. So when generating the array entries I originally write them in to a text file with a layout like Igor suggests. The idea was to copy-paste from that text file in to the MBED online editor. Unfortunately this doesn't work. The editor 'hangs' when you try this. I circumvented this by performing this copy-paste offline and then import the .c file again in to my programm / online compiler. So I consider this problem 1 somewhat solved. It is not the most elegant way though. So far, so good.

Problem 2: Okay, we have the .c file (size 317kb) now in place, containing the large array [73][726]. However, when I want to open the .c file in my MBED online editor this is not possible. It will again result in a 'hang'. I read somewhere else on a forum thread that this could be circumvented by using another browser. I am currently using Chrome, but I also tried IE. Both have the same problem.

Well, okay, I can't open the .c file to see the code but let's assume that the code is okay because I could check it offline before importing. Then the problem still isn't solved because when I want to compile I get an error, it 'hangs' again. If I remember well a time-out occurred, but I'am not sure.

So I have not been able to verify the solution proposed by Igor, because it introduces new problems. Please provide possible solutions for handling such large files/arrays.

Thanks!

29 Oct 2011

R A,

Try organizing your array initialization code via multiple header files that break the text into smaller chunks which the editor and compiler can handle. Either cut the generated text into several files with your off-line editor, or change the generating program to create the multiple headers. Then gather them into the compiled module with '#include' directives thus -

// file data_.cpp -
/* Public */ const signed char lookuptab[726][73] = {
// several big chunks (121 lines per file?) -
#include "data_0.h"
#include "data_1.h"
#include "data_2.h"
#include "data_3.h"
#include "data_4.h"
#include "data_5.h"
};
// end file data_.cpp

Fred

01 Nov 2011

Dear Fred,

Thank you for your reply. I am going to try it the way you suggest. I do think it is not the most elegant way but if it works it's OK with me for now.

Thank you.

01 Nov 2011

Unfortunately the solution as suggested by Fred does not seem to offer a solution. The browser still 'hangs' when trying to open such a header file (52kb) in the web editor.

By the way; the table originally was [73]x[726] entries. So I made the five header file 12 by 726 (instead of 121 by 73).

I have attached such a header file (in txt format), so maybe somebody notices something I shouldn't do because it causes these problems. I think it is straightforward though.

So the problem of handling a large Look-Up-Table isn't solved yet; please provide me with new suggestions for possible solutions?

/media/uploads/raalst1/lut_data0.txt

01 Nov 2011

I succeeded with another approach:

  1. use a table of 73 rows of 726 entries each
  2. put each row into a separate .cpp file:

row70.cpp

#include "rows.hpp"
const signed char row70[726] = {
   105, -126,   48, -127,    7,  -63, -116,    7,  125,   43,   90,  -82,   12,   28,  -49,  115,  -20, -114,    3,    2,  -67,   81,
   ....
   -25, -122,   58,  -36,  -65,  117,  100, -126,  -50,   81, -113, -128,  124,   57,   65,   51, -117,  119, -114,  -59,   39,  -90,
};

The table is an array of 73 pointers:

main.cpp

#include "rows.hpp"
const signed char *table[73] = {
  row00, row01, row02, row03, row04, row05, row06, row07, row08, row09,
  row10, row11, row12, row13, row14, row15, row16, row17, row18, row19,
  row20, row21, row22, row23, row24, row25, row26, row27, row28, row29,
  row30, row31, row32, row33, row34, row35, row36, row37, row38, row39,
  row40, row41, row42, row43, row44, row45, row46, row47, row48, row49,
  row50, row51, row52, row53, row54, row55, row56, row57, row58, row59,
  row60, row61, row62, row63, row64, row65, row66, row67, row68, row69,
  row70, row71, row72,
};

This results in a slight increase of space used because we now have a table of pointers and not a single packed array, but it still results in binary of slightly over 50K - plenty of space remains for the other code.

A compilable program that uses this approach:

Import programrom_lookup_table

73x726 signed char lookup table, fits completely in the Flash (LPC1768) See http://mbed.org/forum/helloworld/topic/2617/ for discussion

A Python script I used to generate the files: https://gist.github.com/1330649

05 Nov 2011

Dear Igor,

Thank you very much for your effort to provide me with a solution. I am going to try implement your suggested solution next week.

I will post here if it provided a solution indeed.

Much thanks in advance!

11 Nov 2011

Well, I tried the solution today and the result is the following:

The browser is able to handle the files formatted in the way as suggested by Igor. So this proves a solution! Thanks. However in my case I store and use the Look Up Table a little bit different then the simple file setup as the example of Igor. This still gives me some problems to handle the files and therefore I haven't been able to compile it and upload it to mbed. But I will first look in to this problem myself as I guess I will be able to solve this.

If that's solved, and I am able to upload the program to mbed, experiments need to prove that using such a large Look-up-Table like this is able in real-time (the original question).

So to be continued...