Taumuon Jabuka

Charting Performance

2012-01-25T13:12:00.001-08:00

I wasn’t going to blog about performance until a later post, but there was a performance issue I wanted to tackle before discussing some other things.

The frame rate sometimes seemed to be as expected, but sometimes slow, and the application was quite unresponsive when handling the Stop button command.

To help nail this down I created a Buffer Frame Rate performance counter, so that I monitor it along with another couple of metrics (I chose to see the count of gen1 and gen2 garbage collections, along with the % time in GC, and % processor time).

The framerate average isn’t bad, but the frame rate is not consistent; it regularly drops below 10 frames per second. This post will discuss optimising the performance of the application to keep the frame rate steady and ensure that the app is responsive.

Performance increases should generally focus on reducing unnecessary work in the whole application, and not micro-optimisations. In this case, it’s realising that the top chart is drawing at 40 frames per second (a buffer of 1000 data points into a 40KHz source), whereas the bottom chart is updating at 400 frames per second (sampling the data to 100 points, and updating the chart on each of those sample points).

However, as there are other types of charts I want to produce it’s worth investigating where the time is spent.

First off, I tried turning off anti-aliasing, and moving over to the d3future project (http://d3future.codeplex.com ), to see if that made any performance difference, but the performance was pretty similar, with the CPU pegged at 100%. A further run generated this interesting trace:

The frame count starts initially high, but after a while performance drops off dramatically, which is followed by some long spikes in the % Time in GC. The drop-off maybe seems to correspond with one of the gen 2 collections. This situation wasn’t so reproducible that I could catch it under a profiler.

My next step was to profile to see where the application was spending its time, just using the Visual Studio profiler. The application’s hot path was in the D3 LineChart’s UpdateCore method, where it was updating the chart’s Bounds using data from the EnumerableDataSource –it was iterating over the whole collection to find the x and y min and max values (to fit the chart to the data area).

It seems unnecessary to iterate over the whole data source to get the minimum and maximum x values – for a linear chart (i.e. not a scatter chart) it would be expected that the first point is at the minimum x value and the last point the maximum.

I created a chart derived from LineChart where I could instead pass in a List of points for the datasource – this means that I could get the last point without enumerating the whole collection, allowing the min and max x values to be quickly found. For the y values, I happen to want the chart to be a fixed axis and not scale to fit the data (instead scaled by a user-configurable gain factor), so there was no need at all to iterate over the collection.

The chart looked like this after those changes:

The frame rate is pretty consistent now. The gen 1 allocations are still occurring at a rate of 200 per minute, but the application is now responsive to the stop click, stopping immediately.

Profiling with memory allocations turned on showed that the types with most instances was System.Byte[] with 32% of the instances allocated in the profiling period.

ConvertByteArrayToFloatArray() previously looked like this:

And after changing this to not use LINQ:

Gives the following:

Performance is pretty similar to previous, but the gen 1 collections are occurring at a slightly lower rate. Now, profiling tells me that the types with most instances allocated is pretty much split between System.Action, System.Object, and System.Reactive.Disposables.SingleAssignmentDisposable.

Profiling at this point identifies the majority of the work now being in LineGraph.UpdateCore() where its transforming all points from their data coordinates into screen coordinates.

The transformation of coordinates for many points is embarrassingly parallel (think GPGPU). Potentially, the GPU could be put to use by simply drawing the points untransformed, adding a transformation onto the drawing context.

Further performance increases could be done for the sliding window chart: A sliding window chart redisplays the same points again and again, as they move left along the x axis. It essentially transforms the same point many times into the new viewport. Doing a transform to move an existing point to the left could be more efficient than transforming again from data to screen coordinates.

This blog so far has looked at some micro-optimisations focussing on identifying areas where work can be reduced. As I said in the beginning, if I wasn’t so interested in optimising for future requirements, I’d simply ensure that I was doing less drawing straight away.

Anyway, the sliding observable can be change to only take every 10th windowed set of values, by introducing another Sample() on the result of the WindowWithCount():

There isn’t actually that much difference in real-world performance.

The rate of gen 1 collections is lower still than previous, but the profiler shows that app is still spending the majority of its time in drawing the charts. Surprisingly the CPU usage doesn’t seem to have dropped much, although in the profiler the time can now be seen to be split between the drawing of the two charts, instead of dominated by the drawing of the sliding window chart.

The micro-optimisations were still worth investigating, as I have charts in mind that will draw multiple traces simultaneously.

Oscilloscope using RX and C# Async CTP

2012-01-18T12:10:00.001-08:00

In my last blog post I described the implementation of a simple ‘oscilloscope app’ in F#, as I wanted to see how the code would be structured using only F# idioms (http://taumuon-jabuka.blogspot.com/2012/01/visualising-sound.html )

My natural instinct would have been to implement it using the Reactive Extensions for .NET (RX Framework), but I first wanted to investigate a pure F# solution. This post describes an alternate RX implementation.

Similar to my last post, I’ll describe the code inside-out.

Creating the Observable

This code returns an IObservable with a float array payload, representing each read from the CaptureBuffer. The implementation could have internally started a dedicated Thread from which to push out values, but instead I’m using the new C# 5 async functionality (using the Async CTP Update 3), so that my code looks pretty similar to the previous F# example.

The observable takes a CancellationToken, whose IsCancellationRequested is set to true once all subscriptions to the observable have been disposed. The CompositeDisposable returned out from the lambda is also disposed of at that point.

The code loops while its CancellationToken has not been cancelled, asynchronously awaiting for one of the WaitHandles to be set, and then it reads from the buffer. The value is pushed out to subscribers in the OnNext.

The ConvertByteArrayToFloatArray() is trivial:

Subscriptions to the observable

First off, the float array returned from the observable is decomposed into the individual values, using a SelectMany, as sampling, buffering and windowing operations all operate on a stream of floats. Then, the observable is published to an IConnectableObservable. The microphone access returns a Cold observable, meaning that each subscriber to it would end up creating their own microphone access. This would work (the CaptureBuffer doesn’t prevent this), but the connectable observable means that instead all clients share the same observable, and ensures that they all see the same values (so that the traces on the two charts are in sync).

The RefCount() means that when all subscriptions to the observable IConnectableObservable variable have been disposed of then the subscription to the underlying observable will also be disposed.

The top ‘oscilloscope’ trace is a simple Observable.Buffer() over the data stream. There is no need to ObserveOn the dispatcher thread as the subscription occurs on the UI thread. Using RX, it would be easy to schedule various parts of the work onto different threads, but I’ll discuss this in a later article (I want to keep everything on the UI thread for now to compare performance with the single threaded F# implementation).

All subscriptions are added to a CompositeDisposable member in the ViewModel – the Stop button’s command implementation disposes of this, which causes all subscriptions to be disposed of, and so the microphone access loop to be terminated via its CancellationToken.

The windowing operation simply samples every 100 data points, and from those sampled data points takes a sliding window of 1000 values to display. The windowCount variable is closed over to allow the y axis to be continually updated.

The Sample operator is simple, but not particularly efficient – it takes a buffer (i.e a non-overlapping window) of count values, and then takes the last value in the buffer.

The WindowWithCount operator is the same one I discussed at http://taumuon-jabuka.blogspot.com/2011/07/rx-framework-performance-awareness.html (with implementation grabbed from http://social.msdn.microsoft.com/Forums/en-US/rx/thread/37428f58-f241-45b3-a878-c1627deb9ac4#bcdc7b79-bbde-4145-88e4-583685285682 )

And as I also talked about in that post, the RX guidelines recommend implementing an operator in terms of existing operator. There’s only one problem in this case, it’s quite slow, (I’ll get quantitative figures on this in a future blog post discussing performance of all approaches).

The following is faster (again, I know more specific figures are needed):

Comparing implementations

For me, the RX solution is cleaner than the F# solution, and easier to follow. I did implement my F# solution in quite an imperative way though, and should have perhaps used AsyncSeq or mailbox processors, but as reading from the microphone is a push-based activity, none of those solutions would be as clean as RX (of course I haven’t covered using RX in F#). The F# version is much faster, and I’ll take a big more of a dig into performance in an upcoming blog post.

Visualising Sound

2012-01-10T14:38:00.001-08:00

This is the first in a series of blog posts about visualising sound, in a similar way to an oscilloscope. The geek in me thought it’d be a fun thing to do, as well investigate different technological approaches to implementing the app (interesting as it’s a real-time performant app).

An oscilloscope has a single screen, which refreshes on a given time period, displaying a number of traces. The user can control that time period, as well as the gain (the y axis scale).

The top graph is essentially the same view as an oscilloscope containing a single trace, and a fixed time period (further blog posts may investigate varying time periods).

The bottom graph is a sliding window with a longer time period – this is the advantage of implementing an oscilloscope in code, we can create charts that aren’t really feasible in a classic CRT oscilloscope.

This series of blog posts will investigate implementing this screen using F# idioms, as well as using the Reactive Extension for .NET (RX Framework), and TPL Dataflow.

There are further things that could be implemented in future blog posts which may be interesting to see how the varying approaches look like:

· Trigger, or Trigger and hold: Only refresh the oscilloscope view once a certain trigger level has been reached. This is interesting as may want to include a certain number of immediately prior to the point where the trigger was set.

· Log many traces.

· Spectrum analyser/FFT.

· Digital filtering.

· Comparing traces, or more complicated math channels.

· Heatmap.

· Adjustable time offset (delay) – useful on the oscilloscope view to centre a waveform on the screen, or for when comparing two or more channels output.

F# Implementation

This blog post covers an F# implementation of the microphone, using asynchronous workflows. The graphing is being done by a nightly build download of Dynamic Data Display (D3). I’m really impressed with the performance, but it is quite difficult to customise.

The low-latency microphone code is from this article on gamedev (http://www.gamedev.net/topic/586706-slimdx-directsound-capture-microphone-stream-with-low-latency-example/).

The implementation of this is pretty simple; I’ll start from the detail out.

The inner loop of the program is an asynchronous workflow that reads from the buffer and returns a sequence:

Note the slightly-strange looking code:

let task = System.Threading.Tasks.Task<int>.Factory.StartNew(fun () -> WaitHandle.WaitAny(waitHandles))

F# has an Async.AwaitWaitHandle() method, which unfortunately only waits on a single handle. We want to wait on both handles so that we get notified when the buffer is full every 4096 instead of every 8192 bytes. With 4 bytes per sample, and a sample rate off 44KHz, this is equivalent to getting notified at an approximate rate of 40 times per second instead of 20 times per second.

I could have implemented Async.AwaitAnyWaitHandle() taking an array of WaitHandles, but looking at the code in the F# PowerPack, the code was quite complex. So, the code instead creates a new future to do the waiting and let us know which WaitHandle was set (this does mean that we’ve got the minor overhead of scheduling a new task to run on the task pool).

The Async.StartImmediate method ensures that the ProcessStream call is marshalled back onto the UI thread. It may be worth in the future looking at doing more of the data processing on a dedicated thread, leaving the UI thread free for drawing and user input.

The convertByteArrayToSequence is simple, it just iterates over the buffer in 4 byte chunks, and converts the values to floats, which it yields in the sequence:

The ProcessStream method looks like this:

For completeness, this is the Seq.sample module extension:

The nastiest bit of the code in ProcessStream is probably towards the end, where the windowedUnderlyingData is manipulated to ensure that the window only contains 1000 samples. It would be nice to do this in a non-imperative way, using Seq.windowed, but the problem is, is that the sequence we’re operating on is only the result of one buffer read operation, whereas windows etc. should operate over the whole data stream, and the sequences can’t be combined into a single sequence using yield! as they’re all generated asynchronously. Similarly, the buffer takes non-overlapping windows over the input sequence, and without taking a buffer over the whole stream, it may miss samples off the end of the sequence portions. Tomas Petricek has written a library, AsyncSeq, http://tomasp.net/blog/async-sequences.aspx which I may investigate in a later post.

The alternative to this would be to implement mailbox processors, having different agents for the buffering, windowing and sampling operations. I did start investigating this, but didn’t feel happy with them being pull-based (they don’t return data unless asked). I could have set them up to act more like a dataflow network, but it does seem to go against their intended use of managing state between different threads. I may revisit this in a future blog post.

I feel that even though F#’s does have nice features which helped to quickly implement the app, RX would probably be a better fit. I guess I won’t know until I implement it in RX and compare the differences.

Family tree timelines

2011-10-30T11:49:00.000-07:00

As I talked about in my previous post, I created a simple family tree visualisation program to let me know which of my ancestors I have the most interest for.

I also prototyped up a timeline view - in the above image. It's probably pretty obvious that it's a prototype, as there are no labels to identify any of the individuals.

The idea for this came about as genesreunited has a non-validated freeform text field for all entries of dates. There's no way to validate whether this information is valid for GEDCOM export - the GEDCOM spec lets various dates, such as approximate dates, bounded dates, dates within a specific quarter etc. to be specified but obviously the date has to be specified in the correct format.

I wanted to check that all dates were both in the correct format, and actually valid (i.e. check for nonsensical dates such as parents born after their children etc).

The idea behind the colouring is for green to show a GEDCOM format valid date, yellow to specify a missing date (with the date inferred), and red to indicate an invalid date.

The opacity is to indicate the 'confidence' in a date - with a specified date range not being at full opacity. Also, the dates can be inferred using a set of rules (e.g. parents should be at least 12 years older than their children, a child is probably born within a year of his or her baptism, the first child is born within a year of his or her parents marriage etc.). These rules could obviously get quite complicated.

The layout matches pretty much the layout of the ancestor chart, with ancestors being adjacent to each other. I was fussing over this a little bit - I thought it'd be nice for the descendents on the chart to be nearest to each other on the x-axis), but there's no way for this to happen through the tree.

I was feeling pretty happy with this, and thought that it's probably worth putting into the app (with some tweakes such as making the y-axis an adorner layer that adjusts with scale etc), but then I found that there's some software which has a pretty-much identical view to this (I did google around for this before implementing, I obviously didn't google hard enough).

Progeny Genealogy has an identical layout (OK, turned on its side). It even has the same idea of using opacity to indicate what data is estimated (not varying opacity, but even still). I guess that there's only so many ways to solve a problem, but it's still gutting when you think you've had an original idea!

Windows 8 Metro Development Experience

2011-10-29T12:35:00.000-07:00

I’ve been running the Windows 8 developer preview for a few weeks, and thought I’d blog about my experiences in converting a Silverlight app I’ve written into a Metro one. I’ll first describe the app, then my experiences developing it.

The App

The application is a family tree viewing application. It came about as I’ve found a few branches my family tree back to the 1600s (with help hooking up with other people on GenesReunited). It isn’t very friendly if you want to see the whole tree as it shuffles all of the individuals around to minimise the screen real estate, which is good for printing, but not so good to make sense of the tree. I was interested in seeing which of my ancestors I had the most history for, and which I wanted to research next, so I created an app to show ancestors without siblings, and to favour clarity over screen real estate.

(When I started writing this app, there didn’t seem to be any family tree apps which showed the whole family tree. I’ve since found that Gramps uses GraphViz to do exactly that).

The screenshot above shows that Metro apps really don’t much unnecessary chrome. Any infrequently used commands are hidden in the app bar at the bottom of the screen. The next screenshot shows the app at full zoom with the application bar hidden.

Development

Now I’ve laid out the background, I can talk about the development experience, and some of that will include talking about Windows 8. First off, Metro’s UI is a bit toy-ish, but I can see that it will feel slick on a touchscreen (I’ve got a Windows Phone 7 device, and am struck by the similarities). The green is pretty garish thoughout, but I’ve attempted to follow this look in my app.

UI and controls

It doesn’t feel as if Microsoft has paid enough attention to using Metro apps with the mouse and keyboard yet. A case in point is in the zooming in this application – I’ve provided a slider in the search bar, but it’s unclear whether there will be a system-wide gesture mapping to pinch-to-zoom in the release. This was necessary for testing, as even though Visual Studio has a simulator which can be used to simulate gestures, the zoom gesture uses the mousewheel, which my laptop does not have.

The actual conversion was surprisingly simple (they promised that this would be the case on the Build videos), but I’m glad that I didn’t hit any blockers. My ViewModels needed minor changes (which I’ll talk about below), and most of my Xaml just got moved across.

The ScrollViewer now allows zooming and panning, so I was able to use this instead of my own ZoomPanControl. Strangely, the zooming is performed by a method instead of a dependency property (making it easier to animate zooms etc). Also, even though it’s drawing visuals, the zoom seems to take a bitmap at full zoom and simply scale that down (this is speculation on my part, but to my eyes the scaled content looks a lot worse than a WPF version which uses scale transforms). Here’s a WPF version of my app at similar zoom:

The text is almost readable, and the connecting lines aren’t suffering from the ugly aliasing.

There are some further niggles, it seems that the ScrollViewer has a minimum zoom factor of 0.1. Additionally, the slider control, even though it was set with a minimum of 0.05 and maximum of 1, would only display values of 0 and 1 on the popup.

Coding

Now I’ve described some of the structural changes, I can describe some of the coding changes. Most of the changes were pretty trivial in the ViewModel – apart from the use of async. The Silverlight of the app was using the Reactive Framework. Other than reading a couple of articles, I hadn’t gotten into looking into C# 5 async yet, but it was pretty trivial to switch over. Testing it is another matter – I ended up downloading the Async CTP to see their unit testing sample, and found that it was the most complex sample throughout. The Reactive Framework allows you to simply control Virtual time using the scheduler, and I haven’t seen anything so simple or elegant for C# 5 async (though testing Observable.FromAsyncPattern methods are similarly tricky to test, as they don't use the scheduler requested; relying on the underlying IO Completion ports for scheduling the work).

[Edit] I originally blogged that I was concerned that there wouldn't be a version of the Reactive Framework for .NET 4.5/WinRT, following some forum rumours. However, the guys have a .NET 4.5 RX build ready.

Other changes in the code mapped naturally across – the FileDialog now returns an IInputStream, but this has a method AsString() to map across to a .NET stream. The List class has had a few of its methods (such as the Sort overload taking a delegate) removed, annoyingly.

Also, now that asynchronous calls are so pervasive, I’m surprised that the Silverlight Toolkit BusyIndicator didn’t make it in.

Visual Studio

First, the unit testing tool is definitely pre-beta. I didn’t actually finish investigating how to unit test my C# 5 async method conversions, as I couldn’t stomach using the tool any longer. I’m also not overly-enamoured with the new Find dialog. Otherwise, it seems to be pretty stable.

Metro-ising

So far I’ve spoken about how easy it was to convert over a Silverlight application to Metro, but Metro does allow many compelling features to be very easily added to the application. Charms could be provided to allow searching of family tree information, and to allow the images to be easily shared.

Once I get hold of a touchscreen device, I’d love to add some snap points to the chart.

Other thoughts

Overall, I’m pleased with the development experience of targeting Windows 8 Metro. I haven’t spoken about the actual platform in this blog, but after the months of silence and confusion about Windows 8, it’s all good news. .NET developers are still first class citizens.

I’m happy that WinRT is back to native code, and as I have experience in C++/CLI I’m very happy that C++/CX seems pretty much identical. From a .NET coder point of view, it’s a little concerning that .NET apps will have a slight performance disadvantage from the COM Interop of the WinRT projected types, but I suppose that’s simply the whole ‘use .NET for productivity, C++ for performance’ argument. And having worked on a few apps that had all of the performant (and usually legacy) parts of the system in C++, with a .NET UI, and the subsequent marshalling layer, it’s quite heartening to think that now we can stay in C++ and write a fast and fluid UI without changing languages.

RX Framework Performance Awareness

2011-07-11T14:03:00.001-07:00

In a post a while ago, here, I implemented a DifferentiateWithTime operator, which was implemented in terms of other RX operators, and at the end I closed out by saying “It does say in section 6.1 of the RX Design Guidelines that new operators should be composed of existing operators, unless performance is a concern – this is something I may get around to investigating in a future blog post.” and thought I’d finally get around to looking at this.

As a recap, the differentiate operator was written using a sliding window operator (updated to use RX 1.1 experimental):

        public static IObservable<double> DifferentiateWithTime
            (this IObservable<double> obs)
        {
            return (from j in obs.SlidingWindow(2) 
                    select j[1] - j[0]);
        }

        // from http://social.msdn.microsoft.com/Forums/en-US/rx/thread/37428f58-f241-45b3-a878-c1627deb9ac4#bcdc7b79-bbde-4145-88e4-583685285682
        public static IObservable<IList<TSource>> 
            SlidingWindow<TSource>(this IObservable<TSource> source,
            int count)
        {
            Contract.Requires(source != null);
            Contract.Requires(count >= 0);

            return source.Publish(published =>
                from x in published
                from buffer in published.StartWith(x).Buffer(count).Take(1)
                where buffer.Count == count
                select buffer
            );
        }

I created a simple test fixture to exercise this.

            const double accelerationGravity = 9.81;
            var count = 10000.0;
            var positions = Observable.Generate(0.0,
                i => i < count,
                i => i + 1.0,
                i => accelerationGravity * i * i / 2.0);

            var stopwatch = new Stopwatch();
            stopwatch.Start();

            var velocity = positions.DifferentiateWithTime();

            var sumVelocity = 0.0;
            using (velocity.Subscribe(i =>
                            { sumVelocity += i; })) { };

            var acceleration = velocity.DifferentiateWithTime();

            var sumAcceleration = 0.0;
            using (acceleration.Subscribe(i =>
                                { sumAcceleration += i; })) { };

            stopwatch.Stop();

            Console.WriteLine("sumVel:{0} sumAcc:{1} time:{2}", 
                sumVelocity,
                sumAcceleration,
                stopwatch.ElapsedMilliseconds);

Monitoring in Perfmon, I saw that during the 10000 iterations there were 170 Generation 0 garbage collections, which does seem quite overkill. The total time was 6580 milliseconds.

I then implemented the DifferentiateWithTime operator directly:

        public static IObservable<double> DifferentiateWithTime
            (this IObservable<double> obs)
        {
            return Observable.Create<double>(o =>
            {
                double previousValue = 0.0;
                var initialized = false;

                return obs.Subscribe(i =>
                {
                    if (initialized)
                    {
                        o.OnNext(i - previousValue);
                    }
                    else
                    {
                        initialized = true;
                    }
                    previousValue = i;
                });
            });
        }

This time there were only 4 Generation 0 garbage collections during the test run, and even more excitingly, the execution time was 379 milliseconds. A 17 time speedup is quite impressive, and shows that it’s worth being careful!

It’s likely that other operations based on sliding windows (rolling averages, VWAP etc) may have similar issues, and may benefit from similar observations. Instead of forcing the user to manually make these changes, it may be possible to do this in a more automated way (I’ve got some ideas I’ll play with when I get time.)

Quick Play with the AMD Stream SDK

2011-07-06T12:40:00.001-07:00

I mentioned in my last blog post that I was disappointed with the performance of Microsoft Accelerator, and wanted to play around with Brahma. I was going to do this sooner, but have been side-tracked with playing around with XNA on Windows Phone 7.

I downloaded the latest OpenCL version of Brahma, but had trouble with the nested loops and aggregation operations (force summations), so didn't get as far as I'd hoped. It’s a shame, as the concept of LINQ to GPU is a great one.

I then took a look at running the OpenCL NBody simulation from the Stream SDK. I couldn't get the simulation to run using the GPU despite trying various Catalyst versions, it failed with a runtime error message "This OpenCL build requires verison 1.4.879, version 1.4.696 installed", but in spite of this, I was impressed with the performance of using the Stream SDK, even running on the CPU.

Whereas my managed CPU-version of the nbody simulation achieved 5 fps (frames per second), (or 8 fps with the drawing disabled – as discussed earlier the WPF drawing code is slow), drawing 2000 bodies, the OpenCL SDK ran at 25 fps drawing 2048 bodies, i.e. a factor of 5 speedup. I didn't bother to parallelise my code but the theoretical maximum speedup on my dual core machine would obviously be a factor of 2, so that's a factor of 2.5 speedup using the Stream SDK on the same hardware.

I switched the Stream SDK NBody example to use the nBodyCPUReference() method to see whether it's slow because of the difference between managed and native code, and it runs at 5 fps compiled native on the CPU, i.e. in the same ballpark as the managed version. As it's not running on the GPU, the Stream version must be faster than the vanilla C++ version because it's making use of the processor's vector hardware, but I can't be bothered to manually code the SSE intrinsics to see if that's the case (but it might be cool to play around with Mono.SIMD if I get time).

Oh, I suppose I should talk about how the code looks - the guts of the algorithm doesn't look much different between the vanilla C++ and the OpenCL version, but there is a lot of hideous boilerplate/setup code different between the two. This is why it'd be great to get a workable managed library to hide all this (alternately, it'll be interesting to see whether C++ AMP abstracts away the OpenCL/DirectCompute complexity).

GPGPU–playing with Microsoft Accelerator

2011-04-23T08:04:00.000-07:00

It’s probably being screamingly obvious to some readers that the boids simulations I’ve been playing with are embarassingly parallel, so I thought I’d have a quick play.

I’ve been reading around about OpenCL and CUDA, but as there’s a Microsoft library with a .NET API for easily programming the GPU, I thought I’d have a play with Accelerator (another interesting .NET GPGPU library is Brahma – I might get around to playing with that one day). Accelerator is higher-level, no need to worry about the low-levels of the GPU memory management.

I decided to play with a simpler example than the boids, to focus on the technology instead of the problem domain. I chose to look at the all-pairs NBody simulation (see more info here).

I quickly coded up a simple example using 1000 bodies. The CPU was able to draw at approx 15 frames per second (I didn’t bother parallelising the simulation on the CPU, as I was hoping for an order of magnitude increase in speed on the GPU). WPF is incredibly slow in drawing, and I found (unexpectedly) that using DrawingVisuals to be even slower. For that reason, I’m only drawing 100 bodies, but all of them are included in the simulation. I was intending to reduce the bottleneck by using Direct2D, and then getting Accelerator to write out to texture memory to save transferring data over the bus.

I didn’t get the results I expected when using Accelerator – I first began by converting the main simulation routine (integration of positions) onto the GPU, and left the all-body force calculation on the CPU. I was surprised to find the simulation slower – I was hitting frame rates of 10 fps.

I guessed that maybe it was maybe transferring too much data between the CPU and GPU, so I then moved onto the force calculation. I was very surprised to find that this made the simulation orders of magnitude slower (i.e. hitting frame rates < 0.01 fps). I profiled this to find that the majority of the time was spent in CompileShader. This isn’t so surprising – I was building up the same calculation for each body, for each frame.

Following the advice in the Accelerator Programmers Guide, I then moved onto using Parameter Objects. This means that it’s able to use the same computation graph with different input data. This did help, but only by an order of magnitude. It’s still not approaching anywhere near real-time frame rates.

I can’t remember where I read it, but I read that it’s recommended using input data sizes of the order 1e6 elements to overcome the overhead of transferring data to and from the GPU. This does make sense, but I was expecting to be at least getting interactive frame rates (as the OpenCL simulations are obtaining). It may be that Accelerator is faster than the CPU with a large number of elements, but it may be that e.g. instead of rendering a frame in an hour, it takes five minutes. It doesn’t seem to be suitable for interactive simulations.

This could be a simple case of user-error. I’ve got the code available on taumuon. If I’m missing something obvious, or you can get faster frame rates than the CPU, please post in the comments

(As I’m discussing performance I guess I should disclose the software and hardware specs. Running Windows x64, on a HP DV3 laptop – 4GB ram, dual core Pentium P6100, ATI Radeon 5470).

F# Flocking (boids)

2011-03-29T14:54:00.001-07:00

A couple of years ago I was blogging about some simple boid behaviour I had implemented in C# (here). I came across this paper which had some interesting ideas I wanted to try out: "Self-organised complex aerial displays of thousands of starlings: a model" by H. Hildenbrandt, C. Carere, C-K. Hemelrijk.

As I'm getting more into F#, I thought this would be a simple reasonable sized application to create to get a feel for how F# works on a slightly larger project (though definitely not large-scale).

Before taking a look at the code, I'll quickly describe which parts of the paper I implemented.

The video generated is available on http://www.youtube.com/watch?v=eil5K7Ir3i8

I haven't implemented all of the ideas in the paper, so my simple application doesn't exhibit the same realistic flocking behaviour, but it does have more realistic behaviour than my earlier efforts. The interesting behaviours were the desire to not stray too far from the roost, the attempt to maintain a steady cruise speed, and to use the nearest seven topological neighbours for cohesion and alignment. I implemented the simulation in 2D for simplicity.

I hardcoded a perception radius instead of implementing the continual adjustment of the perception radius for seven topological neighbours. I also have totally omitted the flight dynamic simulation (no gravity, no banked turns). The paper discusses that the banked turns gives a further air of realism to the simulation.

The coding

This was a real pleasure to implement in F# - a lot less time was thinking about application design, classes and their interactions, the logic in the paper was easy to transfer directly to the keyboard. F# is very compact, so the core logic can be seen on just a couple of screens.

I didn't feel the lack of intellisense too much when developing the core algorithm, I did miss the ability to refactor functions and navigate to usages. I especially missed intellisense when developing the WPF visualisation part of the app, when interacting with .NET objects; I did miss the ability for Visual Studio to automatically add the required namespaces. I must have being spoilt by Visual Studio and Resharper for too long!

The actual WPF application wasn’t such a good fit for F# – there’s no generated code behind file for the XAML, and I feel that using F# would be painful in a WPF or Silverlight application (but just for the view, it should be OK for the ViewModels down).

I implemented a F# Vector type, which can be specified with units of measure (or none). I used units of measure throughout – this was really powerful, and did let me quickly find a few bugs in the implementation.

(NOTE: I still haven’t found a code websnippet tool I’m happy with – you need to click in each of the regions below and scroll down and right to see the whole code). Alternately, the zipped up solution can be downloaded from http://www.taumuon.co.uk/jabuka/FSharpFlock.zip

Vector3D.fs:

module Vector3D

type Vector3D<[<Measure>] 'u>(x : float<'u>, y : float<'u>, z : float<'u>) = 
    static member Zero() = Vector3D<_>(0.0<_>, 0.0<_>, 0.0<_>)

    member v.X = x
    member v.Y = y
    member v.Z = z

    static member (+) (lhs:Vector3D<_>, rhs:Vector3D<_>) =
      Vector3D(lhs.X + rhs.X, lhs.Y + rhs.Y, lhs.Z + rhs.Z)

    static member (-) (lhs:Vector3D<_>, rhs:Vector3D<_>) =
      Vector3D(lhs.X - rhs.X, lhs.Y - rhs.Y, lhs.Z - rhs.Z)

    static member (*) (v:Vector3D<_>, a:float<_>) =
      Vector3D(v.X * a, v.Y * a, v.Z * a)

    static member (*) (a:float<_>, v:Vector3D<_>) =
      Vector3D(a * v.X, a * v.Y, a * v.Z)
      
    static member (/) (v:Vector3D<_>, a) =
      Vector3D(v.X / a, v.Y / a, v.Z / a)

    member v.DotProduct(rhs:Vector3D<_>) = (v.X * rhs.X) + (v.Y * rhs.Y) + (v.Z * rhs.Z)

    member v.magnitude = sqrt(v.DotProduct(v)) * 1.0<_>

    member lhs.CrossProduct(rhs:Vector3D<_>) =
      Vector3D((lhs.Y * rhs.Z - lhs.Z * rhs.Y) * 1.0<_>,
          (-lhs.X * rhs.Z + lhs.Z * rhs.X) * 1.0<_>,
          (lhs.X * rhs.Y - lhs.Y * rhs.X) * 1.0<_>)

    member v.normalise = 
      let magnitude = float v.magnitude
      Vector3D<_>((v.X / magnitude), (v.Y / magnitude), (v.Z / magnitude))

let sumVectors(vectors : Vector3D<_>[]) = 
  let initial = Vector3D<_>(0.0<_>, 0.0<_>, 0.0<_>)
  Array.fold (+) initial vectors

BoidUtils.fs:

module BoidUtils

open Microsoft.FSharp.Math
open Vector3D
open SI

let radiusRoost = 150.0<m>
let hardRadius = 2.0<m> // 0.2<m>
let mass = 0.08<kg>
let timeStep = 0.005<s>
let relaxationTime = 0.05<s>
let cruiseSpeed = 20.0<m/s>
let horizontalRoostWeighting = 0.01<N/m>
let weightingAlignment = 0.5<kg * s^-2>
let weightingCohesion = 1.0<kg s^-2>
let weightingSeparation = 2.0
let perceptionRadius = 50.0<m>

type BodyAxes =
  { Forward:Vector3D<1>;
    Side:Vector3D<1>;
    Up:Vector3D<1> }

type Boid = 
  { Position:Vector3D<m>;
    Speed:float<m / s>;
    Orientation:BodyAxes; }

// All parameterless functions are evaluated once, just on module opening, so pass random in.
let InitialiseRandomPosition(rand:System.Random) = 
  Vector3D<m>((300.0 * (rand.NextDouble()-0.5)) * 1.0<m>,
             ((300.0 * (rand.NextDouble()-0.5)) * 1.0<m>), 
             0.0<m>)

let InitialiseRandomVelocity(rand:System.Random) = 
  Vector3D<m/s>((100.0 * (-0.5 + rand.NextDouble()) * 1.0<m/s>),
                (100.0 * (-0.5 + rand.NextDouble())) * 1.0<m/s>,
                0.0<m/s>)

let InitialiseRandomOrientation(rand:System.Random) = 
  {Forward=Vector3D(0.0, 1.0, 0.0);
   Side=Vector3D(1.0, 0.0, 0.0);
   Up=Vector3D(0.0, 0.0, 1.0)}

let setOrientation(oldOrientation:BodyAxes, velocity:Vector3D<m/s>) =
  let normalisedVelocity = velocity.normalise
  let y = normalisedVelocity.CrossProduct(Vector3D<m / s>(0.0<m/s>, 0.0<m/s>, 1.0<m/s>))
  {oldOrientation with Forward=normalisedVelocity * 1.0<m^-1 s>; Side=y*1.0<m^-2 s^2>}

let calculateCruiseSpeedForce (boid:Boid) =
  (mass / relaxationTime) * (cruiseSpeed - boid.Speed) * boid.Orientation.Forward

let calculateRoostForce (boid:Boid) =
  let horizontalPosition = Vector3D(boid.Position.X, boid.Position.Y, 0.0<_>)
  let distanceFromOrigin = horizontalPosition.magnitude
  match (distanceFromOrigin) with
  | _ when distanceFromOrigin < radiusRoost -> Vector3D<N>(0.0<N>, 0.0<N>, 0.0<N>)
  | _ -> let normalRoostingArea = horizontalPosition.normalise
         let d = boid.Orientation.Forward.DotProduct normalRoostingArea
         let distanceFromRoost = distanceFromOrigin - radiusRoost
         let orientationRoostDotProduct = boid.Orientation.Side.DotProduct normalRoostingArea
         let weightingFactor = match (orientationRoostDotProduct) with
                               | _ when orientationRoostDotProduct > 0.0<m> -> -1.0
                               | _ -> 1.0
         weightingFactor * (radiusRoost * horizontalRoostWeighting * (0.5 + (0.5<m^-1> * d)) * (boid.Orientation.Side))

let findDistanceBetweenBoids(boid:Boid, other:Boid) = 
  (boid.Position - other.Position).magnitude

let findNearestNeighbours(boid:Boid, boids:Boid[]) =
  let sortedByDistance = boids |> Array.sortBy(fun other -> findDistanceBetweenBoids(boid, other))
  Array.sub sortedByDistance 0 7

let findAverageForwardDirectionDifference(boid:Boid, boids:Boid[]) = 
  let differences = boids |> Array.map (fun i -> 1.0<m> * (i.Orientation.Forward - boid.Orientation.Forward))
  let sumDifferences = sumVectors(differences)
  (1.0 / (float sumDifferences.magnitude)) * sumDifferences

let calculateAlignmentForce(boid:Boid, nearest:Boid[]) =
  let averageDifference = findAverageForwardDirectionDifference(boid, nearest)
  weightingAlignment * averageDifference

let findAveragePosition(boid:Boid, boids:Boid[]) =
  let positions = boids |> Array.map (fun i -> i.Position)
  let sumPositions = sumVectors(positions)
  (1.0 / float boids.Length) * sumPositions

let findNeighboursInRadius(boid:Boid, boids:Boid[], radius:float<m>) =
  boids |> Array.filter(fun other -> other <> boid && findDistanceBetweenBoids(boid, other) <= radius)

let calculateCentrality(boid:Boid, boids:Boid[]) = 
  let separations = boids |> Array.map(fun i -> (i.Position - boid.Position).normalise)
  let sumSeparations = sumVectors(separations)
  let count = boids.Length
  match (count) with
  | 0 -> 1.0
  | _ -> (1.0 / float count) * (sumSeparations.magnitude / 1.0<m>)

let calculateCohesionForce(boid:Boid, nearest:Boid[], boidsInPerceptionRadius:Boid[]) =
  let boidsOutsideHardRadius = nearest |> Array.filter(fun i -> abs ((boid.Position - i.Position).magnitude) > hardRadius)
  let centrality = calculateCentrality(boid, boidsInPerceptionRadius)
  let averagePosition = findAveragePosition(boid, nearest)
  centrality * weightingCohesion * (averagePosition - boid.Position)

let calculateSeparationForce(boid:Boid, boidsInPerceptionRadius:Boid[]) = 
  let nearest = boidsInPerceptionRadius
  let separations = nearest |> Array.map(fun i -> i.Position - boid.Position)
  let sigma = 1.8
  let forcesToNeighbours = separations |> Array.map(fun i -> 
    let magnitude = i.magnitude
    let multiplier = 
        match (magnitude) with
        | _ when magnitude < hardRadius -> 1.0
        | _ -> System.Math.Exp(-((magnitude - hardRadius)*(magnitude - hardRadius)/1.0<m^2>) / (sigma * sigma))
    multiplier * magnitude * (i.normalise) * 1.0<kg * m^-1 * s^-2>)
  let sumForces = sumVectors(forcesToNeighbours)
  match (nearest.Length) with
    | _ when (nearest.Length) = 0 -> Vector3D<N>.Zero()
    | _ -> (-weightingSeparation / float nearest.Length) * sumForces

let calculateSocialForce(boid:Boid, boids:Boid[]) =
  let nearest = findNearestNeighbours(boid, boids)
  let boidsInPerceptionRadius = findNeighboursInRadius(boid, boids, perceptionRadius)
  calculateAlignmentForce(boid, nearest)
  + calculateCohesionForce(boid, nearest, boidsInPerceptionRadius)
  + calculateSeparationForce(boid, boidsInPerceptionRadius)

let calculateForce (boid:Boid, boids:Boid[]) =
  (boid |> calculateRoostForce)
  + (boid |> calculateCruiseSpeedForce) 
  + (calculateSocialForce(boid, boids))

let iterateBoid (boid:Boid, boids:Boid[]) = 
  let originalPosition = boid.Position
  let originalVelocity = boid.Speed * boid.Orientation.Forward
  let force = calculateForce(boid, boids)
  let acceleration = force/mass
  let velocity = originalVelocity + (acceleration * timeStep)
  let position = originalPosition + (velocity * timeStep)
  let newOrientation = setOrientation(boid.Orientation, velocity)
  {Position=position;Speed=velocity.magnitude;Orientation=newOrientation}

Program.fs:

module Boids

open SI
open Vector3D
open BoidUtils

open System
open System.IO
open System.Windows
open System.Windows.Threading
open System.Windows.Controls
open System.Windows.Shapes
open System.Windows.Media
open System.Windows.Media.Imaging

let window = Application.LoadComponent(new System.Uri("/FSharpFlock;component/MainWindow.xaml",
                                           System.UriKind.Relative)) :?> Window

let rand = new System.Random()
let viewWidth = 480.0
let viewHeight = 360.0

let mutable frameCount = 0
let mutable boids =
  [|for i in 0 .. 300 ->
    let position = InitialiseRandomPosition(rand)
    let velocity = InitialiseRandomVelocity(rand)
    let tempOrientation = {Forward=Vector3D(0.0, 1.0, 0.0);
                           Side=Vector3D(1.0, 0.0, 0.0);
                           Up=Vector3D(0.0, 0.0, 1.0)}
    let orientation = setOrientation(tempOrientation, velocity)
    {Position = position; Speed=velocity.magnitude; Orientation=orientation}
    |];;

let updateBoids(boids) =
  boids |> Array.map (fun boid -> iterateBoid(boid, boids))

let (?) (fe:FrameworkElement) name : 'T =
  fe.FindName(name) :?> 'T

let GetRotationForBoid(boid:Boid) =
  let forward = boid.Orientation.Forward
  let angleRadians = Math.Atan2(forward.X, forward.Y)
  let angleDegrees = angleRadians * 180.0 / Math.PI
  let rotateTransform = new Media.RotateTransform(angleDegrees, 0.0, 0.0)
  rotateTransform

let color = Media.Color.FromArgb(64uy, 255uy, 0uy, 0uy)

let saveFrame(canvas : Canvas) = 
  let size = new Size(viewWidth, viewHeight)
  canvas.Measure(size)
  canvas.Arrange(new Rect(size))
  let renderTargetBitmap = new RenderTargetBitmap(int viewWidth, int viewHeight, 96.0, 96.0, PixelFormats.Pbgra32)
  let sourceBrush = new VisualBrush(canvas)
  renderTargetBitmap.Render(canvas)

  let bitmapFrame = BitmapFrame.Create(renderTargetBitmap)
  let jpegEncoder = new JpegBitmapEncoder()
  jpegEncoder.Frames.Add(bitmapFrame)
  let filename = System.String.Format("C:\Anim\{0:0000}.jpg", frameCount)
  use stream = new FileStream(filename, FileMode.CreateNew)
  jpegEncoder.Save(stream)
  
let createBoidGraphics(boid:Boid) =
  let obj : Polygon = new Polygon()
  obj.Points <- new Media.PointCollection( [|new Point(-10.0, -5.0);
                                             new Point(0.0, 0.0);
                                             new Point(-10.0, 5.0);
                                             new Point(-5.0, 0.0)|] )
  obj.RenderTransform <- GetRotationForBoid(boid)
  obj.Fill <- new Media.SolidColorBrush(color)
  obj.Stroke <- Media.Brushes.Black
  obj.StrokeThickness <- 1.0
  obj

let drawBoids() =
  let win : Window = window
  let canvas : Canvas = win?canvas
  canvas.Children.Clear()
  for i = 0 to boids.Length - 1 do
    let graphicalBoid = createBoidGraphics(boids.[i])
    let unitlessPosition = boids.[i].Position * 1.0<m^-1>
    System.Windows.Controls.Canvas.SetTop(graphicalBoid, (viewHeight / 2.0) + (unitlessPosition.X))
    System.Windows.Controls.Canvas.SetLeft(graphicalBoid, (viewWidth / 2.0) + (unitlessPosition.Y))
    canvas.Children.Add(graphicalBoid) |> ignore
  // saveFrame(canvas)
  frameCount <- frameCount + 1

let timer = new DispatcherTimer();
timer.Tick.Add(fun evArgs -> 
  [0..5]
  |> Seq.iter(fun x -> boids <- boids |> updateBoids)
  drawBoids()
  )
timer.Interval <- TimeSpan.FromMilliseconds(1.0);

let setup(win: Window) =
  win.Loaded.Add(fun _ -> timer.Start())

[<STAThread>]
[<EntryPoint>]
let main args =
  setup window
  (new Application()).Run(window) |> ignore
  0

MainWindow.xaml:

<Window xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
        xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
        Title="F# Flock" Height="360" Width="480">
    <Canvas Name="canvas" HorizontalAlignment="Stretch" VerticalAlignment="Stretch" 
    Background="LightBlue"/>
</Window>

The rest of the code I hope is simple to read and understand. Coding this up I had some of the most fun programming for a while. With F#, I found I was able to concentrate on the core of the algorithm and very quickly see results.

For this type of project, very algorithmic, F# was a perfect fit. I'd like to get a feel for how to implement F# on a large scale project, and to see how it feels to expose the functionality via an object oriented layer.

F# Units of Measure with the Reactive Framework

2010-11-20T10:04:00.001-08:00

My last blog post dealt with manipulating incoming streams of data, such of position data, composing those streams, and manipulating them, and saw how well RX handles these operations.

As I was doing this, I felt that this would benefit from the extra safety that you can get from F#’s Units of Measure feature.

We can implement an operation to find the separation between two positions (the same as in my previous C# post):

open System
open System.Linq
open System.Threading
open System.Collections.Generic
open Microsoft.FSharp.Math
open Microsoft.FSharp.Linq
open Microsoft.FSharp.Linq.Query

module ObservableEx =
  type System.IObservable<'u> with
    member this.WindowWithCount(count:int)
      = this.Publish(Func<_,_>(fun (p:IObservable<'u>) -> 
        p.SelectMany(
          Func<_,_>(fun x -> p.StartWith(x).BufferWithCount(count).Take(1)),
          Func<_,_,_>(fun x buffer -> buffer)).Where(
            Func<IList<'u>,_>(fun x -> x.Count = count)).Select(
              Func<_,_> (fun x -> x))));

open ObservableEx

let accelerationGravity = 9.81;
let positions = Observable.Generate(0.0,
                  Func<_,_>(fun i -> i < 10.0),
                  Func<_,_>(fun i -> i + 1.0),
                  Func<_,_>(fun i -> accelerationGravity * i * i / 2.0)); 
let positions2 = Observable.Generate(0.0,
                  Func<_,_>(fun i -> i < 10.0),
                  Func<_,_>(fun i -> i + 1.0),
                  Func<_,_>(fun i -> i)); 
let separation = Observable.Zip(positions,
                   positions2, Func<_,_,_>(fun i j -> j - i)); 
let res = separation.Subscribe(fun i -> i |> printfn "%f");

But let’s see what happens if we accidentally do something physically meaningless such as adding a velocity to a position:

let accelerationGravity = 9.81; 
let positions = Observable.Generate(
                  0.0,
                  Func<_,_>(fun i -> i < 10.0),
                  Func<_,_>(fun i -> i + 1.0),
                  Func<_,_>(fun i -> accelerationGravity * i * i / 2.0)); 
let positions2 = Observable.Generate(0.0,
                   Func<_,_>(fun i -> i < 10.0),
                   Func<_,_>(fun i -> i + 1.0),
                   Func<_,_>(fun i -> i)); 
let DifferentiateWithTime (input: IObservable<'a>) =
  input.WindowWithCount(2).Select(fun (j:IList<'a>) -> (j.[1]-j.[0])); 
let velocities = DifferentiateWithTime(positions); 
let separation = Observable.Zip(positions, velocities, Func<_,_,_>(fun i j -> j - i)); 
let res = separation.Subscribe(fun i -> i |> printfn "%f");

The program compiles and runs normally (as we’d expect, the compiler doesn’t know better than the fact that it’s dealing with some float values).

Now, let’s annotate our code with units of measure (I’m using the F# PowerPack). We can calculate the difference between two positions:

let accelerationGravity = 9.81<SI.m SI.s^-2> 
let positions = Observable.Generate(0.0<SI.s>, Func<_,_>(fun i -> i < 10.0<SI.s>), 
                  Func<_,_>(fun i -> i + 1.0<SI.s>),
                  Func<_,_>(fun i -> accelerationGravity * i * i / 2.0)); 
let positions2 = Observable.Generate(0.0<SI.s>,
                  Func<_,_>(fun i -> i < 10.0<SI.s>),
                  Func<_,_>(fun i -> i + 1.0<SI.s>),
                  Func<_,_>(fun i -> 5.0 * accelerationGravity * i * i / 2.0)); 
let DifferentiateWithTime (input: IObservable<float<_>>) = 
  input.WindowWithCount(2).Select(
    fun (j:IList<float<_>>) -> (((j.[1]-j.[0])/1.0<SI.s>))); 
let velocities = DifferentiateWithTime(positions); 
let accelerations = DifferentiateWithTime(velocities); 
let separation = Observable.Zip(positions, positions2, Func<_,_,_>(fun i j -> j - i)); 
let res = separation.Subscribe(fun i -> float i |> printfn "%f"); 
// Next line will not compile 
//let wrongseparation = Observable.Zip(
//                        accelerations, velocities, Func<_,_,_>(fun i j -> j - i));

But if we try instead to calculate the difference between the position and the velocity, the code will no longer compile. This is very cool.

We can also do the same by annotating our IObservables with units:

let accelerationGravity = 9.81<SI.m SI.s^-2> 
let DifferentiateWithTime (input: IObservable<float<_>>) = 
  input.WindowWithCount(2).Select(
    fun (j:IList<float<_>>) -> (((j.[1]-j.[0])/1.0<SI.s>)));
let positions = Observable.Generate(0.0<SI.s>,
                  Func<_,_>(fun i -> i < 10.0<SI.s>), 
                  Func<_,_>(fun i -> i + 1.0<SI.s>),
                  Func<_,_>(fun i -> accelerationGravity * i * i / 2.0)); 
let velocities = DifferentiateWithTime(positions); 
let accelerations = DifferentiateWithTime(velocities); 
let res = positions.Subscribe(fun i -> float i |> printfn "%f"); 
printfn "-- velocities -- ";
let res2 = velocities.Subscribe(fun i -> float i |> printfn "%f");
printf "-- accelerations -- "; 
let res3 = accelerations.Subscribe(fun i -> float i |> printfn "%f");

I love this feature, and can see that it would be incredibly useful with RX, as RX statements can include all sorts of streams of data into a complex operation.

(I was originally mistaken in the original version of this posting, and thought that I couldn’t create the DifferentiateWithTime method to be generic to the units of measure, but was saved by a posting on stackoverflow, here).

RX Framework for manipulating real-life data

2010-11-20T09:03:00.001-08:00

As I said in my previous blog post, in one of my previous roles involved performing real-time analysis of incoming sensor and telemetry data, combining streams of data of different data rates, allowing the user to write their own calculation operations on the data, and displaying it to the user. I wondered what this would have been like to implement using RX.

As an aside, it may be that the new TPL Dataflow library would be more suitable for this – and I am a bit confused about the overlap between some many different technologies, such as RX and the forthcoming C# 5.0 async, or whether TPL Dataflow replaces the Actor model in Microsoft Axum or F#).

Anyway, back with the plot…

Imagine that you have to handle incoming streams of sensor data. This doesn’t have to be hardware sensor data, it could be a phone’s GPS or accelerometer data, or incoming streams of trade data. In the old style of programming there would be a callback or event handler that would be triggered when the data arrived, and to perform aggregate calculations over multiple data streams would involve convoluted code with locks – with RX there’s none of that, just a simple linq query to combine the data:

Imagine that you had two streams of position data (here the observables are generated, but they could be observables from events, the usage is identical, which is beautiful!)

var positions = Observable.Generate(0.0, i => i < 10.0, i => i + 1.0, i => i);

var positions2 = Observable.Generate(10.0, i => i >= 0.0, i => i - 1.0, i => i);

An operator to calculate the separation is as simple as:

var separation = positions.Zip(positions2, (i, j) => new { i, j }).Select(pos => Math.Abs(pos.j - pos.i));

That’s really nice and succinct, and the logic is all in one place (instead of being spread out amongst different callbacks).

As well as calculating the difference between two positions, you might want to find the rate of change of some input data:

static void Main(string[] args)

{

const double accelerationGravity = 9.81;

var positions = Observable.Generate(0.0, i => i < 10.0, i => i + 1.0, i => accelerationGravity * i * i / 2.0);

var velocity = positions.DifferentiateWithTime();

Console.WriteLine("-- velocities -- ");

velocity.Subscribe(i => {

Console.WriteLine(i); });

var acceleration = velocity.DifferentiateWithTime();

Console.WriteLine("-- accelerations -- ");

acceleration.Subscribe(i => {

Console.WriteLine(i); });

}

Again, this is nice. The acceleration is correctly written out for every value as 9.81 (well, within rounding errors).

DifferentiateWithTime is implemented as:

public static partial class ObservableEx2

{

public static IObservable<double> DifferentiateWithTime(this IObservable<double> obs)

{

return (from j in obs.WindowWithCount(2) select j[1] - j[0]);

}

In this case we’re taking the current and previous value and taking the difference between them – this of course is assuming that we are receiving values once per second. We could include the time of each sample in a Tuple, and use the Where operator to ignore values which occur at the same time period (to avoid divide-by-zero errors).

WindowWithCount I found on StackOverflow. This takes a rolling window of values around an observables value, which can be used for operations such as a moving average.

public static IObservable<IList<TSource>> WindowWithCount<TSource>(this IObservable<TSource> source, int count)

{

Contract.Requires(source != null);

Contract.Requires(count >= 0);

return source.Publish(published =>

from x in published

from buffer in published.StartWith(x).BufferWithCount(count).Take(1)

where buffer.Count == count

select buffer

);

}

This is cool, but I am concerned that we’re returning a new list for each sample, even though we’re only interested in two values, this could be hammering the garbage collector for high rates of data. It does say in section 6.1 of the RX Design Guidelines that new operators should be composed of existing operators, unless performance is a concern – this is something I may get around to investigating in a future blog post.

Reactive Framework thoughts

2010-11-20T08:10:00.001-08:00

I have been very slack with blogging recently, as I was too busy with work and life. I've recently moved jobs, and even though I'm just as busy as I was in my previous job, I have a long train commute so I thought that I may as well do something constructive with my time. I figured that blogging is as good as anything else.

In my new role, I'm working on a project that makes heavy use of the the RX Framework, and I’m getting up to speed as fast as I can. It's actually really fun – the way to approach a problem is different to the old method I’m used-to of having async callbacks everywhere, it’s much more functional, and at the start I felt a little bit like my brain had been turned inside out.

The project is using RX for handling the streaming of trading data, and for orchestrating asynchronous operations. The code base is a lot more succinct, understandable and elegant, than it would be without RX (though I’m finding it takes more time to think through how to write the RX operations). There are no .NET events throughout the codebase, all events are exposed as IObservables, allowing for composition with all sorts of async operations.

I've come across the following blog post, where the author was performing calculations on trade data, and that sprung to mind how in a previous job I was manipulating streams of data from hardware devices, and I thought I might go ahead and have a bit of a play with this.

http://eprystupa.wordpress.com/2009/12/20/running-vwap-calculation-using-reactive-extensions-for-net/

I’ll play with this in my next blog post(s).

Theory driven development using Microsoft Pex Explorer

2009-01-11T14:46:00.000-08:00

EDIT: NOTE that some of the contents of this post have been recently been edited thanks to great feedback from Peli de Halleux (http://blog.dotnetwiki.org/). He pointed me at a great post on Test Driven Development with Parameterized Unit Tests that he'd wrote here: http://blog.dotnetwiki.org/TestDrivenDevelopmentWithParameterizedUnitTests.aspx

I've been playing with Microsoft Pex to try out some theory-driven development. I've found it a great tool – actually much better than I was hoping, it's found more bugs, and test cases, than using just unit testing or TDD (Test-Driven Development). It's test-driven development on steroids!

If you've been reading this blog, you'll remember I blogged a while ago about TDD using theories, and what theories are – with the following posts:

http://taumuon-jabuka.blogspot.com/2008/03/comparing-theories-to-more-traditional.html

http://taumuon-jabuka.blogspot.com/2008/03/theories.html

I mentioned that theories could have data-points generated by some sore of explorer, and Jeff Brown (http://blog.bits-in-motion.com/) one of the comments replied that maybe I could use Microsof Pex to do so, and I've found it to be perfect! A lot more powerful than I hoped.

This blog post will try to detail my experiences, but by far the best way to get to grips with this is to download Pex and try writing some theories!

In the example below, I'll create a queue with the following operations:

Enqueue()

Dequeue()

Capacity

Count

It will have an initial capacity, and it will double in size once its capacity is exceeded (similar to the interface on .NET lists, for instance).

First, I'll skip over a few tests written via TDD (a red-bar green-bar refactor cycle), before I get onto writing some theories.

First, in MSTest, we write a test.

        [TestMethod]
        public void Test_NewlyConstructedQueue_CountIsZero()
        {
            Queue<int> queue = new Queue<int>();
            Assert.AreEqual<int>(0, queue.Count);
        }

Then we get the tests to compile, by implementing our queue with a Count property, such that we get a red bar, by getting the count property to return -1.

We then fix the test to get a green bar, but letting the Count return zero:

    public class Queue<T>
    {
        public int Count
        {
            get { return 0; }
        }
    }

We then introduce a test that default constructor creates stack with default stack of capacity 8.

        [TestMethod]
        public void Test_ConstructDefaultConstructor_InitialCapacityIsEight()
        {
            Queue<int> queue = new Queue<int>();
            Assert.AreEqual<int>(8, queue.Capacity);
        }

The implementation is pretty simple:

        private const int initialCapacity = 8;
        public int Capacity
        {
            get { return initialCapacity; }
        }

Now, want to add a Dequeue method, and test that calling it on an empty stack throws an InvalidOperationException.

        [TestMethod]
        [ExpectedException(typeof(InvalidOperationException))]
        public void Test_NewlyConstructedQueue_DequeueThrowsException()
        {
            Queue<int> queue = new Queue<int>();
            int i = queue.Dequeue();
        }

        public T Dequeue()
        {
            throw new InvalidOperationException("Should not call Dequeue on an empty queue");
        }

We're going to come back to look at this test shortly.

We add a test for Enqueue, to check its count is 1.

        [TestMethod]
        public void Test_NewlyConstructedQueue_Enqueue_CountIsOne()
        {
            Queue<int> queue = new Queue<int>();
            queue.Enqueue(1);
            Assert.AreEqual(1, queue.Count);
        }

Add an Enqueue method that does nothing to get this to compile and redbar. We actually have to add some implementation now, to get this to pass.

    public class Queue<T>
    {
        private const int initialCapacity = 8;
        private T[] items = null;

        public int Count
        {
            get { return items == null ? 0 : 1; }
        }

        public int Capacity
        {
            get { return initialCapacity; }
        }

        public T Dequeue()
        {
            throw new InvalidOperationException("Should not call Dequeue on an empty queue");
        }

        public void Enqueue(T item)
        {
            items = new T[initialCapacity];
            items[0] = item;
        }
    }

There are lots of things wrong with this implementation – there are some obvious bugs, we're recreating the array on each Enqueue, not to mention the array being a fixed size, with no capability to grow., and the weird Count implementation. This obviously needs implementing and refactoring, but it passes all our tests, and that's TDD – we don't go adding code until we drive it via adding more tests. So, lets add another couple of tests to drive the implementation:

        [TestMethod]
        public void Test_NewlyConstructedQueue_Enqueue_DequeueReturnsItem()
        {
            Queue<int> queue = new Queue<int>();
            queue.Enqueue(1);
            int item = queue.Dequeue();
            Assert.IsTrue(1 == item);
        }

And can get the tests to pass with the following:

        public T Dequeue()
        {
            if (items == null)
            {
                throw new InvalidOperationException("Should not call Dequeue on an empty queue");
            }
            return items[0];
        }

NOTE: We're really taking baby steps, but to ensure that we're not writing any untested implementation.

Now let's add a test for adding and removing more than one item:

        [TestMethod]
        public void Test_NewlyConstructedQueue_EnqueueTwoItems_DequeueReturnsFirstItem()
        {
            Queue<int> queue = new Queue<int>();
            queue.Enqueue(1);
            queue.Enqueue(2);
            int item = queue.Dequeue();
            Assert.IsTrue(1 == item);
        }

To get this to pass we can more property implement our queue.

    public class Queue<T>
    {
        private int tailIndex = 0; // insertion
        private int headIndex = 0; // removal
        private const int initialCapacity = 8;
        private T[] items = new T[initialCapacity];

        public int Count
        {
            get { return tailIndex - headIndex; }
        }

        public int Capacity
        {
            get { return initialCapacity; }
        }

        public T Dequeue()
        {
            if (Count == 0)
            {
                throw new InvalidOperationException("Should not call Dequeue on an empty queue");
            }
            return items[headIndex--];
        }

        public void Enqueue(T item)
        {
            items[tailIndex++] = item;
        }
    }

To get this to work we had to add more and more example tests – we were saying quite general statements, but expressing this in more and more specific example cases, adding functionality as we went. This process is called triangulation (as I mentioned in an earlier blog post).

There are still a number of limitations here: if we exceed 8 items in the queue, we'll get an IndexOutOfRange exception.

Can quite easily write a test for adding more values for the auto-growth.

Also, a more insiduous bug is that our values can migrate along the array – we're not moving items back towards the back (or front of the queue), so could run out of space even with less than 8 values – a much harder bug to find. This is a subtle bug, and to find it using a unit test would be quite tricky, if you didn't see it up front. USING PEX TO AUTOMATICALLY GENERATE THE THEORY VALIDATION IS GREAT FOR THESE TYPES OF BUGS!

Let's see if we could have written our test in such a way that this problem may have been detected.

        [PexMethod]
        public void Theory_CanAddRemoveAnyNumberOfItemsToNewlyConstructedQueue_IsEmptyAfterwards(int num)
        {
            Queue<int> queue = new Queue<int>();
            for (int i = 0; i < num; i++)
            {
                queue.Enqueue(i);
            }
            for (int i = 0; i < num; i++)
            {
                queue.Dequeue();
            }
            Assert.AreEqual<int>(0, queue.Count);
        }

Use the menu option “Run Pex Explorations”.

4 explorations (unit tests) are generated for this – passing in values of num 0, 1073741824, and 2 and 1.

0 passes.

1073741824 throws an IndexOutOfRangeException

2 throws an IndexOutOfRangeException

1 throws an AssertFailedException

This straight away shows that the code is more bugged than I thought. This would probably have been spotted on the introduction of further tests (for instance, test adding and removing three items from the list), but already highlights the power of theories.

Note: This could have been written as a unit test, but would have had to iterate over all possible integers, instead of just the 4 values that Pex provided.

Passing in a value of 1 – we had a similar test to this in enqueing and dequeing a single item, but we tested that the item dequeued was the same as that enqueued, we didn't test the Count property.

This bug is due to the fact that the headIndex should have been incremented, instead of decremented on dequeuing.

Fixing that and running our tests (including the previously generated ones – without reexploring) results in 9 of the 10 tests passing. The failing case is we're passing in a large in value.

This is obviously due to the fact that we've got a fixed size array, and it doesn't auto-grow.

Let's add an assumption to get our test to pass, before we go on to add the auto-grow functionality.

PexAssume.IsTrue(num <= queue.Capacity, "num is less than capacity");

In theories, assumptions allows us to state the input data for which the theory is valid.

We need to re-run the explorations so we're not calling our test with data points that fail the assumption.

Before we go to get our queue to expand its capacity, let's change our theory to see if it can detect the problem of running out of space after adding and removing items even before it goes out of capacity.

I originally wrote my theory in the format below, but see the second format and following comments, following feedback from Peli de Halleux.

        [PexMethod]
        public void Theory_CanAddRemoveAnyNumberOfItemsAnyEmptyQueue_IsEmptyAfterwards(
            [PexAssumeNotNull]Queue<int> queue, int num)
        {
            PexAssume.IsTrue(num <= queue.Capacity, "num is less than capacity");
            PexAssume.IsTrue(queue.Count == 0);
            for (int i = 0; i <= num; i++)
            {
                queue.Enqueue(i);
            }
            for (int i = 0; i <= num; i++)
            {
                queue.Dequeue();
            }
            Assert.AreEqual<int>(0, queue.Count);
        }

This was rewritten to:

        [PexMethod]
        [PexGenericArguments(typeof(int))]
        public void Theory_CanAddRemoveAnyNumberOfItemsAnyEmptyQueue_IsEmptyAfterwards<T>(
            [PexAssumeUnderTest]Queue<T> queue, [PexAssumeNotNull]T[] values)
        {
            PexAssume.IsTrue(values.Length <= queue.Capacity, "num is less than capacity");
            PexAssume.IsTrue(queue.Count == 0);
            for (int i = 0; i < values.Length; i++)
            {
                queue.Enqueue(values[i]);
            }
            for (int i = 0; i < values.Length; i++)
            {
                queue.Dequeue();
            }
            Assert.AreEqual<int>(0, queue.Count);
        }

The PexAssumeNotNullAttribute states that the theory is not valid for null values of that parameter, but the PexAssumeUnderTest, as well as stating that the parameter cannot be null, gives Pex more hints for tuning its search strategies.

This is a much more general theory – we're now saying given any empty queue, it will be empty after enqueueing and dequeueing.

We can instruct Pex how to construct a queue, that has had items added and removed:

        [PexFactoryMethod(typeof(Queue<int>))]
        public static Queue<int> Create(int numberInitialAdds,
            int numberInitialRemoves)
        {
            Queue<int> queue = new Queue<int>();
            if (numberInitialAdds <= 0 || numberInitialRemoves < 0)
            {
                return queue;
            }
            for (int i = 0; i < numberInitialAdds; ++i)
            {
                queue.Enqueue(i);
            }
            int numberToRemove = numberInitialAdds > numberInitialRemoves ?
            numberInitialRemoves : numberInitialAdds;
            for (int i = 0; i < numberToRemove; ++i)
            {
                queue.Dequeue();
            }
            return queue;
        }

Now, running the theory gives an IndexOutOfRangeException after adding and removing ight items to the queue in the factory – and then subsequently adding and removing one items. This should work – as we're not exceeding the capacity.

This is powerful – if we were unaware of the existence of this bug it's difficult to imagine how we would have come across it in TDD.

Let's fix the failing theory before we remove our assumptions.

        public T Dequeue()
        {
            if (Count == 0)
            {
                throw new InvalidOperationException("Should not call Dequeue on an empty queue");
            }
            T item = items[headIndex++];
            if (headIndex == tailIndex)
            {
                headIndex = tailIndex = 0;
            }
            return item;
        }

Now, the tests run. Let's go on to address the auto-grow issue.

Now, remove the assumption that values.Length <= queue.Capacity and re-explore this theory.

Get an index out of range exception when attempting an array of 15 items to the queue.

We can fix this by implementing auto-grow in the stack:

        public void Enqueue(T item)
        {
            if (tailIndex == items.Length - 1)
            {
                items = new T[items.Length * 2];
            }
            items[tailIndex++] = item;
        }

We can now re-run our tests and they all pass.

Now, deleting all Generated Unit Tests in the class, and re-running Pex Explorations, gives Path bounds exceeded messages – the time is being spent in the factory adding and removing items to the queue, and exploring the paths of auto-growing the stack.

Instead of getting our queue into the required states by manipulating it via its public interface, we can more-directly construct it into any state.

Remove the factory, and add an overloaded constructor.

        public Queue(T[] items, int headIndex, int tailIndex)
        {
            if ((uint)tailIndex >= (uint)(items.Length))
                throw new ArgumentException("(uint)tailIndex >= (uint)(items.Length)");

            this.items = items;
            this.headIndex = headIndex;
            this.tailIndex = tailIndex;
        }

And instruct Pex to use this constructor with an assembly attribute:

[assembly: PexExplorableFromConstructor(typeof(Queue<int>),
    typeof(int[]), typeof(int), typeof(int))]

Now, Pex is able to explore our theory, and finds no failing cases.

NOTE: In my original version of the theory, my theory took an int, the number of values to add to the queue, instead of the array of values, and it that case Pex would pass in a number of integers to add that would cause OutOfMemoryExceptions to occur. Instead, passing in the array of values means that Pex passes in more meaningful data.

The implementation of the queue is progressing; we're autogrowing the stack, but we're not copying the values across. We're also not updating the capacity. We need to check that we can enqueue or dequeue items,and we'd obviously write more theories to do this.

This does show that the thought process behind writing theories is similar to TDD – the tests/theories are only as good as you write, and it's still easy to miss obvious implentation (you still need to think about what you're writing), but I feel that writing theories, with an explorer, allows many more bugs to be caught during the process. Hopefully this has given a good taste of theory driven development.

Faster boids

2008-11-16T10:05:00.000-08:00

I used the built in performance profiler in VSTS to look at speeding the boids up (and there seems to be a bug in the profiler - when memory profiling was turned on, it seemed unable to resolve symbols, so I switched to the CLRProfiler to look at the memory being used).

Most of the time in the application was spent in calculating the boids' steering behaviours.
The optimisations here were to try to reduce the time spent in calculating the forces - one optimisation was that instead of each behaviour (cohesion, separation, alignment) each scanning through the entire set of boids, the results of one of the behaviours could be used by both others.

Secondly, the cohesion force was not updated on each frame - the value is cached for 10 iterations. This should not be a fixed value - there should be some heuristic to determine how it should be varied once work is in to measure the "quality" of the flock.

This boosted the frame rate from approx 3fps to 10fps (dropping to 5 fps after some time).

Next came some micro-optimisations.

Changing the Vector to be a struct instead of a class (to avoid over-stressing the garbage collector) resulted in 14fps dropping to 8 fps after running.

Other micro-optimisations that I tried, but didn't result in any real performance difference included:

Making the trail generator to use a fixed size array (instead of adding/removing from a list).

Removing IEulerRigidBody, calling onto objects directly instead of through an interface.

Changing all doubles to be floats (didn't actually keep this change in the code).

For Scene8, the drawing code was the real bottleneck, changing the gluSphere to be drawn using VertexBufferObjects resulted in double the frame rate (and it isn't particularly optimised - could use glDrawElements).

For Scene7, it's limited by the O(n2) collision detection (this is the next thing to tackle).

Boids

2008-08-17T09:45:00.000-07:00

An improvement of the flocking behaviour in Jabuka is available.

There are now very simplistic birds drawn, to give an idea of the boid's orientation.

The separation behaviour has been fixed. The behaviour was garbage before, the force away from another boid was proportional to the distance away from it. Now the force increases the nearer another boid is.

The boid's orientation is taken as the smallest angle between being aligned with the World's x axis, and the boid's velocity. The roll doesn't behave realistically (see scene 13), but the boid's behaviour isn't realistic. A boid would really change its velocity by adjusting its orientation (change the wing shape to apply a torque to allow it to rotate...)

This paper describes how the steering behaviours should change the intention of the boid, instead of providing actual forces onto the boid.

A simple particle system has been introduced to allow the path of a few individual boids to be more easily seen.

Performance.
Running under the Visual Studio profiler, most of the time was seen to be spent finding the flockmates in proximity of the boid.

The same calculation was being done twice, for both the cohesion and alignment behaviours. Adding a ProximityFinderCache increased the frame rate by 50%, with no change in the calculations. Adjusting the code so that the boids in proximity are only calculated on every third iteration added another 20% to the framerate (giving 15fps with only two TrailGenerators attached).

Maslina and Rakija updates for NUnit 2.4.7

2008-04-21T13:25:00.000-07:00

The above NUnit extensions have been updated, Rakija (the data-driven tests extension) has simply been rebuilt against NUnit 2.4.7.

Maslina (the theory extension) has had some changes.
Firstly, inline Assumptions have been added (i.e. you can Assume.IsTrue()) in the code.

The most important change, however, is that a failure of the pre-called assumptions now results in the body of the theory method not being called, i.e. theories are no longer validated (and similarly, Assume.IsTrue() exits the theory method immediately).

There were some very interesting discussions on the NUnit developer list recently which persuaded me of the error of my ways, most specifically, it can be too 'dangerous' to continue execution of a theory if the user has signalled that the data is invalid.

You should validate that your assumptions are valid when writing theories, but this should be done in either another theory, or plain vanilla unit test.

Comments welcome as always :)

Comparing Theories to more traditional testing

2008-03-19T15:32:00.000-07:00

My old work colleague Tim has recently blogged about using NSpec to specify a stack.

NSpec has the same sort of functionality as a unit testing framework such as NUnit. The terminology has been changed to get over the roadblock that some people have in adopting tests.

Theories actually give something over and above normal unit testing, and that's what I'm going to look at in this blog post. I'm going to look at Tim's example and show how using theories actually differ from Tim's more traditional example.

The stack interface for which the implementation was arrived at via speccing is as follows:


public class Stack<t>
{
public Stack();
public void Clear();
public bool Contains(T item);
public T Peek();
public T Pop();
public void Push(T item);

// Properties
public int Count { get; }
}

The following tests were arrived at:


namespace Stack.Specs
{
[Context]
public class WhenTheStackIsEmpty
{
    Stack _stack = new Stack<int>();

    [Specification]
    public void CountShouldBeZero()
    {
        Specify.That(_stack.Count).ShouldEqual(0);
    }

    [Specification]
    public void PeekShouldThrowException()
    {
        MethodThatThrows mtt = delegate()
           {
               _stack.Peek();
           };

        Specify.ThrownBy(mtt).ShouldBeOfType(typeof(InvalidOperationException));
    }
}
}

That's ample for us to discuss the difference between theories and more normal testing.

For the PeekShouldThrowException test/specification, we can see from the naming of the context that the developer intends to show that for an empty stack, the Peek operation throws an exception. However, what the developer has actually shown is that calling Peek on a newly-created stack throws an exception.

Developers tend to think in fairly general terms, and express this generality by using more specific cases. However, some of this generality can get lost. Theories aim to keep more of that generality.

We can demonstrate this in a theory (don't take much note of the syntax, just the concepts)


 [Theory]
 public void PeekOnEmptyStackShouldThrow(Stack<int> stack)
 {
     try
     {
         stack.Peek();
         Assert.Fail(ExpectedExceptionNotThrown);
     }
     catch (InvalidOperationException) { }
 }

This states that calling Peek() on ANY stack should fail, we need to show that this is only true for an empty stack. We could do this by simply checking for this:


 [Theory]
 public void PeekOnEmptyStackShouldThrow(Stack<int> stack)
 {
     try
     {
         if (stack.Count == 0)
         {
             stack.Peek();
             Assert.Fail(ExpectedExceptionNotThrown);
         }
     }
     catch (InvalidOperationException) { }
 }

But as we'll see in a bit, using assumptions gives us some extra feedback (again, don't focus on the syntax).


 [Theory]
 [Assumption("AssumeStackIsEmpty")]
 public void PeekOnEmptyStackShouldThrow(Stack<int> stack)
 {
     try
     {

         stack.Peek();
         Assert.Fail(ExpectedExceptionNotThrown);
     }
     catch (InvalidOperationException) { }
 }

 public bool AssumeStackIsEmpty(Stack<int> stack)
 {
     return stack.Count == 0;
 }

This is a much more general statement than the original specification/test, we're saying that the stack should fail if we try to Peek on it for ANY empty stack.

We don't care whether this is a newly-created stack, or it is a stack which has been manipulated via its public interface. Also, Liskov Substitution Principle states that we should be able to use any classes derived from Stack, and the theories should hold true.

We validate this theory with example data, in much the same way as when we're doing test-driven development. The extra power comes from the generality in the way that the theory is written - we can imagine a tool that performs static code analysis on the Stack class to confirm that it obeys this.

However, the literature mentions that the most likely way to validate a theory is via an exploration phase, via a plug-in tool that will try various combinations of input data to look for anything that fails the theory.

It is prohibilively expensive to explore every possible combination of inputs, imagine all the possible values of a double, or in our example, there are an infinite number of operations that could happen to a stack that gets passed in.

This fits in nicely with the name theory with parallels with science - it's not feasible to prove it, but we look for data to disprove it.

The example data is important for the red-green-refactor cycle. The exploration phase sits outside that - it finds which input data doesn't fit the theory, allowing the theory to be modifed. There are exploration tools in Java, and I haven't looked too much into it, but it may be possible to use Microsoft's Pex as an exploration tool?

Before I forget, this is a possible way to specify the example data for our stack:


  [Theory]
  [Assumption("AssumeStackIsEmpty")]
  [InlineData("EmptyStack", new Stack())]
  [PropertyData("EmptiedStack")]
  public void PeekOnEmptyStackShouldThrow(Stack<int> stack)
  {
      try
      {
          stack.Peek();
          Assert.Fail(ExpectedExceptionNotThrown);
      }
      catch (InvalidOperationException) { }
  }

  public List<exampledata> EmptiedStack
  {
      get
      {
          List<exampledata> data = new List<ExampleData>();
          Stack stack = new Stack();
          stack.Push(2);
          stack.Push(3);
          stack.Pop();
          stack.Pop();
          data.Add(stack);
          return data;
      }
  }

In my prototype extension, the assumptions are important and are validated, as they tell us something vital about the code. I think that all the information about the behaviour of the system is vital, and should be documented and validated, but there are varied opinions on the list. That's why I'm blogging - give me your feedback :)

If the user changed the behaviour of Peek() such that it was valid on an empty stack (it may return a Null Object for certain generic types), then our assumption would not detect this if it was simply filtering the data - the assumption would say "Peek() fails, but only on empty stacks", whereas Peek() would not fail on empty stacks. See my previous post for the behaviours I have implemented.

Notice in Tim's implementation how his stack is hardcoded to have at most 10 items. When TDDing we may make slightly less obviously limited implementations to get our tests to pass, but forget to add the extra test cases to show this limitation (the process of progressively adding more and more general test cases is called triangulation).

When writing theories, the same process happens, but writing the theories as a more general statement means that a code reviewer/automated tool can see that the developer intended that we intended that we can push a new item onto ANY stack, not just a stack that contained 9 or less items.

Any thoughts? Have I got the wrong end of the stick? If anyone found this post useful, I might full flesh out the equivalent of Tim's example.

Sample Theory Implementation as NUnit Extension.

2008-03-19T13:57:00.000-07:00

There's been lots of comments bouncing around on the NUnit mailing list about what exactly constitutes a Theory, and what the desired features are, so I've created an NUnit extension with a sample Theory implementation - you can get it, Maslina version 1.0.0.0, from www.taumuon.co.uk/rakija

xUnit.Net implements theories but does not have any in-built Assumption mechanism (you can effectively filter out bad data, which is the same as a filtering assumption). JUnit 4.4, I think, only filters out data - it doesn't tell us anything about the state of an assumption.

Anyway, from reading the literature on theories (see my previous blog posting), I quite like the idea of having assumptions tell us something about the code, that those assumptions are validated.

The syntax of my addin is quite poor, and there's not really enough validation of user input, but I'm aiming to try to do some theory-driven development (theorizing?) using it, to see what feels good and what grates.

Any feedback gratefully received (especially - is it valid to say that this is an implementation of a Theory, are validation of assumptions useful or unnecessary fluff?)

Here is the syntax of my extension.


 [TestFixture]
 public class TheorySampleFixture
 {
     [Theory]
     [PropertyData("MyTestMethodData")]
     [InlineData("Parity", new object[] { 1.0, 1.0, 1.0 })]
     [InlineData("Parity 2", new object[] { 2.0, 2.0, 1.0 })]
     [InlineData("Double Euros", new object[] { 2.0, 1.0, 2.0 })]
     // This does not match the assumption, and will cause this
     //specific theory Assert to fail, in which case we will get a pass overall.
     // If the unit under test were changed to somehow handle zero exchange rate,
     // the body of the theory method would pass, but the
     // assumption would still not be met and overall we will register a failure.
     [InlineData("ExchangeRate Assumption Check", new object[] { 2.0, 1.0, 0.0 })]
     // This case will fail, there is an assumption that the dollar value is not three,
     // but passing in a value of 3 doesn't cause a failure in the code, demonstrating
     // that the assumption serves no purpose
     [InlineData("This should fail, assumption met but no failure in method", new object[] { 3.0, 1.0, 3.0 })]
     [Assumption("ConvertToEurosAndBackExchangeRateIsNotZero")]
     [Assumption("DollarsNotThree")]
     public void MyTheoryCanConvertToFromEuros(double amountDollars, double amountEuros, double exchangeRateDollarsPerEuro)
     {
         // Should check are equivalent within a tolerance
         // Calls static method on Convert method
         Assert.AreEqual(amountDollars, Converter.ConvertEurosToDollars(Converter.ConvertDollarsToEuros(amountDollars,
         exchangeRateDollarsPerEuro), exchangeRateDollarsPerEuro));
     }

     // Assumption is that the exchange rate is not zero
     public bool ConvertToEurosAndBackExchangeRateIsNotZero(double amountDollars, double amountEuros, double exchangeRateDollarsPerEuro)
     {
         // Should have a tolerance on this
         return exchangeRateDollarsPerEuro != 0.0;
     }

     // Assume that dollar value not equal to three
     // This is just to demonstrate that an invalid assumption results in a failure.
     public bool DollarsNotThree(double amountDollars, double amountEuros, double exchangeRateDollarsPerEuro)
     {
         return amountDollars != 3.0;
     }

     /// Returns the data for MyTestMethod
     ///
     public IList MyTestMethodData
     {
         get
         {
             List details = new List();
             details.Add(new TheoryExampleDataDetail("Some other case should pass", new object[] { 2.0, 20.0, 5.0}));
             return details;
         }
     }
 }

 public static class Converter
 {
     public static double ConvertEurosToDollars(double amountDollars,
         double dollarsPerEuro)
     {
         return amountDollars * dollarsPerEuro;
     }

     public static double ConvertDollarsToEuros(double amountEuros,
         double dollarsPerEuro)
     {
         return amountEuros / dollarsPerEuro;
     }
 }

A nicer syntax/api would be to have the assumptions inline:


public void CanConvertToEurosAndBack(double amountDollars, double amountEuros, double exchangeRateDollarsPerEuro)
{
Assume.That(exchangeRateDollarsPerEuro != 0.0);
Assume.That(amountDollars != 0.0);

// Checks are equivalent within a tolerance
// Calls static method on Convert method
Assert.AreEqual(amountDollars, Converter.ConvertEurosToDollars(Converter.ConvertDollarsToEuros(amountDollars,
exchangeRateDollarsPerEuro),exchangeRateDollarsPerEuro));
}

Here's the rules of my Theory Implementation

If there is no example data, the theory passes (we may want to change this in the future).
If there are no assumptions for a theory, then each set of example data is executed against the theory each producing its own pass or fail.

If assumptions exist, the each set of data is first validated against the assumption - if it meets the assumption, then the test proceeds and any test failure is flagged as an error.
If the example data does not meet the assumption, then if the test passes it indicates that the assumption is invalid, and that case is marked as a failure, with a specific message "AssumptionFailed". Any assertion failures or exceptions in the actual theory code are treated as passes. (in the future, would we want to mark the specific exception expected in the test methdo if an assumption is not met?).

NOTE: we may want to mark as a failure any theory for which ALL example data fails the assumptions, as a check that the
actual body of the theory is actually being executed. I've not done this for now as it would be trickier with the current
NUnit implementation.

Similarly, I was thinking of failing if any of the assumptions weren't actually executed, but again, this is tricky in the current NUnit implementation (and may not give us much).

Automated exploration would not follow the last two suggested rules. The automation API would need to generate its data and execute it as if it were inline data. It may be helpful for the automated tool to be able to retrieve the user-supplied example data, so it doesn't report a failure for any known case, but this is probably not necessary.

Feedback on these rules would be most welcome. If you want to change the behaviour of the assumptions (i.e. have assumptions only filter and nothing more), then the behaviour can be changed in TheoryMethod.RunTestMethod()

Here's the output of the above theory:

Theories

2008-03-13T14:17:00.000-07:00

I've just released a slightly updated version of my NUnit extension for data-driven unit testing.

There's been a lot of discussion on the NUnit developer list recently regarding Theories - something new in JUnit and xUnit.Net, and it's taken a while to discover why they're so powerful (they're superficially very similar to data-driven unit tests, and a lot of the differences are semantics).

First, there's some good background on theories written by David Saff:
http://shareandenjoy.saff.net/tdd-specifications.pdf
http://shareandenjoy.saff.net/2007/04/popper-and-junitfactory.html
http://dspace.mit.edu/bitstream/1721.1/40090/1/MIT-CSAIL-TR-2008-002.pdf

Theories on first glance look like a data-driven unit test, but I think that the most important difference is, is that:

Theories are, in theory (excuse the pun), supposed to pass for ANY POSSIBLE parameters, whereas data-driven tests only express the behaviour examples that the developer has provided (they are nothing new in unit testing - just a way for a developer to more clearly group parameters together, or get the parameterized data from an external data source without recompiling tests).

Theories are a generalized statement of how the program should run, whereas in TDDing, a very explicit statement of intent is made, which can be made to pass by coding that specific case in the implementation, and then the program is made to work by triangulization - expressing the generalization by giving more inputs. However, the theory literature points out that as we haven't passed in too many data points we can't be sure whether we've actually expressed what we meant.

Theories, by forcing us to write our tests such that they take any inputs, are much more powerful a statement, and allow for the possible inputs to be explored with external tools.

As an aside, one question I posted to the NUnit developer list regarding theories: "One thing that comes to mind, is that theories are written such that all possible inputs should pass. Apart from using a tool such as agitator, is there a way to test that the tests are written in a general way (I mean, if you had a theory that took parameters, but it totally ignored those parameters and worked as a vanilla unit test - i.e. created its own input), then it's not really a valid theory - is
there a way to detect these cases? Probably not, but I was just idly wondering." Answers on a postcard to... well, I'd prefer a reply comment ;-)

2008-02-02T15:06:00.002-08:00

This is a blog post to explain exactly what exactly parameterized data-driven unit testing is and why it’s there, and then to explain a bit about how this effected the implementation of the Rakija NUnit add-in.

First, what is data-driven unit testing? It’s running tests with data which is driven from external data (as may be from an xml file or database). NUnit makes this quite difficult, as the tests are attribute driven, they are fixed, and fixed at the time that the tests are created.

Data-driven fixtures.
A common desire is to run fixtures with different set of parameters. An example of this is to test key input filtering under different UI cultures.

This is a very contrived example, and the tests are in no way realistic, but it demonstrates what data-driven tests are about. My example is a simple class that takes various string inputs and performs operations on them. Here it is:

///

/// Parses and operates on various string values.
///

public static class ValueParser
{
///

/// Returns the addition of two strings representing
/// double values.
///

/// The combined value.
public static double GetAdditiveValue
(string value1, string value2)
{
return double.Parse(value1) + double.Parse(value2);
}
}

And of course, the contributing unit test:

[TestFixture]
public class TestValueParser
{
[Test]
public void TestAdditiveValue()
{
Assert.AreEqual(4.5, ValueParser.GetAdditiveValue(
"2.3", "2.2"));
}
}

Of course in real life, we’d have tests to pass in garbage input, checking for any exceptions etc. Our class would also be much larger, containing many methods, along with many (maybe hundreds) of corresponding unit tests in our test fixture. We’ve happily deployed the first release of our software, and have many happy customers, when our customer representative or product manager informs us that we need our software to run on European users computers. We don’t get panicked, we know that our input data is coming from XML, and is formatted in invariant culture, but we need to make sure to change our code such that double.Parse takes in CultureInfo.InvariantCulture. We’d ideally like to ensure that our tests run in both cultures. We could duplicate our fixture with a different setup test, but we all know that duplicate code is bad, right? So we use the following pattern.

// NOTE: TestFixture class has been removed.
public class TestValueParser
{
protected string cultureString = "invalid";
private CultureInfo initialCulture;

[SetUp]
public void Setup()
{
this.initialCulture
= Thread.CurrentThread.CurrentCulture;
Thread.CurrentThread.CurrentCulture =
CultureInfo.GetCultureInfoByIetfLanguageTag(
cultureString);
}

[TearDown]
public void TearDown()
{
Thread.CurrentThread.CurrentCulture =
this.initialCulture;
}

[Test]
public void TestAdditiveValue()
{
Assert.AreEqual(4.5, ValueParser.GetAdditiveValue(
"2.3", "2.2"));
}
}

[TestFixture]
public class TestValueParserUSCulture : TestValueParser
{
public TestValueParserUSCulture()
{
cultureString = "en-US";
}
}

[TestFixture]
public class TestValueParserFRCulture : TestValueParser
{
public TestValueParserFRCulture()
{
cultureString = "fr-FR";
}
}

We leave all of our tests intact, we have to make some minor modifications to our original test fixture (remove the test fixture attribute, and do some setup work), but we’re able to test our fix very quickly (obviously we follow red bar/green bar/refactor, and write the tests before changing our code), and as we have a high test code the new release of the software works flawlessly, we finish early and spend the remaining time playing Crysis.

This pattern is very common in NUnit, but I haven’t found it named anywhere, I call it the Test Fixture Inheritance Pattern. NOTE: This pattern is not supported in Visual Studio Team System 2005 testing, but it’s fixed in the 2008 version.

(As an aside, I’ve read about the upcoming xUnit framework, and it says that tests aren’t grouped into fixtures, I’m not sure how it would cope with this pattern in that case? It’s possible that you could parameterized each test, and use something like a RowTest attribute to pass in the culture string, but by testing a new culture you’d have to add a new attribute to each and every test.)

The first thing to notice about the Test Fixture Inheritance Pattern is that it isn’t very OO. It wouldn’t be too much work though to create an NUnit extension that would allow parameterizing the test fixture constructor, in a similar way to how the RowTest attribute works, i.e.

[TestFixture]
[Parameter("en-US")]
[Parameter("fr-FR")]
public class TestValueParser
{
protected string cultureString = "invalid";
private CultureInfo initialCulture;

public TestValueParser(string cultureString)
{
this.cultureString = cultureString;
}

[SetUp]
public void Setup()
{
this.initialCulture
= Thread.CurrentThread.CurrentCulture;
Thread.CurrentThread.CurrentCulture =
CultureInfo.GetCultureInfoByIetfLanguageTag(
cultureString);
}

[TearDown]
public void TearDown()
{
Thread.CurrentThread.CurrentCulture =
this.initialCulture;
}

[Test]
public void TestAdditiveValue()
{
Assert.AreEqual(4.5, ValueParser.GetAdditiveValue(
"2.3", "2.2"));
}
}

That would be nothing more than syntactic sugar though (it does make the tests look much neater). This could be more powerful though – it could be expanded to read data from a database or an XML file (again, similar to VSTS’s DataSource attribute).

Rakija instead provides an interface IDynamicFixtureSpecifier, which is used on a class to specify which fixtures to create. Each fixture then must implement another interface, and the fixture need to implement IDynamicFixture. Our example now looks like this:

// NOTE: TestFixture attribute has been removed.
public class TestValueParser : IDynamicFixture
{
protected string cultureString = "invalid";
private CultureInfo initialCulture;

public TestValueParser(string cultureString)
{
this.cultureString = cultureString;
}

[SetUp]
public void Setup()
{
this.initialCulture
= Thread.CurrentThread.CurrentCulture;
Thread.CurrentThread.CurrentCulture =
CultureInfo.GetCultureInfoByIetfLanguageTag(
cultureString);
}

[TearDown]
public void TearDown()
{
Thread.CurrentThread.CurrentCulture =
this.initialCulture;
}

[Test]
public void TestAdditiveValue()
{
Assert.AreEqual(4.5, ValueParser.GetAdditiveValue(
"2.3", "2.2"));
}

#region IDynamicFixture Members

public string Name
{
get { return "TestValueParser " + cultureString; }
}

#endregion
}

The fact that this is a test fixture is detected from the add-in by the fact that it implements IDynamicFixture, I could have instead created a new attribute for the class, and either reflected for the Name property (or created an attribute to return the name), but that’s by-the-by.

To actually specify the instances of our fixture, we use code like the following:

public class SpecifyFixtures : IDynamicFixtureSpecifier
{
#region IDynamicFixtureSpecifier Members

public Type FixtureType
{
get
{
return typeof(TestValueParser);
}
}

public IList GetUserFixtures()
{
List fixtures =
new List(2);
fixtures.Add(new TestValueParser("fr-FR"));
fixtures.Add(new TestValueParser("en-US"));
return fixtures;
}

#endregion
}

Your first thought may be to wonder why I’ve created such a convoluted way of creating fixtures, when a page or so ago I showed how neatly this could be done by creating a new attribute. Well, this is much more powerful, we’re not limited to querying a database or reading an XML file – we could load up our assembly to test, and reflect over certain types in it, creating a new fixture for each type. The sky’s the limit.

Parameterized test methods.
I’ll quickly go over the motivation over parameterized test methods, before discussing why I’ve been forced to implement these myself due to the current NUnit (as of 2.4.6) extension interface, rather than deferring these to Kelly Anderson’s extension.

Another common requirement when unit testing is to run a given test with different input data. Before the existence of any RowTest attribute, a common thing to do may have been.

[Test]
public void SomeTest()
{
// .. read some data in an xml file
// .. for each piece of data, perform some common testing
// .. { assert on the data; }
}

This obviously works, but the problem of it is lack of visibility/feedback. For a file that may contain hundreds of pieces of data, we have a single red or green bar. We’d like to have visibility of each individual case. VSTS has a DataSource attribute to cope with this cases like this (reading from a database or XML File).

Now that I’ve, very briefly, covered the motivations behind parameterized test cases, I’m going to go into the implementation details of Rakija.

Kelly Anderson has created a more powerful interface, similar to Rakija’s, where a method can be decorated with an IterativeTest attribute to specify the test data for the test. (Kelly’s interface is much more user-friendly than Rakija’s).

Unfortunately, I’ve had to duplicate the functionality of this Kelly’s work in Rakija, due to the internals of NUnit’s extensibility mechanism. I’ll explain why below, and propose a change to the mechanism to allow the extensions to co-exist.

Similar to Rakija, Kelly’s mechanism creates a TestCaseBuilder to recognise the parameterized test cases. This works without any problem, but will fail when used with any of the above parameterized test fixtures described above.

Kelly’s extension works by finding the method decorated with his IterativeTestAttribute, creating a new instance of the type that contains that attribute, and calling the method decorated by that attribute to find the parameters to create the test with. He gets away with creating a new instance of the type by the fact that all instances of the type will contain the same data.

The problem comes when you have parameterized test cases – each test case has been created with different parameters, and depending on those constructor parameters we may wish to pass different parameters to our tests (our test fixtures may have been created with a given node of an xml file, and we may wish to pass various sub-nodes of that node to an XML file).

Rakija is forced to deal with this situation by taking control of the parameterized test case situation when parameterized fixtures are also involved.

The proposed fix, to allow dynamic fixtures to exist with any other extension (e.g. Kelly Anderson’s IterativeTest extension, or Andreas Schlapsi’s RowTest extension) is to make a change to the extensibility mechanism.

Currently, NUnitTestFixtureBuilder (or our derived class), has to call

this.testCaseBuilders.BuildFrom(method);

where method is a MethodInfo
And this forces each test case builder either call a static method, or construct a type to create a method on. The return type from this method is a test, which gets added onto the fixture/suite’s list of tests to run.

In the parameterized fixture case, the interface on AbstractTestCaseBuilder would better be:
protected override TestCase MakeTestCase(object instance, MethodInfo method);

or something similar, where instance would be the instance that contains the method. That would allow the method to be invoked on the instance that it lived on, allowing parameterized fixtures to co-exist with the other mentioned extensions.

Excuses

2008-01-29T13:42:00.000-08:00

For not having another Jabuka post yet... Well, I've been really busy at my previous employers getting upto speed on various new technologies, then as you may have read on my other blog, I've been busy preparing for a new job (I might blog a bit about that at some point), and work always takes priority. I did have to create an interesting small WPF 3D application as part of my application process (I'll tart this up and get it online when I get chance).

I haven't given up on Jabuka, I spent a lot of time over Christmas researching different constraint methods (LCP solvers, PGS solvers and Sequential Impulses), and will playing around with this as soon as I get a chance to breathe (oh, and I finally packaged up my NUnit data-driven testing extension, here).

Otherwise, my new years resolution is to play with F# - I attended a Next Gen Usergroup talk last year at Microsoft's Cambridge site by Don Syme. Since then I've had time to do some reading around, but not to actually create anything in anger. Obviously, some functional ideas have influenced C# (lambda expressions etc.) but I want to see how working in a functional mindset might chance some of my ideas of designing code.

There's been lots of blogging recently on immutability in C# (see here and here) recently - in functional languages everything is immutable, and obviously not having immutable state gets around guarding state with multiple threads, it's just the overall program design I can't picture yet (I'm used to thinking of looking for common interfaces, design patterns etc.) There's also new parallel/Concurrent resources available from Microsoft which do fit nicely into all this (see F#'s asynchronous workflows).

A change of approach/jabuka 0.6

2007-10-29T14:56:00.000-07:00

As mentioned on the Jabuka website, I'm moving away from a tutorial-based approach, mainly because of lack of time. It's much quicker to implement new code and then blog retrospectively, highlighting new features and interesting code/design decisions. In the tutorial based approach, making a change/bug fix in an earlier tutorial forces all later tutorials to be updated.

That being said, it's worth discussing changes are in the latest version, 0.6, of Jabuka.
This code introduces a couple of simple steering behaviours, and flocking boids. Given the roadmap, why did I suddenly go off on a total tangent and implement boids? Well, apart from flocking behaviour being especially cool (look on youtube for the Carling Belong commercial, or starling flocks), I wanted to stress the engine (I use that term very loosely given the current functionality of Jabuka) as I'm itching to demonstrate multithreading and performance enhancements. This version of Jabuka has shown that it is still too early to look at performance, however, as the application still has some fundamental flaws to be addressed.

The flocking application implements a flock (based on the algorithms on Chris Reynolds website, and roughly based on the algorithms in the Killer Game Programming in Java book). The changes to Jabuka were that the force for a rigid body is obtained in the Update() method from introducing an IForceProvider interface, implemented by various behaviours.
If you look at the implementation of the steering behaviours, you can see that there is a large number of classes implementing this interface, each performing a simple operation such as aggregation/limitation. This does lead to a proliferation of classes, but I'm happy to live with it for now as it makes unit testing easier, and may lead to more easily changing behaviour dynamically at runtime.

The Update() method calling on the IForceProvider is not perfect in this case - the objects are iterated over, and each object's Update() method calls on its IForceProvider. For the steering behaviours, the behaviour compares the body's location to its neighbours to calculate its force and update its position. The problem is that the resulting locations are dependent on the order in which the bodies are updated. This has problems in measuring the flocking quality (more on this later), and it may be desired to update the steering forces independent of Update(), so we don't do this in every time step (as it's an expensive operation - O(2)?). Also, having the state of an object dependent on every other object on every timestep will get really messy when we introduce multithreading. Having each body's Update() method independent of any other means that it's much easier to parallelise/vectorise/split into multiple threads - it's likely we'd want to avoid making every IEulerRigidBody thread safe, and would want to implement the thread safety at a higher level (though I won't jump the gun, we'll get there soon enough).

The sort of changes above hint that it may be better to have a Physics Manager class, that owns the Collision object, the rigid bodies, and also has knowledge of the IForceProviders and manages the overall sequence of operation.

The larger problem with having the currently flocking behaviour, including collision detection, is that I haven't yet implemented resting contacts (well, any contact forces) apart from collisions, and as objects are forced towards each other, the simulation can halt. I've temporarily fixed this by introducing a scene where the boids don't have any collision detection. I've also introduced a scene which demonstrates the halting, with only two spheres.

As to steering behaviours and flocking itself... I've introduced a scene for the seek behaviour, demonstrating that having the steering force directed towards the target is insufficient, the velocity tangential to the targed needs to be taken into account. The idea is to find the optimal trajectory towards the target. Reynolds copes with this by providing a force such that the body's velocity is adjusted to be the maximum velocity towards the target. This is better, but does mean that the body needs a concept of its maximum velocity (this works OK on Earth, as air friction gives a terminal velocity, but in space this is arbitrary). Also, the maximum velocity may vary - the maximum velocity into the wind is less than having a following wind, and may depend on a body's shape (or its orientation with respect to its velocity).

Looking at the arrive behaviour, where the speed is arbitrarily slowed down, the first thought that comes to mind is that a PID control towards the target would be desired. However, the problem is that the velocity tangential/perpendicular and distance from the target all need to be taken into account - a more complicated control scheme would need to be used, and that may be too computationally expensive.

The current boid implementation currently uses the same proximity distance for all individual behaviours (separation, alignment, cohesion). It may be that for separation, a smaller proximity should be used. Also, currently, I'm using a simple sphere without taking into account the blind spot behind the boid.

There are lots of tweaks to be made (and a Genetic Algorithm could be used to change these dynamically), but many of them are pointless without a method of measuring the quality of the flock. There is an interesting paper on that here. Some background on the flock theory / the underlying physics of flocking, can be found here, and here.