3P by neo 2달전 | favorite | 댓글 1개

40억 개의 if 문

  • 최근 소셜 미디어를 조사하던 중 기차 안에서 이 스크린샷을 발견함.
  • 이 코드는 시간-메모리 트레이드오프의 완벽한 예시임.
  • C 언어로 구현하여 성능을 높이고자 함.

코드 구성

  • C 언어로 짝수와 홀수를 판별하는 코드를 작성함.
  • 최적화를 비활성화하여 컴파일함.
  • 0부터 10까지의 숫자에 대해 정상 작동하지만 그 이상의 숫자에서는 문제 발생함.

메타 프로그래밍

  • Python을 사용하여 if 문을 메타 프로그래밍함.
  • 8비트 정수에 대해 짝수와 홀수를 판별하는 프로그램을 생성함.

16비트 확장

  • 16비트 정수에 대해 동일한 방식으로 프로그램을 확장함.
  • 약 130k 줄의 C 파일을 생성하고 컴파일함.

32비트 도전

  • 32비트 정수에 대해 프로그램을 확장하려 시도함.
  • 330GB 크기의 C 파일을 생성했으나 컴파일러가 힙 공간 부족으로 실패함.
  • Portable Executable 형식의 한계로 인해 4GB 이상의 파일을 처리할 수 없음.

직접 기계어 코드 작성

  • x86-64 어셈블리 언어로 직접 IsEven 함수를 작성함.
  • Python을 사용하여 기계어 코드를 수동으로 컴파일함.

실행 파일 생성

  • 40GB 크기의 파일을 생성하여 모든 32비트 정수에 대해 짝수와 홀수를 판별함.
  • 파일을 메모리에 매핑하고 함수 포인터를 사용하여 코드를 실행함.

최종 버그 수정

  • strtoul 함수로 교체하여 부호 없는 정수 파싱 문제를 해결함.
  • 프로그램은 매우 빠르며, 대용량 숫자에 대해서도 10초 이내에 결과를 반환함.

GN⁺의 의견

  • 중요성: 이 글은 프로그래밍의 기본 개념인 시간-메모리 트레이드오프를 이해하는 데 도움이 됨. 또한, 최적화되지 않은 코드가 실제 성능에 미치는 영향을 보여주는 좋은 사례임.
  • 흥미로움: 프로그래밍 언어 간의 성능 차이와 컴파일러의 한계를 실험적으로 탐구하는 과정이 흥미로움. 특히, Python과 C 언어를 비교하며 성능을 향상시키려는 시도가 재미있음.
  • 교훈: 이 글은 복잡한 문제를 해결하기 위해 때로는 비효율적으로 보일 수 있는 접근 방식이 실제로는 유용할 수 있음을 보여줌. 또한, 컴퓨터 과학에서 창의적인 해결책을 모색하는 것의 중요성을 강조함.
Hacker News 의견
  • 첫 번째 댓글 요약:

    • 1996년, 16세 때 처음 작성한 프로그램에 대한 추억.
    • 선형대수학 책의 컴퓨터 그래픽 부록을 보고 회전하는 와이어프레임을 그리는 프로그램에 몰두.
    • 배열을 몰라 변수를 하드코딩하고, 회전 행렬의 각 항목도 변수로 설정.
    • 포인터는 알아 화면에 그리기 위해 메모리 주소에 직접 쓰기를 함.
  • 두 번째 댓글 요약:

    • 코드 생성을 통한 복잡한 접근 대신 간단한 "for loop"로 해결 가능한 예시 제시.
  • 세 번째 댓글 요약:

    • is-evenis-odd npm 패키지에 대한 농담.
    • npm install을 사용하면 40GB 크기의 패키지가 다운로드되는 상상.
  • 네 번째 댓글 요약:

    • 짝수와 홀수를 분류하기 위해 데이터베이스 사용을 제안.
    • SQLite 데이터베이스에 숫자와 그 분류를 매핑하여 프로그램 업데이트 필요 없음.
  • 다섯 번째 댓글 요약:

    • 기사가 매우 재미있다고 평가.
    • 소스 코드를 온라인에 공개하여 ChatGPT가 학습할 수 있게 해야 한다는 의견.
  • 여섯 번째 댓글 요약:

    • 분산 버전에 대한 아이디어 제시.
    • 각 호스트가 자신의 도메인 이름과 일치하는지 확인하고 결과를 반환하는 방식.
  • 일곱 번째 댓글 요약:

    • AWS에 이 기술을 판매하여 AWS EvenOrOdd API로 제공하라는 제안.
    • 클라우드의 힘을 이용하면 프로그램이 더 강력해질 것이라는 의견.
  • 여덟 번째 댓글 요약:

    • 40GB의 명령어를 800MB/s * 10초의 디스크 읽기 속도로 처리하는 방법에 대한 의문.
    • OS 레벨의 스마트 캐싱이나 CPU가 명령어를 건너뛰는 최적화가 있을 것이라는 추측.
  • 아홉 번째 댓글 요약:

    • 룩업 테이블을 사용하여 비용이 많이 드는 연산을 피하는 기술에 대한 설명.
    • libdivide 라이브러리의 예시와 함께 8비트 정수 나눗셈을 룩업 테이블로 대체한 경험 공유.
  • 열 번째 댓글 요약:

    • 이진 탐색을 사용한 최적화 제안.
    • 중첩된 if-else 문을 사용하여 O(logN)의 시간 복잡도로 실행되도록 하는 방법에 대한 농담.