Mergesort, Quicksort and Heapsort growth

These three sorting algorithms grow at approximately the same rate according to this graph.

They are O(nlogn) on average. Selection sort and bubble sort are O(n^2)
Here's a graph of the O(nlogn) algorithms.

XBMC script for traffic cameras

XBMC is mighty cool. I use it all the time for my media ... and now for viewing traffic cameras. You can get the source from http://code.google.com/p/xmbc-traffic-cameras

XBMC trafffic camera screenshot

Mergesort performance

Updated Sorting performance graph. My Quicksort implementation has weird variations. I'll have to look at the algorithm to figure out what's going on. Mergesort and Quicksort are practically equivalent for these set sizes.

Debian lenny ipv4 socket bind failing

A certain daemon that had been working elsewhere was refusing to bind to v4 on my box. Strace'ing it showed this

connect(5, {sa_family=AF_UNSPEC, sa_data="\0\0\0\0\0\0\0\0\0\0\0\0\0\0"}, 16) = 0
connect(5, {sa_family=AF_INET, sin_port=htons(10042), sin_addr=inet_addr("0.0.0.0")}, 16) = -1 EAFNOSUPPORT (Address family not supported by protocol)
close(5)                                = 0
socket(PF_INET, SOCK_DGRAM, IPPROTO_IP) = 5
connect(5, {sa_family=AF_INET, sin_port=htons(10042), sin_addr=inet_addr("0.0.0.0")}, 16) = 0
getsockname(5, {sa_family=AF_INET, sin_port=htons(60862), sin_addr=inet_addr("127.0.0.1")}, [16]) = 0
close(5)                                = 0
socket(PF_INET6, SOCK_STREAM, IPPROTO_TCP) = 5
setsockopt(5, SOL_SOCKET, SO_REUSEADDR, [1], 4) = 0
bind(5, {sa_family=AF_INET6, sin6_port=htons(10042), inet_pton(AF_INET6, "::", &sin6_addr), sin6_flowinfo=0, sin6_scope_id=0}, 28) = 0
listen(5, 5)                            = 0
write(2, "Config port: 10042\n", 19Config port: 10042

Notice the kernel says IPV4 binding is not supported! I am dual stacked! I had IPV4, I could ping the box and other hosts over IPV4. A quick look at my sysctl.d showed

net.ipv6.bindv6only = 1

Switching this off (0) fixed the issue. You can also do it interactively by

echo 0 > /proc/sys/net/ipv6/bindv6only 

Now everything works as expected.
Update:
This is weird. According to the kernel documentation

bindv6only - BOOLEAN
        Default value for IPV6_V6ONLY socket option,
        which restricts use of the IPv6 socket to IPv6 communication
        only.
                TRUE: disable IPv4-mapped address feature
                FALSE: enable IPv4-mapped address feature

        Default: FALSE (as specified in RFC2553bis)

Which as far as I can tell shouldn't touch the IPV4 stack. I expected to find this sysctl check under net/ipv4 but grep can only find the checks in net/ipv6. Any ideas?

Sorting in awk

I became interested in playing around with simple sorting algorithms and learning awk at the same time. Here is a quick roundup of the first three.

$ bash make_stats.sh
Doing 10 rounds of bubble_sort.awk with a dataset of 100 ints
Average real time in seconds: 0.0151

Doing 10 rounds of quick_sort.awk with a dataset of 100 ints
Average real time in seconds: 0.0476

Doing 10 rounds of selection_sort.awk with a dataset of 100 ints
Average real time in seconds: 0.0048

Doing 10 rounds of bubble_sort.awk with a dataset of 500 ints
Average real time in seconds: 0.3663

Doing 10 rounds of quick_sort.awk with a dataset of 500 ints
Average real time in seconds: 0.2443

Doing 10 rounds of selection_sort.awk with a dataset of 500 ints
Average real time in seconds: 0.0795

Doing 10 rounds of bubble_sort.awk with a dataset of 2500 ints
Average real time in seconds: 9.7188

Doing 10 rounds of quick_sort.awk with a dataset of 2500 ints
Average real time in seconds: 0.335

Doing 10 rounds of selection_sort.awk with a dataset of 2500 ints
Average real time in seconds: 2.1556

Divide and conquer rules the roost especially with large datasets.

Selection sort is obviously much faster than bubblesort.

Probable reasons:

1. Selection sort works on progressively smaller arrays with each iteration
2. Comparisons in bubble sort are expensive compared to moving an element to the end of the array
3. My implementation of bubble sort sucks.. (I'll check it again :( )

The make_stats script is in the same repository. It would be nice to update it to graph these stats using gnuplot


Update: Graphing can now be done by graph_performance.sh. It generates a couple of stats files and the graph in tmp. It expects to find gnuplot in your path. Sort size can be changed by editing make_stats.sh directly.