Using Flash for large lookup array

SAILING_PAUL · August 24, 2019, 4:48pm

I have a large lookup array that makes my program too big for the memory on an arduino uno.

The array is static so it seems that the solution is to story that in flash using PROGMEM.

I’ve tried following some guides to doing that but when I try to verify the sketch I get an error:-

Sketch uses 15078 bytes (46%) of program storage space. Maximum is 32256 bytes.
Global variables use 2053 bytes (100%) of dynamic memory, leaving -5 bytes for local variables. Maximum is 2048 bytes.

I’ve extracted the lookup table and some code to serial print the entries into a smaller sketch and that successfully runs but I don’t think it is putting the array into flash, just normal RAM.

the test code is:-

// Creating new struct for lookup table array
// Needed as contains 2 different data types so a normal
// 2d array can't be used
struct pyClass {
  long pyNumber;
  String pyName;
};

// Lookup table of pyClasses
// Created from 2019 RYA PY Numbers
// Created as Const to save memory
// Max 14 Characters per pyName (otherwise won't fit on display)
const pyClass pyClasses[] PROGMEM = {
// const pyClass pyClasses[] = {
  {1111, "420"},
  {1112, "2000"},
  {907, "29ER"},
  {903, "505"},
  {1038, "ALBACORE/KSTRL"},
  {1027, "BLAZE"},
  {1155, "BRITISH MOTH"},
  {1138, "BYTE C11"},
  {1207, "COMET"},
  {1097, "COMET TRIO MK1"},
  {969, "CONTENDER"},
  {948, "DEVOTI D-ONE"},
  {1029, "DEVOTI D-ZERO"},
  {1119, "ENTERPRISE"},
  {1141, "EUROPE"},
  {1051, "FINN"},
  {952, "FIREBALL"},
  {1172, "FIREFLY"},
  {1130, "GP1HADRON H2"},
  {1073, "LARK/MEGABYTE"},
  {1099, "LASER"},
  {1207, "LASER 4.7"},
  {1145, "LASER RADIAL"},
  {1167, "LIGHTNING 368"},
  {980, "MERLIN-ROCKET"},
  {1194, "MIRACLE"},
  {1390, "MIRROR (D/H)"},
  {1380, "MIRROR (S/H)"},
  {849, "MUSTO SKIFF"},
  {1064, "NATIONAL 12"},
  {1104, "OK"},
  {1642, "OPTIMIST"},
  {928, "OSPREY"},
  {1002, "PHANTOM"},
  {1051, "ROOSTER 8.1"},
  {1004, "RS 100 8.4"},
  {981, "RS 100 10.2"},
  {1046, "RS 200"},
  {970, "RS 300"},
  {942, "RS 400"},
  {963, "RS 500"},
  {916, "RS 600"},
  {845, "RS 700"},
  {799, "RS 800"},
  {1136, "RS AERO 5"},
  {1065, "RS AERO 7"},
  {1014, "RS AERO 9"},
  {1240, "RS FEVA XL"},
  {1359, "RS TERA PRO"},
  {1438, "RS TERA SPORT"},
  {1093, "RS VAREO"},
  {1137, "RS VISION"},
  {1036, "SCORPION"},
  {1074, "SEAFLY"},
  {1099, "SNIPE"},
  {1143, "SOLO"},
  {1089, "SOLUTION"},
  {1128, "STREAKER"},
  {1077, "SUPERNOVA"},
  {1020, "TASAR"},
  {1363, "TOPPER"},
  {1190, "WANDERER"},
  {1102, "WAYFARER"}
};

void setup()
{
  Serial.begin(9600);
}

// Main Loop
void loop() {

  // Checks every entry in the array until a match to the
  // PYNumber is found, updates the ClassName variable
  // then exits the function.
  // If no match is found then ClassName of "UNKNOWN CLASS"
  for (int i = 0; i < sizeof(pyClasses)/sizeof(pyClasses[0]); i++) {
    Serial.println(pyClasses[i].pyName);
    Serial.println(pyClasses[i].pyNumber);
  }
}

Any ideas appreciated :0)

J-M-L · August 24, 2019, 5:42pm

Don’t use the String class in your struct but a pointer

You’ll need to store the text first in flash and then reference them (which you’ll refer to as const char *const)

SAILING_PAUL · August 24, 2019, 6:00pm

OK, I need to learn how to use pointers now :0)

david_2018 · August 24, 2019, 6:48pm

The structure will work if you change String to a character array, but it is a little wasteful of space because you have to allocate enough space to hold the longest text for pyName. The alternative is to store each of the pyName's separately, then put pointers to each individual one in the structure.

The most confusing part of PROGMEM is how to access something once it is put there.

This is a good reference on using PROGMEM.

J-M-L · August 24, 2019, 7:19pm

here is an example

struct pyClass_t {
  int16_t pyNumber;  // or if you need 32 bits declare as --> int32_t pyNumber; 
  const char* const pyName;
};

// you define first your cStrings in flash memory
const char v00[] PROGMEM = "420";
const char v01[] PROGMEM = "2000";
const char v02[] PROGMEM = "29ER";
const char v03[] PROGMEM = "505";
const char v04[] PROGMEM = "ALBACORE/KSTRL";
const char v05[] PROGMEM = "BLAZE";
//... do the same for all your strings

// Then you use the strings names (pointers) to add them into the structure
const pyClass_t pyClasses[] PROGMEM = {
  {1111, v00},
  {1112, v01},
  { 907, v02},
  { 903, v03},
  {1038, v04},
  {1027, v05}
  // ... all your data
};

// this is the number of entries
const size_t nbElements = sizeof(pyClasses) / sizeof(pyClasses[0]);

void setup() {
  // Max 14 Characters per pyName (otherwise won't fit on display)
  char buffer[20]; // Needs to be large enough! (at least 15 = your 14 + 1 char for the trailing null char)

  Serial.begin(115200);
  Serial.println();
  for (size_t i = 0; i < nbElements; i++)
  {
    Serial.print(i);
    Serial.print(F(")\t"));
    Serial.print( (int16_t) pgm_read_word_near(&(pyClasses[i].pyNumber)) );
  // Serial.print( (int32_t) pgm_read_dword_near(&(pyClasses[i].pyNumber)) ); // if you need 32 bits
    Serial.print(F("\t"));
    strcpy_P(buffer, (const char* const)pgm_read_word(&(pyClasses[i].pyName)));
    Serial.println( buffer );
  }
}

void loop() {}

you should see in the Serial Console (set at 115200 bauds):

[color=purple]

0) 1111 420
1) 1112 2000
2) 907 29ER
3) 903 505
4) 1038 ALBACORE/KSTRL
5) 1027 BLAZE
[/color]

of course you need to go through the trouble of defining all the strings if you want to optimize storage.

Note I used integer on 16 bits ( int16_t), not a long which is on 32 bits because your numbers were small - so that saves some flash memory and is more efficient when reading back as you fetch only 2 bytes instead of 4.

if you really depend on a long for the pyNumber, then you need to use 32 bits and instead of calling pgm_read_word_near(), you need to call pgm_read_dword_near() and replace int16_t by int32_t in the structure and when reading the data back (cast)

SAILING_PAUL · August 24, 2019, 7:57pm

Awesome guys, that is really helpful!! I'll give that a go :0)

david_2018 · August 24, 2019, 8:09pm

The other way, putting the text directly into the array. Takes a bit more storage, but a bit less typing. How much more storage depends on the average length of the text in pyName, but using the char * also adds two bytes per string.

// Creating new struct for lookup table array
// Needed as contains 2 different data types so a normal
// 2d array can't be used
const byte max_length = 15; //maximum length of pyName + 1 character for null
struct pyClass {
  long pyNumber;
  char pyName[max_length];
};
char buf[max_length]; //buffer to copy pyName from PROGMEM to RAM

// Lookup table of pyClasses
// Created from 2019 RYA PY Numbers
// Created as Const to save memory
// Max 14 Characters per pyName (otherwise won't fit on display)
const pyClass pyClasses[] PROGMEM = {
  // const pyClass pyClasses[] = {
  {1111, "420"},
  {1112, "2000"},
  {907, "29ER"},
  {903, "505"},
  {1038, "ALBACORE/KSTRL"},
  {1027, "BLAZE"},
  {1155, "BRITISH MOTH"},
  {1138, "BYTE C11"},
  {1207, "COMET"},
  {1097, "COMET TRIO MK1"},
  {969, "CONTENDER"},
  {948, "DEVOTI D-ONE"},
  {1029, "DEVOTI D-ZERO"},
  {1119, "ENTERPRISE"},
  {1141, "EUROPE"},
  {1051, "FINN"},
  {952, "FIREBALL"},
  {1172, "FIREFLY"},
  {1130, "GP1HADRON H2"},
  {1073, "LARK/MEGABYTE"},
  {1099, "LASER"},
  {1207, "LASER 4.7"},
  {1145, "LASER RADIAL"},
  {1167, "LIGHTNING 368"},
  {980, "MERLIN-ROCKET"},
  {1194, "MIRACLE"},
  {1390, "MIRROR (D/H)"},
  {1380, "MIRROR (S/H)"},
  {849, "MUSTO SKIFF"},
  {1064, "NATIONAL 12"},
  {1104, "OK"},
  {1642, "OPTIMIST"},
  {928, "OSPREY"},
  {1002, "PHANTOM"},
  {1051, "ROOSTER 8.1"},
  {1004, "RS 100 8.4"},
  {981, "RS 100 10.2"},
  {1046, "RS 200"},
  {970, "RS 300"},
  {942, "RS 400"},
  {963, "RS 500"},
  {916, "RS 600"},
  {845, "RS 700"},
  {799, "RS 800"},
  {1136, "RS AERO 5"},
  {1065, "RS AERO 7"},
  {1014, "RS AERO 9"},
  {1240, "RS FEVA XL"},
  {1359, "RS TERA PRO"},
  {1438, "RS TERA SPORT"},
  {1093, "RS VAREO"},
  {1137, "RS VISION"},
  {1036, "SCORPION"},
  {1074, "SEAFLY"},
  {1099, "SNIPE"},
  {1143, "SOLO"},
  {1089, "SOLUTION"},
  {1128, "STREAKER"},
  {1077, "SUPERNOVA"},
  {1020, "TASAR"},
  {1363, "TOPPER"},
  {1190, "WANDERER"},
  {1102, "WAYFARER"}
};

void setup()
{
  Serial.begin(9600);
}

// Main Loop
void loop() {
  // Checks every entry in the array until a match to the
  // PYNumber is found, updates the ClassName variable
  // then exits the function.
  // If no match is found then ClassName of "UNKNOWN CLASS"
  for ( unsigned int i = 0; i < sizeof(pyClasses) / sizeof(pyClasses[0]); i++) {
    Serial.print(pgm_read_dword_near(&pyClasses[i].pyNumber));
    Serial.print(F("\t")); //tab
    //copy the string from PROGMEM into RAM
    memcpy_P(&buf, &pyClasses[i].pyName, max_length);
    Serial.println(buf);
  }
  delay(30000); //wait 30 seconds before repeating the loop
}

J-M-L · August 24, 2019, 8:24pm

indeed (note that you don't need the & before buf inmemcpy_P(&buf, &pyClasses[i].pyName, max_length);as buf already represents the pointer to the char buffer.)

for @SAILING_PAUL - the difference between the 2 versions is that for each entry, you consume max_length bytes of memory (15 above) regardless if the string you want to store is short - such as "OK" (would only require 3 byte really) or long such as "ALBACORE/KSTRL" (which requires the 15 bytes).

If you are not short of flash, then proceeding this way will save you some cumbersome typing.
if you are short in flash or if some names are repeated multiple times, then the first approach will only use what's required.

SAILING_PAUL · August 25, 2019, 10:48am

Thanks guys, that worked.

I think I'm OK for flash memory for now:-

Sketch uses 12512 bytes (38%) of program storage space. Maximum is 32256 bytes.
Global variables use 743 bytes (36%) of dynamic memory, leaving 1305 bytes for local variables. Maximum is 2048 bytes.

Just out of interest, would would the effect be of using variable names other than v01, v02? I'm thinking if I used names of Streaker or Contender then the code would be easier to read. But would that make required an increase in memory or does the compiler change them to non-human readable format so it wouldn't make any difference?

(I will probably test it anyway but you probably have an explanation for the results I'll get)

thanks

Paul

david_2018 · August 25, 2019, 11:01am

The variable names are only for use by the compiler, and the person reading the code. There will be no effect on the code generated by the compiler.

GoForSmoke · August 25, 2019, 11:17am

SAILING_PAUL:
OK, I need to learn how to use pointers now :0)

Pointers are memory addresses (the actual data held in the pointer, 16 bits) with variable type for the compiler to know what code to use. You can change a pointer to long into a pointer to byte and look at the bytes.

With Arduino take care not to mix pointers to RAM with pointers to flash.

J-M-L · August 25, 2019, 12:04pm

SAILING_PAUL:
Just out of interest, would would the effect be of using variable names other than v01, v02? I'm thinking if I used names of Streaker or Contender then the code would be easier to read. But would that make required an increase in memory or does the compiler change them to non-human readable format so it wouldn't make any difference?

indeed the variables are replaced by memory addresses (pointers ! ) once compiled, so you can use short or long names - whatever makes sense. As I had no idea what to use for the previous code, I went for something sequential just for the sake of it.

GoForSmoke · August 29, 2019, 11:20am

david_2018:
The other way, putting the text directly into the array. Takes a bit more storage, but a bit less typing. How much more storage depends on the average length of the text in pyName, but using the char * also adds two bytes per string.

Just looking back in the thread because I had not gone so far with PROGMEM to store structs, which will do wonders for code I've trying to frame cleanly (karma was given btw) and I'd like to comment in general (not to David) here.

"a bit less typing" is often what you save for code that won't see a lot of use or reuse. It's not always true but is often enough that those places in code can net results when optimizing (never time to do it right, always time to do it over).

If the text is all close to the same length, a fixed length array is the way to go. But if string lengths vary much, it's a waste.

Lesson is to gather and check your data before writing a sketch to handle it, not "do it this way".
What I have often seen here are problems with sketches that don't get the expected data.

J-M-L · August 29, 2019, 7:20pm

This is a very fair point. If you don’t need to save Flash memory then the array route is definitely the way to go

It’s good to know you have an alternative if memory is tighter

GoForSmoke · August 29, 2019, 10:48pm

I'll be using structs in flash to make my keyword match code cleaner and easier to read/write. The space already saved with variable-length string array means a larger 'dictionary' is possible in user apps that use this software tool.

32K of flash makes 2K RAM able to go pretty far.

J-M-L · August 30, 2019, 6:49am

If I remember correctly - you refer to your inline keyword analyser coming from a Stream -> Remember flash access comes at a time cost (IIRC at least 1/3 slower).

So if you have to iterate over a larger data set - and say you go 10x larger than the one you had in SRAM as you have more space available - that might have consequences.

Your execution will become 3x slower which might be enough latency to overflow the Serial input Buffer and start missing user entry.

Would be interesting to find out if this is just a theoretical threat and if with a large data set you can still handle 115200 bauds in a worst case scenario (I don’t remember how you structured the code and if you memorized a matching tree and progress 1 char at a time or if you create a small local static buffer you iterate over and over again (so exponential with keyword length) until a word is recognized)

GoForSmoke · August 30, 2019, 12:17pm

J-M-L:
If I remember correctly - you refer to your inline keyword analyser coming from a Stream -> Remember flash access comes at a time cost (IIRC at least 1/3 slower).

So if you have to iterate over a larger data set - and say you go 10x larger than the one you had in SRAM as you have more space available - that might have consequences.

Your execution will become 3x slower which might be enough latency to overflow the Serial input Buffer and start missing user entry.

Would be interesting to find out if this is just a theoretical threat and if with a large data set you can still handle 115200 bauds in a worst case scenario (I don’t remember how you structured the code and if you memorized a matching tree and progress 1 char at a time or if you create a small local static buffer you iterate over and over again (so exponential with keyword length) until a word is recognized)

It walks through the word list 1 char at a time. The original from 2016 kept up with 250000 baud with a word list taken from string.h functions chosen to to have multiple alternatives checked, not the worst case but still loaded up.

The Jan 2019 update includes an alternative word-choice optimizer that in a not-worst-or-best-case keyword set averaged 9 us per char when reading from memory instead of serial, that is still 135 cycles on average.

The optimizer, here are the comments:
// we have chars matched and how many chars of the current word the next word matches
// if that number is smaller than already matched chars then no_match
// if that number is bigger then try the next list word
// if that number is the same then try to match the next char to text,
// ---- if they match then new current word and charsMatched++
// ---- else try the next list word

The data walk finds the first word that matches entries "so far" (with the initial char lookup tabled) and if a new entered char does not match the next in the table word, the search/walk goes to the next, etc.

In the old version (with 255 word limit) each letter of the tabled words has a byte telling which word to branch to. There is a sketch just to take a new word list and generate source for the new list code that includes all those offsets, hand linking was not an option.

The new version has the one optimizer byte (no links) and word limit is flash space or 32767 whichever comes first.

This quote-reply window does not let me attach files, if you want a copy of the speed test I'll post it as PM's don't allow attachments either.

For worst cases I would say there's ways around those, the match routine can ID substrings so 200 keys that all start the same can be as 200 keys that follow the same 1. The match routine can work with more than 1 word list too. Worst cases are things to engineer into less-than-worst cases.

J-M-L · August 30, 2019, 3:08pm

In the old version (with 255 word limit) each letter of the tabled words has a byte telling which word to branch to. There is a sketch just to take a new word list and generate source for the new list code that includes all those offsets, hand linking was not an option.

The new version has the one optimizer byte (no links) and word limit is flash space or 32767 whichever comes first.

ah so you have a prep stage to optimize the search. cool

GoForSmoke · August 31, 2019, 3:25am

J-M-L:
ah so you have a prep stage to optimize the search. cool

The new version is more for use in 1284P and 2560 apps than 328P but figure 2000 average 7 char keywords would leave 10K or so for bootloader, sketch and F() macro labels.

There are 2 different word-matched states depending on if a delimiter is read. That allows word+number (different sketch code reads the number) and strings of keywords (sketch supported).

Suppose there were a few such as SPI slaves with select wired ON catching a stream from the master and reporting hits as ID numbers? Dictionary size becomes scalable and worst-case words can be split apart.

I can see this used for serial protocols, what comes in gets numbered up nice for state machine use.

I've done accounting code tied to commercial POS data streams. Depending on inventory and departments and like, a couple 1000 keywords may be enough.

A char by char match is finished when the last char is read. A buffer then match method -starts- then, wastes beaucoup cycles! I started doing char by char user key io on 4MHz 8085 machines at work back in the day as an improvement on the line entry technique (Basic INPUT$) in our business code and my stuff. I like the thing I have now best, in fitting the Arduino niche it is the most evolved and having no insane deadline let it be better.

GoForSmoke · August 31, 2019, 4:22am

A switch-case statement with the PY numbers as the only cases could

switch ( pyNumber )
{
case 1234 :
Serial.print( F( "class name" ));
break;
case 5678 :

.....

default : // catches all the numbers that miss
// error handling goes here
}

If you want to go name-to-number on the fly, my match function and the work making a word list and py number array using structs in PROGMEM can get you there. On the fly can read streamed text files without stopping.