The Multithreaded Chicken

Q. Why did the multithreaded chicken cross the street?

A. To the get other to side

Safer Integer Types (part III)

A few days ago (again at the time of writing, but since I accumulate and schedule posts for a weekly release, that may already mean a few months ago) a friend was a bit nonplussed by the fact that an expression such as:

int x;
unsigned int y;

if (x+y<0)
 {
  ...
 }

was simply never true. At first, you’re thinking “how can this be?” because you’re trying to find values of x and y that, summed together, are obviously negative. That is, without counting on the surprising integer promotion/integral conversion system of C and C++.

Let us see what’s going on exactly.

Cutting Corners

Cutting corners is generally thought of as a bad thing. It generally is, I agree. But in some occasions, optimally cutting corners is the right thing to do. I can show you what I mean. Using the Logo programming language (precisely the KTurtle implementation), I devised the following experiment. Consider the following image:

Two circles drawn with KTurtle

Not Loosing the Perspective

My first true computer, a TI 99/4a (which I talk about also in a previous entry), had 16 or 48 KB of RAM, depending whether or not you had one of the memory expansion cartridges, and that limited quantity of memory severely curbed the complexity of the programs one could write on the machine. However, the limited complexity of the programs, the relative crudeness of the development environment (a BASIC shell) and the slow execution speeds weren’t very obvious to me back then. They were somewhat mitigated by the novelty of the computer itself as a machine, and by the perpetual intense excitement of discovery. The arduous design of programs to save memory, fit more graphics or more code, or even getting our programs to work at all was less about constraints than challenge.

The same kind of constraints—or challenge—followed me over the years as I moved on to different computers. Despite their being more powerful, both faster and sporting more memory, the challenge remained there because while the computers got better, so did I at programming. I kept asking more out of the machine, writing increasingly complex programs needing either more memory or more speed, often both. That meant better algorithms, better data structures, and better implementations¹.

The Fizzbuzz problem

You are given the following assignment:

You are to write a program that must fulfill these simple requirements:

For the numbers from 1 to 100,

• If the number is a multiple of 3, print fizz instead of the number.
• If the number is a multiple of 5, print buzz instead of the number.
• If the number is a multiple of 15, print fizzbuzz instead of the number.
• Otherwise, print the number itself.
• Each output should be followed by a new line.

Can you code that and get it right in less than one minute? In less than two? How many retries will be necessary? Open your favorite editor for your favorite programming language. Ready? Set? Go!

Suggested Reading: An Introduction to Genetic Programming for Scientists and Engineers

David A. Coley — An Introduction to Genetic Algorithms for Scientists and Engineers — World Scientific, 2005, 227 pp. ISBN 981-02-3602-6

(Buy at Amazon.com)

This short book introduces the major concepts in genetic programming under the angle of multi-objective optimization in high-dimensional spaces. We learn about the elementary operator of genetic programming such as cross-over, mutation, and candidate selection (with or without elitism). A good quick introduction to genetic programming, with just the right dash of math!

More Blinking Lights (and a disgression)

In Blinking Lights I told you about how I feel the modern computer for its exterior, except for its screen, is boring. When I look at my Antec case, I see a large, silent black box, which, by its very definition, is uninteresting at best. Something like a rock that slowly dissipates heat.

However Bill Buzbee built a computer that has an interesting exterior, and a much more interesting interior: the Magic-1. The Magic-1 is a computer running at 4.something MHz, and is in the same computational power range as the original 8086 4.77 Mhz IBM PC, except with a more advanced instruction set.

The Magic-1 Computer

Compact Tree Storage

Implementing data structures in a way that uses efficiently memory should always be on your mind. I do not mean going overboard and micro-optimizing memory allocation right down to the bit. I mean organize data structures in memory so that you can avoid pointers, so that you can use contiguous memory segments, etc. Normally, minimizing storage by avoiding extra pointers when possible will benefit your program in at least two ways.

First, the reduced memory requirement will make your data structure fit in cache more easily. Remember that if pointers are 4 bytes long in 32 bits programming, they are 8 bytes long in 64 bits environments. This yields better run time performance because you maximize your chances of having the data you need in cache.

Second, contiguous memory layouts also allow for efficient scans of data structures. For example, if you have a classical binary tree, implemented using nodes having each two pointers, you will have to use a tree traversal algorithm, possibly recursive, to enumerate the tree’s content. If you don’t really care about the order in which the nodes are visited, what’s quite cumbersome.

It turns out that for special classes of trees, complete trees, there is a contiguous, and quite simple, layout.

How many eyeballs to make a bug shallow?

In the The Cathedral and the Bazaar, Eric Raymond said that “Given enough eyeballs, all bugs are shallow.” Of course, what he meant is when you have a large enough tester base and lots of developers, almost all bugs are found, characterized (i.e., how to make them reproducible and what are the effects) and fixed by someone in the developer group. This appears to me as somewhat optimistic and begs the question… how many eyeballs does it take to make a bug shallow?

Soft-Ignore: Filter buggers in XChat

If you, like me, hang out once in a while on IRC to chat with fellow programmers (or with fellow practitioner of your favorite hobby), you may find that some individuals are just not worth your full attention. One easy, and rather definitive way to deal with the problem is to use the /ignore command that allows your IRC client to filter incoming messages from those people, and you just never see them again… quite literally.

However, just /ignoring someone is rude, and may prevent you from keeping a eye on them. You know, the “keep your friends close, your enemies closer” kind of thing.

A long time ago, with a friend, I wrote a mIRC script that shaded the “ignored” people’s text so that it was hard to read (like dark gray on blue), but the text was still available. To view the text, you could either squint or select the text. This week, I present a python version of that script, for XChat, based on the work of Albert W. Hopkins, a.k.a. Marduk, released under the GPL.