C

Roger Cheng

Window Shopping RobotC For My NXT

I remember my excitement when LEGO launched their Mindstorm NXT product line. I grew up with LEGO and was always a fan of the Technic line letting a small child experiment with mechanical designs without physical dangers of fabrication shop tools. Building an intuitive grasp of the powers of gear reduction was the first big step on my learning curve of mechanical design.

Starting with simple machines that were operated by hand cranks and levers, LEGO added actuators like pneumatic cylinders and electric motors. This trend eventually grew to programmable electronic logic. Some of the more affordable Mindstorm products only allowed the user to select between a few fixed behaviors, but with the NXT it became possible for users to write their own fully general programs.

Lego Mindstorm NXT Smart Brick

At this point I was quite comfortable with programming in languages like C, but that was not suitable for LEGO’s intended audience. So they packaged a LabVIEW-based programming environment that is a visual block-based system like today’s Scratch & friends. It lowered the barrier to entry but exacted a cost in performance. The brick is respectably powerful inside, and many others thought it was worthwhile to unlock its full power. I saw enough efforts underway that I thought I’d check back later… and I finally got around to it.

Over a decade later now, I see Wikipedia has a long list of alternative methods of programming a LEGO Mindstorm NXT. My motivation to look at this list came from Jim Dinunzio, a member of Robotics Society of Southern California, presenting his project TotalCanzRecall at the February 2019 RSSC meeting. Mechanically his robot was built from the stock set of components in a NXT kit, but the software was written with RobotC. Jim reviewed the capabilities he had with RobotC that were not available with default LEGO software, the most impressive one being the ability to cooperatively multitask.

A review of information on RobotC web site told me it is almost exactly what I had wanted when I picked up a new NXT off the shelf circa 2006. A full IDE with debugging tools among a long list of interesting features and documentation to help people learn those features.

Unfortunately, we are no longer in 2006. My means of mechanical construction has evolved beyond LEGO to 3D-printing, and I have a wide spectrum of electronic brainpower at my disposal from a low-end 8-bit PIC Microcontrollers (mostly PIC16F18345) to the powerful Raspberry Pi 3, both of which can already be programmed with C.

There may be a day when I will need to build something using my dusty Mindstorm set and program it using RobotC. When that day comes I’ll go buy a license of RobotC and sink my teeth into the problem, but that day is not today.

Roger Cheng

Microchip’s New XC8 Compiler Appears Incompatible With MCC Boilerplate

For the purposes of experimenting with a Pololu stepper motor driver, I wanted to generate pulses from a PIC running a simple program. This meant downloading and installing the latest tools from Microchip for 8-bit PIC development: The MPLAB X IDE, the XC8 compiler, and the MPLAB Code Configurator (MCC).

With these tools set up, I pulled down my previous PIC stepper motor project intending to use it as a starting point. The stepper driver portion will be different, but I wanted the analog dial capability to adjust speed and direction. Before I start modifying code, though, I hit “Build” to make sure everything still compiled.

It did not.

In file included from mcc_generated_files/mcc.c:74:
In file included from mcc_generated_files/mcc.h:52:
mcc_generated_files/interrupt_manager.h:110:6: error: variable has incomplete type 'void'
void interrupt INTERRUPT_InterruptManager(void);
^
mcc_generated_files/interrupt_manager.h:110:15: error: expected ';' after top level declarator
void interrupt INTERRUPT_InterruptManager(void);
^
;
2 errors generated.
(908) exit status = 1

Since “void” is a very fundamental type for C programs, this error tells me this isn’t the matter of a minor typo, something is wrong at a very basic level. As a test, I created a new MPLAB project with a bare skeleton generated by MCC. This “Hello World” program failed to compile in the same way, indicating the problem is a system configuration issue.

A little digging around found the issue was introduced with XC8 compiler version 2.0, introduced just a few months ago in May. It moves C language support up to C99, keeping up with industry standards. However, this change also broke compatibility with old code. Not just old code sitting on a hobbyist’s Github page, but also old boilerplate code generated by MCC.

I expect that Microchip will eventually update these templates in a future MCC update, but for now, PIC programmers that use MCC for rapid prototyping will need to change their project settings to fall back to the older C90 standards. See xc8 2.0 migration document here for more details on this workaround.

 

Roger Cheng

Cache is King

15Puzzle

C is an old familiar friend, so it is not part of my “new toolbox” push, but I went back to it for a bit of refresher for old time’s sake. The exercise is also an old friend – solving the 15-puzzle. The sliding tile puzzle is a problem space that I studied a lot in college looking for interesting things around heuristic search.

For nostalgia’s sake, I rewrote a textbook puzzle solver in C using the iterative-deepening A* (IDA*) algorithm employing the Manhattan Distance heuristic. It rubbed off some rust and also let me see how much faster modern computers are. It used to be: most puzzles would take minutes, and the worst case would take over a week. Now most puzzles are solved in seconds, and the worst case topped out at “merely” few tens of hours.

Looking to further improve performance, I looked online for advances in heuristics research since the time I graduated and found several. I decided to implement one of them named “Walking Distance” by the person credited with devising it, Ken’ichiro Takahashi.

From the perspective of algorithmic effectiveness, Walking Distance is a tremendous improvement over Manhattan Distance. It is a far more accurate estimate of solution length. Solving the sliding tile puzzle with the Walking Distance eliminated over 90% of duplicated work within IDA*.

On paper, then, Walking Distance should be many orders of magnitude faster… but my implementation was not. Surprised, I dug into what’s going on and I think I know the answer: CPU cache. The Manhattan Distance algorithm and lookup table all would easily fit within the 256kb L2 cache of my Intel microprocessor. (It might even fit in L1.) The Walking Distance data structures would not fit and would spill into the much-slower L3 cache. (Or possibly even main memory.) It also takes more logical operations to perform a table lookup with Walking Distance, but I believe that is less important than the location of the lookup table themselves.

In any case: with my implementation and running on my computer, it takes about 225 processor cycles to examine a node with Manhattan Distance. In contrast, a Walking Distance node averages over 81 thousand cycles. That’s 363 times longer!

Fortunately, the author was not blind to this. While building the Walking Distance lookup table, Takahashi also built a table that tracks how one lookup state transitions to another in response to a tile move. This meant we perform the full Walking Distance calculation only on startup. After the initial calculation, the updates are very fast using the transition link table, effectively a cache of Walking Distance computation.

Takahashi also incorporated the Inversion Distance heuristic as support. Sometimes the inversion count is higher than the walking distance, and we can use whichever is higher. Like walking distance, there’s also a set of optimization so the updates are faster than a full calculation.

Lastly, I realized that I neglected to compile with the most aggressive optimization settings. With it, the Manhattan Distance implementation dropped from ~225 cycles down to ~75 cycles per node.

Walking Distance was much more drastic. By implementing lookup into the transition table cache, the per-node average dropped from 81 thousand cycles to ~207 cycles per node. With fully optimized code, that dropped further to ~52 cycles per node. Fewer cycles per node, and only having to explore < 10% of the nodes, makes Walking Distance a huge winner over Manhattan Distance. One test case that took tens of hours with Manhattan Distance takes tens of minutes with Walking Distance.

That was a fun exercise in low level C programming, a good change of pace from the high-level web tools.

For the curious, the code for this exercise is up on Github, under the /C/ subdirectory.