From dacc3cf3e1e7fe6554575cefdb4ac6d7a19a61c6 Mon Sep 17 00:00:00 2001 From: eunhhu Date: Wed, 30 Sep 2026 13:32:49 +0100 Subject: Say what finding items should gain, before measuring it (109) --- docs/research/109-finding-items.md | 34 ++++++++++++++++++++++++++++++++++ 1 file changed, 34 insertions(+) create mode 100644 docs/research/109-finding-items.md (limited to 'docs') diff --git a/docs/research/109-finding-items.md b/docs/research/109-finding-items.md new file mode 100644 index 0000000..2b55ff8 --- /dev/null +++ b/docs/research/109-finding-items.md @@ -0,0 +1,34 @@ +# 109 — 항목 찾기: 소유자가 기다리는 캐시 미스 + +2026-09-30. [107](107-snapshot-nodes-reused.md)의 다음에서 이어진다. 스냅숏이 놓은 노드를 되쓴 뒤, RAM에서 TPC-C를 도는 +소유자의 바쁜 시간 가운데 가장 큰 몫은 항목 찾기(32%)다. 목록의 B+트리를 키로 내려가는 `pure_list_seek`와, 찾은 항목의 +필드를 읽고 쓰는 일이다. + +107에서 하나를 이미 알았다. 찾기가 도착한 잎을 손가락에 남겨 두 번째 걸음을 없애도 아홉 쌍의 중앙값이 +1.5%로, 흔들림 +안이었다. 두 번째 걸음은 방금 지난 노드를 다시 밟으니 캐시에서 싸다. 비싼 것은 첫 걸음이 기다리는 메모리다. + +W=1의 재고는 항목 10만 개, 수 필드 다섯이다. 잎만 4 MB라서 이 Pi의 L3(2 MB)보다 크다. 잎은 필드를 열로 나눠 든다. 그래서 +잎 안의 키 열을 이진 탐색하면 캐시 줄을 차례로 기다리고, 한 항목의 필드 셋을 읽으면 열마다 다른 줄을 기다린다. +한 번에 알 수 있는 주소들을 차례로 기다리는 셈이다. 잎의 키 열을 한꺼번에 가져오는 코드는 이미 있지만, 항목이 +131,072개를 넘는 목록에서만 쓴다. + +착수 기준(측정 전에 정해 커밋했다): + +- **바꿀 결정.** 찾기에 미리 가져오기를 넣을지, 무엇을 넣을지다. 후보는 셋이다. + 1. 잎의 키 열을 목록의 크기와 상관없이 한꺼번에 가져온다. + 2. 찾은 항목의 필드를 열마다 미리 가져온다. 찾은 다음에는 그 항목을 읽고 바꾸기 때문이다. + 3. 안쪽 노드의 키를 단계마다 한꺼번에 가져온다. + + 미리 가져오기로 모자라서 잎의 배치를 바꿔야 한다면(열에서 행으로), 그것은 훑기와 맞바꾸는 큰 결정이다. 여기서 정하지 + 않고 따로 설계한다. +- **최소 확인.** + - 마이크로벤치로 찾기의 비용이 어느 단계에서 오는지 나눈다(안쪽 노드, 잎의 키, 잎의 필드). 항목 10만 개와 40만 개로 + 잰다. + - TPC-C(RAM, W=1, 64터미널)를 전과 후 번갈아 여섯 쌍 이상 잰다. + - 은행 질의([091](091-queries.md), 훑기와 폴드)를 전과 후 번갈아 잰다. +- **넣는 조건.** 셋을 모두 채워야 넣는다. + - 마이크로벤치에서 찾기와 필드 접근이 15% 넘게 빨라진다. + - TPC-C 여섯 쌍 가운데 다섯 쌍 이상에서 거래당 CPU가 줄고, 처리량 중앙값이 3% 넘게 는다. + - 은행 질의의 중앙값이 3% 넘게 느려지지 않는다. +- **측정의 흔들림.** 이 기계는 다른 세션과 함께 쓰인다. 쌍마다 소유자의 코어 몫을 보고, 이웃보다 뚜렷이 낮은 실행은 + 방해받은 것으로 적는다(버리지 않고 밝힌다). -- cgit v1.2.3