Very slow performance of Lst and Map

[NeutraChikara]

Hello,

Avid user of LanguageExt here. I have run into some problems with the Lst and Map structs being very slow.

I can't really figure out what's causing it (a simple equality comparison between the same two lists of strings are fast both for the built in list and LanguageExt Lst).
But I've written two tests to demonstrate the Lst slowness when using Distinct, which is how I discovered the issue.

    internal record SomeData(IEnumerable<string> SomeStrings)
    {
        public IEnumerable<string> SomeStrings { get; } = SomeStrings;
    }

    public class Example
    {
        [Fact]
        public void LangExtListPerformance()
        {
            var langExtList = List("");
            var list = List(
                new SomeData(langExtList),
                new SomeData(langExtList)
            );

            list.Distinct().Consume(); // Very slow
        }

        [Fact]
        public void BuiltInListPerformance()
        {
            var builtInList = new List<string> { "" };
            var list = List(
                new SomeData(builtInList),
                new SomeData(builtInList)
            );

            list.Distinct().Consume(); // Much faster
        }
    }

The tests yields this result

I have done the same thing for Map

        [Fact]
        public void MapPerformance()
        {
            var map = Map((1, ""));
            map.Find(1).ShouldBeSome();
        }

        [Fact]
        public void BuiltInDictPerformance()
        {
            // Simulate the behavior of Map using Try and ToOption
            var map = new Dictionary<int, string> { [1] = "" };
            Try(() => map[1]).ToOption().ShouldBeSome();
        }

Which yields this result

This prevents me from using these (otherwise awesome) structs in some cases. Especially Map hurts to use, since looking up a value is so slow, which is what you tend to use Map for (or at least that's what I use it for ;) ).

[louthy]

Obviously Lst and Map do a lot more work than the mutable built-in types, so I would expect a performance difference. Although they seem quite large. I'll have a look tomorrow.

In the meantime, you could try Seq instead of Lst, it is close to the performance of List for everything other than adding new items, but even then it's not far off. And HashMap is an order of magnitude faster than Map, because it uses a much more advanced data-structure.

There are some benchmarks for comparing like-for-like (to Microsoft's ImmutableCollections library)