5 ms·

https://github.com/codr7/sharpl/pull/1 https://github.com/codr7/sharpl/pull/1 Was: 686 98 1195 Now: 226 79 293 (with net9.0 preview: 201 70 269, another relea

https://github.com/codr7/sharpl/pull/1 https://github.com/codr7/sharpl/pull/1 Was: 686 98 1195 Now: 226 79 293 (with net9.0 preview: 201 70 269, another release another free >10%) The reason for such a significant difference is that `ArrayStack<(int, int)>` only implements `IEnumerable<T>`, which prevented the Enumerable.Last(stack) call from seeing that the type has an indexer which can be used to quickly access the last element instead of traversing it in its entirety. Now, it still requires JIT (or, in this case, compiler back-end and ILC) to reason about the actual type of ArrayStack to optimize away type tests, inline Last() call and devirtualize indexer access, but the better option is simply replacing it with just [^1] which does the same on any indexable type. Generally speaking, it's recommended to use out of box collections whenever appropriate like Stack, List, etc. which already implement all the necessary interfaces which the standard library takes advantage of unless there's a specific need to do otherwise. Also, it is always nice to have .net's aot emit "canonical" native binaries, so it took me about 45s to find the bottleneck by bumping up the numbers in benchmarks.sl and clicking "Sample" in macOS's Activity Monitor. All in all, the code in the project is terse and thanks for showcasing it!

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!
adzm 2y ago
Alternatively ArrayStack could be modified to implement IList right?
- codr7 2y ago
  Right, already tried that; Last() is still slightly slower (I guess because of more layers of indirection).
diggan 2y ago
Interesting .gitignore addition. As someone who basically never writes C# (besides for some mods for games sometimes), is that the default ephemeral files that Visual Studio Code/some other tool writes when dealing with C# projects? Seems like an awful amount of trash if that's the case.
- neonsunset 2y ago
  As description in PR indicates, it’s just a default catch-all gitignore that you can add with ‘dotnet new gitignore’ that covers all kinds of tools and build artifacts, I see no reason to customize it. For large amounts of trash in project you would need to look for other languages, like JS ecosystem or certain Java-related projects :)
  - diggan 2y ago
    > As description in PR indicates, it’s just a default catch-all gitignore that you can add with ‘dotnet new gitignore’ that covers all kinds of tools and build artifacts, I see no reason to customize it. Ah, someone should just come up with a huge file so we can ignore every possible combination at this point :) > like JS ecosystem Heh, JS is probably the language that generates the least trash by default as it's just a index.html file + your single JavaScript file, nothing else required or generated at all, and now you have a interactive website :)
    - WorldMaker 2y ago
      GitHub doesn't have it all in one huge file, but has a somewhat comprehensive template repo of many ecosystems: https://github.com/github/gitignore https://github.com/github/gitignore (This is what is used to populate the templates if you ask GitHub to include a gitignore when creating a new repo, or if you add a new file to a Repo and name it .gitignore and get the template selector to show up.) I believe `dotnet new gitignore` basically shares the same template, even, as this file: https://github.com/github/gitignore/blob/main/VisualStudio.gitignore https://github.com/github/gitignore/blob/main/VisualStudio.g...

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!

adzm 2y ago

Alternatively ArrayStack could be modified to implement IList right?

codr7 2y ago
Right, already tried that; Last() is still slightly slower (I guess because of more layers of indirection).

diggan 2y ago

Interesting .gitignore addition. As someone who basically never writes C# (besides for some mods for games sometimes), is that the default ephemeral files that Visual Studio Code/some other tool writes when dealing with C# projects? Seems like an awful amount of trash if that's the case.

neonsunset 2y ago
As description in PR indicates, it’s just a default catch-all gitignore that you can add with ‘dotnet new gitignore’ that covers all kinds of tools and build artifacts, I see no reason to customize it. For large amounts of trash in project you would need to look for other languages, like JS ecosystem or certain Java-related projects :)
- diggan 2y ago
  > As description in PR indicates, it’s just a default catch-all gitignore that you can add with ‘dotnet new gitignore’ that covers all kinds of tools and build artifacts, I see no reason to customize it. Ah, someone should just come up with a huge file so we can ignore every possible combination at this point :) > like JS ecosystem Heh, JS is probably the language that generates the least trash by default as it's just a index.html file + your single JavaScript file, nothing else required or generated at all, and now you have a interactive website :)
  - WorldMaker 2y ago
    GitHub doesn't have it all in one huge file, but has a somewhat comprehensive template repo of many ecosystems: https://github.com/github/gitignore https://github.com/github/gitignore (This is what is used to populate the templates if you ask GitHub to include a gitignore when creating a new repo, or if you add a new file to a Repo and name it .gitignore and get the template selector to show up.) I believe `dotnet new gitignore` basically shares the same template, even, as this file: https://github.com/github/gitignore/blob/main/VisualStudio.gitignore https://github.com/github/gitignore/blob/main/VisualStudio.g...