>On modern CPUs, avoiding branch misprediction is a key technique to speed up programs. This branchless approach:
>
>for (int i = 0; i < 1000; i++) {
> small_numbers[smlen] = numbers[i];
> smlen += (numbers[i] < 500);
>}
Excuse my terrible ignorance but isn't there still a branch? If numbers[i] < 500 then 1 else 0?
I would think something like addition plus a bit comparison would avoid said branch. Unless compilers already optimize the code, but then wouldn't they also optimize the naive piece of code?
Nah. (numbers[i] < 500) is an expression which evaluates to true (1) or false (0). Evaluating this doesn't require a branch. There are instructions on modern CPUs to turn this expression into a number without a conditional jump. (cmp (compare), setle (set if comparison was less than or equal), then add).
> then wouldn't they also optimize the naive piece of code?
Great question. They do sometimes!
In general, the problem for compilers is that its not obvious which method would be better in some given piece of code. Most branches are highly predictable. Like, imagine a for loop which counts to 1000. At the end of the loop body, the code branches to see whether we should stay in the loop, or exit the loop. The first 999 times through the loop we keep going - so 99.9% of the time, the branch ends up taking the same path. Its very predictable! CPU designers optimise heavily for this, via branch prediction logic. Highly predictable branches run fast. (This is also why array bounds checking doesn't really hurt performance at all.)
But the branch predictor really struggles when the condition is unpredictable - ie, when a conditional branch is taken about 50% of the time. As is the case in a sorting algorithm.
The compiler has no idea whether any condition in your code is predictable or not. There are hints you can use, but it often defaults to just doing whatever you ask it to do.
Here's what the compiler actually does with the code you quoted. You can see the extra branch + jump for the second version of the code:
I clicked around - for some reason even using __builtin_expect_with_probability, none of the compilers I tried will convert from one version of this code into the other.
If you hoist small_numbers[smlen] = numbers[i] out of the if statement then the compiler will produce nearly the same branchless assembly for both cases (the only difference being compare against 499 followed by setle vs. compare against 500 followed by setl).
Taking a second look I want to say you need to hoist the assignment for the loops to be semantically identical anyways.
flohofwoe (above) and aw1621107 (next to this post) both figured out that the magic ingredient isn't whether we code an if or add the boolean value of a comparison to the array size. The magic ingredient is whether the store is conditional or not.
Having the compiler convert a conditional store to an unconditional store can have bad consequences if you have interrupts or task switches or SMP going on, so it's not a good idea to do it -- unless you can guarantee that the thread of execution the compiler can see is indeed the only one. Yeah, yeah, volatile and barriers etc... still, not a good idea.
At the bottom of the page there's a link, "When ‘if’ slows you down, avoid it" [1], that discusses these exact questions. It's basically what @josephg said, but it also shows the assembly language for each version.
There's no branch in that code either way. The comparison operator outputs a value (which is arithmetic, not a branch), and that value is added unconditionally.
The check isn't important; what's important is being predictable so the CPU can guess which way the check will go. I don't know exactly how it works, but after the first couple of loops, the predictor will assume it's always going to end up in the loop and make that the fast path. It may guess wrong the first couple of loops, and the last check wrong, but the other 997 will be correct.
There is a static branch predictor that is used if there is no statistic on a branching instruction yet, and it's really simple: Jumps backward are assumed to be taken (they usually are from a loop), jumps forward are assumed to be not taken.
So the jump that forms the loop will be predicted correctly for all executions but the very last (when the loop ends).
Unless the loop is unrolled, yes, there is a branch to exit the loop. But then that doesn’t matter because the whole goal at the beginning was to avoid branch misprediction (which is not the same thing as avoiding branches entirely).
From a quick search online, the max brightness of your laptop is 400 nits SDR and 500 HDR. My M5 MacBook Pro is 1000 and 1500 nits.
Screen brightness is not something I will compromise on after having a taste of greatness.
I personally wouldn't mind spending 30-40% more for a Linux laptop with similar qualities + repairability. But I will not settle for something much more expensive and worst in some aspects.
There are also arguments agains repairability in Framework's laptop. I did the calculations and for the Framework 16, it would be cheaper to buy a gaming Asus laptop and throw it out in a couple years to replace it versus buying a framework and upgrading it. Utter insanity.
The Macbook Neo is about 500 nits but I'd bet the Asus laptop was more than $600 base.
Looks like the Framework laptops depend on model/screen, between 4-500 but with the new 13 pro hitting 700 nits. For a user replaceable screen, and backwards compatibility (I think), that's pretty solid.
- Tesla's vision only approach seems a lot more competent than the Lidar suites from smaller Chinese makers. Perhaps I misjudged how necessary Lidar was to achieve safe driving.
- Virtually all of the Chinese car infotainment were basically a 1:1 copy of Tesla's. I couldn't find any that genuinely tried something unique lol
> - Tesla's vision only approach seems a lot more competent than the Lidar suites from smaller Chinese makers. Perhaps I misjudged how necessary Lidar was to achieve safe driving.
Three things can be simultaneously true:
* Tesla's cameras are sufficient for some scenarios.
* Tesla's cameras are insufficient for other scenarios.
* A system with good data and bad algorithmic processing is still going to be bad. The Chinese vehicles almost always fail the tests because they see the obstacle but drive into it anyway.
Yeah it's interesting hearing their engineering logic, that fewer sensor types means less sensor collision and faster iteration, where iteration speed is really what matters. I also think people overhyped lidar because they don't understand it, and human behavior is to associate things we don't understand to magic. It's not magic, it performs poorly in inclination weather and can have issues with resolution over range and data processing (although lidar does do a lot of things well).
All of this said, once Karpathy left they have slowly looked at adding new sensors (recently radar), so who knows what the future for Tesla's sensor suite holds.
> I also think people overhyped lidar because they don't understand it
Speaking as a person who understands it extremely well and who has an advanced degree in computer vision, I'm sure that internet randos did, but I promise the people who actually know about the failure modes of the different modalities did not. I don't really expect you to take my word for it, but maybe this will spark an interest in investigating the failure scenarios of 3D reconstruction using cameras in computer vision. Just know that Google is an absolute top tier juggernaut in the CV/ML/AI research world, and they don't use lidar out of ignorance.
> less sensor collision
This isn't a real thing for anyone doing a good job. A sensor can be good for a scenario or it can be bad for a scenario. More sensors feeding input only gives you gradations of accuracy instead of binary accuracy. Having gradations of accuracy is an unambiguously good thing. When you only have one sensor, you have no way to know whether in the moment it is feeding you an optical illusion. That's what it means for something to be an optical illusion. But when you have multiple sensors of different modalities, then you have meaningful information about whether local disagreement between the different modalities means that one is better or worse than the other, because you can contextually characterize the failure scenarios of each.
> It's not magic, it performs poorly in inclination weather and can have issues with resolution over range and data processing (although lidar does do a lot of things well).
Inclement, not inclination. And I hate to be the bearer of bad news, but cameras also do poorly in inclement weather and have issues with resolution over range, and the solutions are identical for both (superresolution, temporal blending, alternate wavelengths, stereo correspondence, etc).
Tesla people always say (said?) things like "Well humans only drive with their eyes, so cars should be able to as well," but that's not a true statement about what humans have in relation to what Teslas have. Humans have many more different sensor modalities than what Tesla's cameras give. Teslas have single-view fixed-focus cameras that, for much of the FOV, can only reconstruct structure from shape assumptions (object detection and classification) and inter-frame changes (optical flow) coupled with sensation of the vehicle's motion. That's all they get. It's not bad at all, especially coupled with advanced machine learning, but you do have more than that coupled with even more advanced machine learning. When you as a human drive, in addition to what Teslas have (you do also have them), you also have binocular stereopsis cues, autofocus lens convergence cues, vehicle-independent motion parallax cues, and the ability to manipulate shade cover so you don't get blinded. Are all those extra cues necessary for every scenario? No, obviously not. Do they help though? Yes. Try driving with only one eye open and without moving your body or head at all. You can absolutely do it, but you won't be as good as you would with both eyes open and free movement.
You could just buy deep out of money SP500 puts expiring in 1+ year. That way you would be "insured" against the bubble popping.
The thing is, every dollar you spend on insurance is a dollar (and its interest) you lose. Furthermore, we don't know when it will pop. 1 year? 5 years?
The more reasonable solution is probably gradually reduce exposure to US markets by selling SP500 shares and turning to Europe and emerging markets ETFs. No need to cash out 401k.
If you just look at the past 20 years, the US has had exceptional returns compared to the rest of the world.
The thing is, historically, high PE ratios like what we're seeing in the US do not correlate with short term returns that are as high. Expected future returns decrease as the PE ratios go up in a pretty linear fashion.
Why 20 years? Just because we know, post hoc, the usa outperformed other places in the last 20 years, in no way means the next 20 years will be the same.
If you want a different point to backtest from, try Japan in the 80s and early 90s
trust goes both ways. you can be cynical about people who take things without paying, i guess. i prefer to be cynical about the corporations who run and stock these grocery stores with substandard products at artificially inflated prices that benefit shareholders and disadvantage people who need to eat food to live.
Think about blaming the grocery store replacing workers with no one in particular before you blame some college pranksters.
Grocery stores in general consolidating, laying off workers, leaving them without pay/benefits, taking advantage of greedflation, etc., is a bigger drain on society.
Shadowy? Kroger's and Albertsons weren't allowed to merge due to anticompetitive practices, price hikes, etc. This was only a couple years ago & is out in the open. You can point all your fingers and toes at the boards of these companies if you need to.
Is it possible that grocery stores are reducing positions to save money? Is it not possible that it is a feedback loop? Why are we blaming the grocery store for replacing labor with machines? Why don't we decry the grocery that hires only 2 people instead of 3?
It's entirely possible that both can be wrong. Shoplifting is bad, but "big corporations pocketing the saved money after understaffing and passing their labor off to the customer" is also bad. We should decry the grocery that hires 2 people instead of 3 just to profit more.
All grocery stores are introducing self-checkout as a way to reduce staffing. It's not a shadowy conspiracy, it's a legitimate fact. Many customers would much rather check out with a person.
> Many customers would much rather check out with a person.
I'm like 50/50 on that. If I've got a lot of stuff it's nice having the space of a full lane for bagging along with another set of hands helping (even more if they still have dedicated baggers!). But if I'm just getting a handful of items a self checkout is faster than waiting in a queue for a full service lane. But if there's a long queue for the self checkout then forget it. If I have to wait I'll wait for service.
I still just prefer the scan and go stuff the most though. Scan with my phone as I shop, check out with a confirmation on the phone, roll on through to the car. I wish all my shopping was that smooth.
I mean, it isn’t really a prank, it is just small scale stealing. It’s fine to not care about that sort of thing, or think it is morally defensible for people who can’t afford food to steal it. But there’s no punchline to make it a prank.
This feels like a thought exercise rather than an argument.
By your logic, it's impossible to prove that a car is driving at 60mph. There could be an error in the speedometer which makes it impossible to verify that said car is going at the speed. You can get asymptomatically close to being sure that you're driving at 60 mph but you can never be 100% sure.
That's not correct. You can prove a car is driving 60mph as soon as you measure it doing that. "proving a negative" is for statements like "There are no purple zebra". You can never prove this because there is always the possibility the purple zebra is somewhere you haven't looked yet. As soon as you find one the statement becomes falsified, but until then it always remains unresolved even if almost certainly true.
Linking back to the parent statement, it's hard to prove a program has no bugs when there is always the possibility the bug just hasn't been found yet. On the flip side it's easy to prove something does have bugs as soon as you find one.
How do you know the one purple zebra wasn't just walking around in a way that meant they were always not where you were looking?
You can probabilistic say "it's extremely unlikely purple zebras exist" but you can never prove 100% they don't exist. And back to the real example, how can you prove there isn't a bug you just haven't found yet?
>
>for (int i = 0; i < 1000; i++) {
> small_numbers[smlen] = numbers[i];
> smlen += (numbers[i] < 500);
>}
Excuse my terrible ignorance but isn't there still a branch? If numbers[i] < 500 then 1 else 0? I would think something like addition plus a bit comparison would avoid said branch. Unless compilers already optimize the code, but then wouldn't they also optimize the naive piece of code?
reply