ReactiveList creation performance

[megafinz]

Do you want to request a feature or report a bug?

Neither, I guess it would be an improvement request.

What is the current behavior?

Currently ReactiveList<T> is quite expensive to create in comparison to ObservableCollection<T> which is a problem in case you have thousands of them created at the same time.

If the current behavior is a bug, please provide the steps to reproduce and if possible a minimal demo of the problem

        var count = 20000;
        var rls = new List<ReactiveList<string>>();
        var ocs = new List<ObservableCollection<string>>();

        var sw = Stopwatch.StartNew();
        for (var i = 0; i < count; ++i)
        {
            rls.Add(new ReactiveList<string>());
        }
        sw.Stop();
        Console.WriteLine(sw.ElapsedMilliseconds);

        sw.Restart();
        for (var i = 0; i < count; ++i)
        {
            ocs.Add(new ObservableCollection<string>());
        }
        sw.Stop();
        Console.WriteLine(sw.ElapsedMilliseconds);

On my machine it takes about 1200ms to create ReactiveLists and 25ms to create ObservableCollections (that's almost 50 times longer).

What is the expected behavior?

It would be nice if creation time of ReactiveLists would be comparable to that of ObservableCollections.

What is the motivation / use case for changing the behavior?

I'd like to lessen the performance impact of creating ReactiveLists in my code. Currently it takes around 20% of overall execution time of that specific code to create them.

Which versions of ReactiveUI, and which platform / OS are affected by this issue? Did this work in previous versions of ReativeUI? Please also test with the latest stable and snapshot (http://docs.reactiveui.net/en/contributing/snapshot/index.html) versions.

We're using ReactiveUI 7.1.0 on Windows for WPF desktop application development.

Other information (e.g. stacktraces, related issues, suggestions how to fix)

Performance profiling shows that the bottleneck sits in the ReactiveList.setupRx method and more specifically in this place (Observable.Subscribe, Profiler Screenshot):

CountChanging.Where(_ => this.areChangeNotificationsEnabled()).Subscribe(_ => this.RaisePropertyChanging("Count"));
CountChanged.Where(_ => this.areChangeNotificationsEnabled()).Subscribe(_ => this.RaisePropertyChanged("Count"));
IsEmptyChanged.Where(_ => this.areChangeNotificationsEnabled()).Subscribe(_ => this.RaisePropertyChanged("IsEmpty"));
Changing.Where(_ => this.areChangeNotificationsEnabled()).Subscribe(_ => this.RaisePropertyChanging("Item[]"));
Changed.Where(_ => this.areChangeNotificationsEnabled()).Subscribe(_ => this.RaisePropertyChanged("Item[]"));

[olevett]

Not sure if this will actually solve your issue, but DynamicData has a variety of helpers and bindings into ReactiveUI. I'll try and get a look into what ReactiveUI is doing, but that doesn't sound ideal!

[megafinz]

Not sure if this will actually solve your issue

I'm not sure either, SourceList does not implement INotifyCollectionChanged so it's can't be used instead of ReactiveList for UI binding.

[kentcb]

Thanks for the issue, @megafinz. Which platform did you measure on? Did you warm up the JIT before measuring? Release build?

[megafinz]

Which platform did you measure on?

.NET 4.6.1, WPF Desktop Application, Windows 10.

Did you warm up the JIT before measuring?

I tried ForceJIT-technique shown in this article, but it gains virtually nothing (around 50ms less of total 2000ms call).

Release build?

Yep.

[kentcb]

Thanks again for reporting this @megafinz.

I've been wanting to dig into performance analysis for a while now, mainly because of issues I've experienced on Android. I used this as something of an excuse to get started.

First of all, I created a harness console project and installed BenchmarkDotNet. I then created these tests:

public class ReactiveListTests
{
    [Benchmark]
    public object CreateReactiveList() => new ReactiveList<string>();

    [Benchmark]
    public object CreateObservableCollection() => new ObservableCollection<string>();

    [Benchmark]
    public object CreateList() => new List<string>();
}

The output on my machine is:

                     Method |           Mean |      StdDev |  Gen 0 | Allocated |
--------------------------- |--------------- |------------ |------- |---------- |
         CreateReactiveList | 15,487.6848 ns | 442.4254 ns | 2.2461 |   6.18 kB |
 CreateObservableCollection |     24.6115 ns |   0.7515 ns | 0.0287 |      64 B |
                 CreateList |     14.5345 ns |   0.3513 ns | 0.0105 |      24 B |

This staggering difference in performance confirms your findings. When I dug into it, I found that the primary culprit was indeed within the setupRx method, but specifically it's the subscriptions with where clauses.

I created a separate harness project that does not even use ReactiveUI. Instead, it just uses Rx and has these tests:

public class Tests
{
    [Benchmark]
    public void CreateSubject()
    {
        var subject = new Subject<string>();
    }

    [Benchmark]
    public void CreateSubjectAndSubscribe()
    {
        var subject = new Subject<string>();
        subject.Subscribe(this.Handler);
    }

    [Benchmark]
    public void CreateSubjectAndWhere()
    {
        var subject = new Subject<string>();
        subject.Where(s => s == null);
    }

    [Benchmark]
    public void CreateSubjectAndWhereSubscribe()
    {
        var subject = new Subject<string>();
        subject.Where(s => s == null).Subscribe(this.Handler);
    }

    private void Handler(string s)
    {
    }
}

Here are the results for Rx 2.2.5 (the version that currently must be used with ReactiveUI):

                         Method |          Mean |     StdErr |     StdDev |  Gen 0 | Allocated |
------------------------------- |-------------- |----------- |----------- |------- |---------- |
                  CreateSubject |     3.1057 ns |  0.0242 ns |  0.0939 ns | 0.0055 |      12 B |
      CreateSubjectAndSubscribe |    70.4401 ns |  0.6057 ns |  2.3457 ns | 0.0366 |      84 B |
          CreateSubjectAndWhere |    25.1264 ns |  0.2732 ns |  1.0581 ns | 0.0141 |      32 B |
 CreateSubjectAndWhereSubscribe | 1,232.8842 ns | 13.7644 ns | 59.9975 ns | 0.2223 |     564 B |

This confirms the terrible (and puzzling) performance of combining Where with Subscribe.

Curious, I tried with Rx 3.3.1 as well:

                         Method |          Mean |    StdErr |     StdDev |  Gen 0 | Allocated |
------------------------------- |-------------- |---------- |----------- |------- |---------- |
                  CreateSubject |     3.4672 ns | 0.0379 ns |  0.1467 ns | 0.0055 |      12 B |
      CreateSubjectAndSubscribe |    69.5999 ns | 0.4029 ns |  1.5603 ns | 0.0371 |      84 B |
          CreateSubjectAndWhere |    26.9942 ns | 0.1980 ns |  0.7140 ns | 0.0136 |      32 B |
 CreateSubjectAndWhereSubscribe | 1,059.3617 ns | 5.1781 ns | 20.0548 ns | 0.1961 |     500 B |

The situation is improved a little here, but nowhere near enough.

That's as far as I've gotten for now, and probably as far as I can go until I have VS2017 and can compile Rx itself (doesn't build with VS2015). Just thought I'd record my notes so I can come back to this later, and so that others can follow along and provide any input.

[paulpdaniels]

I'd be curious if this is just a Where issue. If it is unique to that operator it should be easier to optimize. But if it is systemic to how operators are created, then that could pose a bigger issue.

[kentcb]

@paulpdaniels I had exactly the same kinds of questions bouncing around my head as I tried to fall asleep last night. Here's some updated tests:

public class Tests
{
    [Benchmark]
    public void CreateSubject()
    {
        var subject = new Subject<string>();
    }

    [Benchmark]
    public void CreateSubjectAndSubscribe()
    {
        var subject = new Subject<string>();
        subject.Subscribe(this.Handler);
    }

    [Benchmark]
    public void CreateSubjectAndWhere()
    {
        var subject = new Subject<string>();
        subject.Where(s => s == null);
    }

    [Benchmark]
    public void CreateSubjectAndWhereSubscribe()
    {
        var subject = new Subject<string>();
        subject.Where(s => s == null).Subscribe(this.Handler);
    }

    [Benchmark]
    public void CreateSubjectAndDoSubscribe()
    {
        var subject = new Subject<string>();
        subject.Do(_ => { }).Subscribe(this.Handler);
    }

    [Benchmark]
    public void CreateSubjectAndWhereCustomSubscribe()
    {
        var subject = new Subject<string>();
        subject.WhereCustom(s => s == null).Subscribe(this.Handler);
    }

    [Benchmark]
    public void CreateSubjectAndWhereInSubscribe()
    {
        var subject = new Subject<string>();
        subject.Subscribe(
            x =>
            {
                if (x == null)
                {
                    this.Handler(x);
                }
            });
    }

    private void Handler(string s)
    {
    }
}

public static class ObsExt
{
    public static IObservable<T> WhereCustom<T>(this IObservable<T> @this, Func<T, bool> predicate)
    {
        return Observable
            .Create<T>(
                observer =>
                {
                    return @this
                        .Subscribe(
                            t =>
                            {
                                if (predicate(t))
                                {
                                    observer.OnNext(t);
                                }
                            });
                });
    }
}

And the results:

                               Method |          Mean |     StdDev |  Gen 0 | Allocated |
------------------------------------- |-------------- |----------- |------- |---------- |
                        CreateSubject |     2.7307 ns |  0.0588 ns | 0.0055 |      12 B |
            CreateSubjectAndSubscribe |    64.5907 ns |  0.9030 ns | 0.0368 |      84 B |
                CreateSubjectAndWhere |    24.6428 ns |  0.7624 ns | 0.0136 |      32 B |
       CreateSubjectAndWhereSubscribe |   977.7915 ns | 27.2801 ns | 0.1918 |     500 B |
          CreateSubjectAndDoSubscribe | 1,014.4568 ns |  3.8825 ns | 0.1935 |     504 B |
 CreateSubjectAndWhereCustomSubscribe |   502.8067 ns |  5.4911 ns | 0.2107 |     496 B |
     CreateSubjectAndWhereInSubscribe |    68.8369 ns |  2.0436 ns | 0.0369 |      84 B |

So this is certainly systemic :( Interestingly, collapsing the two operations into the subscription improves performance considerably. I applied this idea to ReactiveList itself and re-ran the tests:

                     Method |          Mean |     StdErr |      StdDev |  Gen 0 | Allocated |
--------------------------- |-------------- |----------- |------------ |------- |---------- |
         CreateReactiveList | 7,066.1903 ns | 36.7655 ns | 137.5638 ns | 1.2838 |   3.45 kB |
 CreateObservableCollection |    22.9333 ns |  0.2316 ns |   0.8971 ns | 0.0289 |      64 B |
                 CreateList |    13.9471 ns |  0.0567 ns |   0.1881 ns | 0.0105 |      24 B |

So performance more than twice as good as it was. Of course, I'm not advocating this as a solution, just presenting the facts. I'd much rather this be solved upstream so all can benefit.

And in all these results, notice the strong correlation between allocations and performance. I suspect the key here is to just allocate less.

[paulpdaniels]

For reference here is what gets called when creating a Where operator: https://github.com/Reactive-Extensions/Rx.NET/blob/v2.2.5/Rx.NET/Source/System.Reactive.Linq/Reactive/Linq/QueryLanguage.StandardSequenceOperators.cs#L1382-L1478

I am most curious about the dual paths that exist, not sure what the distributed version uses. The surprising part seems to be that this comes from the subscribe and not during construction when I would have thought the most objects are being created.