Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Push Ifs Up and Fors Down

matklad.github.io

Post reply on HN
Print view View original

121–130 of 209 posts

Re: Push Ifs Up and Fors Down

#121

Post by gameman144 »

sparkie wrote: post #110

In some cases you want to do the opposite - to utilize SIMD. With AVX-512 for example, trivial branching can be replaced with branchless code using the vector mask registers k0-k7, so an if inside a for is better than the for inside the if, which may have to iterate over a sequence of values twice. To give a basic example, consider a loop like: for (int i = 0; i We can convert this to one which operates on 16 ints pe…

I am not sure that the before case maps to the article's premise, and and I think your optimized SIMD version does line up with the recommendations of the article.

For your example loop, the `if` statements are contingent on the data; they can't be pushed up as-is. If your algorithm were something like:

    if (length % 2 == 1) {
      values[i] += 1;
    } else {
      values[i] += 2;
    }
then I think you'd agree that we should hoist that check out above the `for` statement.

In your optimized SIMD version, you've removed the `if` altogether and are doing branchless computations. This seems very much like the platonic ideal of the article, and I'd expect they'd be a big fan!

Re: Push Ifs Up and Fors Down

#122

Post by pshc »

0xWTF wrote: post #105
Waterluvian wrote: post #53

My weird mental model: You have a tree of possible states/program flow. Conditions prune the tree. Prune the tree as early as possible so that you have to do work on fewer branches. Don’t meticulously evaluate and potentially prune every single branch, only to find you have to prune the whole limb anyways. Or even weirder: conditionals are about figuring out what work doesn’t need to be done. Loops are the “work.” Ul…

Can I float an adjacent model? Classes are nouns, functions are verbs.

http://steve-yegge.blogspot.com/2006/03/execution-in-kingdom...

Re: Push Ifs Up and Fors Down

#123

Post by Waterluvian »

0xWTF wrote: post #105
Waterluvian wrote: post #53

My weird mental model: You have a tree of possible states/program flow. Conditions prune the tree. Prune the tree as early as possible so that you have to do work on fewer branches. Don’t meticulously evaluate and potentially prune every single branch, only to find you have to prune the whole limb anyways. Or even weirder: conditionals are about figuring out what work doesn’t need to be done. Loops are the “work.” Ul…

Can I float an adjacent model? Classes are nouns, functions are verbs.

Didn’t the Apollo guidance computers work with VERB and NOUN?

Re: Push Ifs Up and Fors Down

#124

Post by gameman144 »

turtleyacht wrote: post #112
swat535 wrote: post #108

Earlier quoted context omitted.

But if that’s all you have, then how does your system do anything ? You ultimately need to be able to decide and then act based in that decision somewhere..

One possibility is a file.py that is called by your framework. The interface could be something like def doth_match(*args): return True # the predicate def doeth_thou(*args): # processing things return {} # status object for example The framework loops and checks the first function; if true, then execute the second function. And then break or continue for other rule files (or objects). There could be multiple files r…

I think the parent's argument is that wherever in your framework you're calling `doth_match` and then `doeth_thou`, you have a single function that's both deciding and acting. There has to be a function in your program that's responsible for doing both.

Re: Push Ifs Up and Fors Down

#125

Post by PaulRobinson »

kazinator wrote: post #113

> If there’s an if condition inside a function, consider if it could be moved to the caller instead This idle conjecture is too rife with counterexamples. - If the function is called from 37 places, should they all repeat the if statement? - What if the function is getaddrinfo , or EnterCriticalSection ; do we push an if out to the users of the API? I think that we can only think about this transformation for interna…

If the function is called from 37 places, you need to refactor your code, but to answer your question on that point: it depends. DRY feels like the right answer, but I think we'd have to review an actual code example to decide.

On examples where you're talking about a library function, I think you have to accept that as a library you're in a special place: you're on an ownership boundary. Data is moving across domains. You're moving across bounded contexts, in DDD-speak. So, no, you look after your own stuff.

EnterCriticalSection suggests a code path where strong validation on entry - including if conditions - makes sense, and it should be thought of as a domain boundary.

But when you're writing an application and your regular application functions have if statements, you can safely push them out. And within a library or a critical code section you can move the `if` up into the edges of it safely, and not down in the dregs. Manage your domain, don't make demands of other people's and within that domain move your control flow to the edge. Seems a reasonable piece of advice.

However, as ever, idioms are only that, and need to be evaluated in the real world by people who know what they're doing and who can make sensible decisions about that context.

Re: Push Ifs Up and Fors Down

#126

Post by avianlyric »

shawnz wrote: post #77
avianlyric wrote: post #58

Earlier quoted context omitted.

You’ve kind of answered your own question here. > If you push that conditional out to the caller, now every caller of your function has to individually make sure they call it in the right way to get a guarantee of idempotency In this situation your function is no longer idempotent, so you obviously can’t provide the guarantee. But quite frankly, if you’re having to resort to making individual functions implement stat…

Consider a simple example where you're checking if a file exists, or a database object exists, and creating it if not. Imagine your filesystem or database library either doesn't have an upsert function to do this for you, or else you can't use it because you want some special behaviour for new records (like writing the current timestamp or a running total, or adding an entry to a log file, or something). I think this…

> a database object exists, and creating it if not. Imagine your filesystem or database library either doesn't have an upsert function to do this for you, or else you can't use it because you want some special behaviour for new records (like writing the current timestamp or a running total, or adding an entry to a log file, or something).

This is why databases have transactions.

> simple example where you're checking if a file exists

Personally I avoid interacting directly with the filesystem like the plague due to issues exactly like this. Working with a filesystem correctly is way harder than people think it is, and handling all the edge-cases is unbelievably difficult. If I'm building a production system where correctness is important, then I use abstractions like databases to make sure I don't have to deal with filesystem nuances myself.

Re: Push Ifs Up and Fors Down

#127

Post by sparkie »

gameman144 wrote: post #121
sparkie wrote: post #110

In some cases you want to do the opposite - to utilize SIMD. With AVX-512 for example, trivial branching can be replaced with branchless code using the vector mask registers k0-k7, so an if inside a for is better than the for inside the if, which may have to iterate over a sequence of values twice. To give a basic example, consider a loop like: for (int i = 0; i We can convert this to one which operates on 16 ints pe…

I am not sure that the before case maps to the article's premise, and and I think your optimized SIMD version does line up with the recommendations of the article. For your example loop, the `if` statements are contingent on the data; they can't be pushed up as-is. If your algorithm were something like: if (length % 2 == 1) { values[i] += 1; } else { values[i] += 2; } then I think you'd agree that we should hoist tha…

The point was more that, you shouldn't always try to remove the branch from a loop yourself, because often the compiler will do a better job.

For a contrived example, we could attempt to be clever and remove the branching from the loop in the first example by subtracting two from every value, then add three only for the odds.

    for (int i = 0; i
It achieves the same result (because subtracting two preserves odd/evenness, and nothing gets added for evens), and requires no in-loop branching, but it's likely going to perform no better or worse than what the compiler could've generated from the first example, and it may be more difficult to auto-vectorize because the logic has changed. It may perform better than an unoptimized branch-in-loop version though (depending on the cost of branching on the target).

In regards to moving branches out of the loop that don't need to be there (like your check on the length) - the compiler will be able to do this almost all of the time for you - this kind of thing is standard optimization techniques that most compilers implement. If you are interpreting, the following OPs advice is certainly worth doing, but you should probably not worry if you're using a mature compiler, and instead aim to maximize clarity of code for people reading it, rather than trying to be clever like this.

Re: Push Ifs Up and Fors Down

#129

Post by BobbyJo »

0xWTF wrote: post #105
Waterluvian wrote: post #53

My weird mental model: You have a tree of possible states/program flow. Conditions prune the tree. Prune the tree as early as possible so that you have to do work on fewer branches. Don’t meticulously evaluate and potentially prune every single branch, only to find you have to prune the whole limb anyways. Or even weirder: conditionals are about figuring out what work doesn’t need to be done. Loops are the “work.” Ul…

Can I float an adjacent model? Classes are nouns, functions are verbs.

I like to think of it completely differently: Functions are where you hide things, Classes are where you expose things.

Functions to me are more about scoping things down than about performing logic. The whole program is about performing logic.

Re: Push Ifs Up and Fors Down

#130

Post by worik »

PaulRobinson wrote: post #125
kazinator wrote: post #113

> If there’s an if condition inside a function, consider if it could be moved to the caller instead This idle conjecture is too rife with counterexamples. - If the function is called from 37 places, should they all repeat the if statement? - What if the function is getaddrinfo , or EnterCriticalSection ; do we push an if out to the users of the API? I think that we can only think about this transformation for interna…

If the function is called from 37 places, you need to refactor your code, but to answer your question on that point: it depends. DRY feels like the right answer, but I think we'd have to review an actual code example to decide. On examples where you're talking about a library function, I think you have to accept that as a library you're in a special place: you're on an ownership boundary. Data is moving across domain…

> If the function is called from 37 places, you need to refactor your code,

Really?

I do not have to think hard before I have a counter exampl: authentication

I call authenticate() is some form from every API

All 37 of them

Post reply on HN