Binary tree post order iterative traversal

I’m feeling bothered with the current tree search implementations I’ve found online. I think they are confusing and more difficult than they should be. People state that iterative post order is the “hardest of the three iterative DFS”, while the three implementation are supposed to be at least somewhat orthogonal.

So, here is my implementation of a post order iterative traversal. The idea is that we use a stack to store a program. The program has 3 parts, processing the left and right nodes and processing the current node, just like the contents of the recursive function. We also store context information to know what to do in each part of the program, again, like the recursive function: for children, we do the recursion (add a new program in the stack), for the current node, we process it.

#!/usr/bin/env python

class Tree:
        def __init__(self, val, left=None, right=None):
                self.left = left
                self.val = val
                self.right = right

        def postorder(self):
                stack = [(self.val, False), (self.right, True), (self.left, True)]

                while len(stack) != 0:
                        data, is_tree = stack.pop()
                        if not is_tree:
                                print(data)
                                continue
                        if data is None:
                                continue
                        stack += [(data.val, False), (data.right, True), (data.left, True)]

if __name__ == '__main__':
        t = Tree(1, Tree(2, Tree(3), Tree(4)), Tree(5, None, Tree(6)))
        t.postorder()

To implement the inorder and preorder versions, just change the relative position of self.val when inserting a new program in the stack.

                        stack += [(data.right, True), (data.val, False), (data.left, True)]
                        stack += [(data.right, True), (data.left, True), (data.val, False)]

The Hello Wayland Tutorial

TLDR

I’ve written a hello world for wayland. It’s available at:

https://gitlab.com/hdante/hello_wayland

Introduction

hello_wayland_screenshotFrom the end user perspective it’s very easy to understand what wayland is: it’s a new window system with the display server and window manager merged [1]. From a technical point of view, the goal of wayland is to break from legacy and implement an efficient window system with modern design for modern graphics usage, solving long standing efficiency problems and specific corner cases present in the X Window System [2]. This tutorial shows how to implement a hello world client application for wayland, explaining essential wayland concepts and all the steps required to create any fully working wayland client. The hello world application does not use any GUI toolkit, it directly uses the low level wayland protocol, so that the fundamental parts of wayland are described. The tutorial is a result of my own study of the wayland protocol. The tutorial is divided into 2 posts. This is the first post, that will explain all the concepts and the high level part of the hello world application.

What is wayland again ?

The complete design for the wayland window system is split into several layers. If you download the wayland library source code [3], or take a look at the wayland API [4], you will notice two layers:

  1. The most basic layer is an implementation of inter process communication functionality, together with a few utilities, like a main loop dispatcher and some data types. This is nearly all code present in the wayland library (everything inside the src directory [5]) and has almost no code related to window systems.
  2. The second layer is the window system protocol. Its description is located in a single file, protocol/wayland.xml [6], which should be considered the protocol written in an interface definition language. The IDL file can be passed through the wayland-scanner tool to generate proxy methods in wayland-client-protocol.h and wayland-server-protocol.h. The protocol defines the essential functionality for client applications and the display server, like providing access to input devices and registering shared buffers for displaying on the screen. The wayland library does not implement this protocol. Instead, implementation is split into a third separate layer. In particular the reference server side implementation is part of the weston display server [7], which in turn defines additional layers, both server and client side, to complete the set of wayland protocols. We don’t need to know anything about weston for the hello world application, though, the IDL file has all we need to implement the client-side protocol.

From the description of the wayland library given above, we have successfully found a third definition of wayland, it’s a (special purpose) IPC library, not unlike the D-Bus library, instead of a display server, and this lack of definition for what wayland really is, and how well defined the wayland protocols are and where, is present everywhere. I believe it’s common for people not understand what wayland is even after reading official documentation. I think that the three definitions given clarify the “what is wayland” problem and each can be used for different contexts.

Hello, World!

The introduction ended up rather large, so lets see the main hello world code at once:

#include 
#include 
#include 
#include 
#include 
#include 

#include "helpers.h"

static const unsigned WIDTH = 320;
static const unsigned HEIGHT = 200;
static const unsigned CURSOR_WIDTH = 100;
static const unsigned CURSOR_HEIGHT = 59;
static const int32_t CURSOR_HOT_SPOT_X = 10;
static const int32_t CURSOR_HOT_SPOT_Y = 35;

static bool done = false;

void on_button(uint32_t button)
{
    done = true;
}

int main(void)
{
    struct wl_buffer *buffer;
    struct wl_shm_pool *pool;
    struct wl_shell_surface *surface;
    int image;

    hello_setup_wayland();

    image = open("images.bin", O_RDWR);

    if (image < 0) {
        perror("Error opening surface image");
        return EXIT_FAILURE;
    }

    pool = hello_create_memory_pool(image);
    surface = hello_create_surface();
    buffer = hello_create_buffer(pool, WIDTH, HEIGHT);
    hello_bind_buffer(buffer, surface);
    hello_set_cursor_from_pool(pool, CURSOR_WIDTH,
        CURSOR_HEIGHT, CURSOR_HOT_SPOT_X, CURSOR_HOT_SPOT_Y);
    hello_set_button_callback(surface, on_button);

    while (!done) {
        if (wl_display_dispatch(display) < 0) {
            perror("Main loop error");
            done = true;
        }
    }

    fprintf(stderr, "Exiting sample wayland client...\n");

    hello_free_cursor();
    hello_free_buffer(buffer);
    hello_free_surface(surface);
    hello_free_memory_pool(pool);
    close(image);
    hello_cleanup_wayland();

    return EXIT_SUCCESS;
}

The wayland protocol is verbose, so I separated the code into two parts, one containing the protocol details and another, the main module, shown above, containing the high level "hello world" implementation. The main() function is written at algorithmic granularity and represents the complete set of steps necessary to communicate with the display server to display the hello world window and accept input from the pointer device, closing the application when clicked. A description of the relevant parts of the code follows:

#include "helpers.h"

The helper module contains the hello_* functions and a set of global objects present in wayland. The root global object is the display object, which represents the connection to the display server and is used for sending requests and receiving events. It is used in the code for running the main loop. The helpers module will be described in details in the next part of this tutorial.

static const unsigned WIDTH = 320;
static const unsigned HEIGHT = 200;
static const unsigned CURSOR_WIDTH = 100;
static const unsigned CURSOR_HEIGHT = 59;
static const int32_t CURSOR_HOT_SPOT_X = 10;
static const int32_t CURSOR_HOT_SPOT_Y = 35;

In this tutorial we display an image as the main window and another for the cursor. Their geometry is hardcoded. In a more general application, though, the values would be dinamically calculated.

void on_button(uint32_t button)
{
    done = true;
}

This is the button callback. Whenever a button is clicked, we set the done flag to true, which will allow us to leave the event loop in the main() function.

    hello_setup_wayland();

We begin the application calling a setup function, which connects to the display server and requests a collection of global objects from the server, filling in proxy variables representing them.

    image = open("images.bin", O_RDWR);

Then we open the image file. This image file contains the hardcoded images for the hello world application, already in a raw format for display: it’s the pixel values for the main window, followed by the pixel values for the cursor.

    pool = hello_create_memory_pool(image);

A main design philosophy of wayland is efficiency when dealing with graphics. Wayland accomplishes that by sharing memory areas between the client applications and the display server, so that no copies are involved. The essential element that is shared between client and server is called a shared memory pool, which is simply a memory area mmapped in both client and servers. Inside a memory pool, a set of images can be appended as buffer objects and all will be shared both by client and server.

In the hello world application we mmap our hardcoded image file. In a typical application, however, an empty memory pool would be created, for example, by creating a shared memory object with shm_open(), then gradually filled with dynamically constructed image buffers representing the widgets. While writing the hello world application I had to decide if I would create an empty memory pool and allocate buffers inside it, which is more usual and simpler to understand, or if I would use a less intuitive example of creating a pre built memory pool. I decided to go with the less intuitive example for an important reason: if you read the whole hello world source code, you’ll notice that there’s no memory copy operation anywhere. The image file is open once, and mmapped once. No extra copy is required. This was done to make clear that a wayland application can have maximal efficiency if carefully implemented.

    surface = hello_create_surface();

Objects representing visible elements are called surfaces. Surfaces are rectangular areas, having position and size. Surface contents are filled by using buffer objects. During the lifetime of a surface, a couple of buffers will be attached as the surface contents and the server will be requested to redraw the surfaces. In the hello world example, the surface object is of type wl_shell_surface, which is used for creating top level windows.

    buffer = hello_create_buffer(pool, WIDTH, HEIGHT);

The buffer object has the contents of a surface. Buffers are created inside of a memory pool (they are memory pool slices), so that they are shared by the client and the server. In our example, we do not create an empty buffer, instead we rely on the fact that the memory pool was previously filled with data and just pass the image dimensions as a parameter.

    hello_bind_buffer(buffer, surface);

To make the buffer visible we need to bind buffer data to a surface, that is, we set the surface contents to the buffer data. The bind operation also commits the surface to the server. In wayland there’s an idea of surface ownership: either the client owns the surface, so that it can be drawn (and the server keeps an old copy of it), or the server owns the surface, when the client can’t change it because the server is drawing it on the screen. For transfering the ownership to the server, there’s the commit request and for sending the ownership back to the client, the server sends a release event. In a generic application, the surface will be moved back and forth, but in the hello application it’s enough to commit only once, as part of the bind operation.

    hello_set_cursor_from_pool(pool, CURSOR_WIDTH,
        CURSOR_HEIGHT, CURSOR_HOT_SPOT_X, CURSOR_HOT_SPOT_Y);

After setting up the main window, we configure the cursor. This configuration is required: the client must configure the cursor. Here we set the cursor to be the preset contents of the memory pool (implicitly right after the main window buffer). The helper module then creates a surface and a buffer for the cursor. I had to decide if I would hide the cursor configuration in the helper module or if I would explicitly add a high level step for it. I dedided to go with the second one to show the division of roles in wayland: the client is given a large control over what and how to draw.

    hello_set_button_callback(surface, on_button);

The last configuration step is to set up a callback: associate a surface click with the on_button callback.

    while (!done) {
        if (wl_display_dispatch(display) < 0) {
            perror("Main loop error");
            done = true;
        }
    }

This calls the main loop with the global display object as the parameter. The main loop exits when the done flag is true, either because of an error, or because the button was clicked.

    hello_free_cursor();
    hello_free_buffer(buffer);
    hello_free_surface(surface);
    hello_free_memory_pool(pool);
    close(image);
    hello_cleanup_wayland();

The application finishes by cleaning up everything.

Conclusion

This was the first part of the hello world tutorial. A discussion abot what is wayland was presented and operation was described with help of a high level example. In the next part I’ll describe the helper functions in detail.

References

[1] http://wayland.freedesktop.org/architecture.html
[2] http://mirror.linux.org.au/linux.conf.au/2013/ogv/The_real_story_behind_Wayland_and_X.ogv
[3] http://cgit.freedesktop.org/wayland/wayland/tree/
[4] http://wayland.freedesktop.org/docs/html/
[5] http://cgit.freedesktop.org/wayland/wayland/tree/src
[6] http://cgit.freedesktop.org/wayland/wayland/tree/protocol/wayland.xml
[7] http://cgit.freedesktop.org/wayland/weston/tree/

Can compression slow down network transfers ?

Note: this post is mostly relevant to local links or very fast internet links. The task was to transfer a backup from my notebook to my desktop machine using an ethernet connection. After googling a little about rsync I ended up with the following discussion.

An interesting finding: using modern compression tools degrades transfer performance, because their compression speeds are lower than the disk speeds (and don’t compensate with data compression). For example, gzip compression is about 11MiB/s, while lzmash is 0,5MiB/s, or 22 times slower (2005 data). Expected compression is 2,7 times for gzip and 3,7 times for lzmash (when compressing openoffice):

​http://tukaani.org/lzma/benchmarks.html

This also means that gzip efficiency is limited to a network of 11MiB/s (92,3 Mbps). If a faster network is available, removing gzip will increase transfer rate. Ex: 100 Mbps.

  • File: 1GiB
  • raw transfer time: 85,9s
  • gzip time: 93,1s

Best cases described for gzip varied (in 2005) from 18MiB/s to 24MiB/s in fast mode. A more recent benchmark describes gzip at 54,8MiB/s at its best configuration, compressing source code:

http://pokecraft.first-world.info/wiki/Quick_Benchmark:_Gzip_vs_Bzip2_vs_LZMA_vs_XZ_vs_LZ4_vs_LZO

This raises network break even speed to 460 Mbps.

This updated benchmark describes 2 compressors much faster than gzip: lz4 and lzop. lz4 achieved 341,9MiB/s and lzop 277,8MiB/s. Network break-even jumps to 2.868,2 Mbps, but in this case, transfer would be limited by disk speed (or network). Expected compression is 2,8 times (for source code), versus 3,7 for gzip. Reviewing the transfer example:

  • File: 1GiB
  • raw transfer time: 85,9s
  • gzip time: 18,7s
  • lz4 time: 3,0s
  • gzip transfer time: 276,8MiB @ 23,2s
  • lz4 transfer time: 365,7MiB @ 30,7s
  • gzip decompression: 3,5s
  • lz4 decompression: 0,4s
  • gzip total time: ~26,7s (+latency)
  • lz4 total time: ~31,1s (+latency)

In this case gzip won, since the transfer is limited by the 100 Mbps link, so the best compression won. The improved gzip compression speed to more than 50MiB/s also made a lot of difference (however I’m currently unable to explain this speedup, since a quick and dirty gzip execution in my machine resulted in 17MiB/s).

Selecting the proper compressor, then is a matter of considering the transfer speed of the disk, the compressor and the network together, since each of them may impose a specific upper limit on each step of the transfer.

First steps after you got your Raspberry Pi

Those are the very first steps that you should do right after you received your Raspberry Pi, downloaded the SD images, booted it and randomly played with it for one week. 😀

Change the password: most important step if the Raspberry Pi will be connected to the Internet.

$ passwd

Quick configuration: these are available in Raspbian‘s raspi-config script.

# dpkg-reconfigure keyboard-configuration
# dpkg-reconfigure locales
# dpkg-reconfigure tzdata

Test your SD card:

# dd if=/dev/mmcblk0 of=/dev/null bs=512k count=256 iflag=direct
256+0 records in
256+0 records out
134217728 bytes (134 MB) copied, 6.13969 s, 21.9 MB/s
# dd if=/dev/zero of=/root/test bs=512k count=64 oflag=direct
64+0 records in
64+0 records out
33554432 (34 MB) copied, 10.4764 s, 3.2 MB/s
# rm /root/test

SD card performance should match its class. My SD card is a class 4, so write speed must be around 4 MB/s. Also, slow read speeds could indicate problems.

Update your distro:

# apt-get update
# apt-get upgrade

Improve network configuration: this makes the Pi less dependent on having an external router by adding a permanent static IP address and activating NAT. Skip the network configuration if your Raspberry will always have a router around.

# echo net.ipv4.ip_forward=1 >> /etc/sysctl.conf
# cat << EOF >> /etc/network/interfaces
iface eth0:fixed inet static
 address 10.10.10.1
 netmask 255.255.255.0
 up iptables -t nat -A POSTROUTING -o eth0 -s 10.10.10.0/24 -j MASQUERADE
 down iptables -t nat -D POSTROUTING -o eth0 -s 10.10.10.0/24 -j MASQUERADE
EOF

This extra entry (together with the default dhcp interface rule) allows the following scenarios: rasp pi directly connected to your internet modem (using DHCP address); rasp pi connected to computer (using static address); rasp pi connected to a modem (using DHCP address) and computer (using static address and doing internet connection sharing); rasp pi connected to modem and computer, only the computer connected to the internet (the difference in this case is that the computer got the DHCP address from the modem first).

Now write the startup script:

# cat << EOF > /etc/ifplugd/action.d/ifupdown-more
#!/bin/sh
 set -e

if [ "$1" != "eth0" ]; then
 return
 fi

case "$2" in
 up)
 /sbin/ifup $1:fixed
 ;;
 down)
 /sbin/ifdown $1:fixed
 ;;
 esac
EOF
# chmod +x /etc/ifplugd/action.d/ifupdown-more

This is similar to the standard “ifupdown” script and allows automatic interface configuration.

Configure the static connection to Raspberry Pi on your main desktop machine:

# cat "/etc/NetworkManager/system-connections/Raspberry NAT"
(...)
[ipv4]
 method=manual
 dns=8.8.8.8;
 addresses1=10.10.10.2;24;10.10.10.1;
 ignore-auto-routes=false
 ignore-auto-dns=false
 never-default=false
(...)

The dns line above needs to have some random DNS server, for example, I used Google’s (alternatively install DNS proxy support in the Pi). Use the above connection profile in your main machine when using the Pi as a router.

Add a friendly name to Raspberry Pi:

# echo 10.10.10.1 prosraspberry >> /etc/hosts

This is also in the desktop machine, an easy name to find the Pi. Now connect both machines together and test ssh:

# ssh pi@prosrasperry
The authenticity of host 'prosraspberry (10.10.10.1)' can't be established.
 RSA key fingerprint is 33:95:41:c6:d4:06:8b:79:7e:e4:01:fb:17:39:ed:93.
 Are you sure you want to continue connecting (yes/no)? yes
 Warning: Permanently added 'prosraspberry' (RSA) to the list of known hosts.
 pi@prosraspberry's password:
 Linux raspberrypi 3.2.27+ #160 PREEMPT Mon Sep 17 23:18:42 BST 2012 armv6l
(...)
pi@raspberrypi ~ $

Finally, copy the public key from your main machine to the Pi.

$ scp ~/.ssh/id_rsa.pub pi@prosraspberry:id_rsa.tmp
$ ssh pi@prosraspberry
$ cat id_rsa.tmp >> ~/.ssh/authorized_keys
$ rm id_rsa.tmp

And that’s it. The main point of this initial configuration is that now Raspberry Pi should be completely usable anywhere. You just need a power cable and an ethernet cable to connect to it ! 🙂

I own a Raspberry Pi !

Last week I received my Raspberry Pi. It was not that easy, me and some coworkers tried to import them directly from the UK, but they were not available and we would need to wait for weeks. We were able to cancel the order and buy from Farnell small stock here in Brazil. So it’s true, Raspberry Pies do reach Brazil !

For curiosity, and also to show the Brazilian broken imports regulation, each Raspberry cost us US$ 83,00 (€ 64,00) !!! That’s almost two and a half times the price of a Raspberry, mainly because of the import taxes at 60%. This tax is supposed to protect the Brazilian semiconductor industry, but that industry is non existent. On top of that there is another tax that further expands the value of the import tax, the two combined reaching almost 100%. If we had managed to import it directly from UK, it would have been even more expensive, at around US$ 100,00.

Now for the pictures !

First impressions: I had some goals for the Raspberry Pi. First was to use it as a general server and router at home. The second was to use it as a portable cool “pseudo-notebook”. The third was to have an ARM machine, for study and for fun. My initial view is that the Raspberry Pi is somewhat disappointing for some of these goals, specially number two. In particular I noticed that the board is unable to do web browsing at reasonable performance, taking many seconds to respond to interactive use.

Taking a look at the forums, this is confirmed by a general agreement that rasppi had the specific goal as being a learning device for students and never meant to do web browsing in general. Also I’ve noticed that the rasppi is very dependant on the SD card performance, the minimum officially recommended (a class 4 SD card) not being enough for my goals. At least, there’s some effort being done to overcome part of the performance issues. 🙂

EFL EasyUI toolkit quickstart

easyui demo appEasyUI is an API wrapper for Enlightenment‘s elementary widget toolkit. EasyUI is built on top of elev8, both easyui and elev8 being javascript wrappers for elementary with the goal of rapid application development with the enlightenment libraries. The difference is that easyui is much higher level. This tutorial provides quick installation instructions so that one can play with the library.

Install the enlightenment libraries: currently we need the svn versions, so use some repository listed in the download page.

$ sudo add-apt-repository ppa:hannes-janetzek/enlightenment-svn
$ sudo apt-get update
$ sudo apt-get install libedje-dev libeio-dev
$ sudo apt-get install libelementary-dev

Install V8: that’s the javascript interpreter.

$ sudo apt-get install libv8-dev

Install elev8 and easyui:

$ svn checkout http://svn.enlightenment.org/svn/e/trunk/PROTO/elev8/
$ svn checkout http://svn.enlightenment.org/svn/e/trunk/PROTO/easyui/
$ export elev8path=$HOME/elev8
$ cd elev8
$ ./autogen.sh
$ ./configure --prefix=$elev8path
$ make
$ make install
$ cd ../easyui
$ edje_cc eui.edc
Test easyui:
$ $elev8path/bin/elev8 ./infinigag.js

After this step, the infinigag.js test application should be running.

Next steps: these will be the same for all of us, learn about easyui, what it can do and if it’s worth it. My friends developing it told me that it has zero documentation right now except the source and the example code. Their blogs have some further reading, commented code and videos.