My new AWUS036H long-range USB WIFI adapter with 5dB antenna has arrived! Initial tests under linux shows 60 wifi stations from my desk. Now to try getting it running under plan 9.
I’ve now implemented uploading and deletion of pics. It’s now pretty complete:
horizon% cp /tmp/glenda.jpg /n/flickr
horizon% page /n/flickr/glenda.jpg
reading through graphics...
horizon% rm /n/flickr/glenda.jpg
horizon% ls /n/flickr/glenda.jpg
ls: /n/flickr/glenda.jpg: '/n/flickr/glenda.jpg' file not found
Current limitations:
These are pretty minor but I’ll fix them eventually. For now, I can easily copy stuff to flickr, and copy down all my old pics (in large jpeg format) to my playbook.
I have implemented reading and renaming in my flickrfs server. Example session:
horizon% 8.flickrfs
horizon% cd /n/flickr
horizon% page scan0001.jpg
reading through graphics...
horizon% mv scan0001.jpg 2cv.jpg
horizon% ls 2*
2cv.jpg
horizon%
This sets the title of the image (previously scan0001) to 2cv. This is verifiable via the web interface. UTF-8 works fine:
horizon% mv scan0006.jpg 'Sacré Cœur.jpg'
horizon%
with the result here.
One of the web services I use reasonably frequently is flickr where I like to show my amature photos. Up until now I’ve just been using the web interface to upload my images. It is however really slow and I hate all the clicking, so I thought a 9p fileserver for flickr would be useful for me. Also, I’d like to be able to sync my playbook with flickr and having both mounted would make this much easier (rsync for example).
So I started writing one and I finally got a basic skeleton together. The auth dance took me a while to work out (I’m not experienced with web apps) but I finally got there. The fileserver is written for plan 9 and I use webfs(4) to communicate with flickr and factotum(4) to store authentication tokens.
At the moment all my file server does is list my photos. Here’s an example session:
horizon% 8.flickrfs
horizon% ls /n/flickr
'/n/flickr/Assiette de crudités'
'/n/flickr/Assiette de pêcher'
'/n/flickr/Coffee corner'
'/n/flickr/Confit de Canard'
'/n/flickr/Cuisse de poulet au vin riz avec poireaux'
/n/flickr/Escargots
/n/flickr/Hors-d’œuvre
/n/flickr/IMAG0097
/n/flickr/IMAG0101
/n/flickr/IMG_20090627_0463
/n/flickr/IMG_20090630_0666
...
/n/flickr/small_L9992400_bw
/n/flickr/small_L9992401_bw
/n/flickr/small_L9992403_bw
/n/flickr/small_L9992404_bw
/n/flickr/small_L9992405_bw
/n/flickr/small_L9992411_bw
/n/flickr/small_L9992413_bw
/n/flickr/small_L9992416
/n/flickr/small_L9992420_bw
horizon% ls /n/flickr |wc -l
228
Next up I’ll probably implement renaming so I can give them some better names, they’re admittedly utilitarian. I won’t share the source just yet as it’s extremely underdeveloped. This is my first time writing both a 9p server and a web app, so I’m learning a lot.
After living on local solar time for a couple of days I can say that it’s much better than the ridiculous daylight saving time. As the sun rises at the proper time (around 6am) it is much easier to wake up and get going. Another (side) benefit is that public transport is less crowded as peak hour is naturally avoided.
However, catching trains is more difficult as it requires much more mental arithmetic. I therefore decided that what I need is a little program to just tell me when the next train comes in minutes and then I can easily work out when I should leave. Sounds simple, and you’d think this would already exist, but the SNCF/Transilien website gives absolute times for the next train not relative. I also feel using a web browser is too cumbersome. I thus wrote a little shell script to tell me when the next trains to/from Paris/Évry come.
Here’s some examples, first the direction Paris to Évry-Courcouronnes:
term% rer-d
BIPE: 3m
BIPE: 18m
term%
and from Évry-Courcouronnes to Paris:
term% rer-d -t
MIPE: 4m
MIPE: 18m
MIPE: 34m
MIPE: 48m
MIPE: 63m
MIPE: 78m
term%
The shell script is effectively a simple awk script that scrapes the transilien wap website for the information. Luckily for me, the website also contains the current time to calculate the deltas (awk has no time functions). Here’s the script in all it’s simplicity:
Today we shifted to daylight saving time and I lost 1 hour of sleep. I didn’t notice for a while as most of my clocks correct automatically, and when I finally noticed I was disappointed. I don’t like daylight saving time as I feel it’s disruptive and does not lead to the purported energy saving benefit. Furthermore, I already think Paris is offset too far from local mean time, given that we have a longitude of only 2°2′ yet we are in the UTC-1 timezone.
I rapidly came to the conclusion that what I really wanted was to live on local solar time and not some artificial construction. To this end I wrote a small program to calculate the current local solar time given a longitudinal position, the date and Greenwich mean time. Of course the latter two are pulled automatically from the system clock, so it needs to be in sync with Greenwich (easy enough with timesync(8)).
The program works by first calculating local mean time and then correcting this using the equation of time to local solar time. Local mean time is easy to calculate as it works out to just a 4 minute difference for each degree (longitude). Calculating the equation of time is more tricky, but there are many available approximations. I chose to use the approximation given in wikipedia, but another is implemented (Woolf 1968) but commented out. Basically, the equation of time corrects for two major components: the eccentricity of the Earth’s orbit and the obliquity of the ecliptic.
My code works on both Plan 9 and Plan 9 Port. I now have the Plan 9 Port version loaded into my wmii status bar for local solar time in Paris and Melbourne. As of this writing, the local solar time in Paris is 20:08 while the UTC+2 (dst) is 22:05.
Just for fun I added a flag (-x) to print the local solar time in hexadecimal instead. In this case, it prints out the local solar time rescaled and formatted to the hexclock style. The current local solar time as of this writing in hex is D_81_8.
I’ve just learnt postscript and thought I’d amuse mysef by trying to write some quines. Here’s one console quine:
{(pstack exec) =}
pstack exec
and one using the graphical device:
<< /PageSize [5000 20] /Orientation 0 >> setpagedevice /Courier
findfont 18 scalefont setfont 0 4 moveto /l {( ) dup 0 40 put
show} def /r {( ) dup 0 41 put show} def /quine {dup show l
show r ( quine showpage) show} def (<< /PageSize [5000 20]
/Orientation 0 >> setpagedevice /Courier findfont 18 scalefont
setfont 0 4 moveto /l {( ) dup 0 40 put show} def /r {( ) dup
0 41 put show} def /quine {dup show l show r ( quine showpage)
show} def ) quine showpage
The latter is by far the ugliest quine I’ve ever seen, but at least the former is elegent.
A well known problem in computer science is how to do matrix multiplication. Usually, matrices are stored in memory in either row-major or column-major format, i.e., matrices are stored sequentially in either row order or column order. The conventions vary a little, for example Fortran uses column-major and C uses row-major, but the differences between the two are mostly notational and they both share the same disadvantage: either column or row spatial locality is minimised in one dimension but not both.
This has no impact if the only matrix operations used access the elements in one order only, in fact it’s optimal, but it is a problem for operations that stride across both dimensions simultaneously such as matrix multiplication done in the naïve way to calculate C = AB:
for i in 1:rows(A)
for j in 1:cols(B)
for k in 1:cols(A)
C[i, j] += A[i, k] * B[k, j]
For small matrices this works fine; the three matrices fit into the processor cache so the pipeline can be kept full. The problem is for sufficiently large matrices, each iteration causes a cache miss which slows things down considerably.
The traditional method for addressing this problem is blocking. Instead of calculating the matrix C naïvely as above by iterating through entire rows and columns, you calculate it in blocks. This is the approach taken by BLAS. Unfortunately, the optimal block sizes are very processor dependent as the cache architecture varies quite considerably between processors, so it must be tuned very carefully for each machine to achieve the best performance.
A more radical and interesting idea is to change the storage order of the matrix elements. That is, instead of optimising in one dimension only, the elements are stored to preserve spatial locality in both dimensions. This is done by storing elements along a space filling curve. Indeed, if a fractal space filling curve is chosen then matrix multiplication becomes cache oblivious, that is it uses the cache well at all levels.
In particular, the Hilbert fractal space filling curve has been proposed recently as a matrix storage order, in particular as a sparse matrix storage order (Hasse et al. 2007). I therefore thought I’d have a quick play with it and hacked up the following primitive benchmark.
The implementation stores matrices in a dense array indexed using the Hilbert curve. Upon matrix creation, I calculate two arrays for iterating through a matrix by rows or columns (these are the Δi and Δj arrays in the matrix structure). These arrays contain an offset to the next element, so iterating through the elements is as simple as adding the offset to the current pointer. The functions for converting ordinary indices to Hilbert index were copied from the Wikipedia article.
Benchmarking was done by counting elapsed CPU cycles with increasing matrix size. All benchmarking was done on an Intel Atom machine running the Plan 9 operating system. I timed matrix creation (for the Hilbert storage order) as the time it takes to calculate the offset arrays is important.
Here’s the results. The x-axis is the matrix size and the y-axis the clock cycles. The red plot shows the cycles required to create the Hilbert matrix array (and delta arrays), the blue shows the naïve matrix product, in green is the cycles for Hilbert ordering, and finally in purple is the combined init + matrix product for Hilbert ordering. Clearly the Hilbert ordering is much better than the naïve method, though the scale chosen makes it look particularly bad. Here is is with a log axis:
As expected, the naïve method is faster for small matrices that fit nicely in the cache, but the Hilbert ordering is much better for larger matrices where it doesn’t. All in all it’s a pretty nice speed up (4.7×) for pretty minimal coding effort and zero tuning. Bear in mind also that my code is just hacked together with no optimisation.
So I quite like it, it was easy and has appreciable benefit. However, the conversion between indexing systems is a bit heavy. In some ways, Morton ordering is more appealing because the translation is much faster, requiring only bit interleaving by simple bit operations (Wise et al. 2001) replacing the delta arrays I used to traverse by row/col. Also, addressing a Morton ordered matrix as a quadtree is actually quite easy (Wise 2000) so implementing smarter matrix multiplication algorithms such as Strassen’s algorithm is simpler.
There is also an interesting article (Bader 2006) that uses a Pino curve instead of either Morton or Hilbert. They propose an algorithm that does matrix multiplication without any jumps at all. I haven’t had the time to read the article in more detail.
The dense storage is wasteful. For square matrices of power 2 it is optimal, for anything otherwise it wastes space. A lot of space if it’s a thin matrix.
To install inferno on android you need a rooted phone. Since the inferno guys use cyanogenmod I thought I’d load that up and go from there. In any case, I was running Frozen Yoghurt and not Ginger Bread so my phone was out on date anyway.
I found some overly complicated instructions on the cyanogenmod wiki that provided a starting point. The process is much simpler if you load up the zip files and then run Revolutionary to install and launch ClockworkMod. Of course all this voids the warranty. Here’s what I did:
That was it, my phone is now running Cyanogenmod. First impressions are pretty good, it feels snappier despite all the useless animations (which can be disabled). There’s also a nice guide outlining all the features.
It’s been a while since my last blog post, time to get back into it with something small. Over the weekend there was a lot of traffic on the 9fans mailing list about a port of Inferno to android. The port replaces the whole Java machinery instead of running on top of it. The video demonstration looks quite snappy, I’m tempted to install it on my HTC desire and have a play.
