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.

[andyturk]

Works quite well for Linux kernel.

Yep, Linus has been pretty definite in his assessment of C++.     

On the other hand, both GCC and LLVM are written in C++, and the backstory on GCC moving from C to C++ is interesting.

The real issue for mcu-based projects is the atrocious awfulness of most embedded code. And you're right, it's not about the language, it's about the lack of abstraction, the copied-and-pasted garbage that moves from project to project and the fact that too many embedded programmers don't understand the code they're working on.

[hamster_nz]

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.

Do you have a citation for "all macros should be upper case"? (yes, I agree, but I can't find it written anywhere.. it is more a convention than a hard rule)

And you missed the greatest example of why you shouldn't use macros with careful understanding of how you intend to use them....

Code: [Select]

  x = is_digit(getchar());

gets expand to:

Code: [Select]

x = ((getchar()) >= '0' && (getchar()) <= '9');

So getchar() gets called twice... that is a very strong reason as to why you should avoid them where possible.

[Siwastaja]

Yep, Linus has been pretty definite in his assessment of C++.     

He has some fair points.

In a small software project with one or maybe two developers, they can effectively limit theirselves on which C++ features they use. If one is experienced enough in developing in C++, the results are most likely good, sometimes even nice, elegant and powerful.

However, in a project like linux kernel, requiring huge number of people and requiring certain low-level mindset, writing it in C++ would most likely result in a huge amount of code that's total crap. Designing the OO class models and the object crap around it and maintaining it while the reality around changes would prevent the required low-level work. OO requires careful planning and a powerful crystal ball, which is why the large multi-module projects often fail.

From this viewpoint, it isn't only a language difference; it's social difference: in large C projects, people are more experienced in low-level; in large C++ projects, people, unless very carefully hand-picked, tend to be "fresh out of computer science lessons" mindset, and face a language which is very complex under the hood.

The reason I never became a good C++ programmer is because the nature of my projects has been somewhat similar to what the linux kernel faces: most of the time things work out very well without needing any of the nice features C++ provides. Because of the combination of me not needing it, and it being complex and difficult, I can't write good C++ and probably never will. The difference is, I'm not claiming to be a capable C++ programmer like many mediocre C++ programmers are.

[Kjelt]

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

Sure, in one of my previous jobs I had an 8 bit target with 8KB Rom and 1kB Ram and a table of about 300 bytes for the power over time run up. So we needed to keep time and follow the table otherwise boom 
We ran out of Rom so I put the table in excel made a X Y point graphic and let Excel calculate a second or third order polynome to approach the graph.
Then I implemented the simple polynome in three locs and saved over 240 bytes 
Does not always work but many tables can be calculated with an aproximation algorithm.

Two cons :
- a real catch is the extra time to calculate over a table lookup, so when I set the power setpoint I already calculated the new one in front.
- my colleagues did not get it, when the table changed for a different product I had to do it again although I documented it properly and added the excel to the repo. So for R&D where the table might change each day due to the overhead it is not well suited.

Sometimes you need to split the table to get two or more simple polynomes instead of one complex one.

[andyturk]

From this viewpoint, it isn't only a language difference; it's social difference: in large C projects, people are more experienced in low-level; in large C++ projects, people, unless very carefully hand-picked, tend to be "fresh out of computer science lessons" mindset, and face a language which is very complex under the hood.

That's a great point.

C++ is often taught as a "high level" language, but if you try to apply many of those "high level" idioms directly to an embedded project, you'll create a mess (even if you're using the idiom as intended). So it takes some experience or guidance to use the extra power safely. Metaphorically, if you're a woodworking teacher and have to decide whether to use a bandsaw or hand tools for the next class project, it comes down to how capable your students are.

I've had the good fortune to work on projects with small firmware teams (1-3 engineers), where it was possible to keep coding standards high and directly interact with everyone. Using version control and pull requests for *everything* makes it possible to head off mistakes before they get too far, but also lets less experienced engineers see how APIs should be used (and how even project leads sometimes write buggy code  ).

[phil from seattle]

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.

+1000.  Though there are some exceptions.  Like BASIC...

[Siwastaja]

C++ is often taught as a "high level" language, but if you try to apply many of those "high level" idioms directly to an embedded project, you'll create a mess

C++ is, of course, not really a "high level" language (unless by "high level" we mean pretty much anything beyond assembly, something even C would fit into). This is pretty basic knowledge and even most heavy C++ users, even advocates have no issue admitting this. That's also a strength, if you look at it that way.

Anyone who teaches C++ as a "high level" language has no freaking clue what they are talking about, but CS teachers in universities are often utterly clueless - I have seen it happen.

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.

I can't agree with the "language doesn't matter" mentality. Yes, it's all fine and dandy "don't fight guys" thing trying to prevent a lurking language war from escalating, but please be honest with yourself - of course choosing the programming language (which is almost always much more than just a language: environment, toolset, libraries, "frameworks", and more often than most care to admit - also the team!) matters. It's a massive implementation and project management detail, and these details do matter. Sometimes there are several equally good options, but sometimes not really.

[nctnico]

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

Works quite well for Linux kernel.

If you have ever worked on the Linux kernel you'd wish they converted it to C++. Sometimes the creator of something becomes an anchor. Let's leave it at that.

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.

Sure the language matters. One of the problems with C and in a lesser extend with C++ is that you have to do a lot of leg work like keeping track of pointers and there is no real support for complex data types. All in all that means less productivity compared to languages which allow you to focus more on functionality and less on OS and hardware related stuff.