From c2b955ddf87b1057095b8fa7ca8917190daac82c Mon Sep 17 00:00:00 2001 From: eunhhu Date: Mon, 5 Oct 2026 14:31:30 +0100 Subject: 023: near C is the aim (each within 1.25x, the geometric mean within 1.1x), not past it; representation first, since a keyed list given keys in order stays FLAT and is searched by halves (knapsack's and matmul's 300x) --- docs/design/023-optimizing-tier.md | 23 +++++++++++++---------- 1 file changed, 13 insertions(+), 10 deletions(-) (limited to 'docs') diff --git a/docs/design/023-optimizing-tier.md b/docs/design/023-optimizing-tier.md index bcc1064..a0e2011 100644 --- a/docs/design/023-optimizing-tier.md +++ b/docs/design/023-optimizing-tier.md @@ -1,10 +1,11 @@ # 023 — 최적화 계층: 여러 종류의 일에서 깡연산으로 C를 넘기 -작성일: 2026-10-05. 상태: 설계와 착수 기준(구현 전에 커밋한다). +작성일: 2026-10-05. 상태: 설계와 착수 기준(구현 전에 커밋한다). 같은 날 기준을 C에 가깝게로 고쳤다(사용자). [022](022-arrays-and-registers.md)의 BFS는 C(`bfs.c`)보다 빨라졌지만, 그것은 C가 하지 않는 미리 읽기 덕이었다. 미리 읽기를 끄면 16 ms 대 9.9 ms로 1.6배 느리고, C에 같은 미리 읽기를 하면 다시 C가 앞선다. BFS 하나를 맞춰 넘는 것은 목표가 아니다. 목표는 같은 -aup 코드, 같은 뜻, 같은 기계에서 **여러 종류의 일을 C만큼, 모아 보면 C보다 빠르게** 계산하는 것이다. 그러려면 지금처럼 루프 묶음의 +aup 코드, 같은 뜻, 같은 기계에서 **여러 종류의 일을 C에 가깝게** 계산하는 것이다. 메모리 안의 계산을 두루 C 가까이 하는 것이 뜻이고, +C를 완전히 제치는 것은 목표가 아니다(2026-10-05, 사용자). 그러려면 지금처럼 루프 묶음의 명령을 하나씩 기계어로 옮기는 것이 아니라, 블록 전체를 SSA로 올려 타입과 범위를 알고, 뜻을 지키는 검사를 루프 밖으로 끌어내고, 레지스터를 할당하는 계층이 모든 블록에 있어야 한다. @@ -69,8 +70,8 @@ roots와 BFS만 기계어로 돈다. 나머지는 JIT의 값 모형이 거르거 - join은 처음 쓴 바닥(키 8바이트, 색인과 위치가 따로)에서 1.8이었다. 칸에 키와 위치를 함께 두고 키를 4바이트로 좁혀 0.91이 됐다: 표현이 몫을 정한다. -**그래서:** 바닥의 기하 평균이 0.90이다. 계층이 내는 코드가 바닥의 1.11배 안이면 모아 보아 C를 넘는다. 일마다로는 바닥의 1.22배 안이면 -C의 1.25배 안이다(roots 1.02 × 1.22). **빠듯하다.** JIT의 코드는 C 컴파일러의 것보다 길기 쉽다. 그래도 미달이면 미달로 적는다. +**그래서:** 바닥의 기하 평균이 0.90이다. 계층이 내는 코드가 바닥의 1.22배 안이면 모아 보아 C의 1.1배 안이고, 일마다로도 바닥의 1.22배 +안이면 C의 1.25배 안이다(roots 1.02 × 1.22). JIT의 코드는 C 컴파일러의 것보다 길기 쉬우니 그만큼의 여유다. 미달이면 미달로 적는다. ## 원칙 @@ -148,11 +149,13 @@ C의 1.25배 안이다(roots 1.02 × 1.22). **빠듯하다.** JIT의 코드는 C ## 단계 -1. **IR**: 블록을 SSA로 올리고 타입과 범위를 낸다. 기계어는 그대로 두고, IR을 해석하는 시험용 실행기로 모든 검사의 프로그램을 - 실행기와 견준다(IR이 뜻을 옮겼는지). -2. **코드**: IR에서 레지스터를 할당해 기계어를 낸다. 모든 블록. 검사는 아직 제자리에. -3. **검사 끌어올리기, 루프마다의 작업량과 메모리 몫, 다시 돌리기**(결함이 나면 실행기로). -4. **표현**: 희소한 키의 해시 색인과 걸을 때의 정렬, 텍스트의 정수 자릿수. +1. **표현**(값이 가장 큰 것부터): 차례로 작은 정수 키를 받는 키 있는 리스트는 DENSE로(지금은 키가 차례를 어길 때만 DENSE가 되고, + 차례로 받으면 FLAT으로 남아 키로 찾기가 이분 탐색이다: knapsack과 matmul의 300배), 희소한 키의 해시 색인과 걸을 때의 정렬, + 텍스트의 정수 자릿수. 지금의 JIT과 실행기로 잰다. +2. **IR**: 블록을 SSA로 올리고 타입과 범위를 낸다. 기계어는 그대로 두고, IR을 해석하는 시험용 실행기(명령의 뜻은 실행기의 step으로, + 값마다 그 사실(정수, 범위, −0, 유한)이 맞는지 확인)로 모든 검사의 프로그램을 실행기와 견준다. +3. **코드**: IR에서 레지스터를 할당해 기계어를 낸다. 모든 블록. 검사는 아직 제자리에. +4. **검사 끌어올리기, 루프마다의 작업량과 메모리 몫, 다시 돌리기**(결함이 나면 실행기로). 단계마다 검사로 고정하고, 묶음을 재서 커밋한다. @@ -166,7 +169,7 @@ C의 1.25배 안이다(roots 1.02 × 1.22). **빠듯하다.** JIT의 코드는 C - 기기 사이: 같은 `pure-run` 46번이 Pi(계층), WSL2와 Mac(실행기)에서 출력, 오류, 종료 코드까지 같다. - **통과 조건**(RAM의 Pi 5, `suite-run` 11번의 중앙값, `PURE_AHEAD=0`) - 일마다 Pure의 중앙값이 같은 프로세스의 C의 **1.25배 안**이다. - - 일곱의 Pure / C의 **기하 평균이 1.0 아래**다. + - 일곱의 Pure / C의 **기하 평균이 1.1 아래**다. - BFS를 미리 읽기와 함께 재면 같은 미리 읽기를 한 C(`bfs_ahead`)의 1.0배 아래다. - **뜻의 값**: 일마다, 계층의 코드를 검사 없이 낸 것(`PURE_UNCHECKED=1`, 재기 위한 것이고 답이 같은지만 본다)보다 5% 넘게 느리지 않다. -- cgit v1.2.3