Improve on Union performance

[nathanmascitelli]

Description

In looking at our application which uses the dotnet Unleash client we found that a large amount of memory was being allocated by the client:

Looking at the callstack the Union call in DefaultUnleash.DetermineIsEnabledAndStrategy is what is allocating so many arrays. These allocations can be reduced by replacing the Union call with a preallocated HashSet (which is what Union uses).

Type of change

• [x] Bug fix (non-breaking change which fixes an issue)

How Has This Been Tested?

The following BenchmarkDotnet code was used to validate that this was better performing:

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;

var summary = BenchmarkRunner.Run<UnionExamples>();

Console.WriteLine(summary);

[MemoryDiagnoser]
public class UnionExamples
{
    const int Length = 1000;

    readonly IEnumerable<ExampleConstraint> first;
    readonly IEnumerable<ExampleConstraint> second;

    public UnionExamples()
    {
        first = Enumerable.Range(0, Length).Select(i => new ExampleConstraint { Id = i }).ToList();
        second = Enumerable.Range(0, Length).Reverse().Select(i => new ExampleConstraint { Id = i }).ToList();
    }

    [Benchmark(Baseline = true)]
    public int Union() => first.Union(second).Count();

    [Benchmark]
    public int Preallocate()
    {
        var unique = new HashSet<ExampleConstraint>(first);
        unique.UnionWith(second);
        return unique.Count;
    }

    [Benchmark]
    public int ConcatDistinct() => first.Concat(second).Distinct().Count();
}

class ExampleConstraint { public int Id { get; set; } }

With the results being:	Method	Mean	Error	StdDev	Ratio	RatioSD	Gen0	Gen1	Allocated	Alloc Ratio
Union	53.58 us	1.055 us	1.215 us	1.00	0.00	12.2681	4.0283	150.72 KB	1.00
Preallocate	45.31 us	0.666 us	0.713 us	0.84	0.02	5.4932	1.3428	67.35 KB	0.45
ConcatDistinct	64.52 us	0.762 us	0.712 us	1.20	0.03	12.2070	4.0283	150.77 KB	1.00

So my proposed change uses less CPU and memory then the current Union.

[daveleek]

Thank you for your contribution @nathanmascitelli! we'll have a look!

[sighphyre]

Hey @nathanmascitelli, thanks so much for this contribution, this is awesome!

Kinda curious though, I feel like the numbers here are a bit extreme, any chance you could share how many feature toggles you have in your Unleash instance? I'm just trying to find out if the SDK here is chewing through an excessive amount of memory or if you genuinely have a lot of toggles and this is just streamlining that

[nathanmascitelli]

@sighphyre we have 326 flags at the moment. I assumed this was a large number and that's why this hasn't been a problem for others. We are working on reducing the number of flags.

[sighphyre]

@nathanmascitelli Oh. Oh dear. No that's not a large number at all, that's well within reason for the computations (might be a little bit large for users to understand whats going on with their flags in their system though). For some context here, a similar sized feature set uses less than 15MB of RAM in our Edge server under load. And roughly a quarter of the numbers you're reporting for 40K toggles

Gosh time for some optimisation. Thank you so much for the information!

[nathanmascitelli]

@sighphyre sorry I'm not sure I follow your last statement. Are you saying its time for optimization of the dotnet client or my application? If my application, can you give some guidence on what optimizations you're thinking of? We are just calling IsEnabled on the IUnleash client created by UnleashClientFactory. Admittedly maybe we are calling it too much or something...

[sighphyre]

@nathanmascitelli Sorry! That was super unclear of me! I mean that the Unleash team probably needs to look this one over and see where the SDK is using these resources. Gut feel is that this isn't your application

[nathanmascitelli]

@sighphyre oh I would never count me out for doing something silly :). Jokes asside, thanks for clearing that up. I'm happy to help if I can.