Hello Codeforces!
Recently, in JOI 2018 Spring Camp, a young genius QCFium, wrote a naive $$$O(NQ)$$$ algorithm in the problem Examination, and got the perfect score. The code is as follows:
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
//Naive Solution as follows...
I thought that it was very surprising, but actually, even $$$N,Q \leq 100,000$$$, with the only 3 lines $$$O(NQ)$$$ naive algorithm actually got accepted. To check whether this speedup is actually effective or not, I wrote these two codes: one is with the 3-line speedup, and the other is without the 3-line speedup.
As a result, in custom innovation (code-test) in Codeforces, Code A used 2074ms but Code B used 2292ms. Code A is faster by ~10.5%. Actually, a young genius QCFium said "The more simple the code is, the more relatively faster with 3-line speedup." So, it could be possible that with speedup, the calculating speed becomes x1.2 or x1.5.
So I have some questions to the community.
Is it possible to use this speedup in CodeForces official contests?
And is it legal to use it in IOI selection contests in your country? (Actually in Japanese Olympiad in Inforcatics, it is OK to use this speedup)
I am very appreciate for sharing your opinion.
Thank you for reading this blog.
Yes, I've used such pragmas when trying to break some CF problem and it worked. You just need to pay attention to the compiler, since MSVC-specific pragmas don't work on GCC and vice versa (they're simply ignored).
In our IOI selection last year, one guy managed to squeeze some points out of one problem I reused from JOI with looser constraints. It didn't give full score, I think, but it was still quite an impressive speedup and squeezing points like that was in fact one of the expected strategies for those unable to get full score. I imagine most local olympiads don't care — or don't know it matters. Anyway, adding pragmas for AVX and loop unrolling on top of your every code most likely won't slow it down and
-O3is often unnecessary or sometimes even slower than-O2.We need MrDindows and dmkz here
This is a short example of x8 speed up for
625 000 000multiplications of complex numbers: original 3759 ms, 396 kb, improved 187 ms, 400 kb.I solved a lot of problems (one example), using naive solution in
O(n^2)orO(n*q), whereq,n <= 200000. OnlyOfast, avx, avx2, fmahelps a lot (x8speed up, not so small asx1.2-x1.5), another is not sufficient.AVXforpacked floats / doubles,AVX2for packed integral types,FMAfor more effective instructions. When this is enabled, compiler can generate machine-specific code, that allows to work with 256-bit registers by using of avx instructions. But you need to write code in parallel-style with independent iterations of cycles.You can read a guide to vectorization with intel® c++ compilers. I'm using this too in my everyday work.
UPD. At current time it is a part of GCC/clang compilers, but since C++20 it will be part of standard C++ language. Link, experimental::simd
UPD 2. Increasing of all constraits up to
300-400kwill help to drop all such solutions.Your improved 187 ms, 400kb code contains:
which is a bit different from the 3 lines shown in the blog post:
Which one is better to use for speed up the code?
I think that
-Ofastincludes all safe and unsafe optimizations for speed up. You can check there. I'm using first, but seems that we need to writeunroll-loopstoo.You can compile your source code with next flags:
-fopt-info, -fopt-info-loop, -fopt-info-loop-missed, -fopt-info-vec, -fopt-info-vec-missed. Link to all options. It can detect which lines of code have been failed in process of code optimizations and why.UPD. I remember that something from list of optimizations allowed me to speed up Segment Tree in 2 times, because it removed tail recursion in recursive queries.
But queries in segment tree uses the result from
l to midandmid + 1 to rand them combine them which is not tail recursion i think(since calling the function is not the last thing done in query function of segment tree). Correct me if i am wrong?What does this 3 lines do?? And if i put this pramgas in my code will it speed up?
Hi does this work for cms?
Actually, it does work, at least in JOI 2018/2019 Spring Camp.
Does anyone why does simpler code, make the speedup faster? And also does macros and including bits/stdc++.h instead of iostream for example affect the speedup?
here is another example where a naive solution can get accepted with pragmas: https://codeforces.me/contest/911/submission/33820899
vectorization of code can give really big speedups...
What is
vectorization?Seems like targeting AVX2 improves the performance by about 20%: https://codeforces.me/contest/911/submission/95380976
Is there a way to solve today's Div2B 1143B - Nirvana with this optimization?
To everyone who doesn't know what's going on here: seems that topicstarter doesn't know it either, and it looks like some magic for him.
Better refer to dmkz's message above in the comments.
Just to let you folks know, last time I checked it didn't work on USACO. L
Codeforces uses 32-bit binaries (although the servers themselves are 64-bit IIRC), so AVX won't work. Although I'm not completely sure that every language other than C++ also runs in 32-bit mode. If someone found a language running with a 64-bit interpreter, there would be an opportunity for some "bitness arbitrage"...
Never mind, I am wrong. You actually can generate AVX instructions on x86.
will it work only for naive algo ?? because if i am taking simple input and output ..the execution time slows down to 4x .. so what's use of using it ??
Honestly, the main cause of the speedup is called vectorization, which the compiler does automatically due to the pragmas. After blindly trying for some time, I realized that auto-vectorization has very very limited use cases (i.e. it doesn't work most of the time).
In fact, to truly know how your code has been optimized by the compiler, you need to get down to the assembly code. If you are afraid of the assembly code, stay away from these optimization pragmas and optimize on the algo level only.
This does not work for oj.uz
Consider using
#pragma GCC target ("native")To learn about how different compilers do on different architectures with autovectorization, try
If you try to compile with this, you get a compiler error along the lines of
attribute(target("native")) is unknown.The correct way to specify it in theory would be
#pragma GCC target ("arch=native")or#pragma GCC target ("tune=native").However,
nativeas architecture isn't recognized in pragmas, see https://stackoverflow.com/a/59846262/1176973. Strangely enough, whiletune=nativeas pragma doesn't trigger an error, it doesn't change the output in any way, whereas-mtune=nativeas command line argument does.So all those
tune=native's you can see in some submissions or codebooks (e.g. dacin21_codebook) don't do anything.I think it's a good brief explanation about what exactly
unroll-loopsdoes.https://code-examples.net/en/q/17133ec
are there any downfalls for using these optimizations?
If you don't use them correctly thwy could lead to unexpected behavior from your side
How to identify which One we have to use??? , there are a lot of optimization So can anyone please explain which one should be use or when?? and is there any general optimization option??
You can read about them Your text to link here...
Most of the online judges seem to ignore pragmas these days.
Wow!! And I thought JOI Spring Contest was one of the competitions with tightest time limits...
E869120
#pragma 'Optimizations' might slow down your code as well!
NOTE: I don't know much about #pragma, but just wanted to share something I found out while using it.
Compare these two submissions:
Submission 1: #128317329
Submission 2: #128317405
The difference is just that #pragma optimization part is commented out in the accepted submission (#128317405) rest all is same. The one with the 'optimization' got TLE. ;-;
Try to change your compiler to G++17 64-bit. AVX and loops unrolling works much better in the 64-bit mode simply because of a larger number of available registers. Moreover, the 32-bit mode is becoming increasingly more obsolete every year, fewer people are testing the quality of the 32-bit code generated by modern compilers and there may be regressions.