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.

Project Properties

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.