414owen

no profile record

Submissions

A faster bump allocator for rust

6 pointsby 414owenเดือนที่แล้ว0 comments

A faster bump allocator for rust

6 pointsby 414owenเดือนที่แล้ว0 comments

Speeding up tree-sitter-haskell 50x

8 pointsby 414owen3 ปีที่แล้ว1 comments

{n} times faster than C

447 pointsby 414owen3 ปีที่แล้ว237 comments

comments

7 เดือนที่ผ่านมาdiscuss

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 ปีที่แล้วdiscuss

Word.

2 ปีที่แล้วdiscuss

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

3 ปีที่แล้วdiscuss

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

3 ปีที่แล้วdiscuss

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 ปีที่แล้วdiscuss

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 ปีที่แล้วdiscuss

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 ปีที่แล้วdiscuss

Kind words, much appreciated!

3 ปีที่แล้วdiscuss

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 ปีที่แล้วdiscuss

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 ปีที่แล้วdiscuss

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 ปีที่แล้วdiscuss

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 ปีที่แล้วdiscuss

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 ปีที่แล้วdiscuss

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 ปีที่แล้วdiscuss

> 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 ปีที่แล้วdiscuss

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

3 ปีที่แล้วdiscuss

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 ปีที่แล้วdiscuss

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

4 ปีที่แล้วdiscuss

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

4 ปีที่แล้วdiscuss

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 =