백준 온라인 저지의 맞힌 사람 목록은 제출 기록을 실행 시간의 오름차순으로, 사용 메모리의 내림차순으로, 코드 길이의 오름차순으로 정렬해 보여줍니다.
이는 “효율적인” 코드를 일반적으로 판별하는 기준입니다.
알고리즘 문제 해결을 해 보신 분이라면, 맞힌 사람 목록에 연연하지 않더라도 자신의 코드가 효율적이기를 기대하실 것이라 생각합니다.
보통 연산량이 많지 않을 경우 C/C++ 기준으로 0 ms의 실행시간을 가집니다.
사용 메모리는 C의 경우 보통 1112 KB, C++의 경우 1112 KB 혹은 2020 KB에서 시작합니다.
그런데 가끔 맞힌 사람 목록에 C 혹은 C++에서 156 KB의 메모리 사용량이 표시되는 경우가 있습니다.
이는 __libc_start_main을 재정의하여 이룰 수 있습니다.
아래는 Hello World!를 출력하는 156 KB 프로그램의 예시입니다.
#include <unistd.h>
int main() {}
void __libc_start_main() {
write(1, "Hello World!", 12);
_Exit(d);
}여기서 몇 가지 의문이 생깁니다.
__libc_start_main함수는 무엇인가?- 왜
main만 사용하여 156 KB를 달성할 수 없는가? printf나puts가 아닌write를 사용한 이유는 무엇인가?- 0 KB는 달성할 수 없는가?
먼저 __libc_start_main의 함수의 정체를 알아보도록 하겠습니다.
BOJ에서 사용하는 C 라이브러리 구현체인 glibc 2.23의 코드 중 /csu/libc-start.c에서 해당 함수를 찾을 수 있습니다.
여러 기능을 수행하지만, 가장 중요한 것은 C 라이브러리가 내부적으로 사용하는 IO 버퍼나 글로벌 락 등을 초기화하는 일입니다.
printf나 puts를 사용하지 못하는 이유가 바로 이것입니다.
write 함수는 버퍼나 락을 사용하지 않지만, printf와 puts는 버퍼와 락을 사용하므로 __libc_start_main 재정의 시 런타임 에러가 발생할 수 있습니다.
main만을 사용하여 156 KB를 달성하지 못하는 이유도 같습니다.
main 함수가 실행되기 이전에 이미 버퍼와 락을 할당하므로 main에서 메모리를 낭비하지 않더라도 최대 메모리 사용량에는 버퍼와 락의 용량이 남게 됩니다.
그렇다면 왜 0 KB가 아닌 156 KB인 것일까요?
그 답은 프로그램의 실행 과정과 관련이 있습니다.
BOJ 환경에서 C 프로그램은 동적 링크되는데, 동적 링크된 실행 파일을 실행하기 위해서는 ld-linux.so가 필요합니다.
프로그램과 함께 ld-linux.so도 메모리에 적재되면서 ld-linux.so의 크기 156 KB가 남게 되는 것입니다.
정적 링크된 프로그램을 만들 수 있다면 0 KB도 가능할지 모릅니다.
다만 아직 성공한 예는 없습니다.
Rust의 경우 #![crate_type = "cdylib"] 속성을 지정하여 정적 링크된 프로그램을 만들 수 있으나 아직 밝히지 못한 이유로 2188 KB가 표기됩니다.
156 KB 프로그램에 관심이 생기셨다면, 언제든 solved.ac 디스코드로 놀러오세요!