tavianator

Didn't Google have a tool for this called MOE (Make Open Easy) like 15 years ago? I remember it from some of my open source contributions to Guice

> Airplanes don't have wings

???

No: https://en.wikipedia.org/wiki/Sony_Computer_Entertainment_Am...

Presumably that's just a mistake. The author calls it "stochastic gradient descent" correctly elsewhere in the article

I did try it a while ago and it wasn't profitable, but that was before I added stat() support. Batching those is probably good

My bfs project also uses io_uring: https://github.com/tavianator/bfs/blob/main/src/ioq.c

I'm curious how lsr compares to bfs -ls for example. bfs only uses io_uring when multiple threads are enabled, but maybe it's worth using it even for bfs -j1

You may want to look into improvements to A* for grids, like Rectangular Symmetry Reduction.

> There was no other helix db

https://en.wikipedia.org/wiki/Helix_(database)

They were referencing the title of a specific paper, which invented type classes: https://dl.acm.org/doi/10.1145/75277.75283

The C standard (since C99) says that `main()` has an implicit `return 0`, you don't need to write it explicitly.

I was looking for a relevant paper and found this one, which isn't what I was looking for but is related: https://sigops.org/s/conferences/hotos/2023/papers/liargkova...

My actual "production" implementation of this concept does support that: https://github.com/tavianator/bfs/blob/main/configure

But I wanted the blog post sized version to be simpler for exposition.

Just tried reconfiguring LLVM:

    27.24s user 8.71s system 99% cpu 36.218 total

Admittedly the LLVM build time dwarfs the configuration time, but still. If you're only building a smaller component then the config time dominates:

    ninja libc  268.82s user 26.16s system 3246% cpu 9.086 total

Fixed! https://github.com/tavianator/tavianator.com/commit/aa9d99d5...

Nice! I used to do something similar, don't remember exactly why I had to switch but the two step process did become necessary at some point.

Just from a quick peek at that repo, nowadays you can write

#if __has_attribute(cold)

and avoid the configure test entirely. Probably wasn't a thing 10 years ago though :)

Whoops! Forgot to do that when I switched from a ``` block to raw html

You might be interested in rawhide[1] or fselect[2]. (Note: I don't really use them myself, but they seem to offer something like what you're suggesting.)

Also, this is still a find-style syntax, but my bfs utility supports -exclude [3]. So you can write

    bfs -type f -exclude -path ./excluded_dir

which is a bit more ergonomic.

[1]: https://github.com/raforg/rawhide

[2]: https://github.com/jhspetersson/fselect

[3]: https://github.com/tavianator/bfs/blob/main/docs/USAGE.md#-e...

At least with GNU coreutils, you can use `-r`/`--relative`

Someday I will get that functionality into fd :)

I've replaced Valgrind with sanitizers for most of my workflow. Using the sanitizer APIs in your custom allocator is also easy: https://github.com/tavianator/bfs/blob/main/src/sanity.h https://github.com/tavianator/bfs/blob/31dffd6441ba80ea998ce...

Very interesting, thanks! If I get time I'll try to measure every instruction to see the whole set of affected instructions.

Wrote up the presumed explanation here: https://tavianator.com/2025/shlxplained.html

In general I'd be very surprised if code alignment had much effect on a 10,000 instruction block, especially since the instruction is 5 bytes long so it will quickly unalign itself

> Wait a sec, isn’t this backwards?

No, if you push and pop RCX it's fast again. I mentioned this in the blog post, `mov rcx, 1` is slow but `mov rcx, 1; push rcx; pop rcx` is fast.

Right. Actually it turns out it's 11 bits, since [-1024, 1023] are all supported by the immediate add renamer.

In general I think people are overstating the delay of an additional 64-bit add on register file reads (though I'm not a hardware guy so maybe someone can correct me). There are carry-lookahead adders with log_2(n) == 6 gate delays. Carry-save adders might also be relevant to how they can do multiple dependent adds with 0c latency.

> And, presumably, the OP shift case here is in fact a case of there not being a built-in immediate adder and thus a need for fixup uops being inserted to materialize it?

No, the perf counters show 1 uop dispatched/retired in both the slow and fast cases.

Benchmark code is in the post! The trick is to limit the number of SHLX instructions before you re-initialize RCX. Doing it every 10,000 keeps it fresh enough. I didn't have to disable preemption or anything, perf shows 0 context switches and only ~50 page faults (probably all at startup).

I did try aligning the loop, it didn't matter

SAL and SHL are synonyms, they have the same encoding. SHL only accepts CL as the count register, there's no other form that takes a variable shift count

SHL suffers from the same latency issue as SHLX it turns out