Some updated Vec benchmarks

[NWoodsman]

I benchmarked the vecs, and got this result using BenchmarkDotNet:

Demonstrates that the vecs are really good compared to dot net's default ImmutableList<T> however a bog standard mutable list is still the king.

[julesjacobs]

Thanks for the benchmarks. Indeed, if possible, use a mutable vector. It is impossible to beat that with an immutable vector :) Which operations are you benchmarking?

[NWoodsman]

It was just a clone of your benchmark, adding 1_000_000 ints.

In this run, I compared mutable List<T> with ImmutableList<T>.Builder as it is included in the standard library as a 'cheap' way to work with immutable collections (convert to mutable and then back). I also included a miscellaneous test unpack to test coverting to immutable after 500_000 items and then unpacking/repacking the last 500_000. (Implementations are in the gist below)

https://gist.github.com/NWoodsman/2bb2875b020435ee0811f86acd890fd2

Funny that the half-way interruption actually improved performance slightly.

[julesjacobs]

You might try to implement a builder for the other immutable vectors. I think that would give you a good speedup as well!

[julesjacobs]

Does that help performance in C#? I'm not up to date on .NET performance

[NWoodsman]

Not really. I'm just trying to understand the code. I'm hitting two bottlenecks, the nested structs that are using generic type constraints and the bit shifting. If you could say a word or two describing what the bit shifting is doing, it would help me (i'm new to that)

Otherwise I've been pretty up to date on other language features, readonly record struct might be applicable here which could have performance implications.

Once I understand the bit shifting, I can possibly clean up the single-implementation interfaces.

[julesjacobs]

The bit shifting is adjusting the index in order to find the right child vector to index into. It's a bit complicated to explain, but it may help to try it out on some examples in the debugger and see what is happening.

[NWoodsman]

@julesjacobs The shift amount is 32^x = where x is the number of steps deep of the bucket from root....and instead of using some sort of depth variable to track this, you use nested generics, i.e. Root<Root<Root<>>> etc. That's why you need the new R().Shift call, since the depth is semi-arbitrary at runtime and it's easier to rely on the nested generics to subtract -5 per each depth.

Anything else you can share, I would appreciate, thanks!

[julesjacobs]

Yes you are right. I don't know if that's the most efficient way to do it. Maybe you can find a more efficient way?

[NWoodsman]

[NWoodsman]

I guess in general would you prefer 1. A branch with multiple changes 2. Multiple small PRS 3. you prefer not to work on this anymore... lol.

[julesjacobs]

Great! I've added you to the repo