RadObservableCollection O(1) Item Removal

[Gareth]

I have a RadObservableCollection which is populated with 2560 DataPoint Objects every 800ms.  Each DataPoint object has a Time and Value property (DateTime and Double).

I only want to store 10 seconds worth of data, so every time I add a value, I check whether the collection contains 10 seconds of data or not already.  If it does, I remove the first item in the collection.

1.foreach (RawDataPoint rdp in ldp)
2.{
3.    _Real.Add(new DataPoint(rdp.Time, rdp.Value));
4.    if((rdp.Time.Add(-dataTimeSpan) > _Real[0].Time))
5.    {
6.        _Real.RemoveAt(0); // This is an Order(n) operation.
7.    }
8.}

Unfortunately the RemoveAt(0) function on RadObservableCollection is an O(n) operation and this is causing my application to slowdown as my collection grows to it's "full" capacity, which is many thousands of entries.  Because my data is coming in so fast, I need everything to happen in less than 1 second.

I've created an ObservableQueue<T> class which implements INotifyCollectionChanged and has a ConcurrentQueue as the underlying data type, whose TryDequeue operation is O(1).  Like the following:

 

public class ObservableQueue<T> : INotifyCollectionChanged, IEnumerable<T>
   {
       public event NotifyCollectionChangedEventHandler CollectionChanged;
       private readonly ConcurrentQueue<T> queue = new ConcurrentQueue<T>();

       public void Enqueue(T item)
       {
           queue.Enqueue(item);
           if (CollectionChanged != null)
               CollectionChanged(this,
                   new NotifyCollectionChangedEventArgs(
                       NotifyCollectionChangedAction.Add, item, queue.Count - 1));
       }

       public T Dequeue()
       {
           T result;
           bool dequeued = (queue.TryDequeue(out result));
           if (CollectionChanged != null && dequeued)
           {
               CollectionChanged(this,
                   new NotifyCollectionChangedEventArgs(
                       NotifyCollectionChangedAction.Remove, result, 0));
           }
           return result;
       }

       public T First()
       {
           T item;
           queue.TryPeek(out item);
           return item;
       }

       public IEnumerator<T> GetEnumerator()
       {
           return queue.GetEnumerator();
       }

       IEnumerator IEnumerable.GetEnumerator()
       {
           return GetEnumerator();
       }
   }

My new implementation of the code to update the collection is as follows:

public void Add(List<RawDataPoint> ldp)
{
    foreach (RawDataPoint dp in ldp)
    {
        _Real.Enqueue(new DataPoint(dp.Time, dp.Value));
        if ((dp.Time.Add(-dataTimeSpan) > _Real.First().Time))
        {
                _Real.Dequeue();  // this is an Order(1) operation.
        }
    }
}

However I can't get the solution to work.  Either it locks up my UI or I get a "Collection was modified during enumeration" exception.

Is there any way to better implement a limited size collection where I can remove the first value in O(1) time?

[Gareth]

I've updated my ObservableQueue<T> class to include functions for both "SuspendNotifications()" and "ResumeNotifications()" similar to the RadObservableCollection.  The new class is as follows.

public class ObservableQueue<T> : INotifyCollectionChanged, IEnumerable<T>
{
    public event NotifyCollectionChangedEventHandler CollectionChanged;
    private readonly ConcurrentQueue<T> queue = new ConcurrentQueue<T>();
    private bool NotifyCollectionChanged = true;

    private IList<T> _AddedItems;
    private IList<T> _RemovedItems;

    public ObservableQueue()
    {
        _AddedItems = new List<T>();
        _RemovedItems = new List<T>();
    }

    public void Enqueue(T item)
    {
        queue.Enqueue(item);
        if (CollectionChanged != null)
        {
            if(NotifyCollectionChanged)
            {
                CollectionChanged(this, new NotifyCollectionChangedEventArgs(NotifyCollectionChangedAction.Add, item, queue.Count - 1));
            }
            else
            {
                // Keep a collection of new items to notify of on resume.
                _AddedItems.Add(item);
            }
        }
    }

    public T Dequeue()
    {
        T result;
        bool dequeued = (queue.TryDequeue(out result)); // this is an Order(1) operation.
        if (CollectionChanged != null && dequeued)
        {
            if(NotifyCollectionChanged)
            {
                CollectionChanged(this, new NotifyCollectionChangedEventArgs(NotifyCollectionChangedAction.Remove, result, 0));
            }
            else
            {
                // Keep a collection of items to remove to notify on resume
                _RemovedItems.Add(result);

            }
        }
        return result;
    }

    public T First()
    {
        T item;
        queue.TryPeek(out item);
        return item;
    }

    public IEnumerator<T> GetEnumerator()
    {
        return queue.GetEnumerator();
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }

    public void SuspendNotifications()
    {
        this.NotifyCollectionChanged = false;
    }

    public void ResumeNotifications()
    {
        this.NotifyCollectionChanged = true;

        if(_AddedItems.Count > 0)
        {
            CollectionChanged(this, new NotifyCollectionChangedEventArgs(NotifyCollectionChangedAction.Add, _AddedItems));
        }

        if(_RemovedItems.Count > 0)
        {
            CollectionChanged(this, new NotifyCollectionChangedEventArgs(NotifyCollectionChangedAction.Remove, _RemovedItems));
        }

        _AddedItems.Clear();
        _RemovedItems.Clear();
    }
}

The Add method now includes a "Suspend" call at the start and a "Resume" call at the end to trigger this.  However when I run the app I get an InvalidCastException thrown by Telerik.Windows.Controls.Chart.dll.  It's being raised in my ResumeNotifications() method on the "CollectionChanged" line.

It says "Cannot implicitly cast List<DataPoint> to DataPoint.  I'm using a valid overload on CollectionChanged.

My chart is setup as follows:

01.<telerik:RadCartesianChart Grid.Row="1">
02.    <telerik:RadCartesianChart.Grid>
03.        <telerik:CartesianChartGrid MajorLinesVisibility="XY">
04.            <telerik:CartesianChartGrid.MajorYLineStyle>
05.                <Style TargetType="{x:Type Line}">
06.                    <Setter Property="Stroke" Value="LightGray"/>
07.                </Style>
08.            </telerik:CartesianChartGrid.MajorYLineStyle>
09.            <telerik:CartesianChartGrid.MajorXLineStyle>
10.                <Style TargetType="{x:Type Line}">
11.                    <Setter Property="Stroke" Value="LightGray"/>
12.                </Style>
13.            </telerik:CartesianChartGrid.MajorXLineStyle>
14.        </telerik:CartesianChartGrid>
15.    </telerik:RadCartesianChart.Grid>
16.    <telerik:RadCartesianChart.VerticalAxis>
17.        <telerik:LinearAxis Title="Rx0,Rx1" LabelFormat="G"/>
18.    </telerik:RadCartesianChart.VerticalAxis>
19.
20.    <telerik:RadCartesianChart.HorizontalAxis>
21.        <telerik:DateTimeContinuousAxis
22.                MajorTickLength="10"
23.                LabelInterval="2"
24.                LabelFormat="hh:mm:ss.fff"
25.                FontFamily="Segoe UI"
26.                PlotMode="OnTicks" LabelFitMode="MultiLine" Title="Time" IsStepRecalculationOnZoomEnabled="False">
27.        </telerik:DateTimeContinuousAxis>
28.    </telerik:RadCartesianChart.HorizontalAxis>
29.    <telerik:SplineSeries RenderMode="Light" ItemsSource="{Binding Model.RawData.CapRx_0.Collection}" CategoryBinding="{StaticResource categoryBinding}" ValueBinding="{StaticResource valueBinding}"/>
30.    <telerik:SplineSeries RenderMode="Light" ItemsSource="{Binding Model.RawData.CapRx_1.Collection}" CategoryBinding="{StaticResource categoryBinding}" ValueBinding="{StaticResource valueBinding}">
31.        <telerik:SplineSeries.StrokeShapeStyle>
32.            <Style TargetType="Path">
33.                <Setter Property="Stroke" Value="Green" />
34.                <Setter Property="StrokeThickness" Value="2" />
35.            </Style>
36.        </telerik:SplineSeries.StrokeShapeStyle>
37.    </telerik:SplineSeries>
38.</telerik:RadCartesianChart>

 

 

[Gareth]

In case it makes a difference, my categoryBinding and valueBinding classes are as follows:

public class CategoryBinding : GenericDataPointBinding<DataPoint, DateTime>
{
    public CategoryBinding()
    {
        this.ValueSelector = (dp) => dp.Time;
    }
}

public class ValueBinding : GenericDataPointBinding<DataPoint, Double>
{
    public ValueBinding()
    {
        this.ValueSelector = (dp) => dp.Value;
    }
}

[Peshito]

Hello Gareth,

Thank you for describing your issue in details. I tried to reproduce it in a similar sample project according to your requirements where the data is being populated on every 800th millisecond and the UI updated on every 10th second. The collection I used is of type RadObservableCollection as you did.

If I understood you correctly the issue you experience is caused by the fact that there is a lack of performance when the data is being refreshed. If this is so, I suggest you to use the Direct 2D Rendering mechanism that the RadChartView control supports.

If this does not help, could you prepare a small runnable project reproducing the issue so I could debug it locally and give you a more appropriate solution. As this is a forum thread you could either log a support ticket with the sample project attached or use a third party web site for files sharing.

Regards,
Peshito
Telerik

[Gareth]

Thanks Peshito, I'm having some more success with the rendering now that I've enabled Direct2D options.

I now have another issue whereby some of the data points in my line series seem to be being plotted on the graph with the same X-Axis value (DateTimeContinuousAxis) despite them being different.

If two values have the same DateTime value in terms of Hours:Minutes:Seconds, does the graph control then look for the difference in Milliseconds and then to ticks?  Or what's the smallest unit it inspects?

[Gareth]

<telerik:ChartDataSource x:Name="CapRx0DataSource" ItemsSource="{Binding Model.RawData.CapRx_0.Collection}" SamplingThreshold="{Binding SamplingThreshold}" />

 <telerik:RadCartesianChart Grid.Row="1" x:Name="CapGraphRX">
                                    <telerik:RadCartesianChart.VerticalAxis>
                                        <telerik:LinearAxis Title="Rx0, Rx1" IsStepRecalculationOnZoomEnabled="False" LabelFormat="#.00E-00" />
                                    </telerik:RadCartesianChart.VerticalAxis>
                                    <telerik:RadCartesianChart.HorizontalAxis>
                                        <telerik:DateTimeContinuousAxis
                                                LabelInterval="5"
                                                LabelFormat="hh:mm:ss.fff"
                                                PlotMode="OnTicks" LabelFitMode="MultiLine" Title="Time">
                                        </telerik:DateTimeContinuousAxis>
                                    </telerik:RadCartesianChart.HorizontalAxis>
                                    <telerik:LineSeries RenderOptions="{Binding RenderOptions}" ItemsSource="{Binding ElementName=CapRx0DataSource}" CategoryBinding="{StaticResource categoryBinding}" ValueBinding="{StaticResource valueBinding}"/>
                                    <telerik:LineSeries RenderOptions="{Binding RenderOptions}" ItemsSource="{Binding ElementName=CapRx1DataSource}" CategoryBinding="{StaticResource categoryBinding}" ValueBinding="{StaticResource valueBinding}">
                                        <telerik:LineSeries.StrokeShapeStyle>
                                            <Style TargetType="Path">
                                                <Setter Property="Stroke" Value="Green" />
                                            </Style>
                                        </telerik:LineSeries.StrokeShapeStyle>
                                    </telerik:LineSeries>
                                </telerik:RadCartesianChart>

 

Here is how I have my Graph Setup at the moment and as you can see in the attached image, some of the values are showing as vertical lines, making me think there's 2 values with the same DateTime existing in the collection.

However I have written a method to determine whether the value being added has the same DateTime value as the previous one and if so, is not adding it to the collection, so I don't know why this is happening.

[Peshito]

Hello Gareth,

Please find attached a sample project I worked on. It contains the code snippets you shared. I am however unable to reproduce the issue. I assume the reason behind it is caused by the fact that you have datapoints with DateTime values pretty close to each other. The DateTimeContinuous axis does not plot the data points with equal intervals but in dependence with their exact DateTime value. Hence if there are two datapoints having really close DateTime values it will seems like if they had the same Category values.

Another thing worth mentioning is that in the ObservableQueue's CollectionChanged method, you are using wrong NotifyCollectionChangedEventArgs overload passed as an argument. This however is working well when ChartDataSource is used.

Could you please take a look at the project, attached, modify it so the issue become reproducible and attach it back to this thread. As this is a forum thread you could either submit a new support ticket or use a third party web site for files sharing.

Regards,
Peshito
Telerik

[Gareth]

Thanks for the demo app Peshito, it was an error on my part that was causing the values to display with the same DateTime value.

I'm still struggling with the graph when it comes to displaying 25,000 data points in total.  On my machine the graph control seems to struggle once it reaches the 3000 data point mark and is running in real-time.

Could you provide me with a Demo application with a CartesianGraphControl with 2 Line Series, each series containing 25,000 data points and updating every second?  If that is possible with this control then I'd love to see how it is done.

[Peshito]

Hi Gareth,

Please find attached a modified version of the sample I used earlier. It behaves fine and there are no performance issues having a series with 25 000 points updating on every 100 milliseconds. Have you defined a point template for your series? If so, this might be causing the issue.

I would also like to ask you to update the sample or attach a runnable copy of yours in order to be able to further assist you in resolving this issue.

Regards,
Peshito
Telerik

[Gareth]

I've updated your sample to mirror my situation exactly, however I can't get it to work.

 

https://www.dropbox.com/s/7t03uu3bf7ezyvu/wpf_ChartView_990567-Updated-By-Gareth.zip?dl=0

[Gareth]

Slight alteration from what I uploaded.

The MaxPointsCount should be 25600 and there should be 2 series visible on the graph.  I tried to test it using 1 series with double the points, just out of curiosity but forgot to change it back prior to uploading.  Apologies.

[Peshito]

Hello Gareth,

Thank you for updating the sample. The reason for the slow performance in this case is caused by the fact that you are removing a data point item 256 times on each timer tick. This causes the collection having 50600 points to shift 256 times and this is a slow operation.

I prepared and attached another approach that you could use. The idea behind it is to reuse the data points you already have and update their values. This is the most appropriate performance solution for this scenario. Please take a look at the project attached and feel free to modify it so it could fit your needs. What is important in the sample is the UpdateSeries method used for updating the existing data points with values of the newly created data points. Another important method is the GetOrCreateDataPoint handling the creation of the data points.

We also have AsyncData SDK demo that demonstrates possible approach of handling async data which I recommend as it could be usable for you.

Hope this helps.

Regards,
Peshito
Telerik