The Boston Diaries

The ongoing saga of a programmer who doesn't live in Boston, nor does he even like Boston, but yet named his weblog/journal “The Boston Diaries.”

Go figure.

Friday, September 05, 2008

Yet even more stupid benchmarks

Yet another silly optimization problem. This time, from a silly coding challenge to find the number of integers expressible with unique digits (that is, no single digit repeats) in a base-10 representation up to the value 10,000,000,000 (there are 8,877,690 such numbers, by the way).

The neatest and fastest solution was final program on this page, written in C#. It generates only such numbers; it doesn't try to test each number. Since I don't use C#, I decided to translate the code in C to play around with it. Wasn't all that hard:

#include <stdio.h>
#include <stdlib.h>

int total = 0;
const int pre[(1 << 10) + 1] /* = { ... } */ ;

void generate2(
        int maxlen,
        int currentlen,
        int availabledigits,
        int currentvalue
)
{
  int last = (currentlen == maxlen - 1);
  int x    = availabledigits;
 
  while(x != 0)
  {
    int digit = pre[x ^ (x & (x - 1))];
    x &= (x - 1);
   
    if (digit == 0 && currentvalue == 0)
      continue;
   
    if (last)
      ++total;
    else
      generate2(
        maxlen,
        currentlen + 1,
        availabledigits & ~(1 << digit),
        (currentvalue * 10) + digit
      );
  }
}

int main(int argc,char *argv[])
{
  int len;
 
  for (len = 1 ; len <= 10 ; len++)
    generate2(len,0,0xFFF >> 2,0);

  printf("total: %d\n",total);
  return EXIT_SUCCESS;
}

I pregenerated the pre[] array since I wanted this to run as fast as possible. The code used to generate the array:

for (i = 0 ; i <= 10 ; i++)
  pre[1 << i] = i;

Anyway, once written and compiled (gcc -O4 -fomit-frame-pointer f.c) it ran in about 0.2 seconds (average run) on a 2.6GHz machine. Fast, but I could go faster by running it across the two CPUs in the box. I was expecting about half the runtime, since this is easily parallelizable.

It ran in about 0.16 seconds, a rather disappointing ¾ time. I commented out the code in generate2() just to test the overhead of threading and syncronization and that isn't a factor (program ran in 0.001 seconds).

Undaunted, I decided to try one of the quad-core boxes at The Office. Reworked the code a bit to split the load between four CPUs as evenly as possible, and ran some tests.

0.13 seconds on average. Still not quite half the speed.

Hmmm …

Obligatory Picture

[It's the most wonderful time of the year!]

Obligatory Links

Obligatory Miscellaneous

You have my permission to link freely to any entry here. Go ahead, I won't bite. I promise.

The dates are the permanent links to that day's entries (or entry, if there is only one entry). The titles are the permanent links to that entry only. The format for the links are simple: Start with the base link for this site: http://boston.conman.org/, then add the date you are interested in, say 2000/08/01, so that would make the final URL:

http://boston.conman.org/2000/08/01

You can also specify the entire month by leaving off the day portion. You can even select an arbitrary portion of time.

You may also note subtle shading of the links and that's intentional: the “closer” the link is (relative to the page) the “brighter” it appears. It's an experiment in using color shading to denote the distance a link is from here. If you don't notice it, don't worry; it's not all that important.

It is assumed that every brand name, slogan, corporate name, symbol, design element, et cetera mentioned in these pages is a protected and/or trademarked entity, the sole property of its owner(s), and acknowledgement of this status is implied.

Copyright © 1999-2019 by Sean Conner. All Rights Reserved.