5 ms·

Author here. I'm afraid I've been out of the C# loop too long to know what's fast and what isn't these days. Now that maybe I have the attention of some serio

• neonsunset 2y ago
  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
  • 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
  By all means, keep them coming people :) We just roughly doubled the speed by changing one line of code, that means there's plenty more fun before it gets really tricky. My issue isn't really profiling, its not knowing enough about the platform to do anything constructive with the hot spots.
  • mst 2y ago
    I don't know the platform and would -guess- that this won't actually help, but it's sufficiently fascinating I thought I'd share anyway: https://trout.me.uk/lisp/vlist.pdf https://trout.me.uk/lisp/vlist.pdf (roughly "stitching together efficient cons lists out of arrays") (and /lisp/ has an index if you want to see the other random lisp-related stuff I've collected copies of so I can find it again later)
    • codr7 2y ago
      Interesting, thanks.
• lloydatkinson 2y ago
  I haven't had chance to look over the code but I know that using Span for parsing might be a nice thing to try out. Have you considered making it compile to IL? Or if not that, using the Roslyn API to compile it to C# which is then automatically faster as a result of being compiled. Then getting AOT (ahead-of-time compilation) at build time gives you improved perf basically for free. I see neon has contributed a perf change, I know that he's an expert at using https://github.com/dotnet/BenchmarkDotNet https://github.com/dotnet/BenchmarkDotNet so hopefully you'll be able to do some scientific tests soon. I would love to see another language here for the *Common* Language Runtime (CLR, the core of .NET).
  • pjc50 2y ago
    Bit of a tradeoff there; so long as it's using its own bytecode, the sharpl executable itself can easily be AOT. Once you start trying to create your own assembly at runtime and run that, it's a LOT of work to get the host to still AOT (because you have to include the dotnet runtime anyway to run the inner assembly!) And AOT isn't a lot of free perf; it's mostly equivalent to JIT, the big advantage is faster and smaller startup. (I have used the Roslyn compile API; it's pretty cool but you do have to do more setup. e.g. https://joshvarty.com/2016/01/16/learn-roslyn-now-part-16-the-emit-api/ https://joshvarty.com/2016/01/16/learn-roslyn-now-part-16-th... )
  • codr7 2y ago
    Sure thing, Span is one of the features I haven't had time to dig into yet. Parsing is a one time thing though. Yes, different levels of compiling to C# are definitely on the table as options; for performance, but also to hopefully be able to generate self contained executables. Even just generating my own bytecode for faster startup.
  • WorldMaker 2y ago
    A fun middle ground to compiling to IL is using System.Linq.Expression<T> as a compiler. This was the middle ground that the "DLR" (Dynamic Language Runtime) used to great effect. System.Dynamic is still in the BCL and still useful, even though the dreams of IronPython and IronRuby and interop between them are sort of dead/dormant. System.Dynamic.DynamicMetaObject is still a fun thing to play with in how much power it gives you do some surprisingly optimized dynamic language things, all using System.Linq.Expression<T> as the higher level intermediate language than raw IL.