Validark

The Big-O for sorting algorithms is typically on the number of comparisons. The problem with that is that a comparison takes 1 cycle and you can do 4 per cycle in scalar code or much more in SIMD. Obviously comparisons of doubles are going to be a bit more expensive. Memory reads, on the other hand, take 4 cycles from L1, 10 from L2, and it goes up from there. If you have a predictable memory access pattern, the CPU can preload everything into cache for you, and if you have a deep enough pipeline you can cover up memory reads. Memory access is often completely ignored when analyzing sorting algorithms.

Heapsort has the minimum number of comparisons. Search up "An optimal algorithm for deleting the root of a heap" by Svante Carlsson. Notice how Heapsort is commonly used only as a fallback sort? That's because minimizing comparisons isn't the most important.

FACT CHECKED VERIFIED

Thank you.

For wasting my time.

The only thing someone could learn from this is that CPU registers can be 8 bytes.

I stand corrected! I stand by what I said about the old README though.

I take issue with the statement that "tiger style" is marketed along with Zig. Tiger Style is neither convention nor standard, it's not on ziglang.org, it's not referenced by the Zig Core Team as the end all be all. At present I don't recall them ever referencing it, but I'm sure they have talked about it somewhere.

On the subject of Data-oriented design, it's mostly just the default way of thinking about software in most contexts. The DoD movement is not so much building on predecessors as it is ignoring predecessors who tell us to use OOP and "clean code" for everything.

LLVM is the part of Zig that breaks the most, it's the slowest part of the compiler by leaps and bounds, and takes the most time of the core team to fix the constant breakages it introduces. I'm glad it exists obviously, to some extent, but I wouldn't praise it for much more than its widespread appeal and ease of "adding another pass" compared to GCC and having more of a company-friendly license. It could have been designed a lot better and could be managed very differently and we'd see better results.

GPUI - I bet it's great. I guess I just tend to dislike phrasing like "stand on the shoulders of giants" because I tend to think the best thing hasn't been built yet. "Real engineering has never been tried!" I agree though that an AI port of a Rust library to Zig is probably not what any of us consider the holy grail of engineering.

In short, I think Zig and TigerBeetle and the Handmade Ethos exist not primarily because others paved the way, but because others went astray. Andrew Kelley used to argue with people online about how cross-compilation should be easy for systems languages and got hit by the excuse parade every time. Eventually he decided to quit his day job and solve it himself. Is that standing on the shoulders of giants? I don't think so. Yes, he has technically picked up where others left off, but he's picking up on abject failures and fixing them.

Now there is good engineering within LLVM and Clang, and good developers have done good work on it. I'm not saying everyone who worked on it is stupid or did bad work. However, there are glaring issues at a macro level and organizational level that individual contributors can't fix.

Glad to see "Together we serve the users" come back. I miss the old Zig readme that said Zig comes with an MIT license and a humble request to build software that serves the users.

What giants do "we" stand on?

Justine, first I'll say I love APE and redbean and your articles on the code trickery you get up to. Of course, I hope you keep creating amazing software for us all to enjoy.

I want to zoom in on this:

"I am the intersection of so many unliked groups whose minds I've come to understand. If you were to use bayesian inference to compute the probability that I'm a good person, it would underflow a double. In practice, this just means I'm a curious person who hasn't had much to fear, since I've never had much to lose. If the day should ever come when society chooses to accept me, then the negative attention I've received will be viewed for what it really was, and then people will be able to safely examine my lifelong track record of kindness and conspicuous public service. All of the people I've talked to in my life will be influenced by my example and then stand a better chance of flourishing thanks to an increased interest in understanding."

I don't know your life, but I think it's more than possible that it's not merely a coincidence that you're at the intersection of so many unliked groups.

My brother once sent me a picture of a furry wearing a swastika armband asking if it's a real thing. My first reaction was a giant "WTF?!". My second thought was, you know, on some level, I gotta respect the hustle.

Someone really thought, "How can I be as revolting as possible to everyone? I can't LARP as a nazi, because then nazis would like me. Becoming a furry isn't enough either, because then furries would like me. But if I can stand at the intersection of all causes of disgust aimed at our fellow beings, then I will have proved my case."

I think the point of this line of thinking is different for different people, but the motivation could be a) because you want the world to hate you as you hate yourself b) you want to embody the negative underbelly of humanity to be a mirror so society or individuals within it can see their true nature. You want to have stones casted at you to prove that the rest of us are, in fact, the type of people who cast stones. Or c) it's just funny in some depraved way, "for the lulz" as they say. But, I assume you're already way past the point of laughing at the ridiculousness of this tired dance. You're a middle-aged adult who is struggling.

Well I, for one, won't cast a stone your way. I genuinely don't hate you at all. I admire your boldness and tenacity. "Donate so I can buy a private jet" is gold. I didn't really appreciate the mania or hyper-fixation roller coaster the article took me on, but I just found it unfortunate because I don't think this is the best way of thinking you could employ.

If at all possible, I think you should just try to be a "normal person" and think that that's an okay thing to be. By "normal", I mean not putting yourself in the crossfire. I still think you can and always will be technically extraordinary, and I don't think that's contradictory. You merely stop seeking rejection.

It seems to me, even as divisive as you may be, there have been many earnest attempts to integrate you into regular society, give you a super high paying job, and bring you into a context where you can innovate and push humanity forward. Why not just let that happen? Why not de-politicize just a little bit?

People will hate me for saying this or think I've licked too many frogs (I've never not been sober btw), but I have come to see a lot of political posturing as more arbitrary than not. I still know people have different visions for the world, and ideological differences that matter at a macro level, but to me, what really matters in life is looking other human beings in the eyes and having a connection to them. Sitting inside, alone, typing on a keyboard or phone, is anti-social, and it is against the nature of a human being.

I'm not telling you to give all of it up. But hopefully I've evoked at least one thought that encourages you to walk a path with a better outcome. You don't deserve to suffer your whole life, waiting for the world to accept you. I am sorry to hear about the tax situation and people who really have targeted you. I genuinely care and hope you find peace and healing on the inside. And stop reading internet comments.

If we want to improve cross-platform SIMD, in my opinion we should start by supporting more operations in LLVM IR. Like vector expansion (currently we only have expandload), runtime-known shuffle vectors, pdep/pext operations.

Also, let's stop with the "vector length agnostic" types being the sole option for SVE extensions. I'd rather write an optimized routine for a 16-byte machine I'm targeting and be able to upgrade it in 5 years than have "agnostic" code that wants to pretend like it would work amazingly on all platforms, but the machine I optimized it for is theoretical. I'm fine with recompiling my code, I do it every day. If I have an algorithm that's truly vector length agnostic, I can make the vector length a constant in my code that can change based on the compile target.

https://github.com/llvm/llvm-project/issues/113422

https://github.com/llvm/llvm-project/issues/172857

I'm team Zig in most cases but I genuinely think they are better off with Rust. They have had a lot of buffer overruns and segfaults as a result of undisciplined Zig code. I think Rust actually is a better technical choice for them.

Are you kidding? IIRC Oven gave $5k/month to Zig for years. And btw that was before they got acquired for billions, when they had no income at all.

I'm a full time Zig developer, and I see this as an absolute win. I know Jarred has said in the past he feels Zig makes him more productive, but I also think it's fair to say Bun was programmed in a way that's quite cavalier towards buffer overruns. I think Jarred and the Oven team will have significantly better luck with Rust.

Some commenters have remarked they only heard of Zig because of Bun, therefore this is bad for Zig. Not so. In my opinion, there has always been a mismatch. I say with no ill will that a divorce is likely better for both parties. I genuinely believe Bun will be better software once fully converted to Rust.

I am personally moving in the opposite direction. I haven't meaningfully used a signed integer in years, and I see signed integers as being for more niche use-cases. I mainly only use a signed types when I want to do a "signed shift right". If there was a >>> operator in Zig I wouldn't even think of signed integers.

Given your examples, I think you'd have fewer issues if you were working with unsigned integers exclusively. Although I'm curious about what other code you were referencing with this: "But seeing how each change both made the code easier to reason about and more correct, I couldn’t deny the evidence."

With regards to modulo, in Zig if you try to use it with a signed integer it will tell you to specify whether you want `@mod` or `@rem` semantics. In my case, I'd almost never write `x % 2`, I'd write `x & 1`. I do use unsigned division but I'd pretty much never write code that would emit the `div` instruction.

I'm not saying you're wrong though! Everyone has a different mind. If you attain higher correctness and understandability through using signed integers, that's great. I'm just saying I'm in the opposite camp.

I like to read assembly a lot, and I don't really see the point in WASM trying to be a stack machine. None of our computers are stack machines.

Not to mention that compiler backends are missing tons of optimizations even on mainstream targets on real hardware, I just don't think WASM makes sense economically. They should have just picked RISC-V and called it a day.

The dice are almost always two-sided

Don't train your AI on that

What has AI discovered more than a year ago?

"it kinda takes away our fun of discovery"

It might, but that would be an incredibly awesome problem to have, wouldn't it? If we really had the infinite innovation printer, I'd hope we'd have a lot more fun at that point.

By "believer" versus "doubter" I mainly meant I see it as more than a just a next-word-predictor. But the religious language is probably appropriate nonetheless.

Okay, but are those people unaware that they skipped learning all the fundamentals? I was just surprised that someone would write an article that's supposed to be about a game written in assembly and throw in a line saying that binary arithmetic is a technical obscurity.

How many programmers don't know binary?

The main reason for my top post is that I felt I should admit the AI scored a goal today and the last one or two weeks. I said I'd be impressed if it could solve an open problem. It just did. People can argue about how it's not that impressive because if every mathematician were trying to solve this problem they probably would have. However, we all know that humans have extremely finite time and attention, whereas computers not so much. The fact that AI can be used at the cutting edge and relatively frequently produce the right answer in some contexts is amazing.

I tend to disagree that improvement is inherent. Really I'm just expressing an aesthetic preference when I say this, because I don't disagree that a lot of things improve. But it's not a guarantee, and it does take people doing the work and thinking about the same thing every day for years. In many cases there's only one person uniquely positioned to make a discovery, and it's by no means guaranteed to happen. Of course, in many cases there are a whole bunch of people who seem almost equally capable of solving something first, but I think if you say things like "I'm sure they're going to make it better" you're leaving to chance something you yourself could have an impact on. You can participate in pushing the boundaries or even making a small push on something that accelerates someone else's work. You can also donate money to research you are interested in to help pay people who might come up with breakthroughs. Don't assume other people will build the future, you should do it too! (Not saying you DON'T)

I honestly do think I'm being honest with myself. I have held it in my mind that I'm not impressed until it's innovative. That threshold seems to be getting crossed.

I'm not saying, "I used to be an atheist, but then I realized that doesn't explain anything! So glad I'm not as dumb now!"

I agree with what you're saying, and I certainly don't think the one problem facing my country or the world is just that we didn't solve the right math problem yet. I am saddened by the direction the world keeps moving.

When I wrote that I hope we use it for good things, I was just putting a hopeful thought out there, not necessarily trying to make realistic predictions. It's more than likely people will do bad things with AI. But it's actually not set in stone yet, it's not guaranteed that it has to go one way. I'm hopeful it works out.

Hey, I'm a real person. Here's my website. I have YouTube videos up with my real name and face. https://validark.dev

Perhaps I should have elaborated more but what I mean is I used to think, "I genuinely don't see the point in even trying to use AI for things I'm trying to solve". Ironically though, I think that because I've repeatedly tried and tested AI and it falls flat on its face over and over. However, this article makes me more hopeful that AI actually could be getting smarter.

Fair point, however I am simply more interested in how AI can advance frontiers than in how it can transcribe a meeting and give a summary or even print out React code. I know the world is heavily in need of the menial labor and AI already has made that stuff way easier and cheaper.

However I'm just very interested in innovation and pushing the boundaries as a more powerful force for change. One project I've been super interested in for a while is the Mill CPU architecture. While they haven't (yet) made a real chip to buy, the ideas they have are just super awesome and innovative in a lot of areas involving instruction density & decoding, pipelining, and trying to make CPU cores take 10% of the power. I hope the Mill project comes to fruition, and I hope other people build on it, and I hope that at some point AI could be a tool that prints out innovative ideas that took the Mill folks years to come up with.

I have long said I am an AI doubter until AI could print out the answers to hard problems or ones requiring tons of innovation. Assuming this is verified to be correct (not by AI) then I just became a believer. I would like to see a few more AI inventions to know for sure, but wow, it really is a new and exciting world. I really hope we use this intelligence resource to make the world better.

"Since the number is stored in a binary system, every shift to the left means the number is doubled.

At first this sounds like a strange technical obscurity"

Do we not know binary in 2026? Why is this a surprise to the intended audience?

Using an lea is better when you want to put the result in a different register than the source and/or you don't want to modify the flags registers. shlx also avoids modifying flags, but you can't shift by an immediate, so you need to load the constant into a register beforehand. In terms of speed, all these options are basically equivalent, although with very slightly different costs to instruction caches and the register renaming in the scheduler. In terms of execution, a shift is always 1 cycle on modern hardware.

Awesome algorithm and thank you for donating it to open source!