machhra's blog

Are lambda functions slow?

By machhra, history, 3 years ago, In English

Why did this solution TLE but it passed when I converted the lambda functions to normal ones? Am I doing something wrong here or can lambda functions have this big an overhead?

  • Vote: I like it
  • +28
  • Vote: I do not like it

Comments Comments (10)
| Write comment?
»
3 years ago, # |
  Vote: I like it +67 Vote: I do not like it

Your pragmas are the culprit. Remove them and you'll get AC. Submission: https://mirror.codeforces.com/contest/1580/submission/138986509

Lambda functions are not to blame here.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    lol. I thought having those pragmas cant really hurt. So extended question, why is having pragmas with these lambda functions so slow?

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 3   Vote: I like it +40 Vote: I do not like it

      I've narrowed the problem to -ffinite-math-only -msse3 used together (disabling either one produces AC). Couldn't figure the rest yet. Don't understand why this matters to a program that doesn't use floating point numbers either.

      UPD: The two options together prevent GCC from inlining the get lambda for some reason.

      → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +27 Vote: I do not like it

      I'm not so sure why, but Ofast is worse than O3 in quite a few situations, so I avoid using it. As you mentioned in your comment, removing -ffinite-math-only works (still don't know why), and it is turned on by default if you use Ofast, but not in O3.

      Why a function was inlined in one context and why it wasn't in another context is a question that usually requires insight on the the choice of compiler optimizations in various contexts, which is a very complicated matter overall. In general, if you stick to O3 and target few architectures, your code should not face such weird issues.

      → Reply
»
3 years ago, # |
  Vote: I like it +9 Vote: I do not like it

I'm not sure about your particular scenario but in general lambda functions are a zero cost abstraction.

In fact, due to their narrower scope, the compiler can make stronger assumptions about their use, leading to better optimizations.

→ Reply