백준이나 코드포스 등의 온라인 저지에서 문제를 풀다 보면 알고리즘 외적으로 최적화가 필요한 경우가 종종 생긴다. 이 때 가장 일반적이고 큰 속도 향상을 기대할 수 있는 방법이 기본 입출력 방법인 printf, scanf 혹은 cin, cout 대신 Fast IO를 사용하는 것이다.
아래에서는 알고리즘 문제를 풀 때 입출력을 하는 여러 방법을 제시하고, 각각의 특징을 설명한 뒤, 모든 방법의 속도를 비교하며 마무리한다.
이 블로그에 쓰는 첫 글이라 테스트를 겸하기 위해 일부러 장황하게 썼다. 때문에 읽다 보면 거부감이 들 수 있으며, Fast IO 코드는 글 중후반쯤에 있으니까 바로 코드만 복붙해가는 편을 권장한다.
버퍼링
입출력 방법에 대해 말하기 전에 알면 좋은 부분은 버퍼링이다. 메모리에서 데이터를 쓰거나 읽는 것에 비해 실제 파일이나 콘솔에 입출력을 하는 게 더 느리단 건 쉽게 알 수 있을 것이다. 때문에 중간에 임시로 데이터를 저장할 공간인 버퍼를 두어 가능한 적은 횟수의 입출력을 하여 성능을 개선하는 것을 버퍼링이라고 부른다.
프로그래밍 언어들에선 사용자가 불편함을 느끼지 않도록 적절한 처리를 해주기 때문에 이런 부분을 눈치채긴 힘들며, 개발자 역시 입출력 속도가 매우 중요한 경우는 잘 없어 버퍼링의 존재를 모르는 경우도 잦다.
기본 입출력
밑의 두 방식을 섞어 쓰는 사람이 있다면, 특별한 이유가 없는 경우 반드시 하나만 선택해 쓰도록 하자.
printf, scanf
C를 사용하거나 사용했던 사람들이 자주 쓰는 입출력 방식이다. 포맷팅이 약간 더 쉽다는 것을 제외하곤 그리 장점이 없다.
다음과 같이 버퍼 크기를 조정할 수 있다.
setvbuf(stdin, NULL, _IOFBF, 16 * (1<<20)); // 16MB
setvbuf(stdout, NULL, _IOFBF, 256 * (1<<10)); // 256KBcin, cout
C++의 기본 입출력 방식이다. 위와 다르게 형식 지정자를 입력할 필요가 없어 타입 안정성이나 확장성 면에서 유리하며, 일단 속도가 빠르다.
일반적으로 printf, scanf에 비해 느리다고 알려져 있는데, 기본적으로 C의 입출력 방법과 호환을 위해, 그리고 콘솔에서의 더 나은 사용자 경험을 위해 몇 가지 설정이 되어있기 때문이며, 다음에 해당하는 부분들을 고치고 측정해 보면 상당히 빠른 것을 알 수 있다.
endl을'\n'으로 바꾸자. 자세한 내용은 검색해보면 나오겠지만,endl은 버퍼를 비우기 때문에 자주 사용하면 매우 느려질 수밖에 없다. 단, 코드포스 등에서 인터랙티브 문제를 푼다면 매우 유용하게 사용할 수 있다.ios_base::sync_with_stdio(false);cin.tie(nullptr);를 main 함수 최상단에 추가하자. C의 입출력 방식과 호환을 유지하는 옵션을 끄고,cin으로 입력받을 때 버퍼를 비우지 않도록 한다.
다음과 같이 버퍼 크기를 조정할 수 있다.
char input_buffer[16 * (1<<20)]; // 16MB
cin.rdbuf()->pubsetbuf(input_buffer, sizeof(input_buffer));
char output_buffer[256 * (1<<10)]; // 256KB
cout.rdbuf()->pubsetbuf(output_buffer, sizeof(output_buffer));Fast Input
read로 입력받는 코드와 mmap을 사용하는 방식으로 나뉜다. 입력이 모두 공백 문자(띄어쓰기 및 새 줄) 하나로 나뉘어져 있음을 가정하며, 복붙하기 편하도록 적당히 숏코딩을 해서 쓴다. 짧은 코드라서 알아보긴 어렵지 않을 것이다.
geti는 정수를 입력받는다. getu는 음수가 아닌 정수를 입력받는다. int형 기준으로 작성되었으므로 더 큰 수가 필요하다면 코드의 모든 int를 long long 등으로 바꾸면 된다.
메모리 몇KB에 집착하는 게 아니라면 그냥 Fast IO나 복붙해서 쓰는 편이 더 낫다.
read
범용성이 좋고 메모리를 적게 사용하며 속도도 보통 가장 빠르고 최적화의 여지도 있다. 백준에서는 밑의 코드에서 I와 J를 지역변수로 선언하는 것이 메모리가 작게 잡힌다.
#include <unistd.h>
const signed IS=1<<22;
char I[IS+1],*J=I;
int main() {
auto daer=[&]{if(J>=I+IS-64){char*p=I;do*p++=*J++;while(J!=I+IS);p[read(0,p,I+IS-p)]=0;J=I;}};
auto getu=[&]{daer();int x=0;do x=x*10+*J-'0';while(*++J>='0');++J;return x;};
auto geti=[&]{bool e=*J=='-';J+=e;return(e?-1:1)*getu();};
I[read(0,I,IS)]=0;
}mmap
#include <sys/stat.h>
#include <sys/mman.h>
signed I[36];char*J=(char*)mmap(0,I[12],1,2,0,fstat(0,(struct stat*)I));
int getu(){int x=0;do x=x*10+*J-'0';while(*++J>='0');++J;return x;}
int geti(){bool e=*J=='-';J+=e;return(e?-1:1)*getu();}mmap (clang)
clang은 실행 순서가 gcc와 다르기 때문에, fstat을 첫 번째에 두어야 한다. 이외 부분은 동일.
#include <sys/stat.h>
#include <sys/mman.h>
signed I[36];char*J=(char*)mmap((void*)fstat(0,(struct stat*)I),I[12],1,2,0,0);
int getu(){int x=0;do x=x*10+*J-'0';while(*++J>='0');++J;return x;}
int geti(){bool e=*J=='-';J+=e;return(e?-1:1)*getu();}Fast Output
int형 기준으로 작성되었으므로 더 큰 수가 필요하다면 코드의 모든 int를 long long 등으로 바꾸고, char s[8]에서 8을 원하는 수로 변경하면 된다.
#include <unistd.h>
const signed OS=1<<20;
char O[OS],*K=O;
int main() {
auto flush=[&]{write(1,O,K-O);K=O;};
auto putu=[&](int n){char s[8],*p=s;do*p++=n%10+48;while(n/=10);do*K++=*--p;while(p!=s);*K++=10;if(K>=O+OS-64)flush();};
auto puti=[&](int n){if(n<0)*K++='-',n=-n;putu(n);};
flush();
}개선
현대 CPU들이 아무리 발달되어있다지만, 나눗셈 및 나머지 연산은 단순한 연산들에 비해 속도가 느릴 수밖에 없다. 때문에 10으로 나누며 한 칸씩 진행하는 것이 아니라, 100으로 나누며 두 칸씩 진행하는 방법이 고안되었다. 이렇게 할 경우 나눗셈 횟수는 절반 정도로 줄어들 것을 기대할 수 있다.
constexpr char DGT[]="00010203040506070809101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899";
auto putu=[&](int n){
char s[8],*p=s;
while(n>=100){int x=n%100*2;n/=100;*p++=DGT[x+1];*p++=DGT[x];}
if(n>=10)n*=2,*p++=DGT[n+1],*p++=DGT[n];else*p++=n+'0';
do*K++=*--p;while(p!=s);*K++=10;if(K>=O+SZ-16)flush();
};다만 수 정렬하기 5로 실험을 해보았으나, 실행 속도에 큰 개선은 없었다. 출력이 작기 때문인 것으로 예상된다.
fmt 라이브러리가 정수를 출력할 때 실제로 위 방식을 사용한다.
루프 언롤링
Fast Input 코드에서 getu 함수를 생각해 보자. 수의 범위가 작다면 루프 언롤링을 시도해보는 것도 괜찮으련만, 아쉽게도 unroll-loops 플래그를 줘도 컴파일러가 자동으로 언롤링해주지 않고, 직접 언롤링하는 것은 귀찮은 데다가 코드가 지저분해진다. 그러나, 다음과 약간의 힌트를 주면 컴파일러가 적절히 언롤링을 해준다!
auto getu=[&]{daer();int x=0,i=0;do x=x*10+*J-'0';while(*++J>='0'&&++i<7);++J;return x;};반복 횟수 i를 선언해 최대 7번(입력으로 들어오는 정수의 길이에 따라 달라질 수 있다)만 돌도록 하였다. 언뜻 보기엔 계속 i를 추가에 비교까지 하니 더 느려질 것 같지만, O3 등 최적화 옵션을 주고 컴파일 결과를 보면 똑똑하게도 i는 사라져 있고 언롤링이 예쁘게 되어있는 것을 볼 수 있다.
입력받는 것을 예시로 들었으나, 출력 및 다른 여러 함수에서도 비슷한 방법을 적용할 수 있다. 다만, 모든 문제에 적용하기엔 살짝 번거로움이 있으므로, 정말 1ms가 절실하다면 사용해보자.
Fast IO
Fast Input과 Fast Output의 코드를 복붙하기 편하게 namespace로 묶고 사소하게 최적화가 더해진 코드이다.
적절한 버퍼의 크기는 문제마다 매우 다르지만, 개인적인 경험으로는 예상 입력출력 크기 / 32 정도에서 시작해 줄이거나 올려보는 게 적당해 보인다.
#include <unistd.h>
namespace io {
const signed IS=1<<22, OS=1<<20;
char I[IS+1],*J=I,O[OS],*K=O;
inline void daer(){if(J>=I+IS-64){char*p=I;do*p++=*J++;while(J!=I+IS);p[read(0,p,I+IS-p)]=0;J=I;}}
template<int N=10,typename T=int>inline T getu(){daer();T x=0;int k=0;do x=x*10+*J-'0';while(*++J>='0'&&++k<N);++J;return x;}
template<int N=10,typename T=int>inline T geti(){daer();bool e=*J=='-';J+=e;return(e?-1:1)*getu<N,T>();}
inline void flush(){write(1,O,K-O);K=O;}
template<int N=10,typename T=int>inline void putu(T n){char s[(N+7)/8*8],*p=s;int k=0;do*p++=n%10+48;while((n/=10)&&++k<N);do*K++=*--p;while(p!=s);*K++=10;if(K>=O+OS-64)flush();}
template<int N=10,typename T=int>inline void puti(T n){if(n<0)*K++='-',n=-n;putu<N,T>(n);}
struct f{f(){I[read(0,I,IS)]=0;}~f(){flush();}}flu;
};
using namespace io;입력받을 수 = geti<자리수, 타입>()으로 입력을 받는다. 음수가 아니라면 getu를 사용해서 입력받을 수 있다. 타입을 적지 않는다면 기본적으로 int형, 타입과 자리수를 모두 적지 않는다면 10자리 int형으로 입력받는다.
putu<자리수, 타입>(출력할 수)로 출력을 한다. 음수가 아니라면 putu를 사용해서 출력할 수 있다. 이하는 위와 동일.
기타
GCC 최적화 플래그
clang에선 사용 불가능하다. 대신 기본적으로 최적화나 병렬화를 잘 해주기 때문에 옵션이 필요한 경우는 적다.
각 옵션들은 사용했다가 느려질 수도 있고 빨라질 수도 있으니 여러 가지 시도해 보자. 보통은 O3만 넣는 게 가장 무난하다.
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")
#pragma GCC target("avx,avx2,fma")gcc vs clang
케바케다.
최적화 플래그를 넣지 않은 경우 clang이 보통 더 빠르지만, 간혹 gcc가 나을 때도 있다.
최적화 플래그를 넣는 경우 gcc가 보통 더 빠르지만, 간혹 clang이 나을 때도 있다.
나는 평소에는 clang을 사용하며, 한계까지 최적화했다는 생각이 들면 gcc로 바꿔서 최적화 플래그를 바꿔가며 시험해보는 편이다.
SIMD
시간복잡도에 /8, /32같은 걸 붙이거나 최적화에 발을 담가보고 싶은 사람들을 위해 좋은 문서들이 있다. 백준과 코드포스에선 AVX2를 지원하니 AVX2를 기준으로 찾아보자.
- Compiler Vectorization Tutorial
- Intel CPU Intrinsics Guide (AVX, AVX2, FMA)
- Parsing series of integers with SIMD
예시
수열과 쿼리 17 문제로 간단히 사용 예시를 든다.
#pragma GCC optimize("O3")
#include <unistd.h>
namespace io {
const signed IS=1<<20, OS=1<<18;
char I[IS+1],*J=I,O[OS],*K=O;
inline void daer(){if(J>=I+IS-64){char*p=I;do*p++=*J++;while(J!=I+IS);p[read(0,p,I+IS-p)]=0;J=I;}}
template<int N=10,typename T=int>inline T getu(){daer();T x=0;int k=0;do x=x*10+*J-'0';while(*++J>='0'&&++k<N);++J;return x;}
template<int N=10,typename T=int>inline T geti(){daer();bool e=*J=='-';J+=e;return(e?-1:1)*getu<N,T>();}
inline void flush(){write(1,O,K-O);K=O;}
template<int N=10,typename T=int>inline void putu(T n){char s[(N+7)/8*8],*p=s;int k=0;do*p++=n%10+48;while((n/=10)&&++k<N);do*K++=*--p;while(p!=s);*K++=10;if(K>=O+OS-64)flush();}
template<int N=10,typename T=int>inline void puti(T n){if(n<0)*K++='-',n=-n;putu<N,T>(n);}
struct f{f(){I[read(0,I,IS)]=0;}~f(){flush();}}flu;
};
using namespace io;
inline int min(int x, int y) { return x<y ? x : y; }
int main() {
int N, Q;
int A[2*(N=getu<6>())];
for(int i=0; i<N; i++) A[i+N]=getu<10>();
for(int i=N; --i;) A[i]=min(A[i*2], A[i*2+1]);
Q=getu<6>();
while(Q--) {
char t=*J++; J++;
int i=getu<6>(), n=getu<10>();
if(t=='1') {
for(A[i+=N-1]=n; i>>=1;)
if(int x=A[i]; x==(A[i]=min(A[i*2], A[i*2+1])))
break;
} else {
int x=2e9;
i+=N-1, n+=N-1;
for(int c=i, d=n; c<=d; c=c+1>>1, d=d-1>>1)
x=min(x, min(A[c], A[d]));
putu<10>(x);
}
}
}비교
추가 예정
결론
Fast IO는 물론 만능이 아니다. 아무리 빠른 입출력 방법을 쓰더라도 알고리즘이 느리다면 시간초과를 피할 수 없고, 애초에 입력이나 출력이 작으면 차이도 없으며, 분별없이 사용했다간 추하다는 소리를 들을 수 있다. 그러나 본인이 가능한 알고리즘 수준에서의 최적화를 모두 했다면 필수불가결한 존재임이 분명하다.
백준에서 코드의 실행 시간을 4ms라도 더 줄여보려고 하는 사람들에게 이 내용이 도움이 된다면 좋겠다.