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

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

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.

Sure thing.

I'm not sure what your current level is, but I can give some general advice for people that happen upon this:

---

Haskellers are generally expected to understand most of the typeclassopedia (https://wiki.haskell.org/Typeclassopedia), don't worry about learning it all in one go. I had to read this page many times before I grokked most of it.

---

Avoid tutorials that overuse analogies. A Monad only adds one operation to Applicative:

  class Monad m where
    (>>=)  :: m a -> (a -> m b) -> m b

---

It's important to be really good at using Monads that support multiple effects, to create little DSLs. If I want a component of my program to support throwing errors, creating a log, and reading an environment, (all purely), I'd use something like this:

  type MyDSL
    = ReaderT Environment
        (WriterT [String]
          (Except ErrorType))

Where I work we use free monads instead of monad transformers, but that's just an implementation detail, it's used the same as a transformer stack.

---

Create a cool project, Haskell people like languages. When I was interviewing I showed off a tiny lisp-like language implemented in Haskell (https://github.com/414owen/phage). This was my first non-trivial Haskell project so don't judge it too harshly.

---

Read Haskell Weekly (https://haskellweekly.news/newsletter.html). It's a great source of ideas and knowledge.

---

A lot of Haskell shops use, or are migrating towards using, nix (https://nixos.org/).

---

Apply! The Haskell market seems to favor the interviewee. In the end, I had more than one offer, even for my first Haskell job.

Good luck!

I write Haskell professionally, and I can confidently say that there are plenty of jobs. Some large tech companies (eg. Facebook, GitHub, Twitter), quite a few banks, a lot of consultancy companies, and plenty of random companies I'd never heard of.

It is quite difficult to get a first Haskell job though, because they mostly require production Haskell experience, so there's your chicken and egg problem.

@wheybags I recommend achieving defined-before-use quicksort by throwing in some unnecessary Haskell syntax extensions:

  qs :: Ord a => [a] -> [a]
  qs = \case
    [] -> []
    (x : (partition (< x) -> (qs -> as, qs -> bs))) -> as <> [x] <> bs

I'm very sorry OP didn't stay the course, and opted to write an angry post instead.

Every few months some newbie comes along to the Haskell reddit and asks why is Haskell documentation so confusing, and the post get destroyed by people telling them to get good or just pointing at academic papers.

The Haskell subreddit has a monthly 'Hask Anything', and is generally a friendly forum.

I searched: https://www.reddit.com/r/haskell/search/?q=documentation%20&... and was unable to find any such behavior. In fact, people asking for documentation were generally helped: https://www.reddit.com/r/haskell/comments/eo7orr/where_to_fi...

“Haskell doesn’t suck, the development environment does”

There are certainly people who would agree with this, however our language server is pretty complete nowadays, we have amazing static analysis tools, a variety of formatters, I can't think of any tooling I desperately miss. Then again, I'm an editor person, not an IDE person...

Write types and interfaces for the types and fill in the blanks. Sounds familiar? Because that’s we’ve been doing with Java and the like using UML

Ouch. It's very rare to hear anyone complain about having a type system with strong guarantees. UML... Well I guess I'm not a fan of specifying your design outside of your source code...

Professional developers find themselves describing the system in such concrete ways using types that when the requirements change suddenly their precious castle is reduced to dust

Hmm, so generally the better at Haskell you are, the more you express constraints in terms of Haskell constraints, rather than concrete types. It's a style called `Tagless Final`. I recommend taking a look. It gives you strong guarantees, without breaking any castles.

Somehow Haskellers think that they are more productive with Haskell when the reality in the real world is that only a few languages can proudly make that claim, such as Python and Lisp. These are languages battle tested in actual software products

As other people have pointed out, there are companies that use all three of these. I think it's safe to assume OP didn't measure the productivity of any developers before writing this.

Abstractions with types is a bad type of abstraction because it ignores the basic fact that programs deal with data, and data has no types

Have you heard of datatypes?

In most cases people are looking for schemas, not types

Schemas describe the structure of data. Types describe the structure of data.

Types wrap data and treat it like a black box whereas schema describes the shape and content of data

The former here is actually more of a slight on encapsulation, which is something you can do in Haskell, but is probably more a goto recommendation of OOP languages. It can be pretty useful to only expose the inferfaces you want, and hide the implementation.

most haskellers would agree that purescript is a better choice compared to GHCJS. No man is an island, and yet Haskellers generally convinced themselves that other languages need to learn from Haskell

Are you saying Purescript didn't learn from Haskell? Have you seen PureScript?

Instead of explaining Monads like all other design patterns out there, they insist on using some obscure definition from category theory to explain it

Pick a monad explanation that suits you. There are plenty of posts / tutorials online. Some people like burritos, some people like mathematics. I recommend looking at the type of (>>=), as in the end, that's the only operation a Monad adds (above Applicative)...

Look, when monads are used without the infix notation, the result is horrendous and it looks like yet another callback chain

I think you mean when they're used without `do notation`. This point seems moot, seeing as we have do notation. Explicit binds can be readable, if you're going pointfree.

I tried it myself. Of course, there are very smart people who do understand Monads, but most people would just tell you to “get an intuition for it”, which to be honest is total BS

You'll get there, I recommend leaving the do-notation behind, and writing some functions over Maybe, [], and Writer.

Don't give up on the learning process, there's still time to write a `How I learned Haskell` blog post, or maybe you can write the umpteenth Monad tutorial :)