Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Test::assertion() consumes too much program (flash) memory #70

Closed
bxparks opened this issue Mar 2, 2018 · 7 comments
Closed

Test::assertion() consumes too much program (flash) memory #70

bxparks opened this issue Mar 2, 2018 · 7 comments

Comments

@bxparks
Copy link

bxparks commented Mar 2, 2018

I used ArduinoUnit for one of my projects. Great library, easy to use, thank you.

Problem

I found that it consumes too much program (flash) memory. My unit test suite is about 1200 lines of code, contains 25 tests, using 300 assertEqual() and 8 assertFalse() statements. On an AVR, the sketch generates 49148 bytes of flash memory and 1039 of static memory. This is too big to fit inside an Arduino Nano (ATMega328P, 32kB flash). I ended up breaking the test suite into 6 separate sketches. (The overhead of the split required 3 sketches, and after that, it made more sense to break into 6 logical units, giving me more headroom to add more unit tests to each logical unit).

Having to run 6 sketches is time consuming and error prone. Large program size means that the flashing process takes a long time. Ideally, everything would fit inside a single sketch. I looked into why ArduinoUnit generates so much program memory code.

Diagnosis

The culprit is Test::assertion() and the problem seems to be a confluence of at least 4 things:

  1. The F() macro does not fold duplicate strings into a single string. So each usage of F(__FILE__), for example, will produce a separate string in flash memory, even if the __FILE__ string is the same.

  2. Test::assertion() uses __FlashStringHelper to receive strings, and the various #define macros wrap various strings into the F() macros. Each of those strings consumes separate flash memory, with no deduping.

  3. Test::assertion() is a templatized method. Therefore, each variation of the various assertXxx() macro will produce a new version of Test::assertion(). For example, I believe each of the following produces a new variation:

  • assertEqual(uint8_t, uint8_t)
  • assertEqual(uint8_t, uint16_t)
  • assertEqual(int8_t, int8_t)
  • assertEqual(int16_t, int16_t)
  • (and so on)

Common strings such as F("Assertion"), F("passed"), F("failed"), F("=="), F("( "), etc are all duplicated in flash memory.

  1. The assertOp() macro passes in the string of the arguments (F(#arg1) and F(#arg2)) into the Test::assertion() method. This allows the error message to be very helpful, because it contains the snippet of the actual source code of the parameters that was passed into the assertEqual() (and other) macros, for example:
Assertion failed: (5U=5) == (adjustableConfig.getRepeatPressInterval()=6), file AllTests.ino, line 805.

But this has a huge cost, because every one of those F(#arg1) and F(#arg2) strings takes up flash memory.

Solutions

I have a change which implements 3 solutions, each more aggressively building on the previous. Here are the numbers from my actual test suite that I mentioned above (25 unit tests, 308 asserts):

METHOD | AVR(flash) | AVR(static) | Teensy(flash) | Teensy(static) |         
-------+------------+-------------+---------------+----------------|         
     0 |      49148 |        1039 |         34336 |           2956 |         
     1 |      32360 |        1039 |         30008 |           2956 |         
     2 |      25474 |        1079 |         30008 |           2956 |         
     3 |      25290 |        1067 |         29856 |           2956 |    
  • Method 0: no change, the original code
  • Method 1: remove F(#arg1) and F(#arg2)
  • Method 2: all of Method 1, plus change F() strings into (const char*) (to allow deduping by the compiler)
  • Method 3: all of Method 2, plus reduce the diagnostic string produced by Test::assertion()

Method 1 gives the biggest gain, with the removal of the F(#arg1) and F(#arg2) strings, reducing the program memory size by 35% or about 16kB. The change is that the diagnostic message is now:

Assertion failed: (5) == (6), file AllTests.ino, line 805.

But this is still not enough for my test suite to fit into 32kB of an Arduino Nano.

Method 2 gives a further 14% savings, or about 7kB, for a total program memory savings of 49%. It produces the same diagnostic message as Method 1:

Assertion failed: (5) == (6), file AllTests.ino, line 805.

The cost is about 40 bytes of static memory (occupied by the short (const char*) strings, which are deduped by the compiler). This now fits inside a Nano.

Method 3 is more aggressive about shortening the diagnostic message in Test::assertion(), printing just:

Failed: (5) == (6), AllTests.ino #805.

The benefit is marginal, saving only 180 bytes more (or 0.7%), but it does reduce static memory usage by 12 bytes compared to Method 2.

For completeness, I tested my changes on the Teensy platform (ARM Cortex), and on the ARM processors, the flash memory savings is not as dramatic as the AVR platform. But I think the smaller we can make the program, the faster the edit/compile/test iteration cycle will be.

Proposal

I would like to see my Method 2 implemented, reducing the program memory size by almost 50%, at the cost of about 40 bytes of more static memory, and a slightly more terse diagnostic error message.

My preference would be to see the full Method 3 implemented, because I think the short diagnostic message is good enough. But the flash memory savings is marginal (less than 1%), so I can see the argument that the cost-benefit is not worth it.

Let me know if you would like to see a pull-request for the code that implements all 3 methods, and you can take look.

@wmacevoy
Copy link
Collaborator

wmacevoy commented Mar 6, 2018

Thank you so much for your detailed proposal and analysis. The core problem (in my mind) is the failure of de-duplication of strings in flash memory, which seems like what ought to be resolved. I'm concerned about changing the messaging in case someone is using them in an automated testing situation. How much more RAM does the solution use? This resource seems more precious on these controllers. I do wish we can fix this....

@bxparks
Copy link
Author

bxparks commented Mar 7, 2018

I agree that the fundamental problem is that flash strings are not deduped. But I think fixing that requires fixing avr-gcc, which probably won't happen soon.

With regards to potential problems caused by removing F(#arg1) and F(#arg2), obviously I think saving 35% of flash memory space (16kB in my case) is worth the change. It seems to me that such automated validation code would be incredibly brittle. Any refactoring that changed the #arg1 or #arg2 code fragment within the various assertXxx() statements would break the validation code, even if the unit test itself didn't change.

With regards to your question about RAM, the table I posted has this information, under the column "AVR(static)". The cost of my Method 2 is 40 extra bytes of static RAM, which saves 23kB of flash memory in return. This seems like an acceptable tradeoff, but that's just me. If we went further and used Method 3, 12 fewer bytes (i.e. 28 extra bytes of RAM compared to the original), but returns the same 23kB savings of flash memory.

Anyway, let me know if you would like my help to implement any of my solutions. In the meantime, I'm going to fork this repository and use that for my projects. Having to run 6 unit test sketches across multiple platforms is too much work. My fork will allow me to collapse those 6 sketches into one.

@wmacevoy
Copy link
Collaborator

Could you please see branch iss70, it has a hack for de-duplicating flash strings. I don't know how to compare with your numbers as far as size is concerned, since I don't have your tests. The largest test I have is the firmware self-test, which shrinks about 8k with the change.

firmware.ino wIth de-duped flash strings on a mega 2560:
Sketch uses 34826 bytes (13%) of program storage space. Maximum is 253952 bytes.
Global variables use 730 bytes (8%) of dynamic memory, leaving 7462 bytes for local variables. Maximum is 8192 bytes.

firmware.ino without de-dupping (old way) on mega 2560:
Sketch uses 42912 bytes (16%) of program storage space. Maximum is 253952 bytes.
Global variables use 730 bytes (8%) of dynamic memory, leaving 7462 bytes for local variables. Maximum is 8192 bytes.

@bxparks
Copy link
Author

bxparks commented Mar 18, 2018

The unit test that I use is
https://github.com/bxparks/AceButton/tree/develop/tests/AceButtonTest
Change the #define USE_AUNIT 1 in that file to #define USE_AUNIT 0 to compile with ArduinoUnit.

The numbers I got were:

  • ArduinoUnit/master branch: 54038
  • ArduinoUnit/iss70 branch: 34696
  • AUnit/develop branch: 18666

Your 36% savings is consistent with what I observed by removing F(#arg1) and F(#args2).

But are you sure that you want to go down this road? The solution is hacking the compiler/linker with AVR specific assembly language. Granted, this problem is most egregious in the AVR platform, so you can #ifdef that code specifically for the AVR.

My philosophy is that I'm willing to sacrifice the F(#arg1) and F(#arg2) given that I'm working in an embedded environment with limited resources. So I'm aiming for the smallest flash memory consumption, on all platforms, that will give me reasonable error messages. If I have the line number and the file name, I can easily trace back to the code that generated that assertion.

@wmacevoy
Copy link
Collaborator

Thanks for all your insights & the test code. I agree its a hack that the compiler should do for you, I kept waiting for the compiler to get that fixed, but your comments and effort moved this forward. I would be very grateful if you tested the 2.3.0-alpha on the ESP board. There is some version of widening that should help with the <A,B> template generation; I'll try to think about that and see if I can squeeze a few more KB out...

@wmacevoy
Copy link
Collaborator

wmacevoy commented Apr 4, 2018

Thanks for pushing this forward. iss#73 is a compromise release with a few cool bonus features; that you are welcome to port of course.

@wmacevoy
Copy link
Collaborator

wmacevoy commented Apr 4, 2018

[thread summary] ArduinoUnit 2.3.5-alpha now supports flash string de-duplication on AVR and uses RAM on other platforms, along with a number of memory-saving optimizations that do not change the outcome of tests. It also supports ESP 8266 and ESP 32 platforms (along with development platform "en vitro" tests). Please try the latest pre-release and provide feedback on #73 if you are interested in these features.

@wmacevoy wmacevoy closed this as completed Apr 4, 2018
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants