2 ms·

Nice work, thanks! I'll have a look later, the only part I didn't get was [^1], could you elaborate? About the ArrayStack, I wanted a stack backed by a fixed

by codr7 2y ago

Nice work, thanks! I'll have a look later, the only part I didn't get was [^1], could you elaborate? About the ArrayStack, I wanted a stack backed by a fixed array, because my suspicion was using a fixed array for fundamental collections would be faster. Hence the VM.Config object to set the max sizes. There is also a DynamicArrayStack that supports reallocation, which is currently used by OrderedMap. The plan is to eventually benchmark the alternatives, but start with the simplest thing that could possibly work.

neonsunset 2y ago
Here, calling `.Last()` on `ArrayStack<T>` traverses it from the start. `.Last()` is a static extension method defined on `System.Linq.Enumerable` class and has a signature `static T Last<T>(this IEnumerable<T> source)`. Internally, `.Last()` will try to optimize for the common cases where a type implements `IList<T>` and uses an indexer to simply get the last element. However, because ArrayStack<T> does not implement IList<T>, .Last() does not know that this is possible, therefore costs O(n) as noted above. Instead, we can simply use an index operator `[^1]` which gets the first element from end, which is short-hand for `[stack.Count - 1]`. Other than that, it’s a good idea to lean towards out-of-box tools to avoid investing effort into reinventing another language within C# and use spans for slicing data types - you almost never need to call methods like Array.ConstrainedCopy - this is something quite ancient. The idiomatic way of copying a portion of array today is `source.AsSpan(start, length).CopyTo(dest)`, slicing destination as well if you need so. The prime slice types in .NET are Span<T> and ReadOnlySpan<T>, and can wrap memory of any origin.
- codr7 2y ago
  Just the kind of information/expertise I was looking for, awesome!
  - zebracanevra 2y ago
    And you can find that specilisation here: https://source.dot.net/#System.Linq/System/Linq/Last.cs,80 https://source.dot.net/#System.Linq/System/Linq/Last.cs,80
    - Capricorn2481 2y ago
      Why does the implementation of .Last not just check if .Count? It seems like there are things that don't implement IList but can still be indexed by the last entry?
      - neonsunset 2y ago
        In a strongly typed compiled language, how would you do so (in a type-safe and performant way) only knowing that the type is some IEnumerable<T> implementation and not a particular shape that may or may not adhere to the `T this[int i]` and `.Count //of T` contract?
        Capricorn2481 2y ago
        Is using reflection for a quick property check that much of a performance hit? After all, avoiding it leads to footguns like this where someone didn't realize they were traversing an entire array. I'm not well versed on this topic.
  - neonsunset 2y ago
    Thank you too!

by codr7 2y ago

neonsunset 2y ago

Here, calling `.Last()` on `ArrayStack<T>` traverses it from the start. `.Last()` is a static extension method defined on `System.Linq.Enumerable` class and has a signature `static T Last<T>(this IEnumerable<T> source)`. Internally, `.Last()` will try to optimize for the common cases where a type implements `IList<T>` and uses an indexer to simply get the last element. However, because ArrayStack<T> does not implement IList<T>, .Last() does not know that this is possible, therefore costs O(n) as noted above. Instead, we can simply use an index operator `[^1]` which gets the first element from end, which is short-hand for `[stack.Count - 1]`. Other than that, it’s a good idea to lean towards out-of-box tools to avoid investing effort into reinventing another language within C# and use spans for slicing data types - you almost never need to call methods like Array.ConstrainedCopy - this is something quite ancient. The idiomatic way of copying a portion of array today is `source.AsSpan(start, length).CopyTo(dest)`, slicing destination as well if you need so. The prime slice types in .NET are Span<T> and ReadOnlySpan<T>, and can wrap memory of any origin.

codr7 2y ago
Just the kind of information/expertise I was looking for, awesome!
- zebracanevra 2y ago
  And you can find that specilisation here: https://source.dot.net/#System.Linq/System/Linq/Last.cs,80 https://source.dot.net/#System.Linq/System/Linq/Last.cs,80
  - Capricorn2481 2y ago
    Why does the implementation of .Last not just check if .Count? It seems like there are things that don't implement IList but can still be indexed by the last entry?
    - neonsunset 2y ago
      In a strongly typed compiled language, how would you do so (in a type-safe and performant way) only knowing that the type is some IEnumerable<T> implementation and not a particular shape that may or may not adhere to the `T this[int i]` and `.Count //of T` contract?
      - Capricorn2481 2y ago
        Is using reflection for a quick property check that much of a performance hit? After all, avoiding it leads to footguns like this where someone didn't realize they were traversing an entire array. I'm not well versed on this topic.
- neonsunset 2y ago
  Thank you too!