Preston L. Bannister { random memes }

Took off this week and last with no specific plans. Might have gone driving (might still), but I made several trips in the last year, so … (shrug). Guess I have been on a bit of a home improvement kick. Imagining a new bit, and – much work later – seeing an entirely satisfactory end result, is nice.

Was out in the garage last night, planning the next bit, when my daughter popped out of the house. “Oh, you’re thinking again, aren’t you?” She was not surprised to find me sitting and staring for an hour, before starting on the next bit.

Seems I use roughly the same approach whether cooking, building things out of wood and metal, or writing software. When cooking I never use recipes, I am always changing something, and usually get good results. When building I never use plans (other than occasional rough sketches), will think through the problem and build the next bit in my mind, before starting manufacture – and usually get good results. When writing software I do not have much use for design documents or formal processes, but cannot start until I have thought through the problem, and usually get good results.

In each case I can visualize the end result before I start. In each case I am working without plans (written plans or plans from others), yet … I always have a plan.

As I learned back in school, this pattern of work does not work at all for some of my peers. My upper-division Physics lab class was the first clear example. The lab was – at base – one student alone in a room with a pile of equipment, and a set experiment to complete in a couple weeks. The lab had a new instructor when I took the class, and he was not familiar with the equipment. Also, for some reason, none of the equipment worked. So with little or no instructions, I had to figure out what the equipment did, how it should work, and what needed to be fixed.

Getting the experiments to work was both frustrating, and fun!

Midway through the course, the instructor assigned another student to work with me, as this guy was not doing well by himself. I knew the guy, counted him as a bit of a friend, and thought he was at least as good as I at the theory classes. But in the lab, he drove me nuts. I needed silence so I could visualize how things should work. For the parts I did not understand well enough to visualize, I would disassemble and play with the equipment, until I better understood how it worked.

I suppose it looked to the other guy like I did things in no particular order, while ignoring anything he said. After an indeterminate period of seemingly aimless activity, he’d suddenly hear “Ah … I get it!”, followed by an ordered, logical explanation, and a burst of activity – after which the equipment would (usually) work.

Bet I drove him a bit nuts, as he did to me.

Also, up to that point in the lab class, I thought I was doing poorly. Most times – when the instructor dropped by – the equipment was not working, and I had no coherent explanation (or so I felt) of what to do next. Once the equipment was working, I could – in short order – perform the experiment, and move to the next lab.

Bet also my more present co-workers see something similar – an indeterminate period of seemingly aimless activity, followed suddenly by a burst of activity and plans. Probably drives some folk – of differing nature – slightly nuts.

So my daughter caught me planning, again …

Part of our economic mess starts with the huge flow of dollars sent outside the country to buy oil. We could produce oil from domestic sources, but the base cost is higher than pumping oil out of the ground and shipping halfway around the planet. If the market price is high enough, investing in production from domestic sources looks like a good idea. If the price of oil on the global market drops – as it did in the 1980’s, then domestic production cannot compete.

If you visit towns in western Colorado and south-eastern Utah, you can see a boom-and-bust pattern of development for the 1970’s and 80’s. In the 1970’s the notion of extracting shale-oil got a lot of investment, and caused a modest boom in development. The low oil prices of the 1980’s killed investment in (then uneconomic) shale oil extraction, and development slowed. Investment in shale-oil production since that time has proved a bit slow, as investors are not entirely confident the world oil prices will stay high enough for profitable production.

Keeping dollars in America means more productive economic activity within the country. Domestic oil production should help stabilize consumer prices. How can we fix the cost of imported oil high enough so that domestic production stays profitable?

We could place a tax on imported oil, but this seems likely to become a mess. How would we tax different grades of oil? What about refined products? Is politics likely to grant different rates to different nations and oil companies? We would need a new bureaucracy to set tax rates, would most likely get things slightly wrong, and create new nonconstructive opportunities for politics and corruption.

Better to not create new opportunities for bad behavior.

A far simpler approach would be to place a large retail tax on gasoline, and offer an equally large tax credit for domestic oil production. The idea is to have no net effect on the retail cost of gasoline produced from domestic sources, but make non-domestic sources more expensive – enough so that domestic production is profitable, and investment in domestic production is safe.

I once heard that shale-oil production is profitable when the world oil price is above $70 per barrel. The low point in world oil prices (that killed development of shale-oil production) was around $30 per barrel. A tax of about $40 per barrel (or $1 per gallon of gasoline) should be enough to insure that domestic production is assured profitable. Given assured profits, all feasible forms of oil production (including sustainable production from biologic sources) should be able to attract the level of investment that they need.

Put differently, by making one simplest-possible change in the ground rules, we can let the market solve the production problem, without more-complicated government intervention.

My favorite hash function is without doubt the Pearson hash. In my measurements, for my usage, custom hash tables built using a Pearson hash to index into a power-of-two-sized table, have always performed better than the best alternatives. (For not-small tables each table slot is the root of a binary tree.) Certainly this result is going to be somewhat specific to the use-case and current CPU architecture, but each time performance was important, my solution – using binary trees in 256 hash buckets, using the Pearson hash – won the benchmarks.

The main limitation of the Pearson hash is that it only computes an 8-bit value (i.e. the range 0..255). For some problems a bigger range of values would be good. The means offered in Pearson’s original paper (as I recall – threw out the old magazine long ago, and the paper is not on the web) was to run the algorithm more than once to add additional 8-bit chunks to the hash.

Just now I’m feeling like a bit of an idiot, as it seems the Pearson hash could be easily extended up to 16-bits (or a bit beyond) with a ridiculously small change.

The original Pearson algorithm:

static unsigned char T[] = {
    // The values 0..255 shuffled into random order.
};

static inline unsigned hashOf(unsigned h,const char* s) {
    for (int c = *s++; c; c = *s++) {
        h = T[h ^ (255 & c)];
    }
    return h;
}

The algorithm modified to generate a 16-bit hash:

static unsigned short T[] = {
    // The values 0..65535 shuffled into random order.
};

static inline unsigned hashOf(unsigned h,const char* s) {
    for (int c = *s++; c; c = *s++) {
        h = T[h ^ (255 & c)];
    }
    return h;
}

Note that only the type and size of the table T changed!

With the large cache sizes of current CPUs, the 128KB table will fit nicely into cache, and perform very well. On CPUs with smaller caches, you might want to use a smaller table. Also clearly the table size for a 32-bit hash would be huge. You might want some sort of test for degenerate patterns in T[] (though I’d guess the probability of getting a bad table is very small).

This notion is so simple, I am a bit surprised that no one (so far as I can tell) suggested this approach before.

For large numbers of keys, each bit added to the hash value saves the equivalent of a key comparison. Adding 8-bits to the key saves 8 key comparisons. If the expense added to the hash function is less than the cost of one key comparison (certainly true of string compares), then you are ahead from the first bit added.

Needed to get IM working from my Ubuntu Linux boxes to my employer’s Microsoft Office Communicator (2007?) service. Was using the Microsoft Messenger 4.7 client in a VM hosting Windows, but of late this seems to not work well enough for some of my coworkers (since I am often not actively using that VM).

I had looked at this over a year ago, but the SIPE support for Pidgin did not support the options needed for the IM service as configured by the company. On checking again, it seemed possible that the current version might work, but I needed the most recent version of Pidgin and the SIPE plugin.

So … for future reference.

Building Pidgin and the SIPE plugin from sources on Ubuntu

1. Install the dependencies needed to build from sources.

   sudo apt-get build-dep pidgin pidgin-sipe
   

2. Remove any existing installation.

   sudo apt-get remove pidgin pidgin-sipe libpurple-dev
   

3. Download Pidgin sources.
4. Change to the directory in which you unpacked the Pidgin sources, and build.

   ./configure
   make
   sudo make install
   

5. Download Pidgin SIPE plugin.
6. Change to the directory in which you unpacked the SIPE plugin sources, and build.

   ./configure
   make
   sudo make install
   

7. Now run Pidgin. It should appear in the usual Gnome menu, or can be run from the command line. Given that figuring out the right options for you company’s setup can be tricky (it was for me), you might want to do the initial connection setup with debug output from the command line.

   pidgin -d
   

   Not strictly necessary, as the “Debug Window” (got to via the “Help” menu) offers the same(?) information.

   You might also want to (temporarily) disable any other IM accounts you have configured.

Figuring out the right options to use with your company IM service … you are on your own.