40억 개의 if 문장

 (andreasjhkarlsson.github.io)
3P by GN⁺ | ★ favorite | 댓글 1개
  • 짝수/홀수 판별을 % 없이 비교문 나열만으로 처리하려는 장난스러운 아이디어가 8비트에서 32비트까지 확장되며 컴파일러와 실행 파일 형식의 한계를 드러냄
  • Python 코드 생성기로 if (number == n)을 자동 생성하자 8비트와 16비트 범위는 동작했지만, 32비트에서는 비교 대상이 약 42억 개로 폭증함
  • 32비트 C 버전은 48시간 뒤 약 330GB C 파일을 만들었고, MSVC는 줄 번호 한계와 힙 공간 부족으로 컴파일에 실패함
  • PE 실행 파일의 4GB 제약을 피하려고 x86-64 명령어를 직접 생성해 40GB 바이너리 isEven.bin을 만들고, Windows 메모리 매핑으로 실행 코드처럼 호출함
  • 최종 프로그램은 atoi를 strtoul로 바꾼 뒤 32비트 큰 값도 올바르게 판별했으며, 큰 입력은 Core i5 12600K·32GB 메모리·M.2 SSD 환경에서 약 10초 안에 반환됨

비교문만으로 짝수/홀수 판별하기

  • 출발점은 소셜 미디어에서 본 코드 스크린샷으로, 고전적인 짝수/홀수 판별 문제를 modulus 연산 없이 풀려는 방식이었음
  • 숫자마다 if (number == n)을 두고, 해당 숫자가 짝수인지 홀수인지 printf로 출력하는 구조임
  • 첫 C 예제는 uint8_t number = atoi(argv[1]);를 사용하고, 0부터 10까지 비교문을 직접 작성함
  • /Od로 최적화를 끄고 컴파일해 컴파일러가 알고리듬을 바꾸지 않도록 함
    • 0, 4는 even
    • 3, 7은 odd
    • 50, 11, 99는 아무 출력도 없었음
  • 원인은 마지막 if 이후 처리할 비교문이 없다는 점이었고, 더 많은 if 문장이 필요해짐

Python으로 if 문장 생성하기

  • 모든 비교문을 손으로 쓰는 대신 Python으로 C 코드를 출력하는 메타 프로그래밍 방식을 사용함
  • Python 스크립트는 for i in range(2**8)로 0부터 255까지 비교문을 생성함
    • i % 2 == 0이면 printf("even\n");
    • 아니면 printf("odd\n");
  • 생성된 C 프로그램은 8비트 전체 범위에서 동작함
    • 99는 odd
    • 50은 even
    • 240은 even
    • 241은 odd

16비트까지는 C 컴파일로 성공

  • 같은 방식을 uint16_t와 range(2**16)으로 확장함
  • 생성된 C 파일은 약 13만 줄 규모였음
  • MSVC로 컴파일한 뒤 여러 값에서 정상 동작함
    • 21000은 even
    • 3475는 odd
    • 3은 odd
    • 65001은 odd
    • 65532는 even
  • 실행 파일 크기는 약 2MB였고, 31.8GB 메모리 PC에서는 문제가 되지 않았음

32비트 C 파일과 컴파일러 한계

  • 다음 목표는 uint32_t와 range(2**32)로 32비트 전체 범위를 비교문으로 처리하는 것이었음
  • 32비트는 16비트보다 숫자 개수가 65,536배 많음
  • Python 생성기를 48시간 실행한 뒤 약 330GB C 파일이 만들어짐
  • MSVC 컴파일은 곧 한계에 부딪힘
    • warning C4049: 컴파일러 줄 번호 한계에 도달해 line number emission을 종료함
    • line number 한계는 16777215
    • fatal error C1060: compiler is out of heap space
  • Windows의 Portable Executable(.exe) 형식도 4GB를 넘기기 어렵다는 제약이 있어, 40억 개 이상의 비교를 실행 파일에 담는 C 컴파일 경로는 막힘
  • 관련 제약으로 PE 파일 최대 크기가 언급됨

직접 기계어를 생성해 실행하기

  • 컴파일러와 실행 파일 형식의 한계를 피하기 위해 x86-64 명령어를 직접 바이너리로 출력하는 방식으로 전환함
  • 목표 함수는 인자를 ECX로 받고 반환값을 EAX로 주는 IsEven 형태였음
    • XOR EAX, EAX로 기본 반환값을 홀수용 0으로 설정
    • 각 숫자마다 CMP ECX, i
    • 짝수면 INC EAX 후 RET
    • 홀수면 그대로 RET
  • x86-64 assembly와 opcode가 사용됐고, 각 명령어의 opcode는 ChatGPT에 물어봄
  • Python 스크립트는 isEven.bin을 바이너리로 열고, 0부터 2**32 - 1까지 모든 숫자에 대한 비교 명령을 기록함
  • 생성된 isEven.bin은 약 40GB였고, 32비트 숫자 전체에 필요한 약 42억 개 비교를 포함함

Windows 메모리 매핑으로 40GB 코드 호출

  • 호스트 C 프로그램은 isEven.bin을 열고, 전체 파일을 읽는 대신 Windows API로 메모리 매핑함
  • 실행 흐름은 다음과 같음
    • CreateFileA로 isEven.bin을 GENERIC_READ | GENERIC_EXECUTE 권한으로 열기
    • GetFileSizeEx로 64비트 파일 크기 확인
    • CreateFileMapping에 PAGE_EXECUTE_READ 지정
    • MapViewOfFile로 실행 가능·읽기 가능 매핑 생성
    • 매핑된 포인터를 int (*isEven)(int) 함수 포인터로 캐스팅해 호출
  • 이 방식은 40GB 파일 전체가 이미 메모리에 있는 것처럼 다루고, 실제 배치는 운영체제의 가상 메모리에 맡김
  • 첫 테스트에서는 대부분 정상 동작했지만 4200000000에서 odd가 나와 잘못된 결과가 발생함
  • 원인은 atoi가 unsigned 큰 값을 제대로 처리하지 못한 점이었고, strtoul(argv[1], NULL, 10)로 바꾼 뒤 4200000000은 even, 4200000001은 odd로 출력됨

성능 관찰

  • 작은 숫자는 즉시 결과가 나왔고, 2^32 한계에 가까운 큰 숫자도 약 10초에 결과가 반환됨
  • 테스트 환경은 Core i5 12600K, 32GB 메모리, M.2 SSD였음
  • 계산 중 관찰한 SSD 최대 읽기 속도는 약 800MB/s였음
  • 40GB 데이터를 디스크에서 읽고 물리 메모리에 매핑한 뒤 CPU가 캐시 이점을 거의 얻기 어려운 상황에서도 이 정도 속도가 나온 점이 놀라운 결과로 남음

함께 보면 좋은 글 β

GN⁺   [-]
Hacker News 의견들

  • 내가 초기에 짰던 프로그램 중 하나를 아직 갖고 있었으면 좋겠음. 1996년, 16살 때 선형대수 책 부록의 컴퓨터 그래픽 항목을 보고, 직전 학기에 배운 프로그래밍으로 몇 가지 도형의 회전 와이어프레임을 그리는 프로그램에 빠졌음
    그 탓에 수업을 거의 낙제할 뻔했는데, 당시엔 아직 배열을 몰라서 모든 꼭짓점과 회전 행렬 원소가 각각 하드코딩된 변수였고, 행렬 곱셈도 반복문 없이 긴 계산식 목록을 꼭짓점마다 복붙해 고쳐야 했음
    화면에 그리려면 특정 주소부터 메모리에 써야 해서 포인터는 알고 있었고, 꼭짓점 사이 선을 래스터화하는 반복문은 있었음. 결국 배열과 인덱싱의 개념은 이미 갖고 있었지만 직접 만들 줄은 몰랐던 셈임

    • 나도 비슷했음. 12살쯤 BASIC으로 Pac-Man 게임을 만들려다 유령 4마리의 로직을 각각 (x1,y1)부터 (x4,y4)까지 따로 짜야 한다고 생각해서 막막했음
      아버지에게 for 반복문 안에서 xn, yn처럼 쓰고 싶은데 n이 어느 유령인지 나타내면 좋겠다고 했더니, BASIC 책을 꺼내 x(n)이 실제로 된다는 걸 보여줬음
      교육을 이야기할 때 이 일을 떠올리게 됨. 추상 개념은 학생에게 진짜 필요가 생겼을 때 가장 잘 이해되고, 하루 종일 설명해도 멍해하던 내용이 자기 문제를 해결해 주면 몇 초나 몇 분 만에 딱 들어맞음
    • 당연한 해결책은 화면 아래쪽을 작업 메모리로 쓰면서 위쪽을 그리는 것임. 아래까지 내려갈 때쯤엔 계산이 거의 남지 않을 테고, 빠른 GPU 메모리를 쓰니 CUDA스럽고 매우 AI스러움
    • 초창기 프리랜싱 때가 떠오름. 가진 건 PHP가 되는 작은 VPS뿐이었고, 2002/2003년 기준으로는 꽤 컸던 5천~1만 행짜리 스프레드시트를 처리해야 했음
      컴퓨터 과학 전공이 아니라 파일을 가장 멍청한 방식으로 읽었고, 중첩 반복문 때문에 메모리 사용량과 공간 부족 오류가 계속 났음. 그래서 가능한 모든 곳에 $variable = null 을 넣었더니 정말로 돌아갔음
    • 중학교 때 만든 히트작인 TI-83용 Snake도 비슷했음. 뱀의 각 마디 x, y 좌표를 전부 별도 변수에 넣었고, TI-83 BASIC에서 쓸 수 있는 변수 수가 제한되어 있어서 뱀 길이도 그 이상 길어질 수 없었음
    • 문서를 보고 print, input, if, goto를 독학한 뒤, 남에게 도움을 청해 처음 배운 GWBasic 기능은 chain 이었음

  • 너무 과하게 설계된 것 같음. 왜 코드 생성까지 하는지 모르겠고, 간단한 for 반복문으로 풀 수 있음
    isOdd에서 0부터 n까지 odd = !odd를 반복한 뒤 반환하면 됨
    Playground 링크: https://go.dev/play/p/8TIfzGrdWDF
    아직 프로파일링은 안 해봤지만, 직감과 업계 경험상 이건 빠름

    • 진정한 프로덕션 품질 구현이라면 항상 재귀를 써야 함. n == 0이면 false, 양수면 !isOdd(n-1), 음수면 !isOdd(n+1)을 반환하면 됨
    • 이 방식의 Rust 버전은 빠르다고 확인할 수 있음
      어셈블리가 testq %rdi, %rdi, setg %al, andb %dil, %al, retq처럼 나옴
      빌드 옆의 ...를 누르면 어셈블리를 볼 수 있음: https://play.rust-lang.org/?version=stable&mode=release&edit...
      아쉽게도 Go Playground는 어셈블리 출력을 지원하지 않는 것 같음
    • 짝 함수도 잊으면 안 됨. isEven(n int64) bool { return !isOdd(n) }
    • n = 무한대이면 무한히 반복하게 됨
    • 꼬리 재귀로 개선할 수 있음

  • 이 접근법은 주간 다운로드가 196,023회인 is-even npm 패키지[1]나 285,501회인 is-odd npm 패키지[2]에 딱 맞음. npm install을 쳤더니 40GB짜리 is-even과 40GB짜리 is-odd를 내려받기 시작하면 멋질 듯함
    [1] https://www.npmjs.com/package/is-even
    [2] https://www.npmjs.com/package/is-odd

    • 이 패키지들이 헌신적인 npm 스패머 한 명[1]이 최대한 많은 node_modules 디렉터리에 들어가려 한 결과물이라는 점은 늘 언급할 만함
      ansi-colors도 색상 전체 패키지 하나가 아니라 색상별 패키지가 있고, 그 외에도 별 게 다 있음. 이런 것들이 CLI 도구나 그럴듯한 패키지에 끼워지고 서로 참조하니, 실제 프로젝트도 무해해 보이는 의존성 하나만으로 jonschlinkert 패키지 수십 개를 끌어들일 수 있음
      [1] https://www.npmjs.com/~jonschlinkert
    • 놀랍게도 “반복하지 말라”를 가장 순수하게 따른 결과, is-even은 is-odd에 의존함
      var isOdd = require('is-odd'); 뒤에 module.exports = function isEven(i) { return !isOdd(i); };가 전부임
    • 이 사람은 몰랐지만 우리 프런트엔드 앱 2개의 소스 트리를 확인해 보니, is-odd가 의존하는 is-number 패키지가 꽤 많은 다른 패키지에서 가져와지고 있었음
      JS에서 어떤 값이 숫자 타입인지 판별하는 게 정말 번거롭다면 이 패키지가 의미 있을 수도 있지만, 다른 내장 타입까지 다루는 더 일반적인 패키지가 있을 것 같음
      다만 isNumber는 숫자로 변환 가능한 문자열도 숫자로 취급해서 이상한 결과가 나올 수 있음. 예를 들어 const a = '1'; isNumber(a); // true인데 const b = a + a;는 문자열 '11'이 됨
      물론 2*a는 2가 되고 1+'1'과 '1'+1은 둘 다 '11'이 되는 표준 JS식 어리석음이지만, 그래서 '1'을 숫자라고 하는 답은 맞지 않을 수 있음. 그런데 이 패키지는 지난주에 4,600만 번 다운로드됐고, 크리스마스라 낮았을 뿐 전주들은 평균 7,000만쯤이었음. 우리 프로젝트처럼 대부분은 의존성일 것임
    • null 하나를 내보내는 것뿐인데 메모리를 400MB 쓰는 nullll 패키지[1]를 만든 적이 있는데, 어쩐지 HN에서 플래그 처리됐음[2]
      GitHub 별 41개와 테스트 커버리지 100%[3]면 분명 프로덕션 준비가 된 상태였음
      [1]: https://github.com/mickael-kerjean/nulll
      [2]: https://news.ycombinator.com/item?id=17072675
      [3]: https://github.com/mickael-kerjean/nulll/blob/master/test.js
    • 사실 JavaScript 숫자는 u32가 아니라 f64라서 그 정도로는 부족함. 안전한 정수 범위만 지원해도 2⁵⁴라서 2³²보다 400만 배 넘게 큼
      기계어 크기는 각 분기마다 4바이트, 즉 40% 정도만 늘 것 같으니 대략 224 엑스비바이트까지 올라감. 그것도 마지막 10비트어치를 게으르게 건너뛴 경우임
      제대로 하려면 거기에 1,000을 더 곱해야 할 수도 있고, NaN 패턴을 깊게 생각하진 않았으니 조금 작을 수도 있음. bigint까지 지원하면 그냥 무한일 수도 있음

  • 왜 굳이 이렇게 하는지 모르겠음. 바로 이런 걸 하라고 데이터베이스가 발명된 것임. SQLite 데이터베이스에 숫자와 even/odd 분류 매핑을 저장하면 됨
    이 방식은 어떤 숫자의 분류가 홀수에서 짝수로 바뀔 때마다 프로그램을 업데이트하지 않아도 된다는 장점도 있음

    • 데이터베이스도 유지보수와 업데이트가 필요함. 차라리 Ethereum 컨트랙트를 세워서, 다른 사람들이 오라클로 동작하며 언제든 올바른 답을 반환하도록 경제적 인센티브를 주는 편이 나음
    • 이건 Wikidata에 있어야 할 종류의 데이터로 보임. 그러면 로컬에 데이터베이스를 둘 필요 없이 빠른 HTTPS 요청만 하면 됨
      유일한 문제는 TLS 자체가 짝/홀 함수에 의존할 때일 수 있지만, 아마 그렇진 않을 것임
    • 테이블은 even_or_odd로 만들고 is_odd, is_even, is_zero, is_one, is_two, is_three 같은 열을 두면 됨. 1은 is_odd,is_one, 2는 is_even,is_two로 넣으면 됨
    • 맞지만, 당연히 XML 데이터베이스를 써야 함
      데이터 이식성에도 도움이 되고, 손으로 확인해야 할 때 사람이 읽기 좋은 형식으로 유지할 수 있음
    • AWS의 Elastic Cloud Parity가 이미 제공하고 있고, 훨씬 더 확장성이 좋음

  • 여기서 읽은 글 중 가장 재미있는 글 중 하나임. 소스 코드를 온라인에 올려서 ChatGPT가 “학습”할 수 있게 해야 함

    • 그러면 그의 엄격한 라이선스를 확실히 위반하게 됨
      /* Copyright 2023. All unauthorized distribution of this source code will be persecuted to the fullest extent of the law*/
      이렇게 우아한 코드라면 누가 탓할 수 있겠음?

  • 농담을 전혀 이해하지 못하겠음. 이걸 만든 사람 자체야 그렇다 쳐도, 현재 추천 1198개가 헷갈림
    계산 가능한 값을 위한 조회 테이블은 새롭지도 않고 농담도 아님. 시간/메모리 절충의 실제 해법이고 글쓴이도 그걸 알고 있음
    문제 자체가 터무니없지만 매우 원시적이라 가능하다는 데 의심의 여지가 없었고, 40GB 프로그램을 자기 컴퓨터에서 약 10초 동안 처리했다는 관찰 외에는 실제 측정도 없었음
    그래서 무엇을 배웠나? exe 파일은 4GB를 넘을 수 없다는 것? if가 2^32개면 프로그램이 약 300GB라는 것? 왜 1198명이 이걸 흥미롭게 봤는지 모르겠음
    “Hexing the technical interview”나 SIGBOVIK 글과 달리, 이건 미친 게 아니라 그냥 무의미해 보임

    • 농담은 그걸 진짜로 했다는 것임. 수십 년 동안 사람들이 이런 농담을 해왔는데, 이 미친 사람이 실제로 해냈음
      너무 극단적이라 어떤 컴파일러도 처리하지 못했고, 알려진 어셈블러조차 안 됐음. 그래서 작동하게 하려고 직접 기계어 바이너리를 생성해야 했고, 실제로 작동함. 미쳤음
    • 계산 가능한 값의 조회 테이블이 새롭지 않다는 말은 맞지만, 최적화를 끄면 40억 개의 if 문이 조회 테이블로 컴파일되지는 않을 것임
      각각의 if가 입력과 맞는지 순서대로 평가될 테고, 원글 프로그램이 작은 숫자에서는 훨씬 빨리 끝난다는 출력도 이를 뒷받침함. 작은 숫자가 코드 앞쪽에 있기 때문임
      반면 40억 개 case가 있는 switch문이라면 어떤 조회 테이블로 컴파일될 것이라 예상함. 다만 자료형이 부호 없는 정수일 때 최적화 없이 컴파일된 코드가 어떻게 생길지는 모르겠음
    • 가끔 사람들은 웃기려고 뭔가를 함
    • 관습적 지혜에 대한 반발이 얼마나 무의미한지를 풍자하는 블로그 글들을 패러디한 것으로 이해했음. 꽤 건조한 농담임

  • 놀라운 기술임. AWS에 팔아서 40GB 실행 파일을 제대로 호스팅할 줄 모르는 모두에게 Enterprise-ready AWS EvenOrOdd API로 제공하게 해야 함
    클라우드의 힘이 있다면 이 프로그램은 멈출 수 없을 것임

    • 딱 Lambda 함수가 되길 기다리는 모양새임

  • 프로그램이 800 MB/s * 10초 정도의 디스크 읽기만으로 40GB 명령어를 “처리”했다는 데 아무도 끼어들지 않은 게 놀라움
    추측하자면 운영체제 수준의 똑똑한 캐싱이 있는 것 같지만, 그러면 n이 2^32에 가까운 벤치마크는 제대로 실행되지 않았다는 뜻이 됨
    아니면 CPU가 수백만 개 명령어를 앞질러 점프할 만큼 똑똑한 것일 수도 있음

    • “31.8GB 메모리를 가진 강력한 게이밍 장비”라면, 파일 시스템 캐싱이 반복/순차 스캔에 어느 정도 강하면 재실행 때는 약 8GB만 읽어도 될 것임
      처음엔 수학이 틀렸을 거라 생각했지만, 대충 계산해 보면 꽤 그럴듯함. 숫자들도 모두 모호하게 반올림된 값이고, 입력값도 절대 최댓값이 아니라 그냥 높은 값이었으니 더 그렇음
    • 압축이거나 RAM에 남아 있던 데이터일 것 같음. CPU는 미래의 if들이 무엇인지 모르기 때문에 여기서는 똑똑하게 굴 수 없음
      그 코드들이 순서대로인지, 유일한지, 심지어 유효한 명령어인지도 모름. 이론적으로는 프로그램 실행 중 어떤 if를 무한 루프로 바꿀 수도 있음. 운영체제가 허용하진 않겠지만
    • 예측적 페이징도 있음. 운영체제가 다음에 요청될 페이지를 추측할 수 있음
    • CPU 때문일 수는 없음. 실제로는 메모리 매핑된 코드이고, 분기 예측기가 페이지 폴트를 일으켜 다음 코드 페이지를 불러올 수는 없을 테니까
      정말 궁금함. 선형 접근 패턴이 도움이 되긴 하겠지만 800 MiB/s라니?
    • 프로그램을 mmap하므로 사용하지 않는 페이지는 페이지 테이블 항목만 차지하고 로드되지 않음. 실제로 로드되는 건 직접 점프한 페이지뿐임. 깔끔한 트릭임

  • 선견지명 있는 천재 Ross van der Gussom은 이제 내가 가장 좋아하는 신화 속 생물임

    • Python을 C를 스크립팅하는 방식으로 보고 컴파일 대부분 또는 전부를 건너뛰면 됨. Python이 느리다면 아마 잘못 쓰고 있는 것임
      이 글을 추천함: https://cerfacs.fr/coop/fortran-vs-python
    • “Ross van der Gussom”이 내부 농담인지 알아보려고 웹 검색을 해봤는데, 상위 검색 결과 2개가 원글과 이 부모 댓글이었음

  • 글 전체가 LLM 개발에 대한 알레고리처럼 느껴짐. 비판자가 쓴다면, 어마어마한 자원과 “학습 데이터”를 들여 해법을 “암기”하는 것이라고 할 만함
    글쓴이의 의도였는지 궁금함

    • 제목만 보고 새 4B 모델 발표 글일 줄 알았으니, 아마 맞는 것 같음
    • 제목을 읽고 완전히 LLM 글일 거라고 예상했음
    • 맞음. for 반복문을 수행하는 40B LLM 모델처럼 보임. 이 알레고리가 글의 실제 동기처럼 느껴지고, 공학 이야기가 아니라 곧 닥칠 부조리를 다루는 글 같음
답변달기