Avian’s Blog

Today I spent a couple of hours hunting down a bug in some of Zemanta's C++ code. I won't bore you with details, but I did learn something interesting about the way GCC works.

In essence the bug was due to a broken implementation of string comparison. Like this for example:

int cmp_strings(const char *x, const char *y)
{
	return x == y;
}

Now, if you know some basics you should see right away that this won't compare strings at all. What it will do is that it will compare the memory locations at which the strings are stored. But that's not the interesting part.

The interesting part is that a function like this had a couple of unit tests and they all passed with flying colors, while in real usage it broke horribly (as it should).

How was this possible? Consider the following program using the function above:

int main()
{
	printf("%d\n", cmp_strings("en", "en"));
	printf("%d\n", cmp_strings("sl", "en"));
	return 0;
}

Can you say what the output looks like without compiling it first?

Interestingly, at the first glance the output of this program supports the (wrong) theory that cmp_strings does in fact compare string content (and that's why the unit tests I mentioned passed).

What is really happening is that GCC is optimizing memory usage of the program and is merging equal constant strings. There is no use in storing the same constant "en" string three times in three different locations when one copy will do just fine (they are constant after all). So cmp_strings will work correctly for constant strings, but not for variable ones.

Oh, and -fno-merge-constants doesn't help with this, since it only affects merging of identical constants over multiple compilation units (on GCC 4.2.3 at least). In fact I see no way of disabling this optimization so that I could quickly check if any other code is also broken in this way.

Today I had the opportunity to play with an USB HSDPA modem. This is the latest generation of the packet data connection through a cellular network which can in theory get you a 7.2 MB/s downlink. You get it in a soup can in combination with some subscription plans at Mobitel.

The modem itself obviously has several names, depending on who you trust:

• The advertisement says it's "GlobeSurfer iCON 7.2",
• the front side of the modem says "Option",
• the back side says "Qualcomm 3G CDMA model GI0205"
• and finally lsusb says it's "Globetrotter HSDPA Modem".

It certainly gives you the warm feeling that various marketing departments are working together to reduce the confusion here. Just for the record, USB ID is 0af0:6911.

Anyway, the thing works without problems on Linux. It is used as a standard serial modem with a PPP connection, except that you need to give it some special AT commands first.

When I plugged the modem in I got three USB serial devices: /dev/ttyS0, ttyS1 and ttyS2. First two didn't respond to any AT commands, while ttyS2 responded with the usual OKs. I didn't need to do any extra steps to switch the hardware from the simulated CD mode to modem mode as some people reported.

The actual configs I used are here. I don't know why, but sometimes two attempts are necessary to get a connection.

# pppd configuration (e.g. /etc/ppp/peers/qualcomm)

# Change if using with some other mobile provider
user "mobitel"

connect "/usr/sbin/chat -v -f /etc/chatscripts/qualcomm
/dev/ttyUSB2
115200

noipdefault
usepeerdns
defaultroute

noauth
crtscts
passive
modem
idle 7200

# No support for compression
noccp
novj

# chat script (e.g. /etc/chatscripts/qualcomm)
ABORT		BUSY
ABORT		VOICE
ABORT		"NO CARRIER"
ABORT		"NO DIALTONE"
ABORT		"NO DIAL TONE"
TIMEOUT		5
""		ATZ
OK 		ATE1
OK		AT+CPIN?
# insert your PIN here
READY\r\n\r\nOK-AT+CPIN=your_pin_here-OK	AT
OK		AT+CGDCONT=1,"IP","internet","0.0.0.0",0,0
OK		AT+CGDATA="PPP",1
CONNECT   	""

You also need to enter a proper username and password into chap-secrets file (PAP authentication isn't supported). For Mobitel this pair works:

# Secrets for authentication using CHAP
# client	server	secret			IP addresses

mobitel		*	internet		*

Here's another interesting catch in BeautifulSoup: you can iterate through BeautifulSoup Tag's child nodes simply by using a Tag object as an iterable object. For example in a for loop like this:

for t in tag:
	# do something with t

However, what if tag is a NavigableString? If you're doing a recursive search through the tree, this will happen sooner or later. Since NavigableString doesn't have any child nodes, you would expect that this for loop would throw an exception, right? Well, not exactly.

Since NavigableString derives from Unicode class, it can also be used as an iterable object, however this time you'll iterate through single characters in its contents (which are Unicode objects themselves).

That was a source of some weird parsing errors in some of the code I was working on. So before iterating through a tag, check if it isn't a subclass of NavigableString:

if not isinstance(tag, NavigableString):
	for t in tag:
		# do something with t

BeautifulSoup is a wonderful tool for parsing XML sludge gathered on the bottom of the internet. However you pay for versatility and resistance to broken markup with a big performance hit compared to proper XML parsers. The documentation acknowledges that and suggests that you only parse a part of the document - it doesn't offer any tips on what to do if you really must walk through the whole tree.

Today I found the following trick with which I managed to speed some code that walks entire BeautifulSoup document trees by almost four times:

NavigableString and Tag objects offer a very useful string member which can be used to access the Unicode string contained in them.

This is very convenient, since you only access the string member no matter what kind of node you are processing. However, there is a catch: If the Tag object doesn't contain a single NavigableString, the string member evaluates to None (as per documentation). What happens behind the scenes is that the Tag object doesn't have the string member in __dict__ and the Tag's __getattr__() method gets called. This does an expensive search through all of Tag's attributes (because BeautifulSoup Tag's XML attributes can also be accessed as Python members) before returning None. So hitting the string member when there isn't any will do a lot of processing for nothing.

The second catch is that while the string member is implemented in __dict__ in Tag objects, it's implemented in a (fairly efficient) __getattr__() method in NavigableString.

So the following code:

s = tag.string

can be replaced with this equivalent, which was approximately 4 times faster in my case:

if isinstance(tag, NavigableString):
	s = tag.string
else:
	s = tag.__dict__.get('string', None)

Of course, using hacks like this means that your application now depends on library internals, so big fat warnings are probably in order around such code. The code above was tested with BeautifulSoup 3.0.5 - it's quite possible that newer versions will have things done differently.

Two weeks ago I got the idea that maybe it's time to move away from Nanoblogger and start using some "real" blog software.

Well, after experimenting with Wordpress and MovableType for last two weeks I must say that Nanoblogger still beats them all. Have you ever tried writing a post on EeePC with those Javascript WYSIWYG editors? I'll describe my experiences in some other post, for now I just want to say that all blogging software sucks, Nanoblogger just sucks the least.

So yes, I'm staying with Nanoblogger. I've modified it a bit, added support for comments and I'm hoping to rewrite some parts of it in Perl to make it faster.

Oh, and there's also jsMath:

Anyway, if something's not working for you now, please leave a comment or drop me a mail.

Today I started getting errors like this on Eee:

ata2.00: exception Emask 0x0 SAct 0x0 SErr 0x0 action 0x0
ata2.00: cmd ef/05:fe:00:00:00/00:00:00:00:00/40 tag 0 cdb 0x0 data 0 
         res 51/04:fe:00:00:00/00:00:00:00:00/e0 Emask 0x1 (device error)
	 ata2.00: configured for UDMA/33
	 ata2: EH complete
	 sd 1:0:0:0: [sda] 7815024 512-byte hardware sectors (4001 MB)
	 sd 1:0:0:0: [sda] Write Protect is off
	 sd 1:0:0:0: [sda] Mode Sense: 00 3a 00 00
	 sd 1:0:0:0: [sda] Write cache: disabled, read cache: enabled, doesn't support DPO or FUA

That's with a stock Debian 2.6.23 kernel which I've been running since I first installed Debian.

I just hope this doesn't mean the solid state drive is already reaching its maximum number of write cycles. So far these errors don't seem to have any effect short of annoying me when I'm using the console.

Update: Mystery solved. Some browsing through kernel source revealed that "ef" is ATA command ATA_CMD_SET_FEATURES. This sounded like something hdparm would do and indeed hdparm was being run from some misconfigured ACPI scripts I forgot to clean up yesterday.

I was wondering yesterday why when I press the LCD brightness hotkeys on my EeePC (Fn-F3 and Fn-F4) I don't see the nice GNOME-styled OSD (like the one that pops up when I change the speaker volume).

Well, it turned out that quite a few things needed fixing. Among other things HAL configuration and GNOME Power manager. However even before I could start fixing things there was a non-trivial matter of finding out all the steps that happen after you press the hotkey and before the volume or LCD brightness get changed. As far as I could see this isn't documented anywhere so in case someone else will do something similar, here's what I found out.

Note that this is most likely Debian and EeePC specific and will probably change soon.

Step 1: Hardware

When you press a Fn-F combination, laptop's hardware generates an ACPI event. This event is gets picked up by acpid using the Linux kernel ACPI driver.

In EeePC's case Fn-F4 and Fn-F3 keypresses also directly modify the brightness setting without any software intervention. Not so with audio volume hotkeys.

Step 2: ACPI

acpid consults its configuration in /etc/acpi/events and runs a shell script that corresponds to the ACPI event.

This shell scripts runs acpi_fakekey that inserts a keycode into kernel's keyboard event FIFO. This in effect simulates a keypress on the keyboard.

This is done like so because different laptops have different means of reporting hotkeys (different ACPI events, scancodes, etc.). After this step all these events are translated into a standardized keycode in the event FIFO (like 224 for KEY_BRIGHTNESSDOWN - see /usr/share/acpi-support/key-constants)

Step 3: GNOME

Some GNOME component gets the keypress via an X event and reacts to it. In case of LCD brightness hotkeys the component is GNOME Power Manager and in case of audio volume hotkeys it's the GNOME Settings Daemon.

It might be that HAL also plays a role here. Maybe these applications get the events through dbus from HAL. lshal -m suggests that HAL also reacts to these keypresses, but I haven't dig deep enough into the code to see if GNOME listens to it.

There's also some weird business of how keycodes get translated into X events via xkb settings. A document on Ubuntu Wiki tries to clear this up, but I failed to see the exact connection between codes in X configuration and codes in acpi_fakekey.

Step 4: HAL

GNOME component displays a box with the current status and sends a message to HAL to change the LCD brightness.

HAL has some configuration in /usr/share/hal/fdi/policy that tells it how to do that. For example in case of LCD brightness setting it calls /usr/lib/hal/scripts/hal-system-lcd-set-brightness and /usr/lib/hal/scripts/linux/hal-system-lcd-set-brightness-linux

In case of audio volume GNOME Settings Daemon looks like it changes the setting itself, without resorting to HAL.

Also, since EeePC's hardware changes the brightness itself, this last step is unnecessary - all GNOME needs to do is display the box (and that's one of the things that needed fixing).

Hruške has some well founded arguments against my last Python performance rant.

I stand corrected. I must have messed something up with my measurements. I have now repeated them on two different machines and I got the same results as Hruške. So the in operator in Python is indeed fast when the right hand operand is a dictionary.

I can only say in my defense that I thought that this part of Python documentation confirms that the in operator works in a general way on all iterable objects:

__iter__()
Return the iterator object itself. This is required to allow both containers and iterators to be used with the for and in statements. This method corresponds to the tp_iter slot of the type structure for Python objects in the Python/C API.

As for his other comment about Wikiprep code size:

avian@toybox:~/dev/html2latex-1.1$ sloccount .

... snip ...

Totals grouped by language (dominant language first):
perl:           797 (100.00%)

Total Physical Source Lines of Code (SLOC)                = 797

avian@toybox:~/dev/wikiprep$ sloccount .

... snip ...

Totals grouped by language (dominant language first):
perl:          2060 (85.12%)
cpp:            220 (9.09%)
python:          50 (2.07%)
ansic:           49 (2.02%)
sh:              41 (1.69%)

Total Physical Source Lines of Code (SLOC)                = 2,420

So yeah, Wikiprep Perl code which I maintain for Zemanta is still bigger.

That of course doesn't mean that there aren't any bigger Perl monstrosities in the wild. After a quick survey of free Perl software I have on the disk I found gtablix which has 6283 Perl SLOC and GCfilms with an unbelievable 25758 Perl SLOC (neither of which seems to be maintained BTW).

Quote Python documentation:

latex2html: Probably the longest Perl script anyone ever attempted to maintain.

Hm...

avian@toybox:~/dev/html2latex-1.1$ wc -l html2latex HTML/Latex.pm 
  276 html2latex
 1458 HTML/Latex.pm
 1734 total

avian@toybox:~/dev/wikiprep$ wc -l *.pl *.pm
 2466 wikiprep.pl
  129 images.pm
  359 languages.pm
   80 nowiki.pm
   76 revision.pm
  183 templates.pm
 3293 total

(cue manical laughter)

Update: Please ignore this rant. I don't know what I've been doing wrong here, but my later measurements confirm Hruške's findings.

Python provides a convenient in operator that returns true if the left hand value is an element of the right hand list or dictionary. That's nice and all, but the performance makes it pretty useless in all but trivial cases. Take a look at this graph:

On the vertical axis is time needed for a loop to finish while test_size value is on the horizontal axis.

I ran these three loops that are exactly equivalent as far as the effect of the if statement is concerned:

"in list": the obvious way

list = range(test_size)

for m in xrange(2 * test_size):
	if m in list:
		a += 1
	else:
		b += 1

"in dict": converting to hash doesn't help

list = range(test_size)
dict = dict.fromkeys(list, 1)

for m in xrange(2 * test_size):
	if m in dict:
		a += 1
	else:
		b += 1

"dict.get": the right way

list = range(test_size)
dict = dict.fromkeys(list, 1)

for m in xrange(2 * test_size):
	r = dict.get(m, None)
	if r:
		a += 1
	else:
		b += 1

This simple Python one liner will not do what you expect:

>>> import re
>>> re.sub("the", "", "The Last Lecture", re.I)

Before someone again accuses me of being illiterate: Yes, this behavior is documented. It's still one of those things that go undetected for a long time and bite you in the most inappropriate time. It's right up there with C's "if(x=0) ..." on the annoyance scale.

Matching balanced constructs (like some text that must contain matching pairs of parentheses) is a classical example where traditional regular expressions fail. It isn't surprising then that the Perl FAQ says that you should use text parsing functions from Text::Balanced module when you need to do that.

Perl however also provides extended regular expressions that among a lot of other things also support this kind of matches. Theory says that such extended expressions can't be compiled to finite automata and so typically have worse complexity than the traditional O(n) - something that is also mentioned in another part of Perl documentation.

So when I was confronted today with a problem that involved matching balanced "{{{" and "}}}" pairs (guess what kind of markup uses them) I naturally followed the suggestion in the FAQ.

Well, it turned out that that suggestion isn't one of the best ones. Text::Balanced is slow. Actually it's so slow that the identical code that uses the extended regular expression from Regexp::Common::balanced is around 50 times faster.

So much for the difference between theory and practice.

Linux mmap() call is full of surprises. Take for example the MAP_PRIVATE option. According to the man page, mmap() with this option makes copy-on-write pages, meaning that any changes the process makes to the mmaped region will not be propagated to the underlying file.

This is of course works as advertised, but there is a catch. What if some other process modifies the file? Take for example this simple program:

#include <stdio.h>
#include <fcntl.h>
#include <sys/mman.h>

int main() 
{
	int fd = open("file", O_RDRW);

	char *p = mmap(NULL, 1, 
			PROT_READ | PROT_WRITE, 
			MAP_PRIVATE, fd, 0);

	while(1) {
		printf("%c\n", *p);
		sleep(2);
	}

	close(fd);
}

If file contains a character "A", this program will print a string of As to the console. Now while the program is running you change the contents of the file. Does the output of the program change?

It turns out it does! However only if the program didn't change something in the mmaped region. If you modify the program above so that it writes something, the stream of characters on the console will not change when you modify the contents of the file.

Why is this significant (and why I spent a couple of hours exploring it)? It turns out that the dlopen() call in Linux loads shared objects by simply mmaping them (look at the strace output if you don't believe me). So if you change a .so file on the disk while some application is using it, you'll get a nice segmentation fault.

Now, /proc/*/maps file reveals that the executable itself is also mmaped. However a program doesn't crash when you modify the executable file, so either something gets changed in the program's image after it gets mmaped or I still don't understand everything that's going on here.

A couple of weeks ago a post on geda-dev mentioned a new, free (as in freedom) application for designing printed circuit boards - LiquidPCB. At its web site Hugo Elias, LiquidPCB's author, points out some shortcomings of gEDA's PCB and other traditional CAD tools and how he attempts to fix them in his software. He says it's all about a new, modern user interface.

Discussion that followed on gEDA's mailing list didn't actually touch any of the problems pointed out by Hugo. With some help I managed to get LiquidPCB running this weekend on an old laptop with Windows, so here are some of my thoughts about it.

I mostly agree with Hugo regarding user interface problems. gEDA's PCB has an archaic GUI - most core developers still use its Lesstif incarnation (Lesstif is an reimplementation of Motif, a GUI toolkit from 1980). It surely requires quite a lot clicking around that could be avoided in this or other way, not to mention that it looks a bit out of place on a modern desktop. However I think most of these problems could be solved in a way that doesn't depart so radically from what everyone is used to today.

I think problems that LiquidPCB tries to solve can be split into two groups: First there are those that are shared by basically every complex desktop application today. I believe it's wrong to try to solve this kind of problems separately in each application. For example LiquidPCB reimplements a file selector dialog. From the usability standpoint this is a component that should be shared between all applications. So I believe a better way of solving this problem would be for example to submit patches for GTK file chooser dialog.

Another example are problems with the menu and toolbars. I believe this can be solved with better placing of entries in menus (gEDA's PCB for example has a problem with "Select" and "Buffer" menus where I often open the wrong one). I can't say if the hexagon menu system used by LiquidPCB is better than a well done traditional interface. I found it awkward, but that's because I'm used to traditional interfaces. What bothers me the most is the requirement to hold down the right mouse button while traveling through menus. What I'm almost sure of is that it can't replace keyboard shortcuts. The keyboard with its 100 and so buttons still provides a faster way of switching program states (like switching between select mode, via mode, etc.).

The other group of problems is specific to PCB design. In this field the approach of LiquidPCB looks superior to anything PCB has to offer. What you are doing in PCB design is solving a topological problem. You have a graph and you need to place the vertexes and edges on the plane so that their placement follows certain rules. Now the approach LiquidPCB takes is that it makes you solve that exact problem without requiring you to fiddle with side issues like the exact location of elements. You only say "pin A is placed on this side of line B" and LiquidPCB takes care of the rest. It feels like an autorouter that uses a user's brain to do what it does best (solving the topology) and the computer to do what it does best (finding placement for vias and lines). The example of LiquidPCB's web site showing how to insert a via in the middle of four tracks shows just how much work this approach saves you. In PCB this operation would really involve hundreds of steps where you would first move each of the existing lines out of the way (which could also require moving several components) and only then insert that new via.

I see some purely practical problems with LiquidPCB's approach. For example the constant dynamic optimization means that just opening a file also makes modifications in it. And also, at least from half an hour of playing with it today, it seems it is quite easy to make a mess of things if you're not careful. But I'm sure these problems will be easy to fix.

So in conclusion I think LiquidPCB addresses some quite real problems and shows some promising solutions to them. The program itself is in an early stage of development and isn't useful yet for anything more than playing with it. It will be very interesting to follow its development.

Some time ago gEDA moved their source repositories from CVS to Git. I've heard a lot of nice things about Git but so far I stayed away from it since its philosophy (and terminology - for example meaning of words like commits and revisions) is different enough from CVS and SVN that I never quite understood what certain commands did. Yesterday I finally took some time and read through most of its manual.

I must say that after reading the documentation things do begin to make sense. So I checked out the latest gEDA sources and experimented with Git a bit. Since I wanted to try out how convenient it is to make modifications to your local branch and then submit patches back upstream I started modifying things and in the end I (mostly) fixed one annoyance with gschem.

The problem is that when you have the view zoomed out the schematic quickly gets unreadable. I tried to solve this problem a while ago by porting gschem to Cairo, which provided nice anti-aliased lines and fonts. However that had problems of its own and Cairo support still hasn't been incorporated into gschem source.

Now I took a much simpler approach. It turned out that mayor factor contributing to unreadability is the grid. When zoomed out the features of the schematic get lost in closely spaced grid points. However making grid darker produced the problem that when zoomed in the points were hard to see. So I did a simple modification (made less simple by the awkward handling of colors in the code) that made grid points stand out less from the background when the view is zoomed out.

As you can see from the pictures below, the difference on a zoomed-out view is quite noticeable. It definitely makes gschem usable for editing on one zoom level more than before.

Left patched gschem, right original gschem.

Left patched gschem, right original gschem with grid color changed so that it matches grid color of patched gschem when zoomed out.

You can download the patch from SourceForge.