Блог пользователя machhra

Автор machhra, история, 3 года назад, По-английски

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?

  • Проголосовать: нравится
  • +28
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +67 Проголосовать: не нравится

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

Lambda functions are not to blame here.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      3 года назад, # ^ |
      Rev. 3   Проголосовать: нравится +40 Проголосовать: не нравится

      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.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +27 Проголосовать: не нравится

      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.

»
3 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

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.