Hacker News Reader

Comment by codr7 | Hacker News Reader

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 serious C# nerds, any assistance in making this thing run faster would be much appreciated.

It's not terrible atm, given a managed host language, but I'm sure there are plenty of knobs left to turn.

See the benchmarks section in the README for more info, and the same benchmarks ported to Python in python/fib.py.

Oh, and there's some undocumented yet potentially useful stuff in /Libs; strings, terminal control and IO mainly.

View on HN

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 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).

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-th... )

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.

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.

Interesting, Linq.Expression actually looks doable within my complexity budget.

For small short-lived scripts the compilation (in any native form) time may be much bigger than bytecode execution time. And if a platform does not support dynamic code generation the end result is non-functional code or interpreter inside interpreter for LINQ expressions (as they can still run as interpreted, at least they try). See a comment in Jint readme about that.

I tried to compare some script languages implemented in C# with Roslyn script compilation. Same code to sum up 1M doubles. Roslyn takes almost 100ms to compile the code.

This may become especially painful when source code changes on every execution and reusing compilation result is not possible for some reason, e.g. user input or parametrized string template.

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.

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 (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)

Interesting, thanks.

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!

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.

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.

Just the kind of information/expertise I was looking for, awesome!

And you can find that specilisation here: https://source.dot.net/#System.Linq/System/Linq/Last.cs,80

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?

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?

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.

Thank you too!

Alternatively ArrayStack could be modified to implement IList right?

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

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.

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 :)

> 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 :)

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

(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.g...

Just seem a bit backwards to start with a gitignore that ignores every possible tool one could use with a particular language, rather than going directory/file/pattern by directory/file/pattern. Hence my proposal for these people to take the contents of the github/gitignore repository, fold it all into one big file they can reuse in all their repos, and call it a day.

Like why is there a `.DS_Store` (which is specific to macOS) in the `core.gitignore` file? That belongs in the global `.gitignore` macOS users should have in their home directory, rather than including it in project specific .gitignore.

But I digress, not exactly a huge problem and I won't lose any sleep over it :)

One of the problems in having a single gitignore to ignore all the possible things that there's no strict superset without overlaps. Visual Studio uses files called .user that contain user-specific metadata that should never be committed to source control and other systems might use .user for components that should be committed to source control. Breaking it down by language ecosystem seems an adequate compromise as few repos use multiple languages and when they do there's often a folder hierarchy to respect with nested gitignores.

Reply on news.ycombinator.com