ValueCollections repository

[Joy-less]

I made a repository containing some more ref struct types you might be interested in.

Currently contains ValueList:

using ValueList<int> list = [];

for (int i = 0; i < 100; i++) {
    list.Add(i);
}

Console.WriteLine(string.Join(", ", list.ToList()));

Method	Mean	Error	StdDev	Gen0	Allocated
SmallListOfStruct	17.92 ns	0.122 ns	0.114 ns	0.0255	80 B
SmallValueListOfStruct	15.14 ns	0.050 ns	0.047 ns	-	-
SmallListOfClass	25.69 ns	0.077 ns	0.069 ns	0.0306	96 B
SmallValueListOfClass	18.36 ns	0.037 ns	0.033 ns	-	-
LargeListOfStruct	21,131.86 ns	119.642 ns	111.913 ns	41.6565	131400 B
LargeValueListOfStruct	7,454.80 ns	11.838 ns	10.494 ns	-	-

Link: https://github.com/Joy-less/ValueCollections

[linkdotnet]

Interesting. You might want to add a set of fixed SmallLists like: ThreeELementList that uses also the InlineArrayAttribute.
All in all - you should publish this as a Nuget packages as well if you see fit.

PS: I can't access your repository.

[Joy-less]

Apologies, I forgot to set it to public.
The small lists are an interesting idea. What kind of use case do you have in mind?

[linkdotnet]

Me, personally, non specific. But sometimes you are in need of those super specific collection types.
But they probably don’t make sense in an library.

that said, you already published a nuget package! Way to go!

[Joy-less]

I also added ValueHashSet which uses an ordered Span<T> synchronized with a Span<int> of hash codes, and does a binary search to find the insertion index.

using ValueHashSet<int> numbers = [];

for (int n = 1; n <= 5; n++) {
    numbers.Add(n);
}
for (int n = 3; n <= 7; n++) {
    numbers.Add(n);
}

Console.WriteLine(string.Join(", ", numbers.ToArray())); // 1, 2, 3, 4, 5, 6, 7

It's slower than HashSet but it's zero-allocation.

Method	Mean	Error	StdDev	Gen0	Gen1	Gen2	Allocated
SmallHashSetOfStruct	94.20 ns	0.662 ns	0.620 ns	0.1070	-	-	336 B
SmallValueHashSetOfStruct	137.42 ns	0.616 ns	0.577 ns	-	-	-	-
SmallHashSetOfClass	130.56 ns	0.762 ns	0.675 ns	0.1173	-	-	368 B
SmallValueListOfClass	163.45 ns	0.554 ns	0.518 ns	-	-	-	-
LargeHashSetOfStruct	186,989.50 ns	1,425.253 ns	1,263.450 ns	95.2148	95.2148	95.2148	538656 B
LargeValueHashSetOfStruct	227,245.29 ns	603.642 ns	564.647 ns	-	-	-	-

At some point I'll have to implement ValueDictionary... maybe some other time.

@linkdotnet One change I made that might be relevant to ValueStringBuilder is to move the buffer constructor to a static method.

// Old:
using ValueList<int> numbers = new(stackalloc int[32]);
// New:
using ValueList<int> numbers  = ValueList<int>.FromBuffer(stackalloc int[32]);

This could be changed in ValueStringBuilder to avoid confusion as well. The only problem is that it would be a major breaking change.

[Joy-less]

We do offer both versions, don't we?
1: Span: https://linkdotnet.github.io/StringBuilder/api/LinkDotNet.StringBuilder.ValueStringBuilder.html#LinkDotNet_StringBuilder_ValueStringBuilder__ctor_Span_System_Char__
2. ROS: https://linkdotnet.github.io/StringBuilder/api/LinkDotNet.StringBuilder.ValueStringBuilder.html#LinkDotNet_StringBuilder_ValueStringBuilder__ctor_ReadOnlySpan_System_Char__

Or do I miss something obvious here? :D

Yes, they are both offered, my point though is that someone might pass a Span expecting it to be appended as the initial characters, when really it is used as a buffer and the characters are ignored. For example, someone might pass an array of initial characters and not realise that it's used as a buffer, which doesn't append the characters; it treats it like it's zeroed-out.

[linkdotnet]

True that - we can add the OverloadResolutionPriorityAttribute to favor ReadOnlySpan over Span.a

[linkdotnet]

For example, someone might pass an array of initial characters and not realise that it's used as a buffer, which doesn't append the characters; it treats it like it's zeroed-out.

I gave that a second thought, and the only thing that happens is if you proactively create a Span<char>. Converting strings to a "span-like" objects will always result in ROS. Passing a writeable object to a method that expects something writeable - well - then we write :D

[Joy-less]

For example, someone might pass an array of initial characters and not realise that it's used as a buffer, which doesn't append the characters; it treats it like it's zeroed-out.

I gave that a second thought, and the only thing that happens is if you proactively create a Span<char>. Converting strings to a "span-like" objects will always result in ROS. Passing a writeable object to a method that expects something writeable - well - then we write :D

Might want to make it clear/bold in the doc comment to make sure.

[linkdotnet]

Oh good point. I might add this even to the XML-Doc.

[Joy-less]

I added ValueDictionary because it felt incomplete without it.

using ValueDictionary<string, string> strings = [];

strings.Add("food", "pizza");
strings.Add("drink", "cola");

Console.WriteLine(string.Join(", ", strings.ToArray())); // [food, pizza], [drink, cola]

Performance is comparable to ValueHashSet since it uses the same binary search approach but with KeyValuePair<TKey, TValue>.

[Joy-less]

You might want to add a set of fixed SmallLists like: ThreeELementList that uses also the InlineArrayAttribute.

I finally did this and added lists like ValueList128, generated for capacities of [1, 2, 3, 4, 8, 16, 32, 64, 128, 256, 512].

ValueList128<int> numbers = [];

for (int n = 0; n < 10; n++) {
    numbers.Add(n);
}

Console.WriteLine(string.Join(", ", numbers.Where(number => number % 2 == 0))); // 0, 2, 4, 6, 8

Some interesting points about this implementation:

• Since the buffer is an inlined array, it can live on the heap and therefore can be a normal struct and supports normal LINQ.
• Structs cannot create a span over themselves without copying, so the AsSpan method is an extension method using this ref.
• They are copied implicitly just like normal structs.

Performance-wise, unfortunately there is almost no improvement to spans/array-pools, so I don't think there's much point doing this for ValueStringBuilder.

[linkdotnet]

Interesting, I would have expected some gains from the inlinearrays.
I guess there are some less allocations by definition.

[Joy-less]

I did some deeper benchmarking and I got mixed results.

Example:

[Benchmark]
public int SmallListOfStruct() {
    List<int> list = [1, 2, 3, 4, 5];
    list.Add(6);
    list.Add(7);
    list.Add(8);
    return list.IndexOf(3);
}

Results:

Method	Mean	Error	StdDev	Gen0	Allocated
SmallListOfStruct	35.68 ns	0.508 ns	0.424 ns	0.0459	144 B
SmallValueListOfStruct	17.67 ns	0.094 ns	0.088 ns	-	-
SmallValueList8OfStruct	11.52 ns	0.037 ns	0.035 ns	-	-
SmallValueList16OfStruct	11.82 ns	0.071 ns	0.066 ns	-	-
SmallValueList32OfStruct	18.21 ns	0.025 ns	0.019 ns	-	-
SmallValueList128OfStruct	31.07 ns	0.223 ns	0.208 ns	-	-

So the fixed-size lists can be more performant, but not by much.

[linkdotnet]

I am not sure if the sample size is too small and the benchmark should be restructured. There might be a lot „noise“ inside your benchmark size given the small sample size.