Measuing latency with HdrHistogram

I had the pleasure last year to meet with Gil Tene, an authority on building high performance software and specifically high performance JVM implementations. He gave a brilliant presentation at React San Francisco and then again at YOW in Australia on common mistakes made when measuring performance. He he explained that measuring latency is not about getting a number, but identifying behavior and characteristics of a system.

Often when we set out to measure the performance of our software we can be guided by NFR (Non-Functional Requirements) that really don't make too much sense. More than once I have been presented with a requirement that the system must  process x requests per time-period e.g 5 messages per second. However as Gil points out this single number is either unreasonable, or misleading. If the system must always operate in a state to support these targets then it may be cost prohibitive. This requirement must also define 100% up-time. To work around that, some requirements specify that the mean response time should be y. However this is potentially less useful. By definition what we are really specifying is the 50% of requests must see worse performance than the target.

A useful visualization for pointing out the folly of chasing a mean measurement is illustrated below.


[Source - https://en.wikipedia.org/wiki/Anscombe%27s_quartet]

All of these charts have the same mean value, but clearly show different shapes of data. If you measuring latency in your application and were targeting a mean value, you may be able to hit these targets but still have unhappy customers.

When discussing single value targets, a mean value can be thought of as just the 50th percentile. In the first case the requirement was for the 100th percentile.

Perhaps what is more useful is to measure and target several values. Maybe the 99th percentile plus targets at 99.9% and 99.99% etc is what you really are looking for.

Measuring latency with histograms

Instead of capturing a count and a sum of all latency recorded to then calculate a mean latency, you can capture latency values and assign them to a bucket. The assignment of this value to a bucket is to simply increment the count of that bucket. This now allows us to analyse the spread of latency recordings.

The example of a histogram from Wikipedia shows how to represent heights by grouping into buckets of 5cm ranges. For each value of the 31 Black Cheery Trees measured, the height is assigned to the bucket and the count for that bucket increased. Note that the x axis is linear.



A naive implementation of a histogram however, may require you to pre-plan your number and width of your buckets. Gil Tene has helped out here by creating an implementation of a histogram that specifically is design for high dynamic ranges, hence its name HdrHistogram.

When you create an instance of an HdrHistogram you simply specify

1. a maximum value that you will support
2. the precision you want to capture as the number of significant digits
3. optionally, the minimum value you will support

The internal data structures of the HdrHistogram are such that you can very cheaply specify a maximum value that is an order of magnitude larger than you will expect, thus giving you enough headroom for your recorded values. As the HdrHistogram is designed to measure latency a common usage would be to measure a range from the minimum supported value for the platform (nanoseconds on JVM+Linux, or ticks on .NET+Windows) up to an hour, with a fidelity of 3 significant figures.

For example, a Histogram could be configured to track the counts of observed integer values between 0 and 36,000,000,000 while maintaining a value precision of 3 significant digits across that range. Value quantization within the range will thus be no larger than 1/1,000th (or 0.1%) of any value. This example Histogram could be used to track and analyze the counts of observed response times ranging between 1 tick (100 nanoseconds) and 1 hour in magnitude, while maintaining a value resolution of 100 nanosecond up to 100 microseconds, a resolution of 1 millisecond(or better) up to one second, and a resolution of 1 second (or better) up to 1,000 seconds. At it's maximum tracked value(1 hour), it would still maintain a resolution of 3.6 seconds (or better).

Application of the HdrHistogram

When Matt (@mattbarrett) and I presented Reactive User Interfaces, we used the elements of drama and crowd reaction to illustrate the differences between various ways of conflating fast moving data from a server into a client GUI application. To best illustrate the problems of flooding a client with too much data in a server-push system, we used a modestly powered Intel i3 laptop. This worked fairly well in showing the client application coming to its knees when overloaded. However it also occasionally showed Windows coming to its knees too, which was a wee bit too much drama to have on stage during a live presentation.

Instead we thought it better to provide a static visualization of what was happening in our system when it was overloaded with data from the server. We could then contrast that with alternative implementations showing how we can perform load-shedding on the client. This also meant we could present with a single high powered laptop, instead of bringing the toy i3 along with us just to demo.

We added a port of the original Java HdrHistogram to our .NET code base. We used it to capture the latency of prices from the server, to the client, and then the additional latency for the client to actually dispatch the rendering of the price. As GUI applications are single threaded, if you provided more updates than the GUI can render, there are two things that can happen:

• updates are queued
• updates are conflated

What you do in your client application depends on your requirements. Some systems will need to process every message. In this case they may choose to just allow the updates to be queued. Other systems may allow updates to be conflated. Conflation is the act of taking many and reducing to one. So for some systems, they maybe able to conflate many updates and average them or aggregate them. For other systems, it may only be the last message that is the most important, so the conflation algorithm here would be to only process the last message. Matt discusses this in more detail on the Adaptive Blog.

In the demo for ReactiveTrader we demo queuing all updates and 3 styles of conflation. When we applied the HdrHistogram to our code base, we were quick to see we actually had a bug in our code base.

We had two problems. The first problem was an assumption that what worked for Silverlight, would also work for WPF. As WPF has two threads dedicated to presentation (a UI thread and a dedicated Render thread), we were actually only measuring how long it took for us to put a price on another queue! You can see that the ObserveLatest1 and ObserverLatest2 (red and yellow) lines show worse performance than just processing all items on the dispatcher. I believe this is due to us just doing more work to conflate before sending to the render thread. Unlike in Silverlight, once we send something to the Render thread in WPF we can no longer measure the time taking to actually render the change. So our measurements here were not really telling us the full story.

The second problem we see is that there was actually a bug in the code we copied from our original silverlight (Rx v1) code. The original code (red line) accidentally used a MultipleAssignmentDisposable instead of a SerialDisposable. The simple change gave us the improvements seen in the yellow line.

We were happy to see that the Conflate and ConstantRate algorithms were measuring great results, which were clearly supported visually when using the application.



To find out more about the brilliant Gil Tene

• see his talk at React San Francisco and then again at YOW in Australia
• check out his web site - http://latencytipoftheday.blogspot.co.uk 
• follow him on twitter @giltene
• see his content on infoQ - http://www.infoq.com/author/Gil-Tene
• or look at Azul (https://www.azul.com/) and the things they can make Java code do

I am currently working on the final details of a complete port of the original Java HdrHsitogram to .NET. You can see my work here - https://github.com/LeeCampbell/HdrHistogram.NET

Squeezing out performance from Charting

After my review of the charting products available currently I decided to go with the Slverlight/WPF Data Visualization project (from the WPF Toolkit). I did end up coming up with a trick to squeeze some performance out of the charts. Quite simply that charts don’t handle a lot of data very well. When you have rich data templates, animation and more than several hundred data points, performance is pretty poor. I decided that the first thing to compromise on would be animation. It is nice but I would rather speed. By turning off the animation in the charting I get a little speed up but there still is a simple truth that must be considered. If my graph is only 500px wide then why try to render more than 500 data points? This is my first step to gaining some performance; filter out data by sampling so we never try to get the chart to render more data than it ever could.

I can achieve this by creating a custom CollectionViewSource. The new sub class is simple;

• it has a dependency property of MaxItemCount
• on any change to the MaxItemCount or the Source we sample the data set, and save the values we want to display into a set
• we subscribe to the Filter event and only accept an item if it is included in our sample set

public class CollectionSizeFilter : CollectionViewSource
{
    int _count;
    ICollectionView _defaultView;
    HashSet<object> _toKeep;

    public CollectionSizeFilter()
    {
        Filter += CollectionSizeFilter_Filter;
    }

    protected virtual void CollectionSizeFilter_Filter(object sender, FilterEventArgs e)
    {
        e.Accepted = _toKeep == null || _toKeep.Contains(e.Item);
    }

    protected override void OnSourceChanged(object oldSource, object newSource)
    {
        base.OnSourceChanged(oldSource, newSource);
        _defaultView = GetDefaultView(newSource);
        _count = Count(_defaultView.SourceCollection);

        LoadHashset();
    }

    public double MaxItemCount
    {
        get { return (double)GetValue(MaxItemCountProperty); }
        set { SetValue(MaxItemCountProperty, value); }
    }
    public static readonly DependencyProperty MaxItemCountProperty = DependencyProperty.Register("MaxItemCount", typeof(double), typeof(CollectionSizeFilter), new UIPropertyMetadata(1d, MaxItemCountProperty_Changed));

    private static void MaxItemCountProperty_Changed(DependencyObject sender, DependencyPropertyChangedEventArgs e)
    {
        var self = (CollectionSizeFilter)sender;
        self.LoadHashset();
    }

    private void LoadHashset()
    {
        if (_count <= MaxItemCount)
        {
            _toKeep = null;
        }
        else
        {
            _toKeep = new HashSet<object>();
            var gap = MaxItemCount - 1;
            var spacing = _count / gap;
            double nextIndex = 0d;
            int i = 0;
            foreach (var item in _defaultView.SourceCollection)
            {
                if (i >= nextIndex)
                {
                    _toKeep.Add(item);
                    nextIndex += spacing;
                }
                i++;
            }
        }
        if (View != null)
            View.Refresh();
    }

    private static int Count(IEnumerable source)
    {
        if (source == null)
        {
            return 0;
        }
        var is2 = source as ICollection;
        if (is2 != null)
        {
            return is2.Count;
        }
        int num = 0;
        IEnumerator enumerator = source.GetEnumerator();
        {
            while (enumerator.MoveNext())
            {
                num++;
            }
        }
        return num;
    }
}

To use the new “control” we just treat it like a normal CollectionViewSource but we specifiy the MaxItemCount by binding it to the width of the Chart like this.

<Controls:CollectionSizeFilter x:Key="FilteredData" 
    Source="{Binding MyData}" 
    MaxItemCount="{Binding ElementName=chart1, Path=ActualWidth}"/>

This gave some performance improvements but I thought why not follow this concept down the path a little bit more. For most data that  I want to display I am mainly interested in the trend not the minutia. So why do I try to show a data point on every pixel? I could just sample the data; for example if I have a data set of 1500 data points and a graph that is 500px wide, I get some performance gains by reducing the rendered data set to 500 data points, but why not just show one data point every say 10px? If this is acceptable for your data then you can reduce your rendered data set from 1500 down to 50 (30 times less data to render). To do this is even more simple than the code above. We just need to create and implementation of IValueConverter to do some division, a DivisionConverter.

public sealed class DivisionConverter : IValueConverter
{
    #region IValueConverter Members
    public object Convert(object value, Type targetType, object parameter, CultureInfo culture)
    {
        double numerator = ConvertToDouble(value, culture);
        double denominator = ConvertToDouble(parameter, culture);
        return numerator / denominator;
    }

    public object ConvertBack(object value, Type targetType, object parameter, CultureInfo culture)
    {
        throw new NotImplementedException();
    }
    #endregion

    private static double ConvertToDouble(object value, IFormatProvider culture)
    {
        var result = default(double);
        try
        {
            var source = value as IConvertible;
            if (source != null)
                result = source.ToDouble(culture);
        }
        catch
        {
        }
        return result;
    }
}

So now we can just extend our previous XAML to include the new converter and apply our sample size of 10.

<Controls:DivisionConverter x:Key="divisionConverter" />
<Controls:CollectionSizeFilter x:Key="FilteredData" 
    Source="{Binding MyData}"
    MaxItemCount="{Binding ElementName=chart1, Path=ActualWidth, 
        Converter={StaticResource divisionConverter}, 
        ConverterParameter=10}"/>

Putting it all together I end up with code like below. I prefer to keep my concerns near each other, so here I have defined the filters in the LineSeries Resources instead of where some may put them which is the top of the file. I would however define the key to the DivisionConverter at the top of the file or even in the App.xaml as I will probably use it in many places. Note how I use RelativeSource Binding to find the width of the parent chart.

<chartingToolkit:Chart Name="chart1">
    <chartingToolkit:LineSeries 
        Title="{Binding Title}"
        DependentValuePath="Value"
        IndependentValuePath="Date">
        <chartingToolkit:LineSeries.Resources>
            <Controls:CollectionSizeFilter 
                x:Key="FilteredBalances" 
                Source="{Binding Balances}"
                MaxItemCount="{Binding 
                        RelativeSource={RelativeSource FindAncestor, 
                        AncestorType={x:Type chartingToolkit:Chart}}, 
                        Path=ActualWidth,
                        Converter={StaticResource DivisionConverter}, 
                        ConverterParameter=10}"/>
        </chartingToolkit:LineSeries.Resources>
        <chartingToolkit:LineSeries.ItemsSource >
            <Binding Source="{StaticResource FilteredBalances}"/>
        </chartingToolkit:LineSeries.ItemsSource>
    </chartingToolkit:LineSeries>
</chartingToolkit:Chart>

You may find your millage varies with the sampling size. You may be only comfortable with small values like 3-5 or you may be more aggressive with values around 30. It is your data and you will know what is best for you. The real beauty of this is that problem of performance is a presentation problem. With some simple controls we are able to tame the problem in the presentation layer without having to compromise the purity of our ViewModels (like setting max size values that get sent to databases). Here if we resize the chart, we already have all the data so we just render more data points. Also the solution is very generic, there are no dependencies on the WPF Data Visualization assemblies so you may find other uses for them.

My WPF Charting Comparisons

I have recently been looking for some graphing/charting functionality for a home project I am working on. My requirements are fairly simple:

1. handle data quantities in the region of thousands and tens of thousands of rows/items
2. be able to display line charts with or without data points (there will be so many data points that they can become noise)
3. be able to display multiple sets of data to be able to compare data
4. free or cheap
5. xcopy install

Now as the Charting products I wanted to compare were all going to be in WPF I assumed that these requirements were just a given but apparently not, so let me specify them as well

6. be able to bind the data from my own view model (i.e. I don’t want to have controls littering my View Model)
7. have the graph update as the data changes

Now to see the list of contenders:

• WPF Toolkit Charting (aka System.Windows.Controls.DataVisualization.Toolkit)
• AmCharts
• VisiFire
• DynamicDataDisplay (aka D3)

So for the really quick review of each

WPF Toolkit Charting

This is the CodePlex project from some of the lads at Microsoft. This is presumable of a lesser quality than the rest of the Toolkit as the Charting component is in preview. The WPF Toolkit allows for great looking charts by utilising the power of WPF Styles. It is one of those balancing acts that must be difficult to make when designing software; extensibility vs. simplicity. The WPF Toolkit leans more towards the extensible option. Extending the charts to look the way you want can be done but many will find it fiddly and frustrating, but once done can be very rewarding and the Graphs can look amazing. The WPF Toolkit also utilises the power of WPF binding by allowing me to bind to my ViewModel. So it looks like a good start, however, the clear and painful problem with the WPF Toolkit is performance. When loading up even hundreds of rows/items the performance is fairly poor. When I tried to throw just over a thousand items at a Line Series the performance was completely unacceptable. One other problem I have is that I get intermittent lock ups. When updating the data, the charting code will run off into a loop and not come out of it, freezing the UI. Hmmm another cross.

Positives:

• Extensibility allows for beautiful graphs
• Charts bind to ViewModel
• Free

Negatives:

• Woeful performance
• Random lock ups.

AmCharts

AmCharts appears to be a Charting solution aimed at the financial industry. The chart control that I thought would best fit my needs was the Stock chart. This chart had a great feature that allowed zooming on the X-axis by providing a range slider. Performance was great when I threw ~1500 items at the control. An odd problem I had was the graph would only appear once I resized my window. I think this has to do with binding to a ViewModel as the Demo does not have this problem but it also directly interacts with the control from the Code behind. I want to avoid “messing with controls” from my ViewModel. A more real problem I have is that while the performance is great, the binding seems to be a once off event. Changes to the values in my collection are not reflected by any change to the chart.

Positives

• Good performance
• Charts bind to ViewModel
• Zoom functionality
• Good samples
• Smallest DLL size (223KB)

Negatives

• One time data binding
• Odd problem with Chart not rendering until i resized the window.

Visifire

VisiFire charts looked to be a great option. They were very easy to get up and running, had some good samples like the AmCharts. My first play with the Visifire charts provided me with a good looking chart. My problems came when I went to bind the Charts to my ViewModel…Visifire does not support data binding! I’m not even sure why someone would write a WPF control that does not support data binding. I wasted plenty off time writing some adapters so that I could get data binding working. Data binding is in the wish list for version 3 (how it didn't make it into the wish list for the 1st version I don’t know). Performance of Visfire was pretty good (not spectacular) and sat in between AmCharts and the hopelessly slow WPF Toolkit.

Positives

• Easy to get up and running
• Pretty good looking default charts
• Moderate performance

Negatives

• You cant bind a data series to a collection!

Dynamic Data Display

The Dynamic Data Display (aka D3) is another Microsoft project on Codeplex from a Microsoft research team in Russia. D3 authors claim outstanding performance even with massive amounts of data. Sounds like a sure fire winner! The control library also supports different types of charts to the other libraries like Maps and Isolines ( I have no idea what an isoline is). The samples show some good stuff with smooth moving animated graphs with dynamic data points. The big fail on the project is again, no data binding. All manipulation of the charts needs to be done in C# code and needs to be very imperative. There are some guys, however, who have made posts creating an extension to the controls to support data-binding. Either way, while this looked to be a good set of controls, the authors don’t appear to have followed the Pit-of-Success principle. I would go in to details, but the fact it took me hours of reading forums, looking at samples and coding to just get my Model showing on the screen. When it did get on to the screen it was fast, but didn’t update when the underlying data changed. This is a very immature set of controls but may have a bright future if the team can get some fundamentals right.

Positives

• High performance
• Easy to scroll and zoom data

Negatives

• Hardest set of controls to work with. Everything has to be done in code. Authors seem to miss the point of WPF entirely. Presentation and logic feel very much couple together.
• After all my mucking around the chart didn’t update with my changes to the data.

In summary, I am pretty disappointed with the state of all of these charting controls. What I did manage to get working to a satisfactory state was the WPF Toolkit. As the only real problem I had with the WPF Toolkit charting controls was their performance; I decided that an easy way to get some better performance out of the control was to only show as many data points as there were available pixels. If I only have 400 pixels to show my data it becomes a bit silly to try and get the graph to render 1400 data points. I created a Custom Control that extends CollectionViewSource by having a MaxItemCount property that can be set to effectively filter the amount of data the CollectionViewSource reveals to the Charting controls. The performance was better but I was able to further tweak the performance by adding a DivisionConverter to further reduce the collection size by the parameter specified (10 in my case). This means I only show a data point for every 10 pixels wide the chart is. This ended up being a great compromise….except for the random lock ups. If I play on the Chart for long enough changing the data to update the chart, eventually the program just falls in to a loop. If I can solve this bug I may have a winner on my hands. Ed:—Playing around more I may have got rid of this problem. Still pops up sometimes straight after a build, but a restart fixes it. This may be to do with my build of Win7 (pre release that I am still running). This throws the WPF Toolkit +the 2 tiny bits of filter code clearly into the lead as it can be made to look great and handle tens of thousands of rows.

If any one is interested in the code I used to test/play with each of these libraries you can find a zip of the VS2008 solution here. To see any of the spikes, just set it as the start up project and run or Right click on the project and “Debug”—> “Start new instance”. Only the MyDomain project wont run as that is the Class library that has the small part of the domain to test the charts with.

ChartingPlaygournd.zip – Source code for my tests.