Improve SelectVariant performance

[nathanmascitelli]

Description

In continuing to look for performance hotspots after the latest release, VariantUtils.SelectVariant was identified as an area for improvement.

In the PR three changes were made to improve performance:

• totalWeight was not needed, per the docs this will always be 100%. This removes the Sum call which loops over the list of variants.
• The FirstOrDefault call was removed, this allows for us to loop over the list of variants only once.
• We check if there are any overrides before calling Any.

Type of change

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

How Has This Been Tested?

Using BenchmarkerDotNet the following benchmarks were run:

[MemoryDiagnoser]
public class BenchmarksNoOverride
{
    readonly ActivationStrategy defaultStrategy = new ActivationStrategy("default", new Dictionary<string, string>());

    readonly FeatureToggle toggle;
    readonly UnleashContext context;

    public BenchmarksNoOverride()
    {
        var variantOverride = new VariantOverride("userId", "11", "12", "123", "44");
        var v1 = new VariantDefinition("a", 33, new Payload("string", "asd"), new List<VariantOverride>());
        var v2 = new VariantDefinition("b", 33);
        var v3 = new VariantDefinition("c", 34);
        var vOverride = new VariantDefinition("a", 33, new Payload("string", "asd"), new List<VariantOverride> {variantOverride});
        toggle = new FeatureToggle(
                    "test.variants",
                    "release",
                    true,
                    false,
                    new List<ActivationStrategy> { defaultStrategy },
                    new List<VariantDefinition> { v1, v2, v3 });

        context = new UnleashContext
        {
            UserId = "11",
            SessionId = "sessionId",
            RemoteAddress = "remoteAddress",
            Properties = new Dictionary<string, string>()
        };
    }

    [Benchmark(Baseline = true)]
    public Variant Current() => VariantUtils.SelectVariant(toggle.Name, context, toggle.Variants);

    [Benchmark]
    public Variant New() => VariantUtils.SelectVariantNew(toggle.Name, context, toggle.Variants);
}

[MemoryDiagnoser]
public class BenchmarksWithOverride
{
    readonly ActivationStrategy defaultStrategy = new ActivationStrategy("default", new Dictionary<string, string>());

    readonly FeatureToggle toggle;
    readonly UnleashContext context;

    public BenchmarksWithOverride()
    {
        var variantOverride = new VariantOverride("userId", "11", "12", "123", "44");
        var v1 = new VariantDefinition("a", 33, new Payload("string", "asd"), new List<VariantOverride>());
        var v2 = new VariantDefinition("b", 33);
        var v3 = new VariantDefinition("c", 34, null, new List<VariantOverride> { variantOverride });
        toggle = new FeatureToggle(
                    "test.variants",
                    "release",
                    true,
                    false,
                    new List<ActivationStrategy> { defaultStrategy },
                    new List<VariantDefinition> { v1, v2, v3 });

        context = new UnleashContext
        {
            UserId = "11",
            SessionId = "sessionId",
            RemoteAddress = "remoteAddress",
            Properties = new Dictionary<string, string>()
        };
    }

    [Benchmark(Baseline = true)]
    public Variant Current() => VariantUtils.SelectVariant(toggle.Name, context, toggle.Variants);

    [Benchmark]
    public Variant New() => VariantUtils.SelectVariantNew(toggle.Name, context, toggle.Variants);
}

These produced the following results:

Benchmarks with no VariantOverride

Method	Mean	Error	StdDev	Ratio	Gen0	Allocated	Alloc Ratio
Current	345.7 ns	3.06 ns	2.39 ns	1.00	0.0634	800 B	1.00
New	129.4 ns	2.61 ns	3.11 ns	0.38	0.0196	248 B	0.31

Benchmarks with a VariantOverride

Method	Mean	Error	StdDev	Ratio	Gen0	Allocated	Alloc Ratio
Current	258.7 ns	5.12 ns	5.26 ns	1.00	0.0467	592 B	1.00
New	123.7 ns	2.30 ns	2.15 ns	0.48	0.0196	248 B	0.42

In both cases the new code uses less CPU and memory.

[nathanmascitelli]

@gardleopard thanks for catching the failing tests. I should have caught that they were not running.

I've pushed a fix for most of the tests but there are still 21 failing, all from ClientSpecificationTests.

If I look at the variants from these tests I see that in many cases the weights don't add up to 100 (for example Feature.Variants.B pictured below):

From what I understand from reading the documentation on variant weights this is not a valid state for variants to be in. The way to fix the tests then is to update the variant weights in the test data.

Do you agree? I don't normally think that changing test data to fix tests is the right call but I believe the old code was catering for a situation that doesn't exist in production and so some of the tests do need to be updated.

[daveleek]

Thank you for the contribution @nathanmascitelli. We'll need to have a look at how this will affect distribution calculation. The client spec tests are common for all SDKs and a way for us to ensure identical behaviour across SDKs and platforms, so we should look at why they fail here and if there are performant improvements that can be made that ensure the SDK conforms to the spec

[nathanmascitelli]

Thank you for the contribution @nathanmascitelli. We'll need to have a look at how this will affect distribution calculation. The client spec tests are common for all SDKs and a way for us to ensure identical behaviour across SDKs and platforms, so we should look at why they fail here and if there are performant improvements that can be made that ensure the SDK conforms to the spec

OK that makes sense. I'm just going off what I see in the docs, there may obviouslly be some context or history that I'm missing.

The big thing with this change was to just reduce the number of times we loop over the list of variants. In the worst case scenario on main we could loop over the whole list three times (Sum, override check, target check). My change is an attempt to get this down to just once. If we have to add back the Sum that would still be an improvement.

[daveleek]

My change is an attempt to get this down to just once. If we have to add back the Sum that would still be an improvement.

Ok great! I think we might have to keep it for consistency and historical reasons, but I'll have a look at it!

[daveleek]

I think we have to remove the weight part of this PR, then we can merge and ship a new version. There are backwards compatibility/historical and general conformity among all SDKs reasons for keeping things as they are in that regard.

[nathanmascitelli]

@daveleek added the weight back.

[daveleek]

Great! Thank you @nathanmascitelli!