Hacker’s Delight

and the Arduino (GCC Compiler)

I got a new (used, but new to me) book about computer coding: Hacker’s Delight by Henry S. Warren Jr. This is one of those books that I will read most of more than once, because the material covered is very technical and delves deeply into the intricacies of programming efficiently.

One algorithm that was particularly interesting, for no reason other than the algorithm is clever. This is a method for counting the 1-bits in a binary word. There is the naïve implementation, of course, but iterating through the bits and counting the ones:

for (long j = 0; j < 1000; j++)
{
  x = 0x371FC7C9;
  c = 0;

  for (int i = 0; i < 32; i++)
  {
    c += x & 0x1;
    x >>= 1;
  }
}

I had to run this code 1 thousand times to get a good count. The Arduino (ATMega 328P chip) is FAST! This code ran in 24.58 microseconds per iteration.

There is a much more clever method in the book, which divided the value up into 2-bit blocks and counted the ones using addition, then added the 2-bit values into 4-bits, then 8-bits and finally adding the two 16-bit blocks to get the final count. So I added the code from the book to compare the times:

for (long j = 0; j < 1000; j++)
{
  x = 0x371FC7C9;

  x = x - ((x >> 1) & 0x55555555);
  x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
  x = (x + (x >> 4)) & 0x0F0F0F0F;
  x = x + (x >> 8);
  x = x + (x >> 16);
  c = x & 0x0000003F;
}

This was an impressive optimization, as it ran in zero milliseconds! I increased the loop count to 1 million so I could get a measurable time, and it was still zero milliseconds. WOW! So, I added yet another 1 million iteration loop around the “j” loop. Still zero…

So, 1 trillion iterations in zero milliseconds? That processor is not a super-computer, so something was wrong. I realized the compiler must have been seeing my code as unchanged in each loop and was simply optimizing the loops away.

I added an array with two elements (with identical bit counts) to try to fool the optimizer.

long xx[2] = { 0x371FC7C9, 0x71FC7C93 };
for (long j = 0; j < 1000000; j++)
{
  x = xx[j & 1]; // 0x371FC7C9;

  x = x - ((x >> 1) & 0x55555555);
  x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
  x = (x + (x >> 4)) & 0x0F0F0F0F;
  x = x + (x >> 8);
  x = x + (x >> 16);
  c = x & 0x0000003F;
}

This worked, as I got 8.68 microseconds per execution. This is about 3 times faster than the naïve implementation. Nice.

Now, I may just have a use for that beautiful code someday.

Enhancements

I wanted to display the execution time on a display, so I added the code to a sketch with the test loops in the main loop. Foiled again! The optimized code was, again, optimized away.

I experimented with several changes to fix that. What worked was declaring the array test variable volatile so that the x variable was loaded each iteration:

volatile unsigned long xx[2] = { 0x371FC7C9, 0x71FC7C93 }; 

Garden RGS Construction – Part 4

Hand-laying Track

Straight Stringers

I rip cheap cedar fence boards into ¾” wide pieces, getting four per board. The height of my stringers will be ¾”, so I use the clean-cut sides as the top-bottom. I glue two of these together and cut 1-inch blocks to act as spacers between the straight stringers. (Any stringer scraps can be recycled as spacers.)

I simply glue and clamp these without any nails or screws. The addition of ties and attachment to the baseboard will bond everything together permanently.

Gluing and Nailing Ties

I have a tie-spacing template with ties drawn at 1.2” apart, which gives ten ties per foot. (This is the same as Llagas Creek flex track.) I use small snack-size zipper bags filled with sand as weights for holding the glued ties down while the glue sets. Each bag will cover five ties, so I put them down five at a time.

Once the glue has set, I use a brad nailer to attach each tie to the stringers. Make sure that each nail ends up under the rail by marking gauge lines 45 mm. apart and nailing just outside of those lines. (I thoroughly wet down the ties before I nailed them to help make sure they wouldn’t split.)

Spiking Rail

I start spiking rail down by placing a rail on the ties with a straight-edge and spiking it down in just a few places – say every foot. Then I carefully spike in between those spots, dividing each into halves and so forth until the rail is spiked every two or three ties.

The second rail needs to be spiked in gauge, so I break out my track gauges and put one on each side of the tie I’m spiking. For this rail, I spike the same ties as on the first rail.

At this point I just proceed spiking the remaining ties from one end to the other.

Curved Stringers

I made a curved track jig to use to laminate three pieces per side of bender board or lath cut to ¾” width. I use the same spacers as for the straight stringers. In hindsight, I realized that I could have used fewer spacers on this first curved piece (perhaps using many as construction spacers and not gluing them in place).

I have a curved tie layout template similar to the straight one that I use to get tie spacing consistent.

Garden RGS Construction – Part 3

Building the Matterhorn “table” section

At the high end of the railroad, the elevation above the ground makes it prohibitive to build a retaining wall, so I am going to use a table to elevate the tracks.

Matterhorn table plan

Conventional construction of two 10-foot long, 2-feet wide sections. I’m using treated lumber for everything structural. I got “deck” screws designed for treated lumber: coated with something.

Assembling a frame
Table section in place

I used a string level to set the grade to 2.5%, which is a 3-inch rise in 10 feet.

Setting the grade
Hitting the bubble

I used Urethane foam post mix instead of cement. The way it tended to gush out into a hole because the bag was “floppy” was a problem. In the future, I’m going to get the Urethane in gallon bottles and mix what I need.

First two sections set

The angled sections were difficult, but having an accurate CAD drawing with accurate angles made it doable.

Getting the offset right

Labeling the cuts helped to keep all these similar angles and wood pieces straight. Even with all that, I cut one piece 1-inch too short and had to re-cut it.

Note the various angles

The last two curved sections are read to secure in place. I wised-up and used stakes pounded into the ground and screwed the table sections to them instead of “floppy” boards and clamps.

The three “curved” sections

I covered the frames with 1/4″ hardware cloth, stapled in place.

Hardware cloth installation

I ripped a treated two-by-four in half at a slight angle to form side-rails that will keep the soil and ballast on the table.

Side rails

I used a heavy, professional-grade ground barrier on top of the hardware cloth to provide drainage and keep the soil in place.

Ready for Track!

Next time: Building turnouts and track.

Dry Stack Stone Retaining Wall

I have a path in the back near the railroad that is below ground level on one end. I built a dry stack stone retaining wall with the native basalt I had dug up throughout the yard. First I established a string line to define the edge, and picked the “best” stones for the foundation. They should each be large and extend from the line to the back if at all possible. Each foundation stone must be on a level base so that gravity works to hold it in place.

Foundation stones

The wall is built up by finding stones that “fit” as closely as possible on the stones beneath. Try to use stones that cross a boundary rather than creating a “vertical seam,” which weakens your structure.

Building the wall

Don’t be afraid of break rocks to fit better, though I did reduce a couple to useless chips with the sledge hammer. It took some time, but I am happy with the result.

Finished retaining wall