for (i=0;i<n;i++)
A[i]=0;
for (i=0;i<n;i++)
B[i]=0;
It can be conveniently transformed into this:
for (i=0;i<n;i++)
A[i]=B[i]=0;
They are exactly equivalent except if the first loop never terminates.
Now, the compiler could try to understand if the first loop does or doesn't terminate, and apply or not the optimization accordingly, but Turing tought us that is indeed a hard task!
Or it could decide to never apply it, for fear of those rare and usually pathological cases where the first loop doesn't terminate.
Or it could decide to apply it by default and accept that in those cases the program does something different than what the source code says. The latter is better known as UB.
The third option won, and that's why infinite loops are UB in the standard.
> but Turing tought us that is indeed a hard task!
Analyzing whether a bounded loop terminates is impossible, got it.
>Or it could decide to apply it by default and accept that in those cases the program does something different than what the source code says. The latter is better known as UB.
But the reason why it lets the compiler fuse the loops has nothing to do with whether the loop terminates or not. The infinite loop UB is just a way of adding more UB and then invoking non infinite loop optimization.
We don't know if A[i] aliases with the pointer that stores the address of the B array and note I mean B itself not A and B overlapping. It could also alias with the loop bound. So the first loop must run until completion simply because it could accidentally overwrite a pointer or variable that is used in the second loop.
But now that we have infinite loop UB we can ignore all of that and it's not because infinite loops themselves produce optimization potential, it's because more stuff is UB now so the compiler is allowed to break aliasing rules, which is the actual thing that was preventing the optimization. The infinite loop UB is just the permission slip.
Whenever you write a succinct example or a metaphor to try to explain in a few words a complicated concept, someone will nitpick small details of your construction, thus focusing on the form and missing the spirit!
Forget if "i<n" is decidable or not: the sense is that there will always be some loops that the compiler can't determine if it's finite or not.
Forget if A and B can alias or not: the sense is having two independent actions that can be executed in the same loop or in two consecutive loops.
Let's see... what about the following example, that replaces all a's with @ and all e's with & in a zero-terminated string s?
for (char *p=s; *p; p++)
if (*p=='a')
*p='@';
for (char *p=s; *p; p++)
if (*p=='e')
*p='&';
If a compiler is allowed to assume that the first loop terminates, then it may optimize it to:
for (char *p=s; *p; p++) {
if (*p=='a')
*p='@';
if (*p=='e')
*p='&';
}
You might ask why it's important that the first loop terminates since in this case the extra side effect would just be a dead store - but if the first loop doesn't terminate then it's possible B is an invalid pointer and then accessing it during the first loop is UB when it shouldn't be. Making a nonterminating loop UB is the patch for this.
The standard example is a linked list instead of an array because the compiler can't prove it never has a cycle.
The complaint I have is that for the sake of benchmark wars, UB has been retconned from "The code might not behave the way you want under certain conditions on certain platforms, hopefully you know what you're doing" to "The compiler can do anything it wants, including rickrolling the user."
That is no longer undefined behavior in my book. That is defined behavior that just has an unusually-shitty definition.
It's all moot anyway given other trends in progress, but... UB, bah humbug. Stop trying to fix problems that no one had. This is why people are clamoring to replace C/C++ with Rust and AI and whatever. The language needed to become more understandable and more predictable in everyday use, and instead it got worse.
So you're saying the person you are responding completely failed to make their point clear?
Why use a for loop with a bound as an example instead of while loops with linked lists? He or she can prompt an LLM for a better example so laziness doesn't count as an excuse.
> Why use a for loop with a bound as an example instead of while loops with linked lists?
I'm the author of the example. I wanted to keep it as simple as possible, and this is the most common form of for loop. I was sure that HN readers would be clever enough to "map" it to whatever they have in their mind that satisfy the undecidability of the condition.
But since you're nitpicking, I haven't specified the types of i and n: i is uint8_t and n is uint32_t. Does it terminate? It depends on the value of n!
Expecting a piece of code to be compiled to a precise sequence of machine instructions is exactly what you should not do with high-level languages like C++. Their task is exactly to abstract the machine away. They give you the guarantee that the final observable result will be what you asked for, not that the means to obtain that result will be what you have in mind.
If you write a loop to zero out some memory, it can be compiled to a loop, or to a call to an optimized predefined function, or even to a sequence of single zeroing instructions, if the size is small enough.
Even a single statement as a=0 may be compiled to a "load immediate" instruction, or an "XOR with itself", or a "sub with itself", or a move from another register known to be 0.
I'm not sure what this has to do with my comment. I am aware of all of this. It would be nice if an infinite loop was defined to be 'do nothing, indefinitely'. On architectures with an instruction that works that works precisely that way, it could be turned into that, perhaps, but that's an implementation detail and should follow the as-if principle (I'm also not sure any compiler would bother).
Yes. And structs are just bytes. Levels of abstractions don't do anything the underlying levels don't already do, they just give you means to express your intent in a clearer form.
But there are "cubic bazillions" of possible URLs that are being requested. Even if they boil down to "only" some millions actual commits, their rendered HTMLs are all different.
Yes, this is very difficult to solve for sites with many URL variations, like git repos and heavily threaded forums. Your cache is always full, but the hit ratio is abysmal.
no its only difficult for you. and only at this moment... any minute now you will see the way. btw, the OP is just saying "its OK for now". And the OP is just telling us: this is what has been happening... maybe its difficult for OP also, but they didnt say that. they just said their current setup cant handle it. old tech...have a hackathon to solve for this. OP says it's not a problem for him right now but if we extrapolate what he's talking about it's definitely a problem aaaaaaand It's totally solvable, Even with all of the crazy combinations he's talking about it's still solvable. And it's already been solved using patterns we see in streaming services. This is completely hackathonable. but why do we even need to bother with this? The slurpers are the cause of this, and they can cause this problem because of Murphy's Law. well you can only account for Murphy's Law with good architecture or something like that or whatever. Ha ha hackathon.
have a hackathon to solve for this. OP says it's not a problem for him right now but if we extrapolate what he's talking about it's definitely a problem aaaaaaand It's totally solvable, Even with all of the crazy combinations he's talking about it's still solvable. And it's already been solved using patterns we see in streaming services. This is completely hackathonable. but why do we even need to bother with this? The slurpers are the cause of this, and they can cause this problem because of Murphy's Law. well you can only account for Murphy's Law with good architecture or something like that or whatever. Ha ha hackathon.
There are uses for them but as a sibling comment mentions they're currently extra work to target per vendor. If you squint a bit they're all basically stripped down GPU compute elements with everything except the matrix multiplication hardware removed, a few MB of cache, no RAM of their own, and a nonstandard API.
OpenCL and Vulkan are supposed to gain support eventually but given their extremely constrained instruction sets and the wide variance in capabilities between different hardware models I don't imagine they're the sort of thing you'd want to target manually.
NPUs, at least for apple, are built for relatively small scale efficient background processing. Theyre taking care of extracting structured metadata from freetext, recognizing people & text in photos, indexing file contents, etc. they do this really well with crazy low power draw.
Theyre generally not even a target for current inference frameworks ala ollama, pytorch, etc.
I did see one prototype someone built using private ios APIs a few months back. They were able to run a reasonable SLM about an order of magnitude slower than GPU but with a tiny power draw.
I dont think llama does. There has been some work. They were originally designed for image processing (remove background from calls) and many exist because Microsoft mandated them for "AI laptops". Often they don't have much memory bandwidth, and are limited in compute and they are all incompatible with each other.
Now, the compiler could try to understand if the first loop does or doesn't terminate, and apply or not the optimization accordingly, but Turing tought us that is indeed a hard task!
Or it could decide to never apply it, for fear of those rare and usually pathological cases where the first loop doesn't terminate.
Or it could decide to apply it by default and accept that in those cases the program does something different than what the source code says. The latter is better known as UB.
The third option won, and that's why infinite loops are UB in the standard.
reply