Elective Thinkpad X31 Surgery

My trusty IBM Thinkpad X31 that Stanford bought me in 2003 has taken everything I've dished at it with only a couple of cracks in the case to show for it. At least, until recently. One awful afternoon, after hitting the power button I was briefly greeted with the message "Fan error" before it shut itself off. No amount of coaxing would bring it back.

My desktop is truly ancient, dating back to the last millennium, so I had grown accustomed to doing most tasks on my laptop instead. The first task was to retrieve my data, which is easily achieved with a SATA/IDE to USB adapter. Only one screw needs to be removed to retrieve the hard drive.

I was tempted to take the easiest but most expensive path: shell out for whatever passes for the best of the Thinkpad X series these days. But although working in industry means this remedy wouldn't sting as much as in my student days, it also means I don't spend as much time on my own machines. Now there's other things I'd prefer to get for that kind of money. Similarly, I didn't want to pay for it to be serviced.

My only recourse was to attempt a repair myself. The Lenovo webpage about servicing the Thinkpad X31 spooked me a little. What's going on in that diagram? Do I have to take it apart into a hundred pieces just to replace a fan? The table suggesting that fan replacements should not be undertaken by end users wasn't encouraging either. With a heavy heart, I ordered a 67P1443 fan anyway.

When it arrived, enthusiasm and impatience triumphed and I took out every screw I could see, but the fan remained elusive. Eventually I regained some sense, and Googled for "thinkpad x31 disassembly". The first result contained a links leading to the official Thinkpad X31 hardware maintenance manual. I should have known. What isn't online these days?

Fan replacements turn out to be almost trivial. After removing the battery and hard drive, I only had to remove the four clearly indicated keyboard screws, and then slide the keyboard out. Underneath, I discovered the reason for the fan error. Nestled in the fan blades was a tiny piece of foam, sticky on one side and rose-tinted on the other. A pink pad in my Thinkpad.



I suspect that the fan is still operational, but since I had a new one and had already removed the five screws securing it, I replaced it anyway. Also, it's easier to apply thermal paste to a new fan than clean and reapply to an old one.

The tougher part was figuring out where the pink pad belonged. There was another one in there somewhere that also looked like it had been slightly dislodged. I settled on pressing both of them against some metal frame in the center, where I presume they work best as shock absorbers.



Soon after I received my laptop I wrote a webpage about Linux on a Thinkpad X31. Only when I started blogging did I realize it would be much easier (for me at least!) to maintain with blog posts, and that's probably what I'll do in the future if I have more to add. Sure, it's nice to have all information in one place, but this can be approximated through appropriate use of tags. Furthermore, the dates on each post may also give the reader some idea of how relevant it is.

ALSA and MIDI

I switched to the ALSA driver from the OSS driver for my Creative Sound Blaster Live! card long ago, but I'm still not used to how MIDI is done. I'll record the relevant commands this time, so I won't have to look them up yet again.

Lately, I've had to manually load the snd_seq kernel module.

Programs I wrote that look at /dev/midi00 should now look at /dev/snd/midiC0D0. The behaviour of this device file differs too: I had to change my code so that it could handle a read() call that returned less than the requested number of bytes.

To play MIDI files on my digital piano, I run pmidi -p 16:0 foo.mid.

To send MIDI events to fluidsynth from my digital piano, I run fluidsynth 2> /dev/null (to get rid of spurious warnings), load a soundfont, then run aconnect 16:0 128:0.

Nvidia GeForce 3 Cards on Debian

For a long time I used the Debian nvidia driver packages, but GeForce 3 Ti 200 cards are now considered legacy cards, and not supported by the 97xx and newer series. After a recent upgrade, I had to remove my Debian nvidia packages and

1. Download the 96xx series Nvidia Linux drivers.
2. Run the install script as root.
3. Since I use the xorg X server, I had to move files around:
   mv /usr/X11R6/lib/lib* /usr/lib/xorg/modules/
mv /usr/X11R6/lib/modules/drivers/* /usr/lib/xorg/modules/drivers/
mv /usr/X11R6/lib/modules/extensions/* /usr/lib/xorg/modules/extensions/
   

The BAD Library

Not long after my last post I wrote some code to get some rough timings, and also to experiment with variations of hash tables that my textbooks never taught me: with cuckoo hashing you can have expected constant-time insertion and worst-case lookup time. Additionally, with cells, you get hash tables that can handle over 90% load. Also, hash functions recommended by classic textbooks are no good: Bob Jenkins' hash functions are much better.

Along the way I had to implement (or import from other projects of mine) other abstract data types. Soon I had crit-bit trees, hash tables, linked lists and dynamic arrays.

I finally got around to packaging it up: bad-0.0.0.tar.bz2.

BAD stands for Ben's Abstract Datatype, and also refers to the current state of the code and documentation. See the README for the preliminary results.

Trees, Hash Tables and Tries

As a computer scientist, I'm supposed to possess thorough grounding in fundamental data structures and algorithms. I must be getting rusty, for lately I've been perturbed by basic facts taught to novices.

After some thought I've resolved my difficulties, but now I feel many textbooks need to be rewritten. Either that, or I've made a monumental embarrassing mistake.

Let's say you want an associative array that maps strings to something.

I've known for years that hash table lookups take O(1) time. And that binary search trees have O(logn) lookup time. (In both cases I'm assuming certain conditions are satisfied, i.e. there aren't too many hash collisions and that the binary tree is fairly well-balanced.)

More recently, I learned about crit-bit trees, aka radix trees, Patricia trees or Patricia tries. (See D. J. Bernstein's crit-bit tree page for more references. Briefly, crit-bit trees are like binary trees with two major differences. Firstly, they are tries, which means keys are not stored in any non-leaf node and instead, the position of a node on a tree represents the prefix of the keys stored in its descendant leaves. Secondly, no node has only one child: a crit-bit tree is a trie where any node with a single child has been merged with its child.)

What's the cost of a lookup in a radix tree? It sounds like it must be O(logn) because you need a tree of that depth to store n things.

But you only need to touch each bit (or character, in a k-ary tree where k is the size of the alphabet) at most once during a lookup to decide which descendant of a node to traverse. Isn't this the same as determining the hash of a string? To compute it correctly we must involve every bit of the key. (If traversing the tree is cheap enough, then crit-bit trees are faster than hash tables. Furthermore, unlike a hashing operation, only certain bits, the aptly-named critical bits, need be examined in a crit-bit tree.)

Thus the lookup cost of a radix tree must also be O(1). Therein lies a problem. Why is it that a binary tree of the same size has an O(logn) lookup time? We travel along the same number of nodes!

The answer is that usually when computer scientists analyze these data structures, as an approximation, we view computing the hash function as a constant-time operation, and similarly for a comparison in the binary tree. But to refer to n different objects, the keys must have length at least O(logn), which means it actually takes O(logn) time to hash a key, or to perform a key comparison.

So what we've been saying is that it's okay to ignore a factor of logn. This is sloppy and inconsistent. Why can't we ignore the logn steps required to walk down a binary tree as well? Why can we turn a blind eye to one logn yet scrutinize the other?

We should say that hash lookups and crit-bit tree lookups cost O(logn) (or more accurately, O(m) where m is the size of the keys, which must be at least logn), and that binary tree lookups cost O((logn)²).

This inaccuracy caused me to initially overlook that crit-bit trees could match or even outperform hash tables. It's possible that others have suffered from the same affliction: despite being described (twice, independently) in 1968, the courses and textbooks from my time do not mention radix trees at all, and I suspect the teachers and authors responsible may also not have realized how fast these data structures can be.

This is a shame because they have other advantages over hash tables too: crit-bit trees are deterministic with good worst-case times, grow and shrink as needed (they never require an expensive rehashing nor let vast tracts of an array lie fallow), and support successor and predecessor operations.

The good news is that they seem to be gaining prominence. I feel they are mentioned more on the web (and I'm helping this as well!). I've heard evidence that some CS undergraduates these days are at least aware of their existence. The fact that even I know about them now means they can't be that obscure.

Prisoner Problems

Quite a few well-known logic puzzles involve a prison setting, giving them a darker tone that makes them memorable and more fun to think about.

This joke prisoner problem is amusing but impossible, as its rather surreal solution involves English homonyms.

I also won't bother describing the famous prisoner's dilemma from game theory.

Then there's the paradox about the prisoner who's told he'll be executed some time next week and that it will be a surprise. So he reasons thus: "They can't kill me on Friday, because I would know by Thursday night and it would not be a surprise."

"But this implies if they haven't killed me by Wednesday night, then I know I'm dead on Thursday because I can't be killed on Friday. Which means it wouldn't be a surprise. Hence I cannot be executed on Thursday."

"Repeating this argument a few times shows that I cannot be executed on any day next week!" he concludes triumphantly.

But on Tuesday morning he is executed, much to his surprise! What's going on?

And there's the tale about the prisoner who is to choose his method of execution: if the last statement he utters is true then he is executed in some gruesome fashion, and on the other hand, if it is false then he is executed in some different but equally gruesome fashion. (The particular methods of execution change from telling to telling. I just can't think of any right now.) What should he say?

A tougher puzzle involves one-hundred prisoners in a prison that contains one-hundred cells and a single room with a single light bulb that can be turned on or off. Every day a prisoner is chosen at random and placed in the room. At any time, any prisoner can ask for freedom. When he asks, if every prisoner has spent at least one day in the room with the light bulb then everybody is set free. (The warden has been keeping track.) Otherwise everybody is executed.

The prisoners can talk amongst themselves before entering this bizarre jail, but once inside they are kept isolated, and the light bulb becomes their only means of communication. How can they free themselves?

Lastly, there is a similar problem that is the main reason for this post. A friend told me this puzzle a few months ago and I don't want to forget it.

Again, there are one-hundred prisoners and a special room, but this time the room contains one-hundred identical boxes, each containing exactly one slip of paper bearing a prisoner's name. Every prisoner's name is present, but no one knows which box contains which name.

The prisoners are taken to the room one at a time. Once inside they are allowed to open and examine the contents of up to fifty boxes. They must then leave the room as they found it, so the boxes they chose are closed when they are done.

After all prisoners have visited the room, if each prisoner has seen his name on a slip of paper then they are all free to go. Otherwise they are all executed.

As before, they can all examine the room and boxes (but not open them) and devise a strategy together beforehand, but no communication is permitted once the process begins.

Clearly if a prisoner picks fifty boxes at random he has only a 50% chance of finding his own name, and if every prisoner does this then the chance that all of them find their names is 1/2^100. That is, they will almost certainly be executed.

How can they obtain at least a 30% chance of surviving?

Shiny Colourful Buttons

Here's a trick I've seen mentioned in other geeky blogs that deserves to be more well-known and widespread: only have page icons (favicons) on the Firefox bookmarks toolbar. Simply delete the names in bookmark properties. Or try the Smart Bookmarks Bar extension. Note separators can be inserted to help organize the icons.

Not only is it stylish, but it frees up precious toolbar real estate for more bookmarks. Also I find myself drawn to the pretty little pictures. I visit those enticing links more often nowadays.

One might worry about forgetting which icon does what, but presumably the links on one's toolbar are frequently used, making this unlikely. Anyway, to find out where they go, just click on them! (i.e. the standard action following the thought: "I wonder what this button does...")

The sole drawback is that some webpages don't have icons, or have one that looks identical to another, or looks horrible. To solve this, use the Favicon Picker 2 extension to assign a good icon to that bookmark.

A related idea is to hide text on certain tabs, which can be achieved using the FaviconizeTab extension.

By the way, googling for "favicon picker" finds many of the aforementioned blog posts [1, 2, 3, 4, 5], some containing great screenshots. Not everyone is enthralled by the idea however, and some even want the opposite.