chrka

Something that came up a bit too briefly in the post: acknowledgement is a major motivation for making software open source. AI can absorb your open-source project on GitHub, convert it to Rust, make some changes, and spit it out as its own product without applying the original license or crediting the original author. My former open-source project is now no longer open source.

I'm currently working on the browser editor for my programming language, With the smart tab completion - which parses the entire program up to the cursor every time you press tab - you can avoid a bunch of typing and also potential errors.

You type: radius=10<enter>gc<tab><tab>50 50 r<tab><shift-enter> And right away, you have a circle on the screen.

https://easylang.online/ide/

They say they don't do that. But maybe I should be more skeptical.

That's exactly why my previous public GitHub repo is now private.

I've written something like this in C - including resulting assembler code for ARM and x86.

https://easylang.online/blog/branchless

Exactly. Just like using LibGen is prohibited.

I also recently made an open-source project with 200 GitHub stars private. I never had a problem with others using it as the basis for their own projects. In fact, that happened, and I received credit for it. But LLMs just hoover up everything, process it, and then spit it back out as if it were their own.

Therefore it is srand(1).

Both versions use the same input data. I also tried different random initial values and got essentially the same result. I didn't test hundreds of inputs, since that would have been mostly a waste of time in this case. The algorithm and the data distribution remain practically the same. What I'm measuring is the machine code that Clang generates for the hot loop.

You're talking about the complexity of the Quicksort algorithm, whereas the article is about code generation.

Both versions sort the same data using the same algorithm. Just a tiny change in the source code caused Clang to generate different machine code.

Using different seed values - (srand(1), srand(2), srand(time(NULL))) essentially leads to the same result. With a good choice of pivot, Quicksort is very close to O(n log n) in practice, so that’s not the key factor here.

The interesting thing is that the generated machine code changes significantly.

Don't trust your compiler. Your code is only fast if you're lucky.

https://tiki.li/blog/lucky_code.html

Normally, quicksort works best on random data. But with 90% already sorted and 10% random, it actually becomes harder to pick a good pivot. Sometimes the pivot ends up too large, which creates very uneven splits. When that happens, the algorithm switches to heapsort to avoid worst-case behavior, but heapsort is slower. Now, instead of immediately switching, it tries to partition again. Only if it’s still bad does it fall back to heapsort. That’s why performance improves.

As for your party trick: The performance drop in "blqs" occurred because heapsort was applied directly to a poorly partitioned input. Quicksort now gets a second chance in this case. With 10% random, 90% sorted, the performance drop no longer occurs. It is now faster than std::sort.

You will now see the directory listing. This website was actually created for my primary side project: a simplified programming language for beginners. I just added a blog folder there for other things as well.

Branchful only wins via ILP when data becomes good predictable. But since Quicksort partitioning aims for a 50/50 split, it operates in the worst possible zone for a branch predictor. That's why branchless wins here, as proven by the benchmarks.

Author here. No, it's also called from the non_trivially_copyable branch (as a fallback). I'll fix that.