Rendered at 14:37:08 GMT+0000 (Coordinated Universal Time) with Cloudflare Workers.
anematode 11 hours ago [-]
Nice post!
You can do even a bit better if you're willing to use intrinsics. In particular this kind of operation is well-suited for compress-type operations, available as a first-class operation in at least AVX512, SVE and RVV; you can also emulate them reasonably quickly on NEON and AVX2.
Here's an example, building on the OP's work:
pub fn filter_compress(input: &[f64], threshold: f64) -> Vec<f64> {
use std::arch::x86_64::*;
let mut out = vec![0.0; input.len()];
let mut n = 0usize;
let (head, tail) = input.as_chunks::<8>();
for chunk in head {
unsafe {
let p = _mm512_loadu_pd(chunk.as_ptr());
let m = _mm512_cmpnle_pd_mask(p, _mm512_set1_pd(threshold));
let compress = _mm512_maskz_compress_pd(m, p);
_mm512_storeu_pd(out.as_mut_ptr().wrapping_add(n), compress);
n += m.count_ones() as usize;
}
}
for &x in tail {
out[n] = x;
n += (x > threshold) as usize;
}
out.truncate(n);
out
}
For me it's about 25% less time than the branchless version with 1,000,000 elements, and 60% less with 10,000 elements where memory bandwidth effects are less relevant.
ashton314 9 hours ago [-]
Nice! I saw the code and thought, I bet there’s a way to do some SIMD here… never touched intrinsics in Rust before so I really appreciate you writing it up!
mmozeiko 8 hours ago [-]
See the following pdf for example on how to do this with SSSE3 (pages 104-133) or even SSE2 (pages 151-173)
Thank you for sharing this. How would you emulate this kind of operation on avx2?
dev_hugepages 7 hours ago [-]
I heard there's a way to arrange code such that the compiler can autobectorize easier. I wonder if there's a way to do that here?
Would probably have to pass `-C target-cpu=native` to cargo so that llvm is allowed to use AVX512.
anematode 7 hours ago [-]
Good question. I personally doubt that the compress instruction is easy to coax compilers into generating, as there are many edge cases to consider.
For example, you'll notice here that we perform a full vector store of 8 elements unconditionally, even if only a few of the elements are active. This is safe, though, because the output buffer is as large as the input buffer, and we're chunking by 8, so we'll never trash memory past the end; but this is a tricky analysis. Performance-wise, we rely on the CPU's store buffer to make these overlapping stores cheap.
Instead, you might think that you could just store the elements which are actually active, using a masked store. In fact there is also an intrinsic for this purpose (_mm512_mask_compressstoreu_pd), but it is extremely slow on some CPUs, namely Zen 4, so it's dangerous to use unless you know exactly what CPU you're using. (In my testing, there also seems to be some weird hazard on Zen 5 where multiple memory-destination compress instructions to nearby, even non-overlapping, addresses are serialized. But I haven't looked closer at this.)
cogman10 1 hours ago [-]
I believe the bounds check, in particular, is devastating for autovectorization. There are ways around it, but it requires additional code in safe rust.
Edit: actually looks like autovectorization is in play here [1]. Doesn't look like the bounds check gets in the way at all.
I think WUFFS "iterate loops" might help. WUFFS requires that processing a chunk of N items has code to process one at a time, which means it'll work for any N. However you can optionally provide specialisations for doing K at a time and the compiler is responsible for carving the input up as appropriate so e.g. N = K + K + 1 + 1 + 1 your K-at-a-time code runs twice, the extras are handled 1-at-a-time.
So this divides up the problem, the compiler can vectorize your 8-at-a-time code without needing to handle edge cases where N isn't a multiple of 8, and if a later pass notices we actually never end up using those edge cases they're dead code, if it doesn't they're just a rarely-taken branch once.
Ygg2 29 minutes ago [-]
Keep in mind it's UB to be:
> Executing code compiled with target features that the current thread of execution does not support
I.e. calling AVX512 on Neon architecture.
You need to wrap it in target attributes to even dream of it being safe.
marsven_422 9 hours ago [-]
[dead]
Retro_Dev 11 hours ago [-]
This article is 100% AI written. The data was interesting, the commentary overly verbose and hard to gain useful insights from.
gblargg 10 hours ago [-]
I'm apparently not good at spotting it. I was put off by the overly dramatic presentation. It gets tiring that the author apparently finds this more exciting than I do, and writes like it's enthralling. I just assumed it was an excess of enthusiasm or the first experience with this kind of thing. If it's AI, I'm way behind the game noticing it.
xnorswap 5 hours ago [-]
There are lots of indicators in this text, and this breathless presentation is very much how modern LLMs present things.
Claude also loves to describe things as being "real", particularly saying "X is real".
In this case,
> The reallocations were real, but they were never the bottleneck.
There was never any indication or setup in the text that they weren't real, but it's how it justifies wasted effort, it insists that some phenomenon it corrected but failed to solve the problem "was real".
Another giveaway are nonsensical analogies:
> The predictor is like a barista who starts making your usual order the moment you walk in. If you are a regular, this is fantastic: the coffee is ready when you reach the counter. If you order something random every day, the barista keeps pouring drinks into the sink.
If you order "something random every day", then you don't have a usual order for them to be making, it's an analogy that doesn't work.
And of course, the smoking gun is:
> The smoking gun
It probably won't be a good indicator forever as it has been noticed so much, but it's a particular favourite of the current generation of anthropic models.
flohofwoe 8 hours ago [-]
"The smoking gun" is right there in the text ;) (but also things like "Same million floats. Same threshold. Same function."). Don't know if other models have that same specific style, but it looks very 'claude-y'.
I wouldn't be surprised though if (especially) non-native speakers unconsciously start adopting the Claude writing style when they stare all day long at Claude generated text at work.
saghm 36 minutes ago [-]
Not sure if it was added later, but there's an even more obvious sign: the top of the blog post literally says that an LLM was used to write it.
StilesCrisis 2 hours ago [-]
I would assume non-native speakers talk to Claude in their own language. Now I'm curious if Claude's weird quirks of speech are unique in each language or if they carry over!
flohofwoe 2 hours ago [-]
I'm German but still do all my computing in English (partly out of habbit, but also because Germanized technical text is usually painful to work with because it's full of anglizisms (is that actually an English word?)).
gwerbin 53 minutes ago [-]
One nice thing about English is you can just make up words with plausible etymological roots in Latin/French or Old English and often people will know what you mean. In this case though it would probably be spelled "Anglicism".
enedil 2 hours ago [-]
This isn't a necessarily true assumption. I my social circles of non native English speakers, most of us use English to talk with models.
brettermeier 1 hours ago [-]
I switch languages randomly.
swiftcoder 28 minutes ago [-]
> Don't know if other models have that same specific style
An awful lot of the open-weight models also talk in the Claude-y style. Not sure if an artefact of distilling anthropic models, or just a preponderance of slop in the training set...
dev_hugepages 7 hours ago [-]
> I was put off by the overly dramatic presentation. It gets tiring that the author apparently finds this more exciting than I do, and writes like it's enthralling.
That's one of the main tells that AI wrote this. All the stylistic tics that people usually point out combine to make the writing seem more important than it is.
9 hours ago [-]
__s 1 hours ago [-]
I just scrolled through & read the code snippets. Interesting enough solution at end
HackerThemAll 6 hours ago [-]
It was fun to read and insightful for me, not too artificial, and not too verbose.
I'm glad my internal AI detector doesn't win over my curiosity to learn.
flohofwoe 3 hours ago [-]
The main problem with the article is that the idea to influence backend code generation decisions via specific highlevel code constructs is mostly just mystical bullshit (some compilers do detect specific patterns - usually for bit twiddling hacks, but not on a basic level like control flow optimization).
Using a highlevel language construct like "y += (x > 0) as usize;" doesn't "switch on" branchless code just because the source code looks branchless, compilers are not that dumb anymore.
E.g. I bet that writing
if (x > 0) {
y += 1;
}
...generates the exact same code after optimization, otherwise I would consider that an LLVM bug.
The only reliable way is to mostly bypass the optimizer via simd intrinsics, or drop down to assembler, everything else is just cargo culting.
(fwiw I can't shake the feeling now that the article is recycled, I'm pretty sure I saw those exact same code examples in another "branchless" blog post, but maybe for a different language - because the next question was ineviatably "then why is the code using "if" slower? answer: because it also behaves differently). Or maybe I'm just having a strong dejavu ;)
claudetard 3 hours ago [-]
And, on some architectures, y+=(x>0) is branchful!
wegwerper 4 hours ago [-]
Agree.
Interesting topic but why destroy your own credibility and reputation by shoveling llm-assisted slop to us here at hn?
The post should be flagged, and in general, i wish hn would adopt a no-tolerance policy to enhanced posting like this.
So what if the original text, if it existed in a human written form at all, had weird textual quirks and prose issues the author wished to hide. That texture's what makes humans interesting to engage with in the first place.
aduffy 11 hours ago [-]
idk why this is getting downvoted, I also got this sense, plugged it into Pangram and indeed, 80% AI-written score.
I guess that's fine, but after awhile I get a spidey-sense reading something that feels like a Claude session.
Seattle3503 7 hours ago [-]
Sad to see you getting voted down. But I guess both the pro-AI crowd and anti-AI crowd hate Pangram.
vips7L 3 hours ago [-]
Sad little world we live in tbh.
vinc 7 hours ago [-]
A good part of the article feels like it was written by Claude indeed:
- "The reallocations were real, but they were never the bottleneck."
- "Note that the villain is not the branch itself. It is the branch that [..]"
- "Same million floats. Same threshold. Same function."
- "Notice the price we paid though."
nullsanity 9 hours ago [-]
[flagged]
3997531578 7 hours ago [-]
[dead]
altmanaltman 8 hours ago [-]
Click on their blog index page, see posts going back to early 2010s and use the same writing style. He must have been time travelling and using AI all this time!
grey-area 7 hours ago [-]
I had a look at their blog page out of curiosity, not that you can prove much from the purported dates and text on a blog, which could be edited at any time.
This new blog post is clearly AI edited (probably 'improved' with AI), the old ones are not.
nottorp 6 hours ago [-]
> the same writing style
It's "fake corporate enthusiasm" style. LLMs were just trained in it.
IshKebab 8 hours ago [-]
I think he's asked it to write in his specific style, or possibly he has edited parts of it to his style, or maybe used AI to generate the initial draft.
Something like that anyway. There are some very clear AI tells (smoking guns if you like), but most of it does not read like the prose AI produces by default.
Author if you are here I am curious about your writing process, and why you didn't remove the obvious AI tells.
amiga386 2 hours ago [-]
A much clearer article from yesterday on making casefolding 15x faster by removing an if:
I really hope all these guns give up smoking sometime soon...
haloboy777 8 hours ago [-]
claude sends its regards
aonecode 8 hours ago [-]
indeed
yturijea 6 hours ago [-]
I like how we have pretty much established how branchless coding is superior to branched coding.
However I wonder if the compiler itself could recognize these patterns and turn branches into branchless instead, rather than making the code harder to read? as removing if conditions of course have a readability impact on the code.
adrian_b 5 hours ago [-]
Branchless coding is superior to branched coding whenever the branches are more or less random, which happens frequently when checking some properties of input numbers, like their sign or whether they fall inside certain intervals, or when sorting an array that comes in random order.
When a branch alternative will be taken much more frequently than the other, then branched coding with an "if" becomes superior.
So neither is better in general than the other, whenever the program must choose between alternatives, you must think about whether one is more likely than the other, or if both have similar probabilities.
For instance, when sorting an array, the optimal algorithm is not the same when you expect the input array to have a random order and when you expect it to be already almost sorted.
amiga386 2 hours ago [-]
This is true, but the example given yesterday showed that even if branches can be very well predicted (e.g. processing UTF-8 text which is 99.9999% ASCII), branchless code can result in speedup by making autovectorisation possible.
If the branchless code didn't transform to vector instructions, it would be strictly slower. But if it does, it allows the CPU to work on 16 bytes at a time instead of 1 at a time.
For sorting, conveniently we always definitely need to look at all the elements at least once anyway, so although even the early introspective sorts from the end of last century aren't designed this way both the Timsort and a modern sort like a PDQ sort will end up making that decision early.
"Oh, this was mostly already sorted, done"
If you meant exactly rather than almost then you can still squeak a small win from having an algorithm which is optimised for this case but the vast bulk of your runtime is eaten by the unavoidable work of checking. "Don't check" is faster but then you're not a sort algorithm at all.
bormaj 12 hours ago [-]
Great explanation of why a branchless approach results in such a speed up. I've never really had to deal with performance optimization at this level. Generally it's probably best not to get too involved letting the CPU black box do its thing.
I do wonder, would the performance characteristics of branchless vs branching be consistent across different CPUs/architectures? If you had a CPU that wasn't trying to be fancy with branch prediction, would the regular algo be faster?
throwaway_95283 11 hours ago [-]
CPUs aren't black boxes. They are actually much better documented than almost all the software that runs on them.
If you want to treat the CPU as a black box, trust me you do not want to use a CPU with out a branch predictor, your slow code will run like molasses frozen in antarctica.
The regular algo will be lightyears slower on any CPU that does not have a branch predictor.
nvme0n1p1 11 hours ago [-]
Virtually every CPU has branch prediction, going back to at least the original Pentium (1993), maybe earlier.
If you're running on a very old CPU, yes, the regular algo should be faster.
phire 10 hours ago [-]
I think the Pentium is more or less the first microprocessor with branch prediction. Certainly the most mainstream.
PowerPC 601 arrived at more or less the same time, and the Alpha 21064 was a year earlier. There were a few minicomputers and mainframes before that with branch predictors.
Arguably the 486 could have done with a branch predictor (even a single entry loop predictor would have helped), and maybe the 386 too. But microcoded CISC designs didn't benefit much from predictors because they have multiple cycles to work it out.
And RISC cpus were in their "branch delay slots are awesome" phase throughout most of the 80s. With a bit of trickery (very simple branch conditions and a 2 phase clock), your classic 5-stage MIPS design can fully hide all branches with just a single branch delay slot, so they were a little slow to adopt predictors.
I get the impression that CPU designers in the 80s and early 90s massively underestimated just how beneficial even a small predictor can be.
toast0 9 hours ago [-]
> I get the impression that CPU designers in the 80s and early 90s massively underestimated just how beneficial even a small predictor can be.
It's got a lot to do with how cpu clock speeds were getting way faster, but ram wasn't. That's what makes deeper pipelines attractive, and if you give a cpu a deeper pipeline, it's gonna want a good branch predictor.
phire 6 hours ago [-]
I'm more thinking about how MIPS were quite late to branch predictors.
They were shipping the high-performance R4000 and R4400 with 8 stage pipelines and no branch predictors.
They could have really done with a branch predictor, each branch took three cycles (and the branch delay slot could fill only one instruction, often a useless NOP).
The Pentium only had a 5 stage pipeline and massively benefited from its branch predictor. IBM was slapping branch predictors on PowerPC designs with 4 stage integer pipelines. You simply don't need a long pipeline to justify the benefits of a branch predictor.
adrian_b 4 hours ago [-]
Pentium was the first CPU with a branch predictor that many people could afford to buy.
Before dynamic branch prediction, where the prediction for every branch is updated after each branch execution, depending on its history, static branch prediction had been used for decades, since around 1960, typically using the rule that forwards branches are unlikely to be taken, but backwards branches are likely to be taken. An alternative was to have an instruction bit where the compiler stored its prediction about the probability of a branch being taken.
Dynamic branch predictors began to be used since the mid seventies.
I do not remember now if any notable monolithic CPU had a dynamic branch predictor before Pentium, but prior multi-chip CPUs certainly existed.
vlovich123 9 hours ago [-]
Cortex M0 and microprocessors generally do not. Cortex M3’s looks nothing like the branch prediction you think of when you think consumer or server CPU. Basically branch prediction requires extra power so it’s excluded or greatly simplified in low power use cases.
11 hours ago [-]
imtringued 8 hours ago [-]
I'm not sure how your intuition can be that off, if you don't have a branch predictor then any branching code is going to be even slower than it already is, favouring branchless code even more for obvious reasons.
I say this as someone who is interested in a special type of processor architecture that has no branch prediction at all and would need a branchless subset of Rust to meaningfully program it at high performance.
benj111 3 hours ago [-]
Why no branch predictor at all? Even a brain-dead one that predicts all branches always/never taken is going to provide some benefit, it's not as if the processor can do anything else while it's waiting.
Or am I missing something?
I note the hazard 3 on the pi Pico rp2350 only predicts a branch if it's the last branch and was taken, ie a single loop. Which seems weird to me, so I'm probably lacking understanding somewhere.
Brian_K_White 11 hours ago [-]
Another recent story from github about case folding as part of code search, the simple version of the code had a couple of ifs, and the branchless version was actually slower.
They have a stupendously fast version and it is also branchless, but it just required more than branchless alone.
I'm fuzzy on the details but I think one of the ifs was an early exit, and without that the loop does a memory assignment on every byte instead of skipping most.
The really fast version was also vectorized. The branchless makes it possible to vectorize, but it was the vectorization that actually made it fast.
myshapeprotocol 47 minutes ago [-]
Branchless optimization is such a clean way to squeeze out maximum performance for hot loops. Love this approach.
llama_drama 3 hours ago [-]
Branchless code can indeed sometimes be slower than conventional one, but in this particular case, the article comes to the wrong conclusion. At a 1% kept, the branchless version is slower because it pays the cost of zero-initializing 8 MB of memory when allocating the Vec. This can be easily demonstrated by comparing it with a version that allocates uninitialized memory.
rabiescow 4 hours ago [-]
that's a really clever trick to write to out[n] multiple times but only move the index after the logical condition is true thus ending up with the correct values in out
Worth noting that as written the "trick" results in memory usage proportional to the size of the input rather than the output. If the filter rejects most of the input the difference could be quite noticeable.
returningfory2 4 hours ago [-]
I disagree in the sense that you can rewrite the code to use the trick and also not allocate in advance. Nothing about the trick requires you to allocate up front: before writing to out[n] you can extend the vector if it’s out of bounds. Or, after incrementing n, do out.push(0).
khuey 2 hours ago [-]
You should try writing it out. Doing it without introducing another unpredictable branch is harder than it looks.
I discussed this with a coworker earlier this week and the best they were able to come up with was
for &x in input {
out.push(x);
n += (x > threshold) as usize;
out.truncate(n);
}
which works but is ugly af imo.
claudetard 3 hours ago [-]
This is good technical content, but it's obvious that an AI wrote it.
8 hours ago [-]
codetiger 12 hours ago [-]
Thanks for sharing, optimisations like these are what keeps the fun in programming. I have been optimising my JSONLogic evaluator in rust and used arena allocator and preallocation tricks that gave me good jump in tuning. Let me see if branchless programming techniques can get any further in my case
veqq 11 hours ago [-]
I've been doing leetcode in Janet in a (sometimes) tacit (variabless), branchless way:
(def find-shared-gcd
(comp
(fn [e] (max ;(map (fn [d] (* d ;(map |(- 1 (min 1 (mod $ d))) e)))
(range 1 (+ 1 (min ;e))))))
|((juxt* max min) ;$)))
(defn max-diff `where elements increase` [& numbs]
(reduce max
-1 (filter |(< 0 $) # strip 0s and add -1 in case (= true (apply > numbs))
(map - numbs (accumulate2 min numbs)))))
youaremidwit 6 hours ago [-]
[dead]
bjourne 10 hours ago [-]
This problem is called stream compaction and there is a wealth of research on it. The best methods use prefix scan. They first efficiently compute the index in the output array of each element that satisfies the predicate and then they gather them in one linear operation.
Also, I can tell that you are a good writer. You didn't need the LLM to "polish" your text.
dxdm 8 hours ago [-]
There is clearly LLM-prose involved, but it's pretty well done. Here's one example: "The reallocations were real, but they were never the bottleneck."
LLMs love this pattern. Whether one put it into this text, or the author soaked it up and now used it himself, who knows. But it is one of the few things in the post that gives me the ick.
And then, there's the verbosity.
If I had to guess, an LLM was involved, but the author did a good job with manual writing and editing, too.
claudetard 3 hours ago [-]
If your objects are large, I can see why you would compute indices first. But why do that for floats?
crest 2 hours ago [-]
This is a common pattern a compiler should recognise and optimise into an efficient data and control flow. So much for a sufficiently smart compiler. shrug
crazysim 12 hours ago [-]
Would PGO figure this out?
Sesse__ 4 hours ago [-]
Generally most forms of PGO does not try to capture number of mispredicted branches (which isn't the same as how often a branch is taken).
j16sdiz 11 hours ago [-]
They could.
but.... running PGO is just too much pain.
We can't do it "incrementally", can we?
How about combining with LTO?
edit: I was thinking profiling individual module on a test driver and link them after PGO
stkdump 10 hours ago [-]
I don't know if an optimization is allowed to "invent" a write, but I would be surprised if an optimizer goes that far because I have to believe that the number of cases where more writes improve performance are pretty slim.
rdevulap 7 hours ago [-]
a simple perf stat should show that the "Keep 50% of random data" case will have insanely more branch mis-predictions that the others.
tonyhart7 8 hours ago [-]
"A branch is cheap. A mispredicted branch is not."
You can do even a bit better if you're willing to use intrinsics. In particular this kind of operation is well-suited for compress-type operations, available as a first-class operation in at least AVX512, SVE and RVV; you can also emulate them reasonably quickly on NEON and AVX2.
Here's an example, building on the OP's work:
For me it's about 25% less time than the branchless version with 1,000,000 elements, and 60% less with 10,000 elements where memory bandwidth effects are less relevant.https://deplinenoise.files.wordpress.com/2015/03/gdc2015_afr...
Would probably have to pass `-C target-cpu=native` to cargo so that llvm is allowed to use AVX512.
For example, you'll notice here that we perform a full vector store of 8 elements unconditionally, even if only a few of the elements are active. This is safe, though, because the output buffer is as large as the input buffer, and we're chunking by 8, so we'll never trash memory past the end; but this is a tricky analysis. Performance-wise, we rely on the CPU's store buffer to make these overlapping stores cheap.
Instead, you might think that you could just store the elements which are actually active, using a masked store. In fact there is also an intrinsic for this purpose (_mm512_mask_compressstoreu_pd), but it is extremely slow on some CPUs, namely Zen 4, so it's dangerous to use unless you know exactly what CPU you're using. (In my testing, there also seems to be some weird hazard on Zen 5 where multiple memory-destination compress instructions to nearby, even non-overlapping, addresses are serialized. But I haven't looked closer at this.)
Edit: actually looks like autovectorization is in play here [1]. Doesn't look like the bounds check gets in the way at all.
[1] https://godbolt.org/z/af4qGba5o
So this divides up the problem, the compiler can vectorize your 8-at-a-time code without needing to handle edge cases where N isn't a multiple of 8, and if a later pass notices we actually never end up using those edge cases they're dead code, if it doesn't they're just a rarely-taken branch once.
> Executing code compiled with target features that the current thread of execution does not support
I.e. calling AVX512 on Neon architecture.
You need to wrap it in target attributes to even dream of it being safe.
Claude also loves to describe things as being "real", particularly saying "X is real".
In this case,
> The reallocations were real, but they were never the bottleneck.
There was never any indication or setup in the text that they weren't real, but it's how it justifies wasted effort, it insists that some phenomenon it corrected but failed to solve the problem "was real".
Another giveaway are nonsensical analogies:
> The predictor is like a barista who starts making your usual order the moment you walk in. If you are a regular, this is fantastic: the coffee is ready when you reach the counter. If you order something random every day, the barista keeps pouring drinks into the sink.
If you order "something random every day", then you don't have a usual order for them to be making, it's an analogy that doesn't work.
And of course, the smoking gun is:
> The smoking gun
It probably won't be a good indicator forever as it has been noticed so much, but it's a particular favourite of the current generation of anthropic models.
I wouldn't be surprised though if (especially) non-native speakers unconsciously start adopting the Claude writing style when they stare all day long at Claude generated text at work.
An awful lot of the open-weight models also talk in the Claude-y style. Not sure if an artefact of distilling anthropic models, or just a preponderance of slop in the training set...
That's one of the main tells that AI wrote this. All the stylistic tics that people usually point out combine to make the writing seem more important than it is.
I'm glad my internal AI detector doesn't win over my curiosity to learn.
Using a highlevel language construct like "y += (x > 0) as usize;" doesn't "switch on" branchless code just because the source code looks branchless, compilers are not that dumb anymore.
E.g. I bet that writing
...generates the exact same code after optimization, otherwise I would consider that an LLVM bug.The only reliable way is to mostly bypass the optimizer via simd intrinsics, or drop down to assembler, everything else is just cargo culting.
(fwiw I can't shake the feeling now that the article is recycled, I'm pretty sure I saw those exact same code examples in another "branchless" blog post, but maybe for a different language - because the next question was ineviatably "then why is the code using "if" slower? answer: because it also behaves differently). Or maybe I'm just having a strong dejavu ;)
Interesting topic but why destroy your own credibility and reputation by shoveling llm-assisted slop to us here at hn?
The post should be flagged, and in general, i wish hn would adopt a no-tolerance policy to enhanced posting like this.
So what if the original text, if it existed in a human written form at all, had weird textual quirks and prose issues the author wished to hide. That texture's what makes humans interesting to engage with in the first place.
I guess that's fine, but after awhile I get a spidey-sense reading something that feels like a Claude session.
- "The reallocations were real, but they were never the bottleneck."
- "Note that the villain is not the branch itself. It is the branch that [..]"
- "Same million floats. Same threshold. Same function."
- "Notice the price we paid though."
The blog posts from 2010s are in a completely different style and written by a human: https://www.greyblake.com/blog/vim-preview-plugin/ https://www.greyblake.com/blog/how-to-install-firefox-icewea... https://www.greyblake.com/blog/unexpected-ruby-behaviour/ ...
This new blog post is clearly AI edited (probably 'improved' with AI), the old ones are not.
It's "fake corporate enthusiasm" style. LLMs were just trained in it.
Something like that anyway. There are some very clear AI tells (smoking guns if you like), but most of it does not read like the prose AI produces by default.
Author if you are here I am curious about your writing process, and why you didn't remove the obvious AI tells.
https://github.blog/engineering/architecture-optimization/do...
Discussion: https://news.ycombinator.com/item?id=49127983
When a branch alternative will be taken much more frequently than the other, then branched coding with an "if" becomes superior.
So neither is better in general than the other, whenever the program must choose between alternatives, you must think about whether one is more likely than the other, or if both have similar probabilities.
For instance, when sorting an array, the optimal algorithm is not the same when you expect the input array to have a random order and when you expect it to be already almost sorted.
If the branchless code didn't transform to vector instructions, it would be strictly slower. But if it does, it allows the CPU to work on 16 bytes at a time instead of 1 at a time.
https://github.blog/engineering/architecture-optimization/do...
"Oh, this was mostly already sorted, done"
If you meant exactly rather than almost then you can still squeak a small win from having an algorithm which is optimised for this case but the vast bulk of your runtime is eaten by the unavoidable work of checking. "Don't check" is faster but then you're not a sort algorithm at all.
I do wonder, would the performance characteristics of branchless vs branching be consistent across different CPUs/architectures? If you had a CPU that wasn't trying to be fancy with branch prediction, would the regular algo be faster?
If you want to treat the CPU as a black box, trust me you do not want to use a CPU with out a branch predictor, your slow code will run like molasses frozen in antarctica.
The regular algo will be lightyears slower on any CPU that does not have a branch predictor.
If you're running on a very old CPU, yes, the regular algo should be faster.
PowerPC 601 arrived at more or less the same time, and the Alpha 21064 was a year earlier. There were a few minicomputers and mainframes before that with branch predictors.
Arguably the 486 could have done with a branch predictor (even a single entry loop predictor would have helped), and maybe the 386 too. But microcoded CISC designs didn't benefit much from predictors because they have multiple cycles to work it out.
And RISC cpus were in their "branch delay slots are awesome" phase throughout most of the 80s. With a bit of trickery (very simple branch conditions and a 2 phase clock), your classic 5-stage MIPS design can fully hide all branches with just a single branch delay slot, so they were a little slow to adopt predictors.
I get the impression that CPU designers in the 80s and early 90s massively underestimated just how beneficial even a small predictor can be.
It's got a lot to do with how cpu clock speeds were getting way faster, but ram wasn't. That's what makes deeper pipelines attractive, and if you give a cpu a deeper pipeline, it's gonna want a good branch predictor.
They were shipping the high-performance R4000 and R4400 with 8 stage pipelines and no branch predictors.
They could have really done with a branch predictor, each branch took three cycles (and the branch delay slot could fill only one instruction, often a useless NOP).
The Pentium only had a 5 stage pipeline and massively benefited from its branch predictor. IBM was slapping branch predictors on PowerPC designs with 4 stage integer pipelines. You simply don't need a long pipeline to justify the benefits of a branch predictor.
Before dynamic branch prediction, where the prediction for every branch is updated after each branch execution, depending on its history, static branch prediction had been used for decades, since around 1960, typically using the rule that forwards branches are unlikely to be taken, but backwards branches are likely to be taken. An alternative was to have an instruction bit where the compiler stored its prediction about the probability of a branch being taken.
Dynamic branch predictors began to be used since the mid seventies.
I do not remember now if any notable monolithic CPU had a dynamic branch predictor before Pentium, but prior multi-chip CPUs certainly existed.
I say this as someone who is interested in a special type of processor architecture that has no branch prediction at all and would need a branchless subset of Rust to meaningfully program it at high performance.
Or am I missing something?
I note the hazard 3 on the pi Pico rp2350 only predicts a branch if it's the last branch and was taken, ie a single loop. Which seems weird to me, so I'm probably lacking understanding somewhere.
They have a stupendously fast version and it is also branchless, but it just required more than branchless alone.
I'm fuzzy on the details but I think one of the ifs was an early exit, and without that the loop does a memory assignment on every byte instead of skipping most.
The really fast version was also vectorized. The branchless makes it possible to vectorize, but it was the vectorization that actually made it fast.
I discussed this with a coworker earlier this week and the best they were able to come up with was
which works but is ugly af imo.Also, I can tell that you are a good writer. You didn't need the LLM to "polish" your text.
LLMs love this pattern. Whether one put it into this text, or the author soaked it up and now used it himself, who knows. But it is one of the few things in the post that gives me the ick.
And then, there's the verbosity.
If I had to guess, an LLM was involved, but the author did a good job with manual writing and editing, too.
but.... running PGO is just too much pain.
We can't do it "incrementally", can we? How about combining with LTO?
edit: I was thinking profiling individual module on a test driver and link them after PGO
oh hell nah