C Is Not MATLAB

March 30th, 2009 • , • No Comments

Refactoring some code at work today, I came across a classic example of somebody attempting to use one language like another. The project in question is a port from MATLAB to C, and the purpose of the function is to see if a square matrix is symmetrical within a certain tolerance.

The implementation I replaced worked somewhat like this:

int check_symmetry(double *mtx, int n, double tolerance)
{
    /* Allocate memory to work in */
    double *mtx_trans = (double *) malloc(n * n * sizeof(double));
    double *mtx_diff = (double *) malloc(n * n * sizeof(double));
 
    /* Matrix transpose */
    matxtrans(mtx, n, n, mtx_trans);
    /* Matrix subtract */
    matxsub(mtx, n, n, mtx_trans, n, n, mtx_sub);
 
    /* Assume matrix is symmetric to start with */
    int symmetric = TRUE;
 
    /* Iterate through rows */
    for (int i = 0; i < n; ++i)
    {
        /* Iterate through columns */
        for (int j = 0; j < n; ++j)
        {
            /* Was the difference greater than the tolerance? */
            double val = mtx_sub[i * n + j];
            if (fabs(val) > tolerance)
            {
                /* Exception found: matrix not symmetric
                 * (but notice that we keep looping...) */
                symmetric = FALSE;
            }
        }
    }
 
    /* Clean up memory allocations */
    free(mtx_trans);
    free(mtx_diff);
 
    /* ... and return the result */
    return symmetric;
}

Now, what this is really doing is the equivalent to the following line of MATLAB:

symmetric = max(abs(mtx - mtx')) > tol;

This in itself highlights the massive differences between MATLAB, where matrix operations are fundamental, and C, where they are not. While the above C code gets the correct answer, it’s far from efficient. What should be obvious is that the programmer translated the code, not the meaning.

To analyse this simple case: a symmetric matrix is reflected in the diagonal—the lower triangle is the same as the upper. What we really are trying to find out is if any elements violate this constraint. More verbosely: “does any element in the upper triangle differ from it’s corresponding element in the lower triangle (by more than a certain value)?” Once we’ve figured this out, the operation in C is much, much shorter:

int check_symmetry(double *mtx, int n, double tolerance)
{
    /* Iterate through upper triangle only */
    for (int i = 0; i < n; ++i)
        for (int j = i + 1; j < n; ++j)
            /* Compare to lower triangle */
            if (fabs(mtx[i * n + j] - m[j * n + i]) > tolerance)
                /* Exception found: matrix not symmetric */
                return FALSE;
    /* No exceptions found: matrix is symmetric */
    return TRUE;
}

This achieves the minimum number of iterations and element accesses by ignoring the diagonal, only iterating through the upper triangle and reversing the indices to access the lower triangle. The only potential downside is that it’s not as obvious what’s going on, but that’s what comments are for!

The lesson is that you should always make sure you’re using the correct method for the tool, and not trying to hammer a screw in with a spanner.

Persistent Remote irssi Session

March 28th, 2009 • , • No Comments

I’ve recently moved back to using irssi as my IRC client, because when combined with GNU screen it can be kept independent of a graphical session, or even better, of a particular client machine (if you have a server somewhere). Since I have a home fileserver at the moment, I want my IRC client to always be running there. However, my usual workflow to do this is to open a terminal, SSH to the server, resume screen, move the window and resize it. This is far from optimal for something I usually want open…

Instead, I pieced together a command that I can use as a panel shortcut to do it all for me:

$ gnome-terminal --geometry 100x30-0-0 -x \
        ssh <hostname> -t "screen -D -RR -S irssi irssi"
gnome-terminal –geometry 100×30-0-0 -x
Open “gnome-terminal” at the bottom right of the screen with a size of 100 characters by 30. Run the rest of the command inside the terminal.
ssh <hostname> -t
Connect to <hostname> and execute the supplied command in an interactive pseudo-TTY.
screen -D -RR -S irssi irssi
Do whatever necessary to gain control of the “irssi” screen session if it exists, otherwise create it and run irssi inside it.

MPD + PulseAudio + Ubuntu Intrepid (8.10)

March 21st, 2009 • , , , • 12 Comments

Update (2009-04-12): It appears that in Jaunty everything now obeys the system-wide setting properly, so you only need to edit /etc/default/pulseaudio and add the user to pulse-access.

I’m a big fan of Music Player Daemon (MPD), and up until the last few months I used it almost exclusively.  It’s lightweight, it’s good at what it does, and there are a lot of different frontends available.  One of the things I like most is that it’s not tied to a graphical session in any way—you don’t need a GUI open for it to be playing music.  Normal usage of MPD involves it being started and stopped as a system service.

Unfortunately, this doesn’t play too nice with the concept of how PulseAudio should be used.  PulseAudio is very user- and session-centric, and the recommended setup means than when nobody is logged in, no sound is going to be playing.  While MPD is capable of playing to a PulseAudio server just fine, having the sound server tied to the graphical session means it doesn’t have a sound device to attach to at boot, and the sound device suddenly disappears if the user logs off.

Ubuntu has used PulseAudio for as many applications as possible by default since Hardy (8.04), and while it can be removed, doing so can make life difficult.  This led me to pursue the option of a system-wide instance which everything uses, and which is always running.  But no matter how hard I tried, I got stuck with the same bug: starting GNOME would always result in a per-session instance being spawned in addition to the system-wide one, the two would fight over the sound card, and I would have to manually kill the new one every time I logged in.  Eventually I’d had enough of this and started using something else.

Today, I decided to take another stab at getting this set up properly and finding out where that second PulseAudio instance was coming from.  Thanks to the help of a couple of people in #pulseaudio on FreeNode IRC, I was able to figure out how to do this, so here is the method I used for the benefit of anybody else in the same position.

Stop PulseAudio spawning per-session

By default PulseAudio puts a script in /etc/X11/Xsession.d which causes a “pulseaudio” instance to be spawned with every X session.  The first step is to move this script somewhere else so it’s never run:

$ sudo mv /etc/X11/Xsession.d/70pulseaudio /root/

The second cause of “pulseaudio” being spawned is less obvious.  There is an Esound compatibility layer for PulseAudio so that applications depending on it still work, transparently.

$ ls -l /usr/bin/esd
lrwxrwxrwx 1 root root 9 2009-03-04 11:03 /usr/bin/esd -> esdcompat

However, as of Ubuntu Intrepid (8.10) there is pretty much nothing which depends solely on Esound, but it still gets spawned when GNOME starts.  This causes a PulseAudio session to be spawned for the current user if one can’t be found.  The simple but ugly fix is to move this link to somewhere else:

$ sudo mv /usr/bin/esd /usr/bin/esd.bak

Set up a system-wide PulseAudio instance

To get PulseAudio to actually start on boot, you need to set a variable to tell the init script you want this to happen. Make sure you have the following line in /etc/default/pulseaudio:

PULSEAUDIO_SYSTEM_START=1

Any users that will be using the system-wide PulseAudio instance need to be members of the correct groups. This will most likely be your own user, plus whatever user MPD is running as (”mpd” by default). For each of these users, do:

$ sudo usermod -a -G pulse-access <user>
$ sudo usermod -a -G pulse <user>
$ sudo usermod -a -G pulse-rt <user>

Getting it up and running

First thing’s first, you need to tell MPD to use PulseAudio. This can be achieved by adding the following to /etc/mpd.conf:

audio_output {
       type    "pulse"
       name    "My MPD PulseAudio Output"
}

If you’re feeling lazy, the easiest thing to do right now would be reboot. Otherwise, you’ll need to kill all “pulseaudio” instances, restart the system-wide instance, and restart MPD.

$ sudo /etc/init.d/mpd stop
 * Stopping Music Player Daemon mpd                   [ OK ]
$ sudo killall -KILL pulseaudio
$ sudo /etc/init.d/pulseaudio restart
 * Stopping PulseAudio Daemon                         [ OK ]
 * Starting PulseAudio Daemon                         [ OK ]
$ sudo /etc/init.d/mpd start
 * Starting Music Player Daemon mpd                   [ OK ]

Finally, log out and log back in again to allow your per-session pulseaudio instance to die and for your new group memberships to take effect.

Caveats

  • You get “real-time” processing without any extra effort; by default the system-wide instance will run with priority -11.
  • Some apps are not PulseAudio-aware, but they can usually use an ALSA output; this guide shows you how to redirect ALSA through PulseAudio if you have any problems with the default setup.
  • Updates may undo the moving-a-file type of changes.

“Universities push for higher fees”

March 17th, 2009 • • No Comments

My comment on a recent BBC News article “Universities push for higher fees”:

I’m a university student from a low-income background, and having started my course just after the last raise in fees took effect, I knew from the beginning that I’d be finishing with £32k of debt (including maintenance loan).  While expensive, it’s a risk I was willing to take, since it’s the best way to equip myself for the field I enjoy.  If this number were to be more in the region of £85k, I think a lot of people would shy away from taking on such a staggering debt.

The government needs to realise that if they allow such increases, and also increase student loans to follow suit, then they will be footing the bill for allowing the fees to be raised (and therefore passing it on to the taxpayers).  The vital safety net for most students is that student loans are written off 25 years after finishing/leaving the course, and since the university already has the money, the gap has to be filled from somewhere.  This alone explains the observations leading to “Two thirds believed that fees had not deterred applications from students from poorer families”.  If the government wants to subsidise the universities, then they should propose an increase in per-student subsidies as an alternative, presenting the situation as it really is.

Any attempt to raise or un-cap fees that isn’t backed completely by student loans will be disasterous.  This would change the university admissions process to be less “those who are most able” and more “those who are most able to pay”.  For a government that campaigned on equal availability of higher education, this would be a step backwards.  In a country with a shrinking manufacturing base, intelligent well-educated individuals are a vital resource for staying competitive in a global market.

As it stands, I’ve not heard of universities being severely underfunded, and where they claim to be it can usually be attributed to mismanagement of funds.  If they could survive when we were paying £1150, why can’t they survive when we’re paying £3150?  It seems to me this may be a case of “they did it once, maybe they’ll do it again” on the part of universities, hopeful that the government will grant them more revenue without having to show anything for it.

My painless Linux “upgrade” process

January 7th, 2009 • • No Comments

I like to keep up to date with the latest version of any Linux distro I use (naturally), but for some reason I don’t trust the upgrade process to work properly and/or not leave a load of cruft behind.  I’ve actually attempted an upgrade once just to try and get over my upgrade fear, but instead it went horribly wrong and convinced me to not try again for a long time.

There is a simple way to make reinstallations painless enough that you don’t need to offer yourself up to the upgrade gods, and it takes only a small amount of forward planning.  Always always always use a separate home partition! Keeping your home partition separate allows you to go as far as reformatting your main operating system partition without losing any of the data you really care about.

Note: just in case it’s not obvious, my username is ‘alan’ - replace it with your own username!  If you have multiple users, repeat operations on each user’s home directory.

Here is my typical upgrade/reinstall process.  If you’re planning on using this method, please read the whole thing before starting and make sure you understand what you’re doing and why.  A lot of this is done as root and mistakes can be painful.

1 - Prepare

Your /home partition isn’t going to be reformatted if everything is done correctly, so if you know what you’re doing you shouldn’t even need to do a full backup.  However, you’ve probably got some other things on the root partition that have been changed that you want to keep, at least for future reference.

# Backup /etc
sudo tar czvpf /home/etc.tar.gz /etc
# Backup root's home directory
sudo tar czvpf /home/root.tar.gz /root
# Backup anything else you might want to /home, for example MySQL databases
# (maybe backup /var the same way as above?)
# ...

Next you need to make a note of which partition is which so you don’t accidentally format the wrong one:

$ df
/dev/sda5             11718932   2419420   9299512  21% /
...
/dev/sda7             44133352    219500  41671984   1% /home

So in this case, /dev/sda5 is what you’ll be reformatting and installing your new operating system on, and /dev/sda7 is the one you don’t want to touch in any way whatsoever.

Next you’ll want to write the fstab line for your home partition somewhere so you can use it on your new installation.  The following command will get that from /etc/fstab for you:

$ grep "/home" /etc/fstab
/dev/sda7      /home      ext3     defaults,relatime      0     2

The final preparation step is to move your old home directory somewhere. To do this you’ll need to be logged in directly as root. If you’re running an Ubuntu-based distribution and haven’t set the root password before, do so:

$ sudo passwd

Log out of your graphical session, switch to a virtual terminal (e.g. press Ctrl+Alt+F2), and log in as root. Move your old home directory:

$ mv /home/alan /home/alan-old

Everything should be ready now - time to reboot into the installer of your distro of choice!

2 - Installation

Just install as usual, feel free to obliterate your old root partition but make sure you don’t touch your home partition! Install as if your home directory will be on your root partition along with everything else.  Reboot into your new fresh Linux installation.

3 - Juggling

Now all that’s left to do is get your home directory onto your home partition, get your home partition mounted and move all your files back to their rightful places.

Yet again, this process will require you to log in directly as root to move the home directory around, so set the root password as before if necessary for your distribution.

Now log in as root on a virtual terminal (e.g. Ctrl+Alt+F1) to mount your home partition somewhere, copy your new home directory across, and unmount it again.

$ mount /dev/sda7 /mnt
$ cp -a /home/alan /mnt/
$ umount /mnt

Now we want to make sure the home partition get’s mounted at /home as it should. Edit /etc/fstab with your editor of choice and add the fstab line from earlier. To make sure everything is correct, mount the home partition in a way that’ll use fstab, and check that both the old and new home directories are there:

$ mount /home
$ ls /home/
alan   alan-old

Just in case your user ID has changed, make sure your old home directory is owned by your new user:

$ chown -R alan:alan /home/alan-old

At this point, you should be finished with using the root account, and can log in as normal. If you want to lock the root account (in the way Ubuntu does by default), run

$ sudo usermod -L root

4 - Get your files

Now you should be able to browse both your new and old home directories using your file manager of choice. Open one for each, show hidden files, and start dragging stuff around!

This step might take some time, but has the added advantage that you get to learn where every application stores its user files, and also gives you the opportunity to clear out some junk you didn’t need, clean up your directory structure, or whatever else.

Final notes

This process is probably slower than an upgrade, especially considering the step of sorting your old files into your new home directory. However, it gives you very direct control over the process, lets you start with a nice clean copy of your operating system, and if done correctly doesn’t require a full backup to be made.

I much prefer this method to doing an upgrade because it leaves you free of the “old version cruft” that accumulates when you upgrade—an operating system upgrade is a complex process and is never going to handle every edge case.

If you trust all of your applications to handle old configuration files etc. correctly and you want to save some time, you can skip all of the steps relating to moving/copying of your user’s home directory, so that when you mount your home partition your old home directory is used.  If reinstalling rather than upgrading, I tend to do this.

Important: While I mention that this can be done without a backup, doing so is at your own risk.  Generally speaking it is prudent to backup anything important to somewhere outside of your machine before doing any operating system installation to protect against mistakes.  Otherwise, be extremely careful!  I do things this way because my home directory is always too large to backup anywhere, but I also run an automated nightly backup of the small, important stuff.

Comments and corrections are welcome!

C linked list macro

December 19th, 2008 • , , • No Comments

Here’s a simple macro I came up with a few weeks ago for easily defining linked list types in C.

#define LINKED_LIST(type, name)     \
    struct name ## _ {              \
        struct name ## _ * next;    \
        type data;                  \
    };                              \
    typedef struct name ## _ name;

Usage is simple:

LINKED_LIST(int, int_ll);

gives the same type as

struct int_ll_ {
    struct int_ll_ * next;
    int data;
};
typedef int_ll_ int_ll;

Why I dislike PulseAudio (for now)

December 17th, 2008 • • No Comments

Before this sounds like a rant, I’d like to first say that I think PulseAudio is a very nice concept, from a technical perspective.  It’s about time Linux got a managable sound subsystem, and some of the features–such as network streaming and synchronised playback–are quite impressive.

However, one thing that really irks me is that, as deployed by major distributions, it appears to enforce the narrow-minded view that a desktop is used by only one person, and that sound is only ever going to play when somebody is logged in to a graphical session.  Anybody who uses MPD has probably experienced the pain caused by this already.  Unfortunately my experience so far with Ubuntu Intrepid is that trying to change this results in even more pain.  Having set up a system-wide instance I’m now in the position where the first time I attempt to play sound works correctly, but any subsequent attempts fail until I kill a per-session PulseAudio instance that has magically spawned (even though I’ve set it not to).  Once the per-session instance is dead, I have no more problems and everything works perfectly until the next time I log in.

I’m currently trialing Fedora 10 on my desktop, so I’ll update this post if I have any more luck there.  Feel free to correct me in the comments if I’m just being stupid or missing something!

Edit: I’ve since fixed this problem: MPD + PulseAudio + Ubuntu Intrepid (8.10).

Yet another blog

December 17th, 2008 • 1 Comment

The title says it all.  Yet another blog.  And I don’t just mean in the sense of adding more noise to the Internet.  In the time I’ve been maintaining websites, I’ve probably had around 10 things that might be classified as blog-like, ranging through various pre-existing systems (like WordPress) and several self-written content management systems, frameworks, blogs, wikis, etc.

This can be explained by the kind of person I am–I like to work things out, usually from some set of basic principles.  For me, putting a site together using something like Joomla is no fun–the real fun to be had is in actually working out how to write a database-backed content management system with a plugin architecture and theming.  This means that for all personal websites I have a natural tendency to try and write everything myself.  The symptoms are reminiscent of “not invented here” syndrome, yet the cause is different to most.  Most of my projects that fall in this category have been web applications, for some reason.

Which is why using WordPress is a significant step in the right direction for me.  With the time pressures I’ve gained over the past two years, time to work on fun projects is much shorter than before, and the end result is never finishing anything.  If I have a limited amount of time to spend on a project, I spend it on the one that is the most interesting at the time.  Unfortunately, the “interesting” bits tend to die out about 1/3 of the way through most projects, the other 2/3 being hard work to actually mold it into something usable.  When, for example, my blog software is incomplete and not very nice to use because I never got around to finishing the administration interface, I end up not using it, creating yet another stagnant website.  I regularly have ideas for things to write about, but only have about 30 minutes free in which to write them–the downside of wrestling with unfinished software outweighs the smug feeling of “I wrote this”, turning it to “why did I bother?”.  I’ve started giving up on these dead-end projects, moving project documentation to DokuWiki, moving my blog to WordPress, using gitweb instead of my own Git browser, etc.  This is leading me to consider a wider approach of evaluating my projects based on criterias such as “has it been done already?”, “can I get it done in a short period of time?”, etc., and ditching projects which will be a huge amount of effort for little or no gain.  I simply don’t have the time any more.  It’s become painfully obvious that I need to weed out some of my projects to have any hope of producing anything ever.

Still here?  Awesome.  So after that little ramble, let me tell you what this blog should be…  My aim is to generally write about interesting technical stuff I come across that I think like-minded people would be interested in.  What I’m not going to do is use it to ramble on about my own life in general—I’m sure nobody cares.  (Ok, this post was a bad example—I’m tired, it’s to be expected.)  Hopefully along the way I can improve my writing style to be a bit more readable.

Still here???  Wow.  Congratulations—you win one Internet!  Check back later, I might have written something interesting!  (Or use the RSS feed.)

The curse of Firefox extensions

February 24th, 2008 • • 1 Comment

Note: This is a re-post of an article from my previous blog.

Today is my first day of Firefox usage after a three-week break - a break which taught me something…

First, a little background. I’ve been using Firefox since 0.9, and generally its always been the best browser for me. However, recently I lost my taste for it due to the monumental lack of speed it can display sometimes. I mean things like a half-second delay between hitting Ctrl+T and being able to type in the address bar of the new tab, really long page rendering times, etc. I know that Firefox slowness is generally due to extensions, but I relied on most of my extensions. Here is a list of the extensions I can remember having:

  • AdBlock Plus
  • AdBlock Filterset.G updater
  • CustomiseGoogle
  • Download statusbar
  • Firebug
  • Flashblock
  • Foxmarks
  • NoScript
  • QuickRestart
  • Stop Autoplay
  • Stylish
  • Tab Mix Plus
  • Tiny Menu
  • Web developer toolbar

Then I remembered I had tried the Epiphany browser (for GNOME) at some point in the past, and that it had been quite snappy. To put it simply, Epiphany is a browser that uses the Gecko rendering engine, but doesn’t include all the other stuff that slows down Firefox (which I can only assume to be the Extension framework and XUL). The upside is that its blindingly fast. The downside is that you no longer have all the amazing Firefox extensions you’ve become used to. One other advantage over Firefox is that it already has working tag-based bookmarking (slated for Firefox 3.0).

After forcing myself to cope without my extensions for a day, I started to really enjoy the speed and lack of wait-induced stress - Epiphany stays out of my way and gets stuff done really fast. Once I had the momentum, I just kept going. I discovered nice stuff like the fact typing in the address bar also searches your bookmarks as well as your history (something also in Firefox 3.0). Epiphany’s UI is reasonably customisable, but not to the extent that Firefox’s is.

Eventually I had an epiphany (terrible pun, I know…) - I had just survived 3 weeks without the huge number of extensions I came to think I needed in Firefox. I now realised I could go back to Firefox and use it more sensibly. I threw out my old Firefox profile and started again. I now have only the following well-justified extensions:

  • Flashblock - on a laptop, unexpected Flash ads = bye-bye battery life
  • Foxmarks - because I want my bookmarks on at least 3 different machines
  • QuickRestart - no real effect on performance, and sometimes you want to restart Firefox quickly!
Condensed Firefox layout

Condensed Firefox layout

I’m happier with this setup than I was with Epiphany, and it’s a good trade-off between fancy features and responsiveness. One thing I really like about Firefox is the ability to put anything anywhere on the toolbars, and I use a fairly condensed layout, so I was also really happy to go back to the layout I liked.

In my opinion, the best thing to do when deciding if an extension is worth installing is ask yourself the following questions:

  • Does it analyse and/or change what I am viewing?
  • Does it make comparisons against a large whitelist/blacklist?

Extensions doing either of the above will almost certainly slow your browser down to some extent. You will notice that the only content-sensitive extension I have is Flashblock, which is really worth it on a laptop.

Another option is to have multiple Firefox profiles, one of which is clean (like my current setup), and the other having big slow extensions that you sometimes need, like Firebug. Using the -P option to Firefox you can set up a launcher that starts your second profile instead of the default.

Newer Entries »