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?

StrictWeakOrdering

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('position','absolute');
        $(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!

Use ZeroMQ to control a receipt printer

A customer needed a solution to the following problem. There are multiple web POS systems that need to print to a receipt printer. The web server is not in the same place as the POS terminals, but they are connected to a network.

To solve the problem I used ZeroMQ to connect the web server to the receipt printers. The current solution consists of four parts.

  1. Web app
  2. Web server (connects a PUSH socket to a PULL socket)
  3. ZeroMQ device (a multiplexer receives from a PULL socket and sends these to a PUB socket)
  4. Computer with receipt printer (a sink that receives on a SUB socket subscribed to its own address)

First a user in a browser clicks the button to print a receipt.

This command is converted into a data packet formatted for the receipt printer.

This data packet is send to a small program that connects the web server and the point of sale systems. The first frame of the data packet contains the name of the POS system that should print the receipt.

The command to print the receipt contains the address of the terminal that requested to print.

The two small programs are written in Go. The multiplexer program opens two sockets and reads from one socket and sends the other socket. Program 4 opens a socket and reads from it. It sends the packets that it receives to WinAPI printer functions.

The nice thing of the solution is that the multiplexer program doesn't need to know how many printers are connected. So the customer can just connect a sink program for every new terminal that is added.

File transfers for mobile phones

Sometimes I need to copy a file from my computer to my phone. That's should be really easy. But it's not. I would like it to work like this:

  1. I put a file in a folder.
  2. If my phone is on the same network, the file should be copied from the computer to my phone, without further actions from me.

And that's it. The file shouldn't be copied to a server somewhere else. It should only move from my computer to my phone and never touch the internet.

It also means that this functionality won't work over the internet. So if my phone is not connected to the local wifi, it stays on the computer.

The other way around, if I make a few photos with my phone, these photos should be copied automatically to a directory on my computer when I come home.

Why doesn't it work like this?

Redis queue design choices

In a previous post I wrote about simple job queue in Redis. In this post I like to write a bit about the design choices. I think these choices illustrate a point about design.

Job handle

The job handle in the code is create by the client (with help from the Redis server). This job handle is passed to the queue in Redis and picked up on the other side by the worker.

The worker doesn't need to know the content of the key. The key is opaque. This means that the key could be changed to be something else. In the current case the handle is the build up out of the queue name and a unique id.

The worker only needs to know which commands it can use with that job handle. In this case the commands are HGETALL and DEL. When the job handle changes, because it uses a hash type value, then the workers don't need to change.

After the worker got the hash value with the job from Redis, it can perform it's job. The value is specific to the worker and this shouldn't change. In the content of the value uses the keys and value types then the workers keep working. Upgrading the content can be done separately for the client and the worker, if you keep the same keys in the job and only add keys. The workers can get upgraded later with the newer commands. This could also be done the other way around as long as the new worker understands the old job data.

The keys here are similar to URI in HTTP (and REST). The value of the URI is opaque. As a client you shouldn't create URI yourself, but you should the follow the URI from the server according to its media type.

Incrementing the id of the job

Handle of the job consists of the name of the queue and a unique id. We get this id from Redis using the INCR command. The command returns the current value + 1. We use this exact value in the handle. In a way we use the value in pre increment way. We increment and then use the value. This means that we can use the exact value that we got back from Redis.

Another way is to say that the value in Redis is id of the next job. By incrementing the value we say that we used this value. The only problem is that the returned value is one higher than the value we would like to use. So we need to decrement the returned value with 1.

The design choice here was to use the exact value from Redis. In a way this is the same as the job handle example. There the worker uses the exact value that it got. This choice makes it easier, because there is no calculation needed

Redis is a flexible solution to a lot of problems, but as always you need to make choices to get a solution the works for your problem.

Welcome

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

Profiles