Removed Analytics

I just removed Analytics from my website. It's not important for me. I don't have the time to look at it.

Sorting DNS records

I don't update my DNS records often, but when I do I like these records sorted.

A DNS record consists of the following fields: domain name, type and prio (for some types). I use these fields to determine the order of the records. That is also the order in which these fields should be ordered.

The first insight I had about sorting domains was that the domain names consist of parts separated by a period. The domain names may be strings. But a domain name is actually a reversed array of strings. We map the domain name from "" to [ "com", "example", "sub" ]. This puts it in an order that makes lexicographical compare work. To compare domain names is to compare these arrays of parts with a lexicographical compare function.

sub lexicographical_compare(\@\@) {
    my ($a, $b) = @_;
    my $i = 0;
    while ($i < @$a && $i < @$b) {
        my $c = $a->[$i] cmp $b->[$i];
        return $c if $c; # $c != 0;
    return @$a <=> @$b;

sub compare_dns_record {
    my ($a, $b) = @_;

    my $c = lexicographical_compare($a->{domain_parts}, $b->{domain_parts});
    return $c if $c;

    $c = $a->{type} cmp $b->{type};
    return $c if $c;

    $c = $a->{prio} <=> $b->{prio};
    return $c;

The second insight here is that the record itself can also be compared lexicographically. But this is harder to write in Perl. In Haskell, for example, this is the default for tuples.

Rotate one to the left

Last week I wrote a small function in Perl that rotates and array to left. The function takes the item from the front and appends it to the back.

# precondition: @list >= 1;
sub rotate_left_by_one {
    my $ar = shift;
    my $item = shift @$ar;
    push @$ar, $item;

After calling this function as many times as the length of the array, it leaves the items in the same order they started in. Every call to this function puts a different item in the first location. I use it to compare this item to the rest of the items.

You would use it like this:

while (1 .. @list) {
    # your code

This function works great when the code doesn't depend on the order of the items in @list. The items in @list will be in a different order than what it started with for most of the iterations of the loop. This means that the code in the loop body needs to have the commutative property.

Low level code

Google released the PDF code of Chrome just a few days. I took a look at it. This file (core/src/fpdfdoc/doc_vt.cpp) is an example of how the code looks.

Sometime later it dawned on me that this code is built out of only low level pieces. There are almost no algorithms extracted to functions.

An example would binary search. There are five copies of binary search hidden in just that file. No wonder this file is 1864 lines of code.

What else would be hidden in there?


I always forget what strict weak ordering means, but it's quite simple, actually.

My explanation is based on the Programming Conversation of last week and I hope this will help me remember the next time I hear about this.

Let's start with ordering. A relation is an ordering if it is transitive.

ordering -->  for all a, b, c: r(a, b) and r(b, c) => r(a, c)

And now strict.

strict  -->   for all a:  !r(a, a)

This means that for a strict relation comparing a with itself will never be true. An example of r that is strict is <. A value will never be less than itself.

The complement of strict is reflexive.

reflexive -->  for all a: r(a, a)

This means that for a strict relation comparing a with itself will always be true. An example of relation that is reflexive is equality.

total   -->  for all a, b: r(a, b) or r(b, a) or a = b
weak    -->  for all a, b: r(a, b) or r(b, a) or (!r(a, b) and !(r(b, a))

Total ordering means that two objects relate to each other in one of three ways: a < b or b < a or a = b.

Weak ordering means the two objects relatie to each other in one of three ways: a < b or b < a or ( !(a < b) && !(b < a) ).

Broken interface of Math.min

In an article about creating a column layout I found the following two lines of code:

var min = Array.min(blocks);
var index = $.inArray(min, blocks);

This first finds the minimum value in blocks and then the index of that value. This combination of lines is very strange. Array.min already knows the index of the minimum element and throws it away. Then the programmer needs to find the index again with a linear search.

This means the interface of Array.min is incomplete. A more general version would return the index of the value in the array that is minimal. This can't be written on top of the Array.min function in a efficient manner.

The following is a function that returns the index of the minimum element in elements.

// elements is a non-empty array
function min_index(elements) {
    var i = 1;
    var mi = 0;

    while (i < elements.length) {
        if (elements[i] < elements[mi])
            mi = i;
        i += 1;
    return mi;

The corresponding max_index looks like this:

// elements is a non-empty array
function max_index(elements) {
    var i = 1;
    var mi = 0;

    while (i < elements.length) {
        if (!(elements[i] < elements[mi]))
            mi = i;
        i += 1;
    return mi;

Stability in column layout

I was reading the notes on programming PDF and found a discussion about writing min and max functions for multiple arguments. I didn't what to use this for. Also there was a discussion about stability. Stability is when you leave elements in the same position when they're the same. This seems to be about sorting.

At the same I was implementing a Pinterest like column layout. I already had a working version. But sometimes the images weren't loaded completely and the algorithm would overlap images, because the height of the element wasn't known.

So I started searching for solutions to this problem and found this answer on StackOverflow from the creator of the Pinterest layout himself. He doesn't have the solution to my problem, but suggests to put the element in the shortest column. This will solve a problem that I hadn't seen yet.

So I implemented the following:

function min(cols) {
    return (cols[0] < cols[1]) ? 0 : 1;

$(window).load(function() {
    var start = 100;
    var cols = [ start, start ];
    var w    = [ 0, 330 ];

    $('.submission').each(function() {
        var col = min(cols);

        var height = $(this).height();
        $(this).css('left', w[col]+ 'px');
        $(this).css('top', cols[col]+ 'px');
        $(this).css('width', '320px');
        cols[col] += height + 32;

As you can see in this case with two columns we can pick a column based on the height of column. At first I didn't think this had anything to do with stability. But it does. If you run this code the first element will be inserted in the right column. This is because the 0 in column 0 is not smaller than the 0 in column 1, it's equal. The min function will return 1 in this case, which is the right column.

Stability in the case of column selection is that the algorithm prefers to insert the element in the left column instead of the right column in case of equal heights.

There is a simple change that should be made to the min function to fix this problem. We need to swap the operands of the < operator and the return values so we don't lose stability.

function min(cols) {
    return (cols[1] < cols[0]) ? 1 : 0;

Properties like stability are general and also apply to Javascript.

Renewed interest in C++

In the previous post I showed a playlist of presentations by Alexander Stepanov, the creator of STL. In these videos he talks about algorithms and data structures (written in C++). This principled explanation of programming makes a lot of sense to me. And has me take a renewed look at C++.

Programming conversations

BitTorrent Sync

A month ago I wrote about File Transfer for mobile phones. There I wrote how I think a solution for file transfer should work. A few days later I found Bittorrent Sync. Problem solved!


My name is Peter Stuifzand. You're reading my personal website.