## Particle Filter in F#

Since my last blog post, I’ve been reading the Probabilistic Robotics book. I coded up a Kalman Filter in C++ (https://github.com/taumuon/Kalman-Filter).

It’s been a while since I’d coded up any F#, so I converted a particle filter over from Python. The code is from the online MOOC Artificial Intelligence for Robotics from Udacity.

The idea is to perform robot localisation, by creating a set of particles randomly over the entire state space. On a noisy sensor reading, the probability of that sensor reading having being made for each particle is calculated. Then, all particles undergo a weighted resampling (weighted by the measurement probability).

In this example, the sensor reading is the distance to four beacons at a known position in space. The same algorithm is used in Simultaneous Location and Mapping (SLAM) applications, where the sensor readings could be sonar, radar, visual etc.

The F# code is nice and compact at only 94 lines. The project is available at https://github.com/taumuon/Particle-Filter-FSharp

## .NET SIMD to solve Burgers’ equation

I’m enrolled on the mooc Practical Numerical Methods in Python, and module 2 has covered the Burgers’ Equation. This is a great course by the way, and it’s not too late to join up!

I am impressed with the productivity of Python. ipython notebooks, SymPy, plotting etc. are all great and I feel that .NET could benefit from a similar ecosystem.

That said, I’ve been itching to play with the new .NET SIMD support and this seemed to be a suitable example.

The Python notebook demonstrated how using Python’s array notation to solve the Burgers’ equation using finite difference resulted in a 9 fold speed increase, on  my machine taking 25ms instead of 200ms.

I translated the code into C#, and it completed in 2ms, so I immediately was impressed (not surprised though – an interpreted versus (JIT) compiled language…). This wasn’t going to tell me much about SSE improvements though, so I increased the number of spatial samples a hundred fold, and the number of timesteps by 10.

The time was then increased to 2580ms.

Installing .NET 4.5.2 and using RyuJIT CTP4 to compile and run, the running time reduced to 1880ms. RyuJIT can’t arrive fast enough!

I then implemented array swappping, instead of continually creating and copying arrays, to see if it would reduce pressure on the GC (Calculate2 in the gist), but it had no significant difference.

I then pulled the calculation of (nu * dt / dx) into a variable (Calculation3())

This resulted in a calculation time of 230ms.

Then, I felt it was time to implement SIMD. The documentation is a bit scarce, but it wasn’t too tricky to figure out. My machine has 128bit SSE registers, so it can add two doubles (64 bit) in a single operation.

Running this resulted in a calculation time of 90ms, so slightly greater than 2x speedup. I’m not sure whether it was able to make further optimisations based on the changed structure of the code, but this is a great win. This is implemented in Calculation4() in the gist.

The gist is available here: https://gist.github.com/taumuon/5d4db567c57f9846971d

## ViewGene now has mapping

The newly-released version of my genealogy/family tree Windows 8 app now has Bing Maps integration, which allows the migration paths of all ancestors to be plotted.

I wanted to see visually how my ancestors moved, after researching how my ancestors moved from villages in the 17th century into towns, and then larger towns.

I’d love to see anyone else’s migration paths!

The below is just a made up sample – I’ll share my map after sanitising the data.

Try it in the Windows Store.

## ViewGene

This blog has been quiet for a while, but I’ve been busy working on a Windows Store genealogy application, ViewGene.

This is quite a niche application, but it was written to cope with a couple of use cases which are missing from other family tree websites and applications – it’s useful to have it open in conjunction with your favourite family tree software or website.

The first problem is that many of the family tree websites, when showing the whole tree (pedigree chart) of ancestors, compress the tree to make the best use of screen real estate. This is fine to save paper, but it does make it very difficult, when navigating the tree, to know what the generation is of any ancestor on the screen.

ViewGene ensures that ancestors of any generation all appear at the same vertical level – this makes it easy to see which branches of the tree need more investigation. This view wouldn’t necessarily work well when printed out, but touch-based pan and zoom do mean that it’s easy to zoom out to see the ‘shape’ of the tree, and to zoom in to see the individual details, meaning that it works for interactively investigating the data.

The second use-case is to validate and see the lifelines of the ancestors. Many of the family tree websites allow free-form entry of dates. This means that it is easy to mistype and enter a date of the wrong century, or to enter semantically incorrect dates such as a child born before the father. The Timeline Fan chart allows for some of these problems to be easily seen. The chart also allows the user to see, for example, which ancestors were alive on a given census year.

The current release includes very limited validation, to check that dates match allowable GEDCOM formats, but does not check for semantically incorrect dates. Also, there is very basic date inference for missing dates. If I devote any more time to the application, I’ll want to improve both of these points – it should be possible to validate that children were conceived whilst both parents were alive, and that siblings can’t have been born in the same gestation period etc.

## Windows Store application observations

The chart functionality is quite generic, and would work well on any touch-screen platform (such as iOS), much of the development effort was spent in building an application following Windows Store idioms.

The first was to ensure that the application works when snapped (though this could do with further improvement). The second was to use semantic zoom, which definitely makes it easier to navigate through a large number of individuals in the GEDCOM file). Adding a very large number of individuals to the GridView results in Invalid Quota exceptions being thrown. Even if this weren’t the case, there would be a usability issue in navigating through so many individuals. To fix this, if there are a large number of individuals in the GEDCOM file the application adds a further level of navigation through the first letter of the surname.

It would be quite easy to add images to the application (such as pictures of ancestors, or scans or pdfs of documentation), but it is quite tricky in a Windows Store application – the GEDCOM file contains paths to images, but it is not possible from a Windows Store application to open files other than via the open file dialog. It may be possible to work around that by instead presenting an open folder dialog (which would allow access to all files and sub-folders within that folder) and then allowing the user to choose the GEDCOM file from a list, but that definitely feels clunky.

The Pedigree Chart is implemented as an ItemsControl, populated with either Boxes or Lines, with an ItemsTemplateSelector to distinguish between them. It works well, and there are no obvious performance issues, but the ItemsControl does crash if too many items are added, so the number of ancestors are limited to 1000.

The timeline fan is implemented as C++/CX WinRT component, deriving from SurfaceImageSource, with all drawing being performed in Direct2D. If I get time to invest in this, I want to switch out to a VirtualSurfaceImageSource, so that the amount of information presented is customised to the zoom level on the screen.

## Non Windows Store issues

There are a few issues not related to a Windows Store application.

The application currently does not have editing – the GEDCOM format is too flaky to be a reliable interchange format; it does not round-trip without the possibility of corrupting the user’s information. Ideally, the application would allow connecting to a website to obtain the user’s family tree information, but ancestry.com does not provide a user-accessible API. Geni.com does, and if I get time I intend to investigate that.

It is also trickier than it needs to be to implement mapping – it looks fairly easy to integrate with Bing maps, but the problem is that location data in the GEDCOM file doesn’t necessarily match up with the required data for plotting points on the map. It is possible to ask the data to enter that information, but then the application should maintain it. This isn’t too much of a problem, but it should be maintained per GEDCOM file, and to allow the user to re-import updated GEDCOM files would rely on GEDCOM merging.

The GEDCOM parser is written in C#, mostly as a GoF state machine, with some functional elements. When I originally started coding this up, I intended to start by creating a clunky procedural looking parser (which maintains the state with many flags), then show how an OO GoF pattern was nicer, then show how a F# implementation is nicer still. If I get time I still intend to create a F# version of the parser.

Speaking of F#, the layout logic for the timeline fan is implemented in a functional way, but would be nicer in F# – the problem is that it then needs to communicate with the WinRT component to do the drawing. F# can’t directly interop with WinRT, so it would be necessary to create a C# wrapper or consumer of the F# library just for this – and it seems overkill.

Overall, developing a Windows Store app is fairly easy if you have Silverlight or WPF skills. There are quite a number of features I want to add to the application, but how much time I’m going to dedicate to it depends on feedback or download numbers of the current version of the app.

Pašticada is a beef pot roast, requiring many hours of preparation, so is usually served at Christmas or Easter.

This recipe quite closely follows the recipe here.

The beef cut in Croatian recipes is usually described as top round, but butchers in the UK who were shown the pictures from Croatian recipe books say that the cut of beef to get is Silverside:

Carefully trim off the white fat that the butchers leave on. Spike the beef all around with a knife, and insert pieces of garlic and pancetta:

Marinate in a bowl of red wine vinegar. Cover in a fridge, and leave to marinate for at least overnight, and ideally 24 hours, turning occasionally.

After marinating, dry off the beef, and fry off in a mixture of lard and olive oil until brown on each side. Remove from the heat, and fry off a kilo of finely chopped onions and some pancetta in the same oil. Once softened, return the beef along with chopped carrots, celery, parsley, a handful of dried prunes, a whole bulb of garlic, a few cloves, and a few peppercorns.

After half an hour, add some beef stock, half a bottle or so of full bodied red wine, a spoon of fruit jam, and some tomato concentrate. Leave to cook on a low heat for two to three hours.

Once the meat is cooked, remove from the pan and slice:

Remove the juice, and put through a colander and then push through a fine sieve.

You don’t want to liquidise the mixture, as it will end up thicker and bittier than desired, instead of a really rich gravy. This is what’s left after sieving:

Now, return the beef slices and gravy back to the pan and cook for another hour.

Serve with potato gnocchi  and a dusting of parmesan cheese:

## Francuska Salata

In Croatia, Christmas dinner is a multi-course extravaganza. First off, a beef soup is served, followed by starters, then a pot roast, followed by roast veal and potatoes, and then a dessert.

The starter is typically a platter of cured meats and cheeses, bread, and Francuska Salata. Francuska Salata literally translates as French Salad, but actually translates as Olivier Salad. It is a dangerous move to over-fill on starters as it will be a struggle to eat later courses.

To make Francuska Salata, cook carrots and potatoes and dice finely.

Mix with peas, chopped boiled egg, finely chopped gherkins, salt, pepper, lemon juice and mayonnaise.

Serve with bread, meat and cheeses, but don’t eat too much!

## Bakalar

Similar to fritule, Bakalar is eaten in Croatia on days of fast; especially on Good Friday and Christmas Eve.

Bakalar is known in the UK as salt cod, the cod is salted and dried for preservation. In Croatia, they sell it in the supermarkets on the shelves as it is fully dried out (see here for an example). In the UK salt cod can be bought from Italian Delicatessens, but tends to be not quite as dried out.

The bakalar needs soaking for two to three days in water to rehydrate and remove the salt. Change the water frequently, and keep covered in a fridge.

Remove as much of the skin and bones as you can, then place the code in a saucepan and bring to the boil. Once it is soft enough, remove the flesh from the bones. Remove from the pan, but retain the liquid.

Peel a few potatoes, slice, and alternate layers of potato and cod in the saucepan.

When cooked, add plenty of good extra virgin olive oil, enough to make even Jamie Oliver embarrassed. The olive oil is one of the key ingredients in this dish, and needs to be good quality – look for a good green colour and fresh smell. We’re lucky to get home-pressed olive oil from Marijana’s relatives in Croatia.

Don’t even think of mashing the mixture. In Croatia, the tradition is to firmly grasp the lid of the saucepan and shake vigorously; this breaks up the potatoes and mixes in the cod.

Add a generous handful of parsley and four to five clothes of finely chopped garlic, and mix well together.

The starch released from the potato, and the oil give a creamy consistency, and this is truly delicious. Season to taste, and enjoy with a glass of good white wine.

## Fritule

Fritule are similar to mini doughnuts. In Croatia, it is traditional to eat fritule on days of fast, such as Good Friday or Christmas Eve.

Soak a handful of raisins in rum. Beat two eggs, add 50g of vanilla sugar and beat in 200g of yogurt. Then, mix in 300g of self-raising flour and then the rum and raisins. You can also add other flavours, such as cinnamon or lemon rind.

Heat a pan of oil, to a medium-high heat; you want the fritule to cook fully throughout before the outer exterior gets too dark.

Turn once while cooking so that each side is evenly cooked, before removing with a slotted spoon and leaving to dry on kitchen towel. Finish by dusting with icing sugar.

Enjoy!

## Njoki

It’s tradition in Croatia to eat Pašticada sa domaćim njokama (pot roast with home made potato gnocchi), and the njoki/gnocchi can be made in advance. They’re not at all tricky to make, and are delicious covered in thick rich gravy.

Take some fluffy potatoes (I’ve got Maris Piper) and place them into a pan of cold salted water, and bring to the boil.

Once boiled, the skins of the potatoes turn really soft, and can be peeled off. Unless you’ve got asbestos fingers you might find it easier to use a sharp knife.

Now, prepare the work surface with flour and rice the potatoes. Ricing instead of mashing helps the moisture in the potatoes evaporate. If you think the potatoes are soggy you could pop them into an oven for a couple of minutes after peeling. We used strong bread flour – apparently the protein in the flour helps to soak up moisture.

Make a well in the potatoes and add an egg, some salt, and a generous knob of butter.

Bring all the ingredients together to form a dough, but don’t over-work them. You’re not baking bread, so definitely don’t go kneading it!

Roll the dough into even portions, and then take each portion and roll it into long sausages. Chop each sausage evenly.

Some recipes recommend pressing each gnocchi against a fork, but rolling out against a grater adds a better looking finish, and helps the gnocchi soak in and hold a generous amount of the rich gravy.

Press the gnocchi flat against the grater, and push downwards so that it flattens out against the grater. Then, roll it around to form the gnocchi shape.

## Metro Bullet source code

I’ve updated the demo that shows the Bullet Physics Engine in a DirectX 11 Metro application to build in the Release Preview drop of Visual Studio (original blog post: http://www.taumuon.co.uk/2012/04/bullet-physics-and-directx-11-on-windows-8-metro.html ).

The code needs some tweaks – I need to change the manifest, and change some stuff over to Platform::Agile, but it builds and runs so I thought I’d get it out there.

The code is available at: https://github.com/taumuon/Metro-Bullet