What are the traditional ways to optimize program memory usage?

What are the generally practiced methods for the optimization program memory usage?

First, note you are searching for ways to lower SRAM memory. This contains global (variable) memory and heap space (dynamic memory + stack memory).

• Avoid memory gaps, by not using dynamic memory (with free/malloc/new).
• Avoid using the String class.
• Avoid global memory in SRAM by using PROGMEM, F(..) if possible.
• Use the smallest variable size (e.g. uint8_t instead of int).
• Store arrays of booleans into bits (8 booleans per byte).
• Use bit flags if applicable.
• Use some compressed type of memory internally (affects performance), e.g. if you have many 6 bit values to store, store them not in separate bytes but use 6 bytes for 8 times 6 bit values).
• Avoid passing arrays by value.
• Avoid a deep call stack with many (big) variables. Note this affects your design, so use it as a last resort.
• If you need a calculatable table, calculate each value instead of storing it as a table.
• Do not use longer arrays than needed, and think about reasonable maximum array sizes otherwise (see hcheung's comment below).
• (this is not a complete list).

Is there any difference in memory usage if the variable is declared globally or locally.

Yes, local variables are added to the stack, but are removed after the function ends, global variables stay (but are only created once). Note that variables on the stack (and also dynamic memory) are NOT taken into account in the memory calculated in the warning message during compiling.

Will it matter what the control statement/selection statements are (like if, switch )

No, this will only affect the program memory.

Usage of Serial monitor. Serial.print()

Probably yes, the serial monitor probably reserves (quite?) some memory as a buffer.

Low memory available, stability problems may occur. How bad are these warnings?

How bad it is, depends on how much memory is used which is not calculated, which is dynamic memory, and stack memory.

You can calculate it manually (which can be quite cumbersome for a big program), you can also use the GitHub library for this:

Arduino MemoryFree

If you know how much heap memory you use worst case, than add it to the calculated global variables memory. If this is less than your maximum available SRAM memory, you are safe.

I just want to add a single bullet to Michel Keijzers’ excellent answer:

• think about every single item you are storing in memory and ask yourself the question: do I really need to keep this in RAM?

It may sound silly to state what many would consider obvious, but we have seen here many instances of novices who do not take this into consideration. As a simple example, consider this function that averages 500 analog readings:

int averageAnalogReading()
{
    // First take and store the readings.
    int readings[500];
    for (int i = 0; i < 500; i++)
        readings[i] = analogRead(inputPin);

    // Then compute the average.
    long sum = 0;
    for (int i = 0; i < 500; i++)
        sum += readings[i];
    return sum / 500;
}

Storing all those readings is completely useless, as you can just update the sum on the fly:

int averageAnalogReading()
{
    long sum = 0;
    for (int i = 0; i < 500; i++)
        sum += analogRead(inputPin);
    return sum / 500;
}

For the same reason, if you need some kind of running average to smooth data, you should consider using an exponentially-weighted running average, which can be incrementally updated without storing the readings.

What are the generally practiced methods for the optimization program memory usage?

(nb. as per Edgar's comment I emphasise that this is about using PROGMEM more efficiently.)

• If you can replace code with a table whose size is ≤ the lines of code, do it.

  • Instead of using a sequence of ifs, find a way to collapse the procedure into a table
  • Use tables of function pointers if it makes sense
  • Sometimes you can come up with a mini-language that is much more dense than AVR instructions, for example encoding robot logic into 16 commands, and then you can pack two commands per byte. This could collapse your memory usage 50-fold.
• Use functions instead of repeated code—this may sound obvious but there are often subtle ways of rewriting code (but bear in mind that function calls have overhead)
• Use hash tables rather than tables with big gaps
• Use fixed point rather than floating point (e.g. you can take a byte and interpret its value as ranging from 0.00 to 2.55, instead of using a 4-byte float)

Is there any difference in memory usage if the variable is declared globally or locally.

Let's talk about the stack.

void A() {
    byte a[600];
    ...
}
void B() {
    byte b[400];
    ...
}
void loop() {
    byte xxx[1000];
    ...
}

This program will firstly use at least 1000 bytes of RAM all the time. There is no real difference compared to declaring xxx globally. But then what is critical is which function calls which.

If loop() calls A(), and then loop() calls B(), the program will not use more than 1600 at any time. However, if A() calls B(), or vice versa, the program will use 2000. To illustrate:

loop() [1000]
  └──── A() [1600]
  │    [1000]
  └──── B() [1400]
  └──── A() [1600]
  └──── B() [1400]

versus

loop() [1000]
  └──── A() [1600]
        └──── B() [2000]
  │    [1000]
  └──── A() [1600]
        └──── B() [2000]

Will it matter what the control statement/selection statements are (like if, switch )

Not much difference for a small number of cases. Otherwise it depends on your code. The best way is to just try both and see which is better. But:

switches usually use jump tables which are quite compact if you cover nearly every case in a range (0,1,2,3,4,..,100). ifs usually use a sequence of instructions, which take up more bytes and cycles than a jump table entry, but it makes more sense if you don't have a consecutive stretch of cases.

Usage of Serial monitor. Serial.print()

I don't believe that makes a lick of difference. Serial buffers are tiny (say 64 bytes, or 128 for a bigger board) and I believe they are allocated whether or not you use Serial.

Of course "literal strings like this" and char[] buffers consume memory. You can comment them out (or use #ifdefs) when you don't need them.