Thinking outside the IDE to make a fast-counting Arduino

[Udo Klein] took on the challenge of counting as fast as possible using an Arduino board. The quest involves a search for short-cuts that will let him drive a 20-bit counter as quickly as possible using the stock hardware. But the catch is that the Arduino environment has some overhead running in the background which will slow things down. He looks into each of these road bumps, then shows one way to get around them.

The code uses a command we don’t normally see in modern C embedded programming; the goto statement. He’s using this to bypass the extra cycles used by the Arduino’s in-built loop() function. The only command that is run within his hacked loop is a deeply nested set of macros. They’re toggling output pins using the hardware XOR built into the AVR chip. This is directly addressing the registers and thereby dumps the slowdown added by the digitalWrite() function.

The result is a software counter that toggles the output lights (see the clip after the break) at about 98.9% of the hardware clock speed. Pretty impressive, but [Udo] figures he can make it just a bit faster yet.

Comments

  1. beta4 says:

    I don’t get why there’s the need for a goto.
    Using an infinite loop like a for(;;) or a while(1) within loop() will achieve the same result.

    • LordNothing says:

      hes doing it because everyone told him not to :D

    • Stan says:

      Same here. I used it once in my early days and my C teacher ripped me a new one for using goto. Calling me a terrible programmer, etc.. He nearly had a meltdown..
      I never have used goto’s since. He said they were a lazy tool of a weak mind..

      • LordNothing says:

        i had a similar experience in high school. we had a computer class, but since the teacher was a former software engineer he had an advanced class for real geeks where he taught actual computer science and not just how to use word and excel. i was in that class. anyway after learning about the evils of the goto statement, and being the rebel that i am, i included it in every single assignment for teh lulz. used to drive him nuts.

    • Erik Johnson says:

      I still never understood why people rip goto. They refer to a book from ancient times without reading or comprehending it (enter the bible)

      • Chris C. says:

        Amen.

        Sure, using other program flow statements *most* of the time is good practice. But every now and then you run across something that is best and most simply solved by a GOTO.

        Needlessly rearranging your code to avoid it is a waste of time. It may also require additional nested indentations and/or parenthesis, which can make code harder to read and understand than the GOTO it replaces. Nothing is served except zealotry.

        And in a way, you really didn’t avoid GOTO at all; because that’s what the compiled assembly code is using. If “GOTO is considered harmful”, then it should be universally so. Yet I’ve never heard an assembler programmer complain about it, or suggest it should be removed from the language. Hmm. :)

      • kcstrom says:

        I agree with Chris’ comments. goto creates much cleaner, easier to follow, and maintainable code when used appropriately in c. Other flow constructs are better for general use most of the time, but for things like multiple error points that all need to release a semaphore/set a return variable/etc., goto is so much better.

      • Velli says:

        Revelation 20
        12 cin >> deadpplz
        13 GoSub Judgement(deadpplz)
        14 GoTo Hell

        Nah, the bible is a terrible coding reference.

    • Because it is more appropriate.

      while (1) {

      }

      creates a new variable scope. Thus depending on how clever the compiler optimizes this may or may not result in the desired code.

      Now my whole article is about agressive performance optimization. So basically I use the C compiler such that it will generate the desired assembler code. The article is not at all about the benefits of structured programming, object orientation, design patterns or anything else.

      Hence I consider goto most appropriate because I want the compiler to generate a “jmp” instruction.

  2. andygoth says:

    In my experience, most folks who rail against goto are directly or indirectly influenced by the *title* of E. Dijkstra’s famous paper “Goto Considered Harmful”, without having any actual understanding of the contents of that paper. The problem isn’t goto, it’s languages (e.g. very old Fortran) that require its use in common cases better handled by structured programming. I almost never need goto, but when I do, I really really need goto, and the non-goto workarounds are less maintainable than simply using goto.

  3. Any loop can be reduced to a set of gotos, the reverse is NOT true. That is to say: some control flows *cannot* be written in terms of loops (at least the loop constructs that C allows) as per CS theory

  4. ryokimball says:

    Beware of raptors.

  5. NewCommentor1283 says:

    if used sparsely, it can be a sweet indulgence.

    if used extensively, the program is just too dam complicated and confusing to debug!

    glitches can arise…

    but for a specific main loop, or a precicion loop with NO return statements or out of loop branches, it can apparently, in that case, speed execution up. :) (on AVR)

    PS: i usually do not use it anymore because my loops (of any kind) tend to get convoluted. goto just makes it worse.

    i was stubborn but slowly accepted the facts from my own debugs, and subsequent REWRITES of code.

    spending a little time to type in and think about non-goto commands saves a hell of a lot of time later on.

  6. pedrodiogo says:

    I honestly don’t understand, if the issue is speed why rely on the compiler when you can be sure it will run as fast as you make it using assembly ?

    • Erik Johnson says:

      ASM is not always portable between models, much less architectures. That aside, many hobbyists (hack, even “educated” developers) don’t know it or maybe find it too difficult(?).

      From what I’ve seen of the ardino code, they have a provided main() that is essentially “main(){setup();while(1) loop();}” If I remember, if you declare your own main() entry point, this overrides the in-built one and makes this “hack” moot. The in-build main does is a look of subroutine calls to your code, writing an infinite loop inside it prevents the return and re-calling.

      • Erik Johnson says:

        Damn fingers & lazy eyes! typos everywhere

        From what I’ve seen of the ardino code, they have a provided main() that is essentially “main(){setup();while(1) loop();}”
        If I remember right, when you declare your own main() entry point, this overrides the in-built one which makes this “hack” moot. what the in-built main does is a loop of subroutine calls to your code, writing an infinite loop inside it prevents the incessant returns and re-calling.

      • ABS says:

        Nor is C (the IO registers mentioned are not necessarily universal across the avr range, nor is the CPU scale registers). If he desperately wants such speed, asm really is a better tool.

      • Erik Johnson says:

        The “registeres” aren’t part of the language, they are macros in a hidden #included file which technically could be made portable. (They turn into inline assembly instructions, depending…)

        No debate in ASM for speed :)

      • Jarel says:

        Does no one else write inline assembly? You can have the best of both worlds!

      • Jarel says:

        Inline assembly from scratch, I meant.

      • Erik Johnson says:

        Nah, unless using specific opcodes C wouldn’t compile to. I have used it for inserting an “INT 3″ for debugging purposes (x86) before, but that’s hardly much of anything

  7. Aprone says:

    I was very happy to read some comments that have escaped the mindless “My teacher told me not to/I’ve heard it is evil/I’ve heard is makes you a bad programmer” answers. This actually made my morning to learn that there are, in fact, other people out there who understand that the compiled assembly code is using GOTOs in the end anyway. I have never wasted my time avoiding the use of a GOTO just for the sake of avoiding it. A single GOTO can usually turn 5 minutes worth of coding into a 30 second ordeal. Just use it responsibly. :)

    • Erik Johnson says:

      I’m also happy to see the goto circlejerk. I learned assembly before I did C, and when coming from an understanding of a machine’s execution flow you (I) tend reduce a statement into its assembly equivalent in my head as I write it out and make optimisations on the fly, goto is one of those – most commonly in a non-conditional loop with an exit mid-execution, and/or several loops deep.

      “OMG it is messy~” is no excuse, tab your shit. Put the destination labels out-of-indent from the flow. “Where is that goto going?” “Oh, there is the label!” vs “where is this nest of conditional breaks ending?” “Hmm, close curly.. if/then.. close curly.. close curly.. does this curly line up with the start of the loop I’m breaking? Oh yeah. Here we are.”

      • spike says:

        Best practices have contexts, there are(were) contexts where goto is a best practice; ex. in malloc/release C code a single exit discipline – often implemented with gotos – was followed. In RAII C++ the single exit discipline is unnecessary, and gotos are harmful, evil, bad, whatever. In C# there are another set of best practices, etc…

        I have maintained old C Code w/plenty of Gotos within; the real problem with gotos is there is no expected destination. see a continue you know the loop is starting over, see a break you know the loop is exiting. see a goto, you don’t know if its implementing a loop, a break, a continue, or some other construct; you don’t know where to look!

  8. SavannahLion says:

    Heh, never using GOTO. I remember the first language I tried to learn involved writing line numbers at the beginning of every line. I used GOTO extensively. Living in Bucktooth, Nowhere there was no one around who could formally teach me. So armed with only the book that came with it, no floppy drive, and an eight year olds stupid persistence I would stay up late into the night, crying usually, as I tried to insert new lines of code between poorly numbered lines ane watching my code break because I forgot to alter tthe GOTO.

    After.formal schooling, I avoided GOTO for *YEARS* often creating convoluted and difficult (though at the time I thought brilliant) code.

    I’m older and I have my share of languages under my belt. I’ve since learned the most effective method of writing code means to leverage and understand all aspects of the tools, that includes GOTO.

    • TD-er says:

      Perhaps a bit too late now, to learn some basic BASIC tricks ;)
      But there is a reason why line numbers increased by 10.
      This way you could insert line 21, 22, 23 etc. between 20 and 30.
      To increase the line-count-distance, you could call “renum”, which also corrects the GOTO and GOSUB statements.

  9. Sam says:

    I was just burned by an ancient GOTO in a FORTRAN program yesterday. I had an invalid condition that should have been handled just a couple of lines earlier, but because I see GOTOs so rarely it took me a while to catch on to the fact that the previous code was being skipped under certain conditions.

    Somehow it took 25+ years for someone to notice the bug.

  10. Jac Goudsmit says:

    All discussions of “goto useful” / “goto bad” aside… if a simple “for(;;) do_something();” doesn’t produce the same code as “label: do_something(); goto label;”, it means the compiler is buggy or you’re doing something wrong.

    • yquemener says:

      for(;;) or while(1) indicate loops more clearly than goto. I wouldn\’t be surprised if some compilers managed to unroll loops, when the optimizations flags are enabled, while failing to do so with goto. Therefore, a for(;;);do(); could be compiled as label:;do();do();do();do();do();do();goto label; while a label:;do();goto label; wouldn\’t be modified.

      That said, I agree with the general sentiment that too often people repeat arguments without understanding them.

      • Maybe, however my code *is* an unrolled loop. And the unroll is much more agressive than the compiler ever could. So there is no point in unrolling this any further. If you do not follow my point please analyze how my code gets expanded by the macro processor and then the compiler.

        Again: this was no exercise in structured programming. It is an example for the price of extreme performance optimization. After the algorithm is optimized (and I did this) the only thing that remains is to break down abstractions and to squeeze out any overhead. Nobody ever said, that this will increase readability or maintainability.


    • All discussions of “goto useful” / “goto bad” aside… if a simple “for(;;) do_something();” doesn’t produce the same code as “label: do_something(); goto label;”, it means the compiler is buggy or you’re doing something wrong.

      I think I disagree. The “simple” loop construct opens up a new variable scope similar to an anonymous subroutine. Thus if the loop body is sufficiently large the optimizer may come to suboptimal conclusions. In my example the loop body is extraordinary large. Have a look at how the macros expand.

      So bascially I have to look up what it will generate. On the other side the goto forces the compiler to keep the scope and avoids any possible optimizations.

  11. Mike Bradley says:

    When I started (1978) programing, I had “if (condition) then goto” all over the place!

  12. Mike says:

    The only good GOTO is an ON ERROR GOTO

  13. asdf says:

    Hahah ‘portability’ comments ….

  14. Cyril says:

    JMP

    QED

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 93,533 other followers