414owen

Wow, okay. I would imagine this makes mathematicians quite angry? I guess you're responsible for all the operations you use in your proof being well-behaved.

It sounds like subtraction over Nats needs to be split into `sub?`, and `sub!`, the former returning an option, and the latter crashing, on underflow, as is the Lean convention?

To use the default `sub`, you should need to provide a witness that the minuend is >= the subtrahend...

The version with silent underflow is still useful, it should just be called `saturatingSub`, or something, so that mathematicians using it know what they're getting themselves into...

Word.

re2c works like a charm. I'm generally confident that I couldn't write faster scanners by hand if I tried.

This code was written a while ago, but I decided it merited a write-up recently.

I have DietPi running on a Raspberry pi Zero W (armv6l), which is a system that's supported by barely any distros nowadays.

It was easy to preseed, has the absolute bare minimum amount of processes running, and is altogether a fantastic distro. Highly recommended.

This is pretty much `assembly language the game`: https://tomorrowcorporation.com/humanresourcemachine

It's not a useful architecture, but it teaches the thought process really well, and you end up discovering a lot of optimization naturally.

For this article, I'm measuring every step to see what the performance implications of the changes are, which, along with some educated guesses and some googling/reading other articles, was enough for me to figure out what was going on.

In part two (https://owen.cafe/posts/the-same-speed-as-c/) especially, I didn't know what was going on with the benchmarks for a long time. Eventually I got lucky and made a change, which led to a hypothesis, which lead to more tests, which led to a conclusion.

The array lookup approach taken in part two:

https://owen.cafe/posts/the-same-speed-as-c/

But taking the length of the string as a parameter is not, because that changes the problem statement (making the solution vectorizable)

Also note that you'll try to read element -1 of the input. You probably want to change the `>=` to a `>`

Kind words, much appreciated!

I guess the question is whether the compiler should optimize a function containing a loop for a single null terminator, or for more data.

I would suggest the latter is what you want most of the time.

There's also the option of running a quick check for the null terminator before the loop, and then optimizing the loop for the other options.

But in any case, I think the demonstration of the technique of rearranging branches is interesting, and I needed a program to apply it to.

So I actually did try that, but and IIRC it didn't produce a CMOV with either gcc or clang. I didn't put it in the repo because it wasn't an improvement (on my machine) and I decided not to write about it.

Maybe you get different results though?

That's the thing, a C compiler has all the information it needs to know that the maximum amount of times a '\0' can be processed in the loop is once (because the function returns), but there's no upper bound on the amount of times other characters are seen in the loop.

I might be missing a reason that this information of opaque to the compiler though, in which case, this section of the article is indeed lacking, but I'm happy to learn :)

Very interesting approach. I should probably have specified that the somewhat naive assembly in `02-the-same-speed-as-c/loop-5.x64.s` is the fastest version I have.

On my machine I'm getting 0.244s for `loop-5.x64.s` and 0.422s for your implementation above.

I'm not sure why exactly we're seeing this discrepancy, and for what it's worth your implementation looks faster to me. I guess this is why you need to always benchmark on the hardware you're going to be running the code on...

Nice! There's a part two in which I rewrote the C. I got a 12x speedup :)

https://owen.cafe/posts/the-same-speed-as-c/

And as others have pointed out, you can tweak the input, then vectorize the algo, if you want to go that route.

I considered this a pedagogical exercise and I sincerely hope nobody will start dropping down to assembly without a very good reason to.

The version that's friendly to the compiler is described in part two: https://owen.cafe/posts/the-same-speed-as-c/

It achieves 3.88GiB/s

I intentionally didn't go down the route of vectorizing. I wanted to keep the scope of the problem small, and show off the assembly tips and tricks in that post, but maybe there's potential for a future post, where I pad the input string and vectorize the algorithm :)

> because without FDO (or PGO) the compiler has no idea how likely each branch is to be taken

So, the maximum amount of times you can hit '\0' is once in the string, because then the function returns, but you can hit the other characters many times, which seems to be information a compiler has access to without PGO.

PGO does help, of course, and on my machine gives me 2.80s, which is better than the code at the end of the `Rearranging blocks` section :)

> I assume that their test input (which isn't described in the post, and is also not in their GitHub repo)

It's described under `Benchmarking setup`, and is in the repository here: https://github.com/414owen/blog-code/blob/master/01-six-time...

Side note: There's a part two to this post (linked at the bottom) where I make the C code as fast as I possibly can, and it beats all the assembly in this post.

I never said writing assembly is (necessarily) a good idea, I just find optimizing it, and deciphering compiler output, an interesting challenge, and a good learning opportunity.

Yes, I explained in the `Benchmarking setup` section that I used `march=native`, but I guess I forgot to mention I used -O3.

I'd probably look for a tech co-founder. Such a small percentage of startups make it, and having a learning-as-you-go tech team will not help those already small chances.

That said, passion and curiosity win out in the long run.

If you build a POC without the right expertise you might find the product needs rewriting from scratch pretty soon. That might be fine though.

A clickbait title for an in-depth look at hand-optimizing a very simple loop.

I would. A few basic requirements are: git, linux, a desktop computer (or to be allowed to use my own)

I'm using lemon to parse a programming language.

Lemon produces this report for my grammar:

    Parser statistics:
      terminal symbols...................    19
      non-terminal symbols...............    42
      total symbols......................    61
      rules..............................    75
      states.............................    56
      conflicts..........................     0
      action table entries...............   377
      lookahead table entries............   379
      total table size (bytes)...........  1433

It generates a parser that seems to be a reasonable size:

    $ wc src/parser.c
    2200 10090 78282 src/parser.c

I've tried a few other parser generators, lemon was my favourite.

re2c for tokenizing, and lemon for parsing =

I migrated my main personal project (a programming language written in C) to Tup recently. So far I love it, it seems to 'just work'. Some highlights:

No need to map header (or other) files to C files. Tup detects when files are read and adds them as implicit dependencies.

Environment variables (that are used) are considered build inputs, so no need to `make clean` when you need a build with debug symbols.

---

Admittedly my project is quite straightforward, but I thoroughly recommend giving Tup a try.

I think almost everyone who writes Haskell has in the past written in other languages, and clearly those who stick with it prefer it.

I'm personally far more productive in Haskell than in any other language I've tried. I don't know what's the Right Way, but it's the Best Way I've found so far.

Helix is my daily driver and it's got such nice defaults I haven't even bothered configuring it.

For modern code editing it's just faster. Everything's built in natively.

Thanks :)

I actually posted https://select.pink/ to HN ages ago, but it died in `new`: https://news.ycombinator.com/item?id=24959045

OP's game has some nice features. The timing is neat, and to be honest I didn't even consider using the source as the visualization.

Huh, I wrote a very similar game a while ago. Select elements with CSS selectors to get to the next level: https://select.pink/

Mine displays the elements as nested blocks, instead of printing a tree.

So, what's the plan? Reimplement every popular extension that doesn't have good performance?

> the asynchronous communication between the renderer and the extension-host severely limits how fast bracket pair colorization can be when implemented as an extension. This limit cannot be overcome

Nope, I'm not convinced. If it can be done internally, then you should expose more internals until it's possible to do it with the public API.

I bet this could be made really performant if vscode had incremental parsing, like tree-sitter+Atom.