Ondemand scheduling does not work on the Pentium 4


Pentium D logo as of 2006
Image via Wikipedia

Finally got to the bottom of my issue with power saving and scheduling on my Pentium D machine (essentially a dual core Pentium 4).

It seems apparently lowering heat output (the Pentium D is a notoriously hot running processor), the “ondemand” frequency scheduler is not likely to save power in the real world and has been deliberately broken by the kernel maintainers.

As an email on LKML from October 2009 put it:

p4-clockmod is NOT true CPU frequency scaling, it just forces the CPU to  idle on a periodic duty cycle and has no effect on CPU frequency. The  clock modulation feature is basically just engaging the same mechanism  the CPU uses to reduce heat output when it gets too hot, and which is  not meant as a power saving mechanism. When engaged, it does reduce heat output and power usage, but not as much as it reduces system  performance, and means the system will simply take longer to return to  idle. In short, using p4-clockmod can only increase power usage in any real workload.

Advertisements

The game of life


Conway's Game of Life
Image via Wikipedia

The one piece of programming I have ever done that I am most proud of is a lump of Z80 machine code I wrote in 1981 to run “Conway’s Game of Life” for the ZX80 in the school Easter holidays.

Users could set the start up pattern and then let it run – though it could not be stopped once started, though as I used an interrupt service routine to display the screen it didn’t suffer from the grey screen problem (“fast mode” for you johnnie-come-latelys with your ZX81s).

I loved watching the patterns move and whirl across the screen and even though the only way I could get this to restart was to switch the computer off and on and reload the program from tape, I did it over and over again.

I just wish I had the code still… but at least I can still play the game with this great little java applet.

Seven years of spamming


How a botnet works: 1. A botnet operator sends...
Image via Wikipedia

A couple of weeks ago Microsoft did the world a favour, taking down the Rustock botnet and reportedly reducing the volume of spam email worldwide by a third.

Thew new chief botnet out there is “bagle” – and this is not such a great story. Because the bagle botnet – generally thought to have, at least originally, to be the work of one person – has been running for over seven years.

It is incredible to think that one criminal could engage in this activity – almost by definition in plain sight – and get away with it for so long.

Groovydoc issue


LED elevator floor indicator
Image via Wikipedia

I have been working on a coding exercise using the Groovy programming language and struggled for a bit with an issue with Groovydoc, the documentation protocol the language uses (which is meant to be very similar to Javadoc).

Groovydoc documentation is very thin on the ground and it seems to me that the tool is not exactly complete either, so actually working out why things are failing can be a bit of trial and error.

Anyway, I had my code all in the package “elevators” but when I ran this:

groovydoc -d groovydoc -private *.groovy

Inside the source directory it produced garbage files (did not recognise the packages properly, trying to put everything in the DefaultPackage but also generating broken files for elevators package also).

Going one directory level higher and trying this:

groovydoc -d groovydoc -private -sourcepath . elevators

Produced the same result. But this (two directory levels out) seems to work:

groovydoc -d src/groovydoc -private -sourcepath src elevators

The diagonal proof


This is a pre-1909 image of Georg Cantor (he w...
Image via Wikipedia

I am just reading Computability and Logic and it (or at least the old, 1980, edition I am reading) has a rather laboured explanation of Cantor’s 1891 proof of the non-enumerability of real numbers (the diagonal proof) so to reassure myself and because it is interesting I thought I’d set out a version here (closely modelled on that found in The Annotated Turing).

If you are already lost then – here’s what it’s about: it is a proof that the infinite number of real numbers (that is to say numbers with something after the decimal point eg 3.1) is a bigger infinity that the infinite number of integers – or if you want think in terms of fractions – the rational numbers. One – the infinite number of integers or rationals – is countable, the other is not.

This is a pretty mind-blowing proof and it is also fair to say that a minority of mathematicians have issues with Georg Cantor‘s theory of the continuum, but that is for another blog post, perhaps.

So here’s the example:

Let’s start setting out the real numbers that are less that one:

0.00000000000.....
0.10000000000......
0.20000000000......
0.30000000000......
0.40000000000......
0.50000000000......
0.60000000000......
0.70000000000......
0.80000000000.....
0.90000000000.....
0.01000000000.....
0.02000000000....
.....
0.11000000000.....

And so on. Now this looks like it might be enumerable (countable) by assigning an integer to element in the list- the first in the list is number 1, the second number 2 and so on. Hopefully you can see that this should, in theory, list all the numbers (except it doesn’t, as we will prove)

Bur let’s us take the number formed by the diagonal. In our case this is:

0.00000000000.....
0.10000000000......
0.20000000000......
0.30000000000......
0.40000000000......
0.50000000000......
0.60000000000......
0.70000000000......
0.80000000000.....
0.90000000000.....
0.01000000000.....
0.02000000000....

ie 0.0000000000.......

And let’s add 1 to every digit, so we get 0.111111111111....: is this number in the list? We will now show you that it cannot be by checking off the numbers in the list one by one.

First of all, we can eliminate the first number in the list as a match, because its first digit is 0 and our number has 1 as the first digit. Then we can eliminate the second number in the list in the same way (ie it’s second digit does not match). In fact it is clearly the case that we can eliminate number N from the list because it will not match at digit N.

OK, you say, let’s fix that by adding this ‘new’ number to the list:

0.11111111111......
0.00000000000......
0.10000000000......
0.20000000000......
0.30000000000......
0.40000000000......
0.50000000000......
0.60000000000......
0.70000000000......
0.80000000000......
0.90000000000......
0.01000000000......
0.02000000000......

But let’s diagonalise that one:

0.111111111111.....
0.00000000000......
0.10000000000......
0.20000000000......
0.30000000000......
0.40000000000......
0.50000000000......
0.60000000000......
0.70000000000......
0.80000000000......
0.90000000000......
0.01000000000......
0.02000000000......

And we get 0.1000000000...... Once again adding 1 to all the digits we get a new number 0.2111111111111.... – which we can show in the same way does not exist in the original list (set)

Linux core dump in “The IT Crowd”


“The IT Crowd” isn’t really about IT at all, but it is very funny… and it also displays a core dump – coloured blue presumably to make it look like a BSOD – in its title credits. It looks like it is some problem caused by the Anaconda backup process.

Have a go on the freeze frame to see it.

The Joshua Tree, Walter Benjamin and the internet revolution


Walter Benjamin
Image via Wikipedia

In front of me I have a CD of The Joshua Tree, U2’s fifth studio album, and one of the greatest Irish cultural achievements of the 20th century – something that helped propel Ireland from the fringes of Europe to the global mainstream.

I am not sure when I bought the CD (to replace the vinyl from 1987), perhaps ten years ago, perhaps further back. One thing I do know, and which I noticed tonight, is what it cost – £13.99 – because the HMV price sticker is still there.

According the all items RPI there has been a general 33% inflation between March 2001 and February 2011, so the “real terms” price was a whopping £18.60: can you imagine paying that for a CD (assuming you buy them at all) these days?

The price has effectively more than halved and I see no sign that this is likely to stop: Walter Benjamin‘s essay on The Work of Art in the Age of Mechanical Reproduction spoke a more profound truth than even he could have imagined, for both good and ill. The internet revolution is real and it is not going to stop.

The era of super abundance for information is close.

 

Flattered by spam


Linux-kernel-structure
Image via Wikipedia

I hate spam. Like everyone else on the internet.

But maybe not all spam. I now get occasional emails from two technical recruiters in the United States asking me if I want a job as a Linux kernel engineer. As I have never signed up with Texan technical recruiters I assume they got my email address from either greping the kernel or LKML.

Either way I admit to being slightly flattered by it, even though they have almost certainly sent out thousands of these things.

The rubbish written about the “supermoon”


Full Moon view from earth In Belgium (Hamois).
Image via Wikipedia

I am all in favour of using marketing techniques to improve science education. But the garbage that has been talked about the so-called “supermoon” really is shaming: scientists who popularised this idea plainly did not bother too much with the mundane, such as the fact that we are that close to the Moon every 28 days.

The recursive cash changing algorithm


This is another one from Structure and Interpretation of Computer Programs which is a great book, but not a particularly easy read (not least because Scheme, the language in which the programs in the book is written is just different from C/Java etc). This example annoyed me for some time so I am writing down an explanation in case someone else wants to look it up…

Anyway this one is about the number of ways of to change cash. The algorithm is based on the fact that you can break down the number of ways to sort change of the sum n with t types of coin as follows:

  • All ways to sort n with t-1 coins; plus
  • All ways to sort n-d with t coins, where d is the denomination of the coin excluded in the above case.

(Think about it for five pence with two pence and one penny coins. One way to sort with pennies and two ways to change three pence with a two pences and pennies.)

To solve this recursively we have to define the degenerative cases – ie the points at which the recursion stops. These are:

  • If the sum to be cashed to change is 0 then there is 1 way to do it;
  • If the sum to be cashed to change is less than 0 then there are 0 ways to change it;
  • If there are 0 coins then there are 0 ways to offer the change.

So how does it work … hopefully the graphic below shows how (changing 10 pence with fives, twos and ones):

Coin changing algorithm tree

The idea is that f(n, {c}) returns the number of ways n can be changed with the set of coins {c}. In this tree the number of leaf nodes (10) is the answer. I have cheated here – the turquoise leaves are not degenerate cases – each has to be worked down to a case where the one would apply if the algorithm is to be universal, though we can simply add an extra rule when the set of coins being used consists of only 1p coins – that is 1 way of sorting. (But if the universal rule was applied then the number of computing steps increases greatly – as each of those 1p cases has to be worked down to a degenerate case).

Update (27 March 2011): There were actually a couple of mistakes in how the terminating cases were shown in the graphic, fixed now I hope.