Saturday, January 31, 2009

Searching indexes on a maemo device: a customized solution

In a previous post I had a video showing one of the libferris inverted file metadata index plugins on maemo. Unfortunately that implementation was designed for a desktop machine, meaning for many many more files, slow disk head seeks, blazingly fast CPU(s).

While these videos are not as snazzy as some others, I make them so folks can get an idea of the real performance of the software. Saying its "acceptably fast" or takes less than a second is all well and good, but seeing the snail or rabbit move gives an immediate gut feeling if its "fast enough".

The new maemo custom designed metadata architecture uses the mmap() design. I always have my reservations about mmap() because it encourages data structure and algo choices that are directed at an in-memory world. That is all great if you can cache the entire memory mapped file in main memory, but often leads to kittens crying when there isn't enough RAM for that. For maemo with 128mb total RAM this is also an issue, but with the much faster disk seeks of flash storage the relatively poor data clustering of mmap()ed designs is a bit less important for performance. But of course, data clustering and physical layout is always interesting when playing the indexing game.


libferris maemo audio search by regex on URL from Ben Martin on Vimeo.

Shown in the video above is a search using the new "custom mobile device" libferris metadata index. As I continue to type a regular expression to match against the URL, libferris gives some search results on each character entered. Note that this is against an index with over 10,000 URLs in it. This index format will be available in libferris 1.2.7+. The index format sports a probabilistic regular expression prefilter for URL matching. This means that the results of the prefilter might include some false positives, but anything the filter drops out is definitely not a match. You have to run the regex itself on all results of the prefilter to drop out the false positives. The prefilter can drop the number of times a regular expression is evaluated down to less than 100 in 10,000 URLs given only a 3-4 character regex. This helps out oodles when you want to run raw regex searches on big (for a portable device) indexes and you want your results asap.

An unfortunate current side effect of the mmap() design is that the index is architecture dependant. Mainly because some secondary offset-pointer information is 64 or 32 bit width dependant, so its a matter of tracking those peskies down and clamping them to a fixed width. To get around that for now, I indexed the 10,000 odd audio files over NFS from an n810.

Some information for those looking to play, if you are using boost to memory map, you may well discover that atomic_cas32() calls __sync_val_compare_and_swap() which is not actually available on the maemo device (for me). This is with a modified scratchbox using gcc version 4.2.1.
I'm not sure if there is an accepted cas et al library for maemo/armel. I leave the hacks for __sync_val_compare_and_swap() to the reader and their accepted level of concurrency control risk.

Thursday, January 29, 2009

Searching for audio files on an NFS share from maemo


Searching for audio files on an NFS share from maemo from Ben Martin on Vimeo.

The n810 only has one memory slot. With an 8gb card in there you might fit 1,000 ogg files onto your storage. That was quite boaring, so I instead indexed an NFS share that is over 10x larger ;) I'm using one of the libferris inverted file backends for the index, which is more targeted at the desktop machine assumptions of having a faster CPU and expensive disk head seeks. Needless to say, I'm hacking on a custom index implementation for maemo which will be more oriented at a slower CPU with much much less expensive disk seeks for flash based storage.

Note that the time after I run ferris-music-search to when the first message appears on the console "Using index..." is fairly much all wasted in dynamic linking. A major slowdown that I've yet to sweep away for running apps on maemo.

The artist and title info is taken from the ID3 tags in the audio files. Indexing time is roughly 3 to 10 milliseconds per file when performed on the desktop. The inverted file index format is portable from desktop to maemo device. I plan to make the new explicit maemo format portable too, so you can make indexes on powerful machines and rsync them over to the maemo device. Assuming you are indexing stuff that is stored on your file server, not the maemo device.

During the typing for the first search on title, possible completions are shown by taking your input as a substring of the title you seek. This is more effective if you keep it in mind because you can choose just a few keys in a substring of the title. All searches are performed using regex matching on strings, which is much slower than direct equality because of the huge complications it introduces for indexing. But it is interesting, even with modestly 10x the number of files you can cram onto an n810, using nasty slow regex searching, the performance is acceptable for much of the time. There are a few cases that I'll improve, particularly regex searching on whole URLs.

Notice that the name and URL are shown as columns, so you can easily "group by" when you click on the appropriate header. I need to also include the artist, title etc ID3 fields into the results,. Oh, and have the ability to click on a few files and see the whole ID3 and metadata of those files "side-by-side" so you do not have to try to read it from the results list.

So now when I see a CD in the shops, I wont have to wonder how many of those Mozart tracks I have already, I can know for sure :-p

Monday, January 19, 2009

Accelerometers hit Canola2 and PDF viewing

Of course, if a unit comes out with an embedded accelerometer in it then using a "slightly clunky" wiimote will no longer be needed as the source of motion data. I recently added the ability for libsixdof to control closed source applications as well as properly patched open source ones. This was mainly to let Google Earth finally take some advantage of proper sixdof devices, but it works equally well for Canola2 on maemo.


Controlling Canola2 using libsixdof and a wiimote from Ben Martin on Vimeo.

Two big features that libsixdof brings is the ability to configure what happens when the controller is moved on an axis, and how frequently that happens. So, if you don't like your images flicking past at 20 images / second in Canola, you can limit it to whatever / second. In the video, having maximum axis movement will only ever scroll 3 images / second. So when I hold the unit causing a continual next image movement I can still see what is happening and Canola2 does not get overloaded with events.


Flipping pages in a PDF by moving the n810 from Ben Martin on Vimeo.

Again the wiimote is actaully held behind the device. I'm sort of getting the hang of the controlling code etc so that you can use more subtle rotations of the device to issue commands to the running program. This is using the same stuff that the Canola2 video did, I could patch a PDF viewer, but for discrete events like next-page it doesn't really make a huge difference. Panning is the big thing that screams out for patching.

Sunday, January 18, 2009

Like a walk in the park..

A walk through the botanical gardens the other day with a digital camera and I had a nice little harvest of background images. Unfortunately the initial scale and crop of the scaled creature to 800x480 means his head is hidden somewhat under the status icons. But many of the other more generic ones work well for backgrounds. Plus I get the added bonus of having a collection of prescaled 800x480 images for demoing Canola hacks.







Wednesday, January 14, 2009

Didn't your n810 come with an accelerometer?

Shown below is a video of the forthcoming 0.1.0 release of libsixdof with a wiimote. I have hacked up maemo-mapper to have initial support for libsixdof, I'll have to clean up the patch before letting other human eyes see it's nastyness :| I decided to use the C++ sixdof API which means there is a single C++ source file in my build of maemo mapper, it was just faster to get it coded that way. Perhaps I'll convert to the libsixdofc ANSI C API before sending the patch.


Didn't your n810 come with an accelerometer? from Ben Martin on Vimeo.

Although libsixdof supports other 6-degrees of freedom controllers too, getting those controllers to work on maemo is a little more of a challenge. For example, I would love to use the portable spacenavigator usb device with maemo. Even though most folks have the USB cabling to hook up the unit, and it gets detected by the n810 when you have USB in the right mode, getting XInput events from evdev on maemo might be another battle. It is not like that part is trivial on a desktop distro either right now unfortunately. I might end up hacking support for direct /dev/input/foo kernel devices into libsixdof to get around that issue and have "real" 6dof devices working under maemo.

Hello, planet maemo

OK, so now I have relevant posts aggregated onto planet maemo, hi everybody </dr-nick>.

For those who haven't discovered it, I run a personal repository of packages for maemo. If you break your maemo device by using my repository, you get to keep both pieces. I have a few n810 units and of course my primary open source software suite, libferris, is ported to maemo and available in my repository. Libferris is a virtual filesystem which includes rich index and search capabilities. There are many nice choices for index+search for maemo, with Tracker coming out soon in the standard maemo distribution, strigi available for the n810 etc. Of course, I use libferris on maemo for my indexing ;)

My repo also contains a few handy misc packages like unison, sshfs, fuse, and tinc. Anyone notice the hints that I like filesystems? The unison package could be made to have a few less dependencies, but it works well already. I have compiled afuse, obexftp and obexfs for maemo but those are not in my repository yet because I'm having trouble getting the 810 bluetooth to work from the normal obex packages instead of through the osso-gwobex layer. It would be nice to be able to mount a mobile phone's sd card through FUSE on the n810 and share storage a bit more, but I digress.

You'll also notice cwiid and libsixdof added recently to the repository. I have been playing with a wiimote on the desktop and on the n810. The libsixdof on the 810 can read the state of the wiimote OK. The wmgui tool locks the CPU of the n810 at 100% when using the accelerometer mode, so clearly you have to be somewhat smarter about what you update for each event on an embedded device. I have hopes that I can hack maemo mapper to use libsixdof soon and thus be able to control it on an n810 using a wiimote ;) Getting other six degree of freedom controllers to work will be more of a problem on maemo because you need to use a very recent evdev with a patch for some devices.

One of the issues that still plagues libferris on maemo is the lack of prelinking. Starting an application that uses libferris causes the CPU to spend a bunch of time resolving symbols before it can start executing anything. I've enabled hidden symbols, compiled with a later gcc than the scratchbox normally uses and played games to speed things up, but getting close how quick a desktop machine can resolve symbols at application startup has still escaped me. I might end up rsyncing / to nfs:/foo and running prelink on an n810 just to see if/how much that helps things out.

Tuesday, January 13, 2009

Combine: wiimote, Google Earth, libsixdof and Linux

Oh, and a nice seat, and you get another HID to use for moving around. This is using the upcoming 0.1.0 release of libsixdof which has wiimote support. Note that you can also use the spacenavigator true 6dof device. If you are using the later then you'll need evdev 2.1.0 or later, and if you're using 2.1.0 see this bug for a patch to get more than X and Y axis working.

More information to follow, including a video and details on the space navigator and GE.



libsixdof and a wiimote to control Google Earth under Linux from Ben Martin on Vimeo.

Saturday, January 10, 2009

Chinook vs Diablo

While most folks have upgraded to Diablo long, long ago, I fell into the trap of actually using the n810 early on. So I had a nice chinook setup and didn't really want to do the Wintel mantra of reinstalling just to get diablo. But now I've been playing with both, with two n810 devices, because its always more fun with two ;)

So one is running the Chinook from about Feb 2008 and the other RX-44_DIABLO_5.2008.43-7. I thought that wifi felt faster on Diablo, so I did a little measuring. Its quite slap happy but does show some considerable difference, using the same DLink DIR-855 AP for both devices.

On the server:
dd if=/dev/zero of=10mb bs=1024 count=10240

On the tablet:
time wget -Y off http://x/10mb

The results:
chinook:
real 0m29.301s
user 0m1.047s
sys 0m1.828s
350k/s

diablo:
real 0m24.815s
user 0m0.656s
sys 0m1.188s
546k/s

The chinook k/s is quite stable at around 350. On diablo things move around quite a bit in terms of speed. Perhaps this bursty nature works well for browsing making things 'feel' faster too.