414owen

no profile record

Submissions

A faster bump allocator for rust

6 pointsby 414owenw zeszłym miesiącu0 comments

A faster bump allocator for rust

6 pointsby 414owenw zeszłym miesiącu0 comments

Speeding up tree-sitter-haskell 50x

8 pointsby 414owen3 lata temu1 comments

{n} times faster than C

447 pointsby 414owen3 lata temu237 comments

comments

7 miesięcy temudiscuss

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

2 lata temudiscuss

Word.

2 lata temudiscuss

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

3 lata temudiscuss

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

3 lata temudiscuss

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.

3 lata temudiscuss

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.

3 lata temudiscuss

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 `>`

3 lata temudiscuss

Kind words, much appreciated!

3 lata temudiscuss

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.

3 lata temudiscuss

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?

3 lata temudiscuss

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

3 lata temudiscuss

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

3 lata temudiscuss

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.

3 lata temudiscuss

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 the post, but maybe there's potential for a future post, where I pad the input string and vectorize the algorithm :)

3 lata temudiscuss

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

3 lata temudiscuss

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

3 lata temudiscuss

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.

3 lata temudiscuss

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

4 lata temudiscuss

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

4 lata temudiscuss

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 =