Hello Debian, my old friend

I’ve been using Linux as my primary operating system since early 2000. Similarly to many Linuxers, I’ve done my share of distro hopping. Here is, as far as I can recall, some of the distributions that I’ve used seriously (where seriously means for more than 6 months at one time) in order:

  • Mandrake (yes, that was before they changed their name)
  • Slackware
  • Debian
  • Ubuntu
  • Arch Linux
  • Lubuntu

Though I had known of Linux for a couple of years, it was only when I bought an issue of Linux France magazine that came with a Mandrake 6.1 CD and clear instructions that I decided to install Linux. I was quite lost at first, but after buying O’Reilly’s “Running Red Hat Linux”, I could do most of what I wanted to do.

Later on, I decided to try Slackware, because apparently that was for more hardcore users, and I wanted to be hardcore. Then came Debian, because I had heard great things about apt-get (and boy was I impressed the first time I used it!). I used Debian for a solid 4-5 years before Ubuntu appeared on the radar and started making a solid impression on the Linux world. I decided to try it out, and I really liked that it took away some of the drudgery of Debian.

I then had a foray of a year and a half with Arch Linux before I came back to Ubuntu, but this time I used Lubuntu since the first thing I did after booting Ubuntu was to uninstall over 100 packages relating to Gnome. As time went on, I kept using Lubuntu, but I became less and less happy with it, always hoping that the next major release would solve my issues, but it became clear that it wouldn’t happen.

Among the issues I had with Ubuntu were:

  • The upgrade process never worked for me, I always had weird issues that were usually resolved by reinstalling the entire OS.
  • The release process produced distributions that were less and less stable.
  • Ubuntu quickly pushed new products that didn’t feel like they had anything to do with the Unix philosophy
  • I had some weird bugs that I reported, but went without solutions.
    • If I used lightdm and the french Canadian keyboard layout, pressing and holding certain keys (the right and down arrow keys for examples) would not repeat them; changing the login manager or the keymap fixed the issue, but this was weird.
    • plymouthd (a piece of software that I just don’t understand) constantly used 5-7% of my CPU. Uninstalling it was not an option since so many packages depend on it. Disabling it caused other weird issues with the display
  • It seems that Ubuntu is becoming less and less a Linux distribution, and more and more its own OS.

Last week, I just had enough. I want a stable and simple operating system, and I was no longer getting that from Ubuntu. Debian Wheezy had been released a few weeks earlier, and I decided that it was time to go back to my ol’ trusty distro.

I downloaded the LXDE Live DVD, booted it and less than an hour later the system was installed and ready to roll. I added some repositories to have access to Chrome and the latest Emacs snapshots, the only two programs that I want to be as up to date as possible. In less than two hours, I had a system that looked and worked exactly like my Lubuntu setup (except that the load average was closer to 0.0 than 1.0 as with Lubuntu!)

It’s been a week, and I have had no problems with Debian. The first time I used Ubuntu was because of the promise of easy hardware configuration; Debian Wheezy has that. My sound card and video card were automatically recognized and properly configured, I only had to install firmware-realtek to get my Wifi card working, my integrated webcam worked without me having to install or configure anything, so did my multiple gaming controllers.

The Debian folks have produced a truly fine operating system. For the next two years, I’ll be doing my M.Sc and I most likely won’t have the time or the inclination to fiddle and hack my OS, so I think that this stable Debian installation will suit me perfectly.

It’s good to be back!

Sorting algorithms in OCaml

We had a mini snow storm in Montreal this weekend, so instead of going to my usual Saturday afternoon chess club, I spent the day writing sorting algorithms in OCaml. It had been a while since I’d revised my notes from my algorithms class (which I finished two years ago), and I thought it’s be a nice time to do some review.

I implemented the following algorithms:

  • Bubble sort, O(n^2)
  • Selection sort, O(n^2)
  • Insertion sort, O(n^2)
  • Merge sort, O(n lg n)
  • Quick sort, O(n lg n)*

* Pivots are chosen at random.

I also wrote a small driver program to test them all on bunch of arrays. Here’s a sample run:

$ ./bench.native --iters 250 --max-elems 2500
Algorithm                       : Total		Average
insertion sort                  : 2.142468	0.008570
bubble sort                     : 5.517859	0.022071
selection sort                  : 2.795310	0.011181
merge sort                      : 0.115057	0.000460
merge sort + selection sort     : 0.100913	0.000404
merge sort + insertion sort     : 0.098223	0.000393
quicksort 1                     : 0.098276	0.000393
quicksort 2                     : 0.090065	0.000360
Array.sort                      : 0.106113	0.000424
Array.stable_sort               : 0.071891	0.000288

(The times are in seconds.)

A few notes: I have implemented an second merge sort function that can use an alternate sorting function when the arrays get small enough. Quicksort 1 and quicksort 2 are both implementations of an in-place Quick sort, but using different implementations. Finally, Array.sort and Array.stable_sort are OCaml’s standard library’s sorting functions.

During the implementation, I realized (again) that merge sort is my favorite sorting algorithm; the idea is simple, the implementation is easy (both with arrays and linked lists) and offers good performance. Insertion sort, which is super easy for linked lists, is a trickier than the other O(n^2) algorithms, because one of the invariants is a little unnatural; the element should be inserted not at position i, but i+1. It makes sense, but I was caught when I initially wrote the code, and ended up with an incorrect algorithm.

Notably missing from the list of algorithms are heapsort (which I’ll hopefully implement this week) and newer algorithms such as timsort and introsort, which I know little about.

I have made my code available on Github if you wish to look at it; I would also love to get some input on the quality of the code, or how to improve my code.

DCPU-16 implementation in F#

Ashley Feniello has an implementation of Notch’s DCPU-16 computer written in F#. One thing I really like was this pattern:

let mem i = (fun () -> memory.[i] |> int), (fun v -> memory.[i]  registers.[i] |> int), (fun v -> registers.[i]  v), (fun _ -> ())
let pc, sp, o = reg 8, reg 9, reg 10
let get v = (fst v) ()
let set v i = (snd v) i

It makes reading and writing to memory and into registers general, easy and abstract. Very nicely done, Ashley!

On not consulting users

The hot sports news today in Montreal is regarding the new NHL jerseys. These new jerseys (and also the socks the players wear) were designed by CCM-Reebok. The company hailed them as an important breakthrough in the sport, claiming that they were lighter than regular jerseys. The players, however, all seem to dislike the new gear: the jerseys and socks are impermeable, so instead of absorbing the water and sweat, it drips down into the skates and gloves of the players. Montreal Canadien player, Mike Komisarek, told Montreal newspapers that he needed to change gloves twice per period and socks between every period. You’d think that CCM-Reebok would’ve asked players what they think of the new gear before getting the NHL to impose it.

As a programmer, it’s not rare to hear stories about how management decided to replace one software by another without consulting the users who will use the new software. It’s comforting to know that we’re not the only discipline where this sort of clueless, unilateral actions occur.

Reddit: what Digg people will be talking about in two weeks

C++ is a horrible language, says Linus Torvalds, posted to Reddit on September 6th, 2007.

Linus Torvalds hates C++, posted to Digg on September 21st, 2007.

I usually found this “news appearance” pattern: Reddit gets it first, then Digg gets it, then Slashdot. The one exception are Apple stories where those are posted 29 times on Digg in a matter of seconds and all dugg up to the most popular stories, while Reddit gets one submission and it never reaches #1 (mostly because we’re busy upvoting xkcd)

Edit: Oh, and it seems Digg people can’t read articles. They’re all “well for a kernel, C is a better choice than C++.” They’re talking about git, not Linux!

Celebs of Reddit

One reason I prefer Reddit to Digg is because it seems people know each other better in the comment sections, especially in the section I hang out the most in, the programming section. More than that, some known developers hang there and shoot the breeze with the rest of us. Here’s an incomplete list of those developers:

What other celebrities hang on reddit?

Contributed by others:

Page navigation in Django

Django is cool, it gives you free pagination: you say “I just want 20 articles per page” and it’ll split your result set in sets of 20 objects. The thing that’s missing is a template tag to add navigation between these pages. I wrote a small sub-template, which depends on two of my own template tags, to automatically add page navigation. First, here are the template tags needed:

def pagination_get_string(get_dict, page_num):
    import copy
    get = copy.deepcopy(get_dict)
    get['page'] = page_num
    return '?' + get.urlencode()

def range1(n):
        return range(1, int(n) + 1)
    except ValueError:
        return []

Quick note about these two. pagination_get_string copies the current GET string and adds page=x to it. This ensures that if your pagination occurs in a search view with several parameters, moving between pages keeps the same parameters. range1 is pretty self-documenting, it returns a list from 1 to n (inclusively). Now, here is the sub-template:

{% load wsftags %}
{% for page_num in pages|range1 %}
    {% ifequal page_num page %}
        {{ page_num }}
    {% else %}
        <a href="{% pagination_get_string request.GET page_num %}">{{ page_num }}</a>
    {% endifequal %}
{% endfor %}

Just save this in a template directory and be sure to change the {% load %} statement to reflect the name of your own custom template tag file. You know, I think I should make this an inclusion_tag… Bah, another day. Anyway, to use it, just add this line to the template you wish to be paginated:

{% include "pagination.html" %}

Et voilà!