diff options
Diffstat (limited to 'docs/design')
| -rw-r--r-- | docs/design/023-optimizing-tier.md | 4 |
1 files changed, 2 insertions, 2 deletions
diff --git a/docs/design/023-optimizing-tier.md b/docs/design/023-optimizing-tier.md index 88645d7..2003af5 100644 --- a/docs/design/023-optimizing-tier.md +++ b/docs/design/023-optimizing-tier.md @@ -142,10 +142,10 @@ roots와 BFS만 기계어로 돈다. 나머지는 JIT의 값 모형이 거르거 ### 6. 표현 (바닥이 가정한 것) - **희소한 키로 둔 이벤트의 리스트**(HASHED, 했다): 수 키가 차례를 어기고 작은 정수가 아니면, 항목의 셀을 키 집합(열린 주소, - 키의 비트, 2배 넘는 칸)의 그 키의 칸에 둔다. DENSE가 키의 자리에 두듯 해서, 키로 찾기는 칸의 키와 셀을 같은 번호로 읽는다(C의 해시 + 키의 비트, 칸의 4/5까지: 표가 L3에 들게; 절반까지면 조인 112 ms, 4/5면 84)의 그 키의 칸에 둔다. DENSE가 키의 자리에 두듯 해서, 키로 찾기는 칸의 키와 셀을 같은 번호로 읽는다(C의 해시 표처럼 두 미스가 겹친다; 넣은 차례로 두고 칸에 위치를 두면 미스가 줄을 선다: 조인 129 ms에서 108). 차례가 필요할 때(걷기, 위치, 찾은 위치, 되돌리기, 공유, 저장) 칸들을 키의 비트 순서로 여덟 비트씩 기수 정렬해 FLAT이 된다. 지우기까지 두 번이고, 그다음은 - FLAT이나 트리다(오가며 정렬하지 않게). 계층은 키로만 찾는 리스트의 비트 열 1번 비트로 HASHED를 알고(한계는 모두 1: 키의 경계 검사가 + FLAT이나 트리다(오가며 정렬하지 않게). 일반 코드의 APPEND도 표가 자라지 않는 한 칸을 바로 찾아 넣는다(sort 58 ms에서 37). 계층은 키로만 찾는 리스트의 비트 열 1번 비트로 HASHED를 알고(한계는 모두 1: 키의 경계 검사가 그대로 맞다), 찾기는 줄 밖에서 칸을 탐사한다(DENSE의 길에 분기가 늘지 않게). - **텍스트 키의 이벤트 리스트**(했다): 리스트가 그 키를 안다(`text_key`, 트리의 리드는 그대로 수 키만). 이벤트의 리스트는 처음 넣을 때부터 HASHED이고, 칸에는 텍스트 바이트의 해시(FNV-1a)를 두며 같은 해시는 칸의 키 셀과 바이트로 견준다. HAS와 키로 읽기는 |