49
Push Ifs Up And Fors Down (matklad.github.io)
submitted 1 year ago by lysdexic@programming.dev to c/programming@programming.dev
22 comments fedilink hide all child comments
you are viewing a single comment's thread
view the rest of the comments
[-] ShaunaTheDead@kbin.social 3 points 1 year ago

I'm curious, is there a difference in doing it like this?:

var condition = var1 && var2

for walrus in walruses {
  if (condition) {
    walrus.frobnicate()
  } else {
    walrus.transmogrify()
  }
}

Doesn't assigning the condition to a variable make it so that it's only really evaluated once?

[-] nik9000@programming.dev 12 points 1 year ago

I'm reasonably sure compilers can shift the if out. I believe it's called "loop invariant code motion". Won't work in call cases, but in the variable case it should.

[-] lysdexic@programming.dev 0 points 1 year ago

I’m reasonably sure compilers can shift the if out. I believe it’s called “loop invariant code motion”.

That scenario would only apply if the condition was constant and specified at compile time. There's no indication on whether var1 or var2 are compile-time constants or predicates evaluated at runtime.

[-] nik9000@programming.dev 9 points 1 year ago

I don't believe you have to specify the condition at compile time. I think that optimization would fall under dead code elimination.

For the invariant code motion stuff the comparison just has to be invariant from start to finish. At least, that's been my experience. The compiler will just shift the if stement.

But, like, there are totally times when it can't figure out that the thing is invariant. And sometimes it's just more readable to move the if statement out of the loop.

[-] lysdexic@programming.dev 0 points 1 year ago

I don’t believe you have to specify the condition at compile time. I think that optimization would fall under dead code elimination.

How do you tell if some code behind a conditional is dead if the predicate that drives the condition is evaluated at runtime?

[-] nik9000@programming.dev 4 points 1 year ago

Sorry. I wasn't clear. If the conditional is constant a compile time you get the dead code optimization. The path not taken is removed. If it's not constant at you may get the loop invariant movement. But only if the compiler can tell that it's invariant.

My point wasn't that you should always rely on this behavior. At least, I didn't mean to say that. I suppose what I should have said is more like "in many cases you won't see any performance difference because the compiler will do that for you anyway."

I suppose I have value judgements around that like "generally you should do the thing that is more readable and let the compiler take care of stuff like moving the loop invariant". That's been mostly true for me. But only mostly.

[-] lysdexic@programming.dev -2 points 1 year ago* (last edited 1 year ago)

If it’s not constant at you may get the loop invariant movement. But only if the compiler can tell that it’s invariant.

The point is that if the predicate is evaluated at runtime then the compiler plays no role because there is no compile-time constant and all code paths are deemed possible.

I suppose what I should have said is more like “in many cases you won’t see any performance difference because the compiler will do that for you anyway.”

I understand that you're trying to say that compilers can leverage compile-time constants to infer if code paths are dead code or not.

That's just a corner case though. Your compiler has no say on what code paths are dead if you're evaluating a predicate from, say, the response of a HTTP request. It doesn't make sense to expect this hypothetical scenario to be realistic when you have no info on where a predicate is coming from.

[-] Lmaydev@programming.dev 3 points 1 year ago* (last edited 1 year ago)

They're talking about moving the calculation of the if condition outside of the loop. Which the original commenter mentioned. https://en.m.wikipedia.org/wiki/Loop-invariant_code_motion

You are the one that brought up dead code elimination.

[-] coloredgrayscale@programming.dev 3 points 1 year ago* (last edited 1 year ago)

The variable is set once, but the if expression is still evaluated every time (unless the compiler can optimize it)

(edit after skimming the article: yes,using the variable would solve the problem of the last example)

So there would be the branching overhead in every iteration. But that's something the cpu branch prediction should cover, especially since the taken branch will be identical in every loop.

Same also applied to the implied condition to break the for loop (only the first few and last iteration should be wrong predictions)

[-] pipe01@lemmy.pipe01.net 1 points 1 year ago

You still need to read the variable in each iteration, but the cost of that is probably negligible

[-] declination@programming.dev 4 points 1 year ago* (last edited 1 year ago)

Modern optimizing compilers are magical. I would need to check assembly but I would actually expect the if to be hoisted out of the loop entirely to relieve pressure on the branch predictor.

this post was submitted on 17 Nov 2023
49 points (88.9% liked)

Programming

17680 readers
42 users here now

Welcome to the main community in programming.dev! Feel free to post anything relating to programming here!

Cross posting is strongly encouraged in the instance. If you feel your post or another person's post makes sense in another community cross post into it.

Hope you enjoy the instance!

Rules

Rules

  • Follow the programming.dev instance rules
  • Keep content related to programming in some way
  • If you're posting long videos try to add in some form of tldr for those who don't want to watch videos

Wormhole

Follow the wormhole through a path of communities !webdev@programming.dev

founded 2 years ago
MODERATORS
snowe@programming.dev
Ategon@programming.dev
MaungaHikoi@lemmy.nz