Codesize Optimisation Tips

[@rt]

Hi Guys

I’ve spent 18 months staring at two constant arrays before two methods of optimisation dawned on me just last night.
They are both tables of bitrates for the vs1003b audio codec decoder & DAC chip for an MP3 player.

The first just incremented from 64, in units of 16, so the table could be computed, and eliminated altogether.

For the second:

Code: [Select]

const unsigned int stdbitratesa[7] = {112,128,160,192,224,256,320};
I just halved the value of each element, so it can be defined in an unsigned char array, and saved program memory.
Then the value is simply multiplied by two as it is accessed. Sounds fine for any const array consisting of all even values.

Does anyone else have any tricks to share that the compiler might not optimise?
Cheers, Brek.

[TomS_]

Hm. Are you sure that int type is 8 bits?

edit: oops, re-read and I see some values > 255 so yes, must be 16 bits. Never mind that. 

Also, I'd have thought that simply pulling some data out of memory would be quicker than pulling a value out of memory, then multiplying it?

If the native integer size of the micro is not 8 bits, theres a chance that this actually results in more instructions executed, as it needs to extract an 8 bit value from a larger piece of memory, then multiply it - all of that is extra instructions = more space used.

So, trade off of a few extra bytes of memory to store some bigger values vs more instructions?

[hamster_nz]

Random Optimization Hint #1
Try to avoid unused external linkage where possible - make as many functions and file-level variables "static" as possible. Also make sure you declare constants as 'const'.

Code: [Select]

int size = 10;


Code: [Select]

static const int size = 10;

This gives the compiler more information, allowing it to work its magic.

Random Optimization Hint #2
For 'simple' functions (e.g to check the range of a value), sometimes it is better to use a "#define func(x)  ...." rather than "int func(int x)".

e.g.

Code: [Select]

int is_digit( char c) {
  return (c >= '0' && c <= '9');
}

vs:

Code: [Select]

#define is_digit(x)  ((x) >= '0' && (x) <= '9')

Random Optimization Hint #3
Optimization and debug do not play well with each other. There is nothing as painful as code that is so squished to smaller part that you can no longer enable compiler debug options....

Random Optimization Hint #4
You can't optimize for everything (e.g. code size, RAM usage, run time CPU, maintainability, correctness, ease of testing, ease of debug, portability, low development cost...)  all at the same time.

Have a clear idea what are your hard constraints, and what are your must-haves, and what goals are aspirational goals, and what is not important in this case

[@rt]

If the native integer size of the micro is not 8 bits, theres a chance that this actually results in more instructions executed, as it needs to extract an 8 bit value from a larger piece of memory, then multiply it - all of that is extra instructions = more space used.

So, trade off of a few extra bytes of memory to store some bigger values vs more instructions?

16 bit dsPic this one, and I can see the program memory used. In this case smaller, but would have been a speed trade off.

Random Optimization Hint #1
Try to avoid unused external linkage where possible - make as many functions and file-level variables "static" as possible. Also make sure you declare constants as 'const'.

Code: [Select]

int size = 10;


Code: [Select]

static const int size = 10;

This gives the compiler more information, allowing it to work its magic.

Ok, the first will be dead easy to try, thanks

Yes I have a pretty good idea what my goals are.
My graphics and audio library has to be readable, and fast, but for the demo programs that use it, all bets are off.

I do have some performance metering such as frame counter that will also suffer with
ineficiency of the demo programs, so can see what I’m doing generally.

What I wanted out of the thread is other ideas, because it’s down to every reasonable size saving counting.

[@rt]

Hang on, the first example of size is variable, the second is constant.
Does “static” pertain to both where either won’t be accessed outside of the file it was defined in?

[hamster_nz]

Hang on, the first example of size is variable, the second is constant.
Does “static” pertain to both where either won’t be accessed outside of the file it was defined in?

Without the "static" it will have the chance that an external module will need to access it, so it must be assigned a location in memory RAM. With "static" the compiler can optimize things, it might even deduce that the value is never assigned in the current module so must be a constant. Adding "const" saves the compiler from needing to deduce this....

The old-schooler in me would prefer to use "#define SIZE (10)" rather than "const int size = 10;"... oh, so old-school! 

[NorthGuy]

The old-schooler in me would prefer to use "#define SIZE (10)" rather than "const int size = 10;"... oh, so old-school! 

I always use "define" in such cases. I don't think using esoteric considerations such as "old-school" can do any good. When I was young I was susceptible to following irrational rules of that kind, such as I tried to program without "goto". Looking back, I regret it very much.

[SiliconWizard]

Unless you need to access those values very very often in your code, it's probably going to be only a few words of code and/or RAM more or less and a few cycles of execution. Is it really worth the trouble?
I have a hard time figuring out why you would need to change bitrates so often that it really has any impact, but of course we'd need to see your code to figure that out.

It could also be more of a rhetorical question, considering much larger arrays, in which case the answer would be that it all depends on the target architecture. You'd get different answers probably for 8-bit, 16-bit, 32-bit, large or limited amount of RAM, cached RAM/cached code or not, speed of code execution, and so on.

If you strictly talk about code size, again it depends. Whatever the method of declaring your arrays, if they have initial values, those will be stored in code area anyway. Depending on your qualifiers and whether the compiler considers them constant or not, accessing the data may be done from RAM or Flash, again there is probably no single answer on that. You would have to check the resulting memory map and generated assembly code to make sure.

[mikerj]

For the second:

Code: [Select]

const unsigned int stdbitratesa[7] = {112,128,160,192,224,256,320};
I just halved the value of each element, so it can be defined in an unsigned char array, and saved program memory.
Then the value is simply multiplied by two as it is accessed. Sounds fine for any const array consisting of all even values.

For that case you could also use the first value in the table as an offset i.e. subtract 112 from all values to create the table, then add it when you do a table lookup.  That would have the advantage of working with odd values.

I've also offset tables to remove negative values on small processors like PICs and AVRs, since working with unsigned values can make quite a good saving in instruction cycles.

[@rt]

The bitrate could only be looked up when the track changes, but it’s not execution time I’m optimising for,
it’s only code size until fetching data from the card and sending the decoder chip can’t keep up with the highest bitrate.

What matters for me is the compiled code is smaller. There were three of these tables.
One could be calculated, one is more or less left alone, and the one posted could almost be calculated in the same manner,
but subtracting 112 could work.

It almost increments in the same unit, except the last value would need an additional check IIRC.. subtracting 112 is a go I think. Thanks

[NorthGuy]

It almost increments in the same unit, except the last value would need an additional check IIRC.. subtracting 112 is a go I think. Thanks

Assuming this is dsPIC, by replacing the 16-bit entries with 8-bit ones you save 3.5 instructions (I'm it is not worth the effort for all practical purposes, but that's not the point).

Multiplication by 2 is actually a shift and can be done in 1 instruction. Actually on dsPIC you can load and shift with a single instruction, so the extra instruction may not be needed if the compiler is smart enough (it probably isn't). Hence you save either 2.5 to 3.5 instructions.

Adding 112 has a disadvantage because the CPU needs to load 112 from somewhere. So, the savings are at best 2.5 instructions.

Of course, compiler can use lots of unnecessary instructions, so there may be less savings, no savings at all, or may be even a loss.

[@rt]

It’s easy enough to find out... well maybe not at 5:30am,
but it all adds up. I do have previously removed functionality
waiting for space to uncomment back in.

[Twoflower]

The last time I was thinking about to squeeze a few bytes out of my code was writing assembler on a 86HC11A1FN with no external RAM/ROM. That little one had 256Byte(!) RAM and 512Byte(!) EEPORM. Today I would see this only as a challenge. Because if you have to look for 4 Bytes you're probably run into problems sooner or later. Of course there are exceptions if you have an existing system and need to patch something in there.

Back to topic:

You also should look what the compiler actually made out of your optimisation efforts. Especially some modern compilers can decide themselves if in-line functions are effective or not. I've heard one high performance computing guy say 'Damn, the compiler is better than me in optimizing stuff'. That probably also applies to the size if you ask the compiler to optimize for size. Maybe the compilers are not that perfect optimizing the size like for speed.

Use the right parameters for the compiler can easily squeeze some bytes out of your code (for gcc it's -Os). But I've read somewhere that -O3 sometimes is nearly as small as -Os but much faster in execution. Also select the right target. And probably check all parameters of the compiler/linker to see if there's a option that applies for your configuration.

If the CPU don't support floating point or you're use some math functions you can easily bloat your code. Check the linker mapfile (ld switch -Map=mapfile)  to see what's actually in your code. Maybe you can replace some parts by a minimal replacement.

[@rt]

The last time I spent anything like 18 months on a microcontroller program was 2009 for a pic 16f628.

The optimisation attribute for code size doesn’t always result in the smallest size for any given file,
and none of them do any of the kind of size optimisation mentioned in this thread.
Sure, it finds more than I can, but I can still do a great deal more than the compiler.

This video belongs in the “Other Videos” section, and I wouldn’t have actually posted it here,
but it certainly shows what I mean. All of these programs are on a single dsPic33FJ128GP802.

Some data is loaded from an SD card ROM file, but generally only data that can be loaded once per program.
Frequently accessed data such as font, basic menu sounds, GIU graphics, and animation, etc.
are all still in the chip’s program memory, and I don’t think it could be this fast
if I got carried away with my graphics library as I am with the demo programs.

[hamster_nz]

The old-schooler in me would prefer to use "#define SIZE (10)" rather than "const size_t size = 10;"... oh, so old-school! 

I always use "define" in such cases. I don't think using esoteric considerations such as "old-school" can do any good. When I was young I was susceptible to following irrational rules of that kind, such as I tried to program without "goto". Looking back, I regret it very much.

Me too, but purists bang on about the value not having a defined data type (eg size_t), and things that can make a difference depending on the context in which they are used (for example, you can find the address of a "const int" and create a pointer to it).

[@rt]

I didn’t even know the use of DEFINE for numeric values such as Pi was considered a bad thing.
Understood about the type, but I always assumed it was a double if you defined enough decimal precision.

GOTO, I have read pertaining to C, that it indicates your code was not flowing consecutively,
which may make some sense, but of course an integral part of assembler.

[Siwastaja]

Me too, but purists bang on about the value not having a defined data type (eg size_t), and things that can make a difference depending on the context in which they are used (for example, you can find the address of a "const int" and create a pointer to it).

These "purists" (who, typically, are far from actually being purists and accept any horrible kludge as long as it's too complex for them to actually understand, and made by a large enough consortium or authority, such as Boost Libraries ) are always quick to note there is no type is #define'd constants and macros, but totally fail to see this is sometimes just the desired behavior, since there are no C++ templates in C - macros can provide such functionality, and this is by design, not a coincidence or "misuse".

C preprocessor is often criticized, but when used correctly, it's much more powerful and useful than most people know. I have seen some beautiful, easy to use, flexible, robust libraries done this way. For example, a simple preprocessor kludge like https://troydhanson.github.io/uthash/ is way better than many overcomplicated, poorly designed modern "boost" things that begin as some kind of "elegant" computer science thing, but often fall apart when the reality doesn't match the dreams.

C ain't beautiful -- but the "purists" almost always fail to provide real-world alternatives, and they are ready to abandon any elegance they were originally talking about in the blink of an eye and keep going, producing bloated mess while still believing they are "better".

[andyturk]

... For example, a simple preprocessor kludge like https://troydhanson.github.io/uthash/ is way better than many overcomplicated, poorly designed modern "boost" things that begin as some kind of "elegant" computer science thing, but often fall apart when the reality doesn't match the dreams.

Wow! Thanks for posting that. uthash is some serious macro hacking--not sure I've seen an entire library/subsystem written as macros before.

[nctnico]

... For example, a simple preprocessor kludge like https://troydhanson.github.io/uthash/ is way better than many overcomplicated, poorly designed modern "boost" things that begin as some kind of "elegant" computer science thing, but often fall apart when the reality doesn't match the dreams.

Wow! Thanks for posting that. uthash is some serious macro hacking--not sure I've seen an entire library/subsystem written as macros before.

IMHO you should consider using the actual C++ before resorting to these kind of macro hacks to emulate C++ (in this case templates / STL library) in C. I'm not a fan of putting code in header files and certainly not the amount of uthash.

[andyturk]

IMHO you should consider using the actual C++ before resorting to these kind of macro hacks to emulate C++ (in this case templates / STL library) in C. I'm not a fan of putting code in header files and certainly not the amount of uthash.

Agree. I'd never use uthash in a project, but the care and thoughtfulness that went into creating it deserve respect.

I moved to C++ and stopped writing plain C years ago. The only time I reach for the preprocessor these days is to do something that's entirely outside of C++ semantics. E.g., X Macros.

[Warhawk]

Random Optimization Hint #2
For 'simple' functions (e.g to check the range of a value), sometimes it is better to use a "#define func(x)  ...." rather than "int func(int x)".

e.g.

Code: [Select]

int is_digit( char c) {
  return (c >= '0' && c <= '9');
}

vs:

Code: [Select]

#define is_digit(x)  ((x) >= '0' && (x) <= '9')


This is not very smart.
First of all, all macros should be uppercase. In this case IS_DIGIT(x).
Second, if you replace functions by macros, you loose type check. This is very dangerous and often leads to problems. In the first example of yours, when you call is_digit(myvar) and myvar is not char, you get a warning during build. In case of the second example, you get nothing. Of course, some macros will always work but some give you headache.

I suggest using inline functions rather than macros.

What I learned in the industry:

• Don't optimize your code!
• Don't use any hacks, tricks or fancy features unless you need to. In this case, document it properly!
• Start your code with pen and paper, then with comments, then fill-in the code.
• Stay consistent with comments and naming nomenclature. Don't use non-English characters (?š??žýáí etc.)
• Use English. Broken English is ten times more helpful than proper German or Czech (in my case) etc.
• Use tools like astyle. I also like to replace // with /* */ for comments.
• Keep functions short. If you can't fit it on a single PC screen, split it into several smaller functions.
• Use the same optimization (I prefer -O0 or -O) for debug and release code.
• Use the pre-processor for compiler version check, return warning if somebody tries to compile your code with a different compiler.
• Do not utilize more than 60-70% of program memory at time of release.
• Read the datasheet and talk to the HW guy if you are only a SW guy!!! -> Understand the HW, the architecture and MCU capabilities
• Do not over feature!
• ... and more I can't recall now but do it automatically.. :-)

What I am trying to say is that a robust code, properly tested and released on time, is more about coding style and good programmer habits. I've seen a code from a very experienced embedded programmer which worked perfectly and very efficiently. The problem was when the guy left the company. Nobody could maintain the code and later on we replaced the module completely.

Google for Jack Ganssle articles.

PS: Don't get me wrong, I also like tricks such as:
https://graphics.stanford.edu/~seander/bithacks.html
or
http://dunkels.com/adam/pt/

[Siwastaja]

Agree. I'd never use uthash in a project, but the care and thoughtfulness that went into creating it deserve respect.

I did. Found it by accident, gave it a shot due to clear documentation and easy usage. Took about half an hour to learn completely and use for the intended purpose. Wrote the actual code, compiled immediately OK and passed all testing with zero bugs, which is quite rare when working with any new "concept". I moved on and didn't think about it too much. Maybe it isn't any good, don't know, haven't analyzed it. But if that's the case, then the reason for that must be something else than "it's not C++", or "it uses preprocessor 'hacks'".

I always find funny when some people think C++ is some kind of "golden standard" or basic underlying physical phenomenon like gravity, so if someone else is doing something that could indeed be done with C++, then that act of doing it without C++ is described as "emulating C++" and is automatically substandard . The wording by nctnico is just so ridiculously funny IMO. "Actual C++"!?

What if, by any chance, someone just knows other ways of doing things than C++? Maybe the world doesn't revolve around C++ after all? What if everything wasn't referenced to "C++ way of doing it" to begin with?

You know, I don't think anyone disagrees with the fact that C++ is kind of an overly complex mess, overdesigned by a large committee through adding features, more features, and some more features. I recognize it's powerful and capable (partly because of the sheer number of features), but I find it strange when people think about it as something elegant and basic, or a golden rule. I think the exact opposite: most actual C++ programs end up looking like complex hacks, and it's very difficult to be a good C++ programmer.

[andyturk]

Siwastaja,

I backed into C++ ~30 years ago and used it in a successful project when it was still called cfront. The potential for complexity scared me a little at the time, but it was possible to use only a few idioms/techniques to good effect. Today, there's stuff in C++14 and '17 that would probably set my hair on fire if I thought about it. But a handful of concepts that C++ provides are particularly useful in building maintainable code (IMO), especially for bare-metal embedded systems. On the other hand, I understand why so many people dislike the language and avoid it: Bad C++ is a lot worse than bad C.

Personally speaking, I don't want to go back to straight C because it'd feel like tying one hand behind my back.

[nctnico]

I always find funny when some people think C++ is some kind of "golden standard" or basic underlying physical phenomenon like gravity, so if someone else is doing something that could indeed be done with C++, then that act of doing it without C++ is described as "emulating C++" and is automatically substandard . The wording by nctnico is just so ridiculously funny IMO. "Actual C++"!?

What if, by any chance, someone just knows other ways of doing things than C++? Maybe the world doesn't revolve around C++ after all? What if everything wasn't referenced to "C++ way of doing it" to begin with?

C++ has all the kind of element handling functionality uthash offers under the hood in a standard, very well tested and easy to use way. At some point you have to realise plain C isn't the best tool for any programming job. The same goes for C++ at some point but for programming a microcontrollers there aren't much alternatives.

[NorthGuy]

At some point you have to realise plain C isn't the best tool for any programming job.

Works quite well for Linux kernel.

I think the language doesn't matter. What matters is vision, design, algorithms. Once you have this all in place, you can use assembler, you can use C, you can write in C++, or anything else you want. Moreover, when you have a good design, it's quite obvious that the language you use doesn't have any practical significance.