Nearest power of two

I was inspired by some code that I saw on StackOverflow that computed base-two logarithms in O(log2(N)) operations, where N is the number of bits in the integer. The following function computes the nearest power of two that is not less than a given value. I've compiled it with gcc and clang, and it optimizes into branch-free code.

 int nearest_power_of_two(int x)
 {
   unsigned int z = ((x > 0) ? x - 1 : 0);
   z |= z >> 1;
   z |= z >> 2;
   z |= z >> 4;
   z |= z >> 8;
   z |= z >> 16;
  return (int)(z + 1);
 }

Here is a related function, a simple log2() calculator for 64-bit values. Unlike the function above, it rounds down instead of rounding up. Note that the compiler should automatically unroll the loop:

 int log2_int(unsigned long long x)
 {
   static const unsigned long long t[6] = {
     0xFFFFFFFF00000000ull,
     0x00000000FFFF0000ull,
     0x000000000000FF00ull,
     0x00000000000000F0ull,
     0x000000000000000Cull,
     0x0000000000000002ull
   };
 
   int y = 0;
   int j = 32;
   int i;
 
   for (i = 0; i < 6; i++) {
     int k = (((x & t[i]) == 0) ? 0 : j);
     y += k;
     x >>= k;
     j >>= 1;
   }
 
   return y;
 }

More efficient implementations exist that use CPU intrinsics, but I love the simplicity of these algorithms. I can't claim credit for either of these, since they are just slight modifications of existing code.

Back to training!

Wow, it's already March! The Calgary Marathon is just 3 months away, so I don't have time to train for a full marathon, but it might be nice to do a half. Hard to believe that I ran six consecutive marathons between May 2011 and Aug 2012… six marathons in 16 months. And all those four-hour training runs, I can't even count the number of times that I've run back and forth across this city. Yeah, a half-marathon will be a nice change.

Also, about the toenail that I lost after the Edmonton Marathon, it grew back after about three months. I did take before and after photos, but honestly, is that something that anyone really wants to see?

Virtual revisitation

Here's another way to waste time with Google: find foreign city streets that you visited in years past. And what better time to do so, than on the 10th anniversary of the visit? The photos are of a small street at the southwest corner of Akihabara Station in Tokyo. The first is a photo that I took in 2002, the others are Google photos taken in 2008 and 2009. Hey, Google, where are some pics from 2012?

Lost a toenail. Oops!

After the Edmonton Marathon, my baby toenail was floating on top of a blister. So I guess that I shouldn’t be too surprised that the whole toenail came loose. I was wiggling it around and it fell right off… oops! So now I'm recording the toe and the date, so that I'll know exactly how long it took to grow back. Left baby toe, September 6th. Expect another post on this matter in a few months.

Fast power-of-two check

power of two

Is N a power of two?

This fits into the "bit trick" category. How can you check if a number is a power of two, without writing a loop? Here is a method I found on a couple websites a few years back (can't remember which ones):

  if (n != 0 && (n & (n-1)) == 0) {
      /* n is power of two */
  }

The reason that "n & (n-1)" is zero for a power-of-two is shown in the picture. Subtracting one will only clear the highest bit if it is the only bit that is set (and powers-of-two are the only numbers that have only one bit turned on). However, you also have to check if n is zero, because anything & zero is zero.

Edmonton again

Last year Edmonton was my most enjoyable marathon (even with the extreme heat), and I was looking forward to running it again this year. And I did run it… but it wasn’t quite as much fun.

So what went wrong? Well, I usually fuel up before a race with a bowl of oatmeal, which I had prepared just the way I like it the day before. Unfortunately, the hotel microwave was, well, too dirty to use. I ate my oatmeal cold and my stomach was very slow to digest it. Then, horror of horrors, I didn’t make it to the start line on time (the train schedule is pretty sparse on Sundays, and finding stations in a strange city ain’t the easiest thing even if you have a map). But just four minutes late, which isn’t the end of the world.

The race itself was just a bit slow (even though I was passing tons of people thanks to my late start), but at the halfway point I found myself next to another experienced runner named Budd who encouraged me and helped to keep me from losing speed. Well, it helped for a while… but at 34k I hit the wall hard and just shuffled along for the final few kilometres. My final time was just under 3:30.

Food and tardiness were factors in my underwhelming performance, but the main issue was training. Because this was my third marathon of the year, I’d been training since November, around 9 months in total. My training regime has become stagnant, all I do is run. No core training, no weights, and even my “sprints” are just fast runs. So I’m taking a break (if you can call 50k a week a “break”) and will resume serious training in January, in preparation for the next Calgary marathon.

A very compact list type

I still do some programming in C, and like to indulge myself by creating my own container types instead of using the standard template library. One of my favorite custom containers is a null-terminated list that has one-third the memory overhead of std::vector and std::list but is still efficient and growable.

Let’s say that you need to store a list of pointers or IDs, and you need to efficiently add to, remove from, or iterate through the list. If the item size is only 8 bytes (e.g. for a 64-bit pointer), then the std::list overhead of 16 bytes per node (plus the malloc chunk overhead) means that at most one third of the allocated memory will be used to store your items. The std::vector doesn’t have any per-item overhead, but it does have a fixed overhead of 24 bytes.

A null-terminated list (or vector, if you prefer) has a fixed overhead of just 8 bytes when empty, i.e. the size of a pointer. Because it is null-terminated, it doesn’t need a “size” member like std::vector, and a simple trick allows it to be growable without storing its size. In terms of functionality, it is essentially a very compact std::multiset with O(N) operations, i.e. it is at its best when used to store a small number of items. For a large number of items, the small overhead provides little benefit.

Here’s an example of a list of pointers, with append() and remove() methods:

  typedef struct _list_type {
      void **entries; /* the list is just a “void**” */
  } list_type;

  void list_append(list_type *l, void *p)
  {
      size_t i = 0;
      size_t n = 0;

      if (l->entries) {
          /* create a new list if none exists */
          l->entries = (void **)malloc(2*sizeof(void *));
      }
      else {
          while (l->entries[n] != 0) { n++; }
          /* if n+1 is a power of two, double the list size */
          if (n+1 >= 2 && (n & (n+1)) == 0) {
              void **tmp = l->entries;
              l->entries = (void **)malloc((n+1)*2*sizeof(void *));
              for (i = 0; i < n; i++) { l->entries[i] = tmp[i]; }
              free(tmp);
          }
      }
      l->entries[n++] = p;
      l->entries[n] = 0; /* null-terminate the list */
  }

  void list_remove(list_type *l, void *p)
  {
      size_t i = 0;

      if (l->entries) {
          /* find the item in the list */
          while (l->entries[i] != 0 && l->entries[i] != p) {
              i++;
          }
          /* remove the item from the list */
          while (l->entries[i] != 0) {
              l->entries[i] = l->entries[i+1];
              i++;
          }
      }
  }


The trick here is the check for when the list length reaches a power of two, which is a hint to double the allocated space. There isn’t any code to reduce the amount of allocated memory, it is assumed that after the initial growth of the list, the number of items will remain relatively constant.

I’d like to talk about how I used this to add weak pointers to vtkObjectBase, and about how the “(n-1) & n” power-of-two check works, and how the above code can be modified to work more efficiently with the way malloc() and new [ ] handle memory chunks, but this post has probably raised enough eyebrows already. What can I say, I still love C programming, regardless of all the fancy stuff that C++ provides.

Vancouver Marathon

The Vancouver Marathon has been on my list for a long time, and it did not disappoint. The scenery is beautiful (and also very familiar, I lived in Vancouver from 1990 to 1995). My favorite part, undoubtedly, was running through the University of British Columbia and Pacific Spirit Park. I love the cedar forests that surround the university.

All of the ups and downs on the route were a bit of a surprise to me… I didn't remember Vancouver having so many hills! My watch was only a rough guide to my progress, because each kilometre was so different. Eventually I fell in beside a runner who had done the marathon several times before, and he was glad to provide me with a few tips. Unfortunately, though, I started falling behind after we reached Stanley Park.

My final time was 2:58:15. Not quite a personal best, but a good time nonetheless.

Sedona Marathon

Sedona is a very pretty city, in the middle of Arizona's Coconino National Forest and surrounded by red mesas covered in desert vegetation. It is also the site of the most challenging marathon that I have ever run.

Before this marathon, my only experience with Arizona was Phoenix, which is flat, flat, flat. The Sedona landscape is more akin to the Grand Canyon. Not only did the marathon have plenty of hills, but most of it was on dirt roads covered in slippery red dust and fair-sized pebbles. It was very much like the kind surface I would imagine on Mars, but at full gravity (and, thankfully, with plenty of oxygen). As a souvenir, I brought a few grams of red dust back with me in my socks. My finish time was 3:22, a fair bit above my personal best, but all the runners faced the same challenges, and in the end I was third in my age category and sixth overall!

Finish time notwithstanding, it was a wonderful trip. I had the opportunity to visit with my sister and two nieces and to spend plenty of time hiking up the mountains that surround the city on all sides.

Long runs and longer hunger

On Feb 4th I'll be running my next marathon… technically a winter marathon, but because it will be in Arizona, it won't feel like winter to me. Next week the weather in Calgary will be hovering around 15 below zero, while Arizona will be 15 above.

Today, however, the weather in Calgary was perfect. It was almost exactly zero degrees, which is the best I can hope for in January. So I took advantage of this beautiful, sunny day and did a 50km training run, with just 700mL of Gatorade as fuel, to get my body used to burning fat instead of carbs. The fat-to-carb burn ratio is key to marathon performance.

As with any really long run, I was successful in exhausting my body's carb supply. When this happens, a runner hits the proverbial "wall" but for myself (and I'm guessing it is the same for most people who have run a few marathons) the transition is gradual and not as shocking as the name suggests.

There is, however, a strong after-effect that I feel after running my body out of carbs: hunger! This afternoon, I ate like crazy. Lots of bread, a big bowl of chilli, a stack of peas, a couple big yams, a hunk of fish, and constant snacking throughout the afternoon and evening. But my body keeps telling me it wants more, and it will continue to do so until it has digested all this food and re-filled my liver with glycogen. In other words, this hunger will persist all day, but will be gone in the morning. I know because this has happened many times before, it is just one of the less-enjoyable parts of long-distance running.