5
\$\begingroup\$

I'm developing an embedded solution (STM32L4R5 MCU - Cortex-M4F: 120 Mhz / 640 kb of ram) featuring a parallel NAND Flash (MICRON) interface and my platform lacks hardware ECC computation powerful enough to handle page sizes of 8KB so I elected to use software ECC. This one, to be precise. I refactored it as much as I could, unrolling some loops and replacing the count_bits_in_byte with a lookup table. The result is 5-10 2 times faster code (depending on the input). Measured with an oscilloscope.

This piece of code takes a 256 byte input and outputs 3 bytes of error correction code.

static void compute256(const uint8_t *data, uint8_t *code)
{
    uint32_t i;
    uint8_t column_sum = 0;
    uint8_t even_line_code = 0;
    uint8_t odd_line_code = 0;
    uint8_t even_column_code = 0;
    uint8_t odd_column_code = 0;

    for (i = 0; i < 256; ++i)
    {
        column_sum ^= data[i];

        // lookup table containing number of set bits in any given byte
        if ((setBitsInByteLookupTable[data[i]] & 1) != 0)
        {
            even_line_code ^= (255 - i);
            odd_line_code ^= i;
        }
    }
    // unrolled this loop
    if (column_sum & 1) {  even_column_code ^= 7;  odd_column_code ^= 0;} column_sum >>= 1;
    if (column_sum & 1) {  even_column_code ^= 6;  odd_column_code ^= 1;} column_sum >>= 1;
    if (column_sum & 1) {  even_column_code ^= 5;  odd_column_code ^= 2;} column_sum >>= 1;
    if (column_sum & 1) {  even_column_code ^= 4;  odd_column_code ^= 3;} column_sum >>= 1;
    if (column_sum & 1) {  even_column_code ^= 3;  odd_column_code ^= 4;} column_sum >>= 1;
    if (column_sum & 1) {  even_column_code ^= 2;  odd_column_code ^= 5;} column_sum >>= 1;
    if (column_sum & 1) {  even_column_code ^= 1;  odd_column_code ^= 6;} column_sum >>= 1;
    if (column_sum & 1) {  even_column_code ^= 0;  odd_column_code ^= 7;} column_sum >>= 1;
    // unrolled this loop
    code[0] = 0;
    code[1] = 0;
    code[2] = 0;

    code[0] <<= 2;
    code[1] <<= 2;
    code[2] <<= 2;

    /* Line 1 */
    if ((odd_line_code & 0x80) != 0)
    {
        code[0] |= 2;
    }

    if ((even_line_code & 0x80) != 0)
    {
        code[0] |= 1;
    }
    /* Line 2 */
    if ((odd_line_code & 0x08) != 0)
    {
        code[1] |= 2;
    }

    if ((even_line_code & 0x08) != 0)
    {
        code[1] |= 1;
    }
    /* Column */
    if ((odd_column_code & 0x04) != 0)
    {
        code[2] |= 2;
    }
    if ((even_column_code & 0x04) != 0)
    {
        code[2] |= 1;
    }

    odd_line_code <<= 1;
    even_line_code <<= 1;
    odd_column_code <<= 1;
    even_column_code <<= 1;

    code[0] <<= 2;
    code[1] <<= 2;
    code[2] <<= 2;

    /* Line 1 */
    if ((odd_line_code & 0x80) != 0)
    {
        code[0] |= 2;
    }

    if ((even_line_code & 0x80) != 0)
    {
        code[0] |= 1;
    }
    /* Line 2 */
    if ((odd_line_code & 0x08) != 0)
    {
        code[1] |= 2;
    }

    if ((even_line_code & 0x08) != 0)
    {
        code[1] |= 1;
    }
    /* Column */
    if ((odd_column_code & 0x04) != 0)
    {
        code[2] |= 2;
    }
    if ((even_column_code & 0x04) != 0)
    {
        code[2] |= 1;
    }

    odd_line_code <<= 1;
    even_line_code <<= 1;
    odd_column_code <<= 1;
    even_column_code <<= 1;

    code[0] <<= 2;
    code[1] <<= 2;
    code[2] <<= 2;

    /* Line 1 */
    if ((odd_line_code & 0x80) != 0)
    {
        code[0] |= 2;
    }

    if ((even_line_code & 0x80) != 0)
    {
        code[0] |= 1;
    }
    /* Line 2 */
    if ((odd_line_code & 0x08) != 0)
    {
        code[1] |= 2;
    }

    if ((even_line_code & 0x08) != 0)
    {
        code[1] |= 1;
    }
    /* Column */
    if ((odd_column_code & 0x04) != 0)
    {
        code[2] |= 2;
    }
    if ((even_column_code & 0x04) != 0)
    {
        code[2] |= 1;
    }

    odd_line_code <<= 1;
    even_line_code <<= 1;
    odd_column_code <<= 1;
    even_column_code <<= 1;

    code[0] <<= 2;
    code[1] <<= 2;
    code[2] <<= 2;

    /* Line 1 */
    if ((odd_line_code & 0x80) != 0)
    {
        code[0] |= 2;
    }

    if ((even_line_code & 0x80) != 0)
    {
        code[0] |= 1;
    }
    /* Line 2 */
    if ((odd_line_code & 0x08) != 0)
    {
        code[1] |= 2;
    }

    if ((even_line_code & 0x08) != 0)
    {
        code[1] |= 1;
    }
    /* Column */
    if ((odd_column_code & 0x04) != 0)
    {
        code[2] |= 2;
    }
    if ((even_column_code & 0x04) != 0)
    {
        code[2] |= 1;
    }
}

Probably using assembly would be a solution, sadly I'm a little less proficient with assembly than a lobotomized duck.

Any pointer would be greatly appreciated. How can I further optimize an ECC code computation?

\$\endgroup\$
5
  • 2
    \$\begingroup\$ You'll need to provide platform specific info: what kind of CPU are you using, how much cache if any, etc. \$\endgroup\$
    – aghast
    Sep 23, 2021 at 7:57
  • 1
    \$\begingroup\$ Hi. Welcome to Code Review! My first thought on reading this was to wonder how much you gained from unrolling the two loops. I.e. if you put the loops back, is it still about 5-10 times faster? How are you timing in general? \$\endgroup\$
    – mdfst13
    Sep 23, 2021 at 8:01
  • 1
    \$\begingroup\$ Sadly I had no access to the platform last night and I timed it on my PC. I just redid the test right now and it's twice as fast (4ms-3ms down to 2 ms-1.5 ms), measured with an oscilloscope. Most probably most of it comes from the lookup table. I'll try it now. \$\endgroup\$
    – Paul Jon
    Sep 23, 2021 at 8:04
  • 1
    \$\begingroup\$ @PaulJon What optimization features and compiler do you use? GCC happily unrolls the loops on x86 on its own. \$\endgroup\$
    – Zeta
    Sep 23, 2021 at 8:12
  • \$\begingroup\$ @Zeta Im using arm gcc. However, I can't really use optimizations, as it tends to break some of STM's HAL. \$\endgroup\$
    – Paul Jon
    Sep 23, 2021 at 8:15

3 Answers 3

9
\$\begingroup\$

Shift the constants not the variable

    if (column_sum & 1) {  even_column_code ^= 7;  odd_column_code ^= 0;} column_sum >>= 1;
    if (column_sum & 1) {  even_column_code ^= 6;  odd_column_code ^= 1;} column_sum >>= 1;
    if (column_sum & 1) {  even_column_code ^= 5;  odd_column_code ^= 2;} column_sum >>= 1;
    if (column_sum & 1) {  even_column_code ^= 4;  odd_column_code ^= 3;} column_sum >>= 1;
    if (column_sum & 1) {  even_column_code ^= 3;  odd_column_code ^= 4;} column_sum >>= 1;
    if (column_sum & 1) {  even_column_code ^= 2;  odd_column_code ^= 5;} column_sum >>= 1;
    if (column_sum & 1) {  even_column_code ^= 1;  odd_column_code ^= 6;} column_sum >>= 1;
    if (column_sum & 1) {  even_column_code ^= 0;  odd_column_code ^= 7;} column_sum >>= 1;

As I hinted in a comment, I'm not sure how much unrolling this loop gained you. When doing this kind of optimization, you need to measure each step separately (at least, independently is even better). But starting from this code, you could simplify it with

    if (column_sum &   1) { even_column_code ^= 7;  odd_column_code ^= 0;} 
    if (column_sum &   2) { even_column_code ^= 6;  odd_column_code ^= 1;} 
    if (column_sum &   4) { even_column_code ^= 5;  odd_column_code ^= 2;} 
    if (column_sum &   8) { even_column_code ^= 4;  odd_column_code ^= 3;} 
    if (column_sum &  16) { even_column_code ^= 3;  odd_column_code ^= 4;} 
    if (column_sum &  32) { even_column_code ^= 2;  odd_column_code ^= 5;} 
    if (column_sum &  64) { even_column_code ^= 1;  odd_column_code ^= 6;} 
    if (column_sum & 128) { even_column_code ^= 0;  odd_column_code ^= 7;} 

You already know what your shift is supposed to achieve. So if unrolled, you don't need to do it as a shift. You can shift the 1 manually instead.

Skip no-ops

    code[0] = 0;
    code[1] = 0;
    code[2] = 0;

    code[0] <<= 2;
    code[1] <<= 2;
    code[2] <<= 2;

I believe that you could simply leave off the last three lines. Because left shifting 0 will end up with 0. This was required in the loop for consistency. It's effectively a no-op. But unrolled you can skip this. That might pick up three instructions (if the compiler didn't already optimize it out).

More constant shifting

    odd_line_code <<= 1;
    even_line_code <<= 1;
    odd_column_code <<= 1;
    even_column_code <<= 1;

    code[0] <<= 2;
    code[1] <<= 2;
    code[2] <<= 2;

    /* Line 1 */
    if ((odd_line_code & 0x80) != 0)
    {
        code[0] |= 2;
    }

    if ((even_line_code & 0x80) != 0)
    {
        code[0] |= 1;
    }
    /* Line 2 */
    if ((odd_line_code & 0x08) != 0)
    {
        code[1] |= 2;
    }

    if ((even_line_code & 0x08) != 0)
    {
        code[1] |= 1;
    }
    /* Column */
    if ((odd_column_code & 0x04) != 0)
    {
        code[2] |= 2;
    }
    if ((even_column_code & 0x04) != 0)
    {
        code[2] |= 1;
    }

This is the second "iteration" of your unrolled loop. It could be

    code[0] <<= 2;
    code[1] <<= 2;
    code[2] <<= 2;

    /* Line 1 */
    if ((odd_line_code & 0x40) != 0)
    {
        code[0] |= 2;
    }

    if ((even_line_code & 0x40) != 0)
    {
        code[0] |= 1;
    }
    /* Line 2 */
    if ((odd_line_code & 0x04) != 0)
    {
        code[1] |= 2;
    }

    if ((even_line_code & 0x04) != 0)
    {
        code[1] |= 1;
    }
    /* Column */
    if ((odd_column_code & 0x02) != 0)
    {
        code[2] |= 2;
    }
    if ((even_column_code & 0x02) != 0)
    {
        code[2] |= 1;
    }

For the third iteration, the constants to & would be 0x20, 0x02, and 0x01.

More advanced

The next step would be

    /* Line 1 */
    if ((odd_line_code & 0x40) != 0)
    {
        code[0] |= 8;
    }

    if ((even_line_code & 0x40) != 0)
    {
        code[0] |= 4;
    }
    /* Line 2 */
    if ((odd_line_code & 0x04) != 0)
    {
        code[1] |= 8;
    }

    if ((even_line_code & 0x04) != 0)
    {
        code[1] |= 4;
    }
    /* Column */
    if ((odd_column_code & 0x02) != 0)
    {
        code[2] |= 8;
    }
    if ((even_column_code & 0x02) != 0)
    {
        code[2] |= 4;
    }

But that would require changes to the first and third iterations to match. Get rid of all the <<= in that section of code and change the |= constants in the first iteration with 32 and 16 (for 2 and 1 respectively).

Timing

When testing these, you really should be testing each change separately and if possible, independently. Separately means that you should change one thing and then time that one thing. So each of

  1. Convert function call to lookup table.
  2. Unroll loop.
  3. Unroll the other loop.

should be timed separately.

What you may find is that unrolling the loops doesn't help you, or even makes it worse (unrolling loops can bypass optimizations that the compiler would otherwise make).

Independently means that you should try testing them with and without the others. So compile with the function call converted. Time. Then undo that and try with an unrolled loop. Then undo that and try with the other loop unrolled.

Once you've tested them independently of each other, then you can time with them in various combinations. Sometimes you'll find that two optimizations that work separately don't work well together. Timing this way will allow you to pick the better one.

Note that I have suggested additional optimizations in this post. They only make sense with the unrolled loops. So that increases the number of possibilities.

  1. With loop.
  2. Unrolled.
  3. With the constants shifted.
  4. With the no-op instructions removed.
  5. With the no-op instructions removed and the constants shifted.
  6. With the other constants shifted (implicitly removes the no-op instructions).
  7. With the both sets of constants shifted.

Only the second unrolled loop has no-op instructions and two sets of constants to shift. The first unrolled loop only has three possibilities. That's forty-two combinations to check (perhaps we've stumbled onto the Ultimate Question). Note that if something doesn't work independently, you might drop it from potential combination checking. While not impossible, it is less likely that an optimization that didn't work independently would start working in combination.

Caveat

I'm not an embedded guy. To me, an oscilloscope is something that makes pretty but abstract art, like a screen saver, not something that I would use to test how fast code is. I have tried to express general principles. These may or may not be practical in your situation.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Thank you kindly for the great pointers, they make a lot of sense. And every little bit of extra speed counts. One half of a ms can make or break my project. \$\endgroup\$
    – Paul Jon
    Sep 23, 2021 at 9:24
  • \$\begingroup\$ BTW, 42 was an Asterisk in ASCII. :)) Found that funny. \$\endgroup\$
    – Paul Jon
    Sep 23, 2021 at 9:29
  • \$\begingroup\$ "oscilloscope is something that makes pretty but abstract art, like a screensaver" got me laughing for 5 minutes :D :D a good beginning for an entry in Uncyclopedia :D \$\endgroup\$
    – morgwai
    Oct 12, 2021 at 16:36
2
\$\begingroup\$

mdfst13 already gave a great review of the code itself. I'll just add this:

Consider changing the ECC algorithm

Since you are implementing ECC in software, you are free to choose whatever algorithm you want. You could change it to something more friendly for the Cortex-M4 CPU to calculate. In particular, if you don't use the ECC code to correct for single-bit errors, but only to detect errors, then you can choose an arbitrary checksum or hash function.

\$\endgroup\$
6
  • \$\begingroup\$ Thanks for the suggestion. Being a NAND flash, though, the probability of writing 8kb of data with 0 bit errors is marginal. I do need some form of error correction... \$\endgroup\$
    – Paul Jon
    Sep 23, 2021 at 11:03
  • \$\begingroup\$ @PaulJon "the probability of writing 8kb of data with 0 bit errors is marginal" Eh? What's that supposed to mean? Why wouldn't you write correct data? ECC as in actual error correction is pretty much only there to spot data retention over time. Or what other purpose are you using it for? \$\endgroup\$
    – Lundin
    Oct 5, 2021 at 7:02
  • \$\begingroup\$ @Lundin Pure NAND flash has a relatively high rate of defects. So without any hardware error correction and/or a list of bad blocks provided by the factory, you have to deal with that in software in some way. \$\endgroup\$
    – G. Sliepen
    Oct 5, 2021 at 17:57
  • \$\begingroup\$ @G.Sliepen I take it you mean read disturb, which would be another form of data retention. Errors during write don't need ECC, they are simply dealt with by reading back what you have just written and comparing it. \$\endgroup\$
    – Lundin
    Oct 6, 2021 at 6:23
  • \$\begingroup\$ @lundin What do you mean, "what do I mean"? When writing to NAND, due to the hardware (physical) characteristics of the storage ICs, bits get wrongly flipped. As in, you issue a "write 0000 0010 in X row, Y column" command, and it ends up "0001 0010" in that particular place. It's not due to software errors, it's because of the actual hardware. Thats why NAND vendors issue datasheets with "minimum required ECCs". I don't mean to sound like an as***e or anything, but your comment denotes you don't have much experience with NAND storage. \$\endgroup\$
    – Paul Jon
    Oct 16, 2021 at 12:14
1
\$\begingroup\$

From what I remember ST Cortex M4 has some "wannabe cache"-like feature, "ART accelerator", something like that. This is supposedly mainly there to reduce wait states. But if it works like normal data/instruction cache (I don't know any details here, I'd have to check the friendly manual), then regular for loops is probably as good as it gets when accessing adjacent flash memory. That could mean that manual loop unrolling is actually harmful for optimization.

At any rate, it's fairly safe to assume that flash wait states is a bottleneck. So you should focus on minimizing branches.

For example, something like column_sum & 1 is 0 or 1, so there shouldn't need to be a branch there. You have to disassemble to tell if it makes any difference, but maybe code like this will eliminate the branch:

uint32_t bit = column_sum & 1;
even_column_code ^= mask*bit;
odd_column_code ^= (7-mask)*bit;

Come up with similar tricks to get rid of as many of those slow if statements as possible!


In general, you should never do bitwise arithmetic on small integer types or signed integer types - the former get implicitly promoted to the latter. See Implicit type promotion rules. What you are risking is that upon setting MSB at any point, you could end up with shifting a negative number, which is poorly-defined behavior and almost always a bug.

This means that all your uint8_t should be swapped for uint32_t - which is unlikely to affect performance on a Cortex M.


The usual mini-optimization of no pointer aliasing between parameters is possible:

static void compute256 (const uint8_t* restrict data, uint8_t* restrict code)

It may or may not have an effect. Seems more likely to get optimized on gcc than other compilers.


However, I can't really use optimizations, as it tends to break some of STM's HAL

Well, you are done for then. When something like that happens, everyone needs to raise a support ticket with ST asking why their code sucks. If enough people do it, they will eventually have to hire professional programmers to fix the so-called "HAL".

Now if you are already stuck with their bloatware, what you can perhaps do is to play around with local optimization per translation unit: #pragma GCC optimize ("O3") and #pragma GCC optimize ("O0"). Brittle bloatware code gets the -O0, properly written C code gets optimized.

For what it's worth, one of the most likely reasons for hardware drivers breaking upon optimization is missing volatile qualifiers for register access or variables shared with ISRs or DMA etc. So if you are lucky, the problem is just something trivial like that, not the hardest bugs to track down.

\$\endgroup\$
1
  • \$\begingroup\$ you, sir, are surely right. their code makes no sense whatsoever. applying not skills, but barely common sense reduces the execution time of a simple function such as a SPI transmit from x (their implementation) to x/4. Bloatware is an understatement. \$\endgroup\$
    – Paul Jon
    Oct 16, 2021 at 14:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.