Quanta 기사들이 수학에 시적이거나 과장된 표현을 너무 많이 섞어서 오해를 불러일으키는 점이 아쉬움 Quanta 기사에서 “특정 작업들은 실행 시간에 비례하는 만큼의 공간이 필요했다”고 말하지만, 복잡도 위계(hierarchy)만 봐도 그런 일반적 직관이 나오진 않음 “일부 알고리듬”에 국한된 이야기만으로 전체 직관을 만들 순 없음
독자에게 너무 친절한 건지, Quanta가 P 복잡도 클래스를 “합리적인 시간 내에 풀 수 있는 모든 문제”라고만 설명하면서 polynomial이라는 용어 자체를 안 쓴 게 좀 모욕적으로 느껴짐
Perl 철학을 담은 “Camel Book”에서 이런 구절이 있음: “메모리가 부족하면 사면 되지만, 시간이 부족하면 방법이 없음” 그저 재미있는 책이라 애정함
이 말도 양면성이 있다는 생각임 컴퓨터 메모리보다 더 필요한 프로그램은 당장 돌릴 수 없는 반면, 오래 걸려도 어쨌든 실행은 할 수 있으니 시간도 결국 중요한 자원임
미리 계산해둔 값들을 저장해둔 룩업 테이블의 승리 예전엔 프로세서가 필요 없을 정도로 모든 연산을 중앙에서 저장할 수 있다면 처리 속도가 혁신될 수 있을 것 같았음 (사실 빠른 검색이라는 별도의 난제 존재)
예전에 저장 시스템 일을 시작할 때 4KB 블록을 미리 전부 계산해서 저장해두자는 아이디어를 냈는데, 고유 4KB 블록 수가 우주의 원자 수보다 많다는 지적을 받고 깜짝 놀랐던 기억임
HashLife라는 알고리듬이 Conway의 Game of Life에서 이와 비슷한 작업을 Turing 완전하게 수행함 너무 복잡하고 다양한 상태를 다룰 때도 점프하듯 미래 상태를 미리 계산할 수 있다는 사실이 신기하게 느껴졌음
retrieval(검색)룩업 자체도 캐싱한다는 아이디어에는 문제가 없다는 농담
커뮤니티 단위 캐싱, 즉 프리컴파일된 소프트웨어 배포 방식에서 사실상 구현되고 있음 효율적으로 컴파일하지 못해서 언어 기능을 포기해야 한다는 전통적 장벽도, 클라우드 병렬 컴파일과 전세계 캐시로 극복 가능 출시에 한 번만 컴파일 되면 다 함께 쓸 수 있음
“중앙에 모든 연산을 저장한다면 프로세서가 필요 없을 것 같다”는 말의 연장선으로, 아예 검색 내역까지 메모이즈해줄 생각임
Quanta 스타일이 시적인 탓에 실제로 이 연구가 실질적인 컴퓨터에도 적용 가능한지, 아니면 순수 이론적 시나리오인지 이해하기 어려움 더 많은 메모리를 쓰는 대신 컴퓨터 속도가 느려진다는 의미인지 궁금함
raster 그래픽 프로그래밍을 오래 해왔고, 룩업 테이블 활용이 자연스레 몸에 배어 있음 최근엔 여러 도형을 미리 DB에 넣어두고 쿼리 때마다 최적화된 결과를 쓸 수 있는 서버 도구를 개발함 복잡하지 않고 직관적인 패턴임 MIT 교수에게 특별히 배운 것도 아니고 그냥 몸으로 익힌 작업 방식이었는데 수학적으로 정당하단 증거를 보니 뿌듯함 많은 알고리듬적 노하우가 사실 실무자들의 경험에서 비롯될 때도 많다는 생각임 (ex: winding number 알고리듬)
게임의 최적화를 하면서 요즘 얻고 있는 성과는 모두 룩업 테이블을 상황에 맞춰 다루는 방식임 꼭 정적 배열만 룩업 테이블일 필요 없고, 시간에 따라 약간씩 변하는 데이터도 마찬가지로 활용 가능함 GPU에서 작업을 처리하는 쪽으로 눈을 뜨게 됐고, 컴파일 혹은 런타임 때 정적으로 만들어지던 테이블을 런타임 중 일부만 바꿔서 텍스처처럼 GPU로 넘기는 구조에 효율성이 큼 어디까지를 룩업 테이블로 부르느냐의 경계가 흐릿해짐
공간(메모리)이 시간보다 훨씬 많은 결과값을 표현할 수 있다는 점이 직관적으로 느껴짐 테이프 길이 n에서 O(n) 시간 동안 쓸 수 있지만, 2진수 테이프라면 n길이에 2^n가지 구성이 존재함 공간을 제대로 쓰면 시간에 비해 훨씬 많은 표현력이 생긴다고 생각함
내 직관: 셀 하나에 수백 번 계산한 중간 결과가 저장될 수 있음 만약 중간 결과를 저장하지 못하고, 매번 똑같은 걸 다시 계산한다면 효율이 크게 떨어짐 캐시에 0% 히트율이 나오는 상황은 매우 드물고, 대부분은 공간을 활용한 효율화가 가능함 반대로 한 번의 시간으로 수백 개 셀의 공간을 대체하긴 어렵고, 현재 컴퓨팅 구조에선 무한한 SIMD가 불가능함
O(1) 메모리 랜덤 접근 가정이 너무 당연시되는데, 실제로는 컴퓨터 크기가 커질수록 접근 비용이 O(n^(1/3))까지 커짐 데이터센터에서 생생히 체감 가능 UMA 말고 다른 모델이었던 걸로 기억남
P ≠ PSPACE가 증명되지 않은 만큼, 직관보다 수학적으로 입증하는 게 어려운 영역임
한편으론 맞는 말이지만, 병렬화가 어려운 문제(예: alternating machine PTIME=PSPACE)에서는 공간이 큰 이득을 주지 못할 수도 있음 논문에선 t/log t에서 sqrt(t log t)로의 도약이 혁신적이지만, 무한 병렬화에도 극복되지 않는 실체적 한계가 있을 것임
실무에선 작업 특성에 따라 달라짐 대입 연산보다 저장소 접근이 훨씬 느릴 때는 다시 계산하는 게 빠를 때도 있음
시간-공간 간 “역관계”는 한쪽 자원을 제한할 때, 다른 쪽 최적값을 무조건 얻을 수 없는 현상으로 설명 가능함 예를 들어 정렬 알고리듬에서 시간/공간/안정성 세 가지 제약이 있을 때, 안정성을 추가로 만족하면 오히려 시간이나 공간 효율이 떨어짐 현재까지는 비안정 정렬만큼 빠르고 메모리도 적게 드는 안정 정렬은 없음
Quanta Magazine의 기사 스타일이 개인적으로 마음에 듦 컴퓨터 과학자뿐 아니라 관련 분야에 관심 있는 일반인까지 시야를 넓혀줌 조감도와 친근한 설명 방식이 새로운 시각과 아이디어를 주는 계기임
Ryan Williams의 강연과 논문을 링크로 공유함
single-tape 튜링 머신이 입력으로 이진수 N을 받고, tape 오른쪽에 1을 N개 쓰려고 하면, 시간 N에 N칸 공간이 필요해 보임 그런데 어떻게 N보다 적은 공간에서 이걸 시뮬레이션할 수 있는지 궁금함 tape의 임의 위치로 점프가 불가능한 튜링 머신 구조 특성상 실제 컴퓨터랑 어떤 관계가 있는지도 궁금함
멀티테이프 튜링 머신은 단일 테이프보다 아주 빠르고, 여기서 말하는 “공간”은 입력/출력 제외한 임시 작업 공간임
논문은 결정 문제가 주된 대상으로, 출력이 1비트만 필요한 상황만 고려함 출력이 N비트라면 사실상 N개의 결정 문제를 붙인 것과 동일하다는 설명임
Hacker News 의견