diff options
Diffstat (limited to 'docs/design')
| -rw-r--r-- | docs/design/023-optimizing-tier.md | 9 |
1 files changed, 6 insertions, 3 deletions
diff --git a/docs/design/023-optimizing-tier.md b/docs/design/023-optimizing-tier.md index a0e2011..0c4666d 100644 --- a/docs/design/023-optimizing-tier.md +++ b/docs/design/023-optimizing-tier.md @@ -141,9 +141,12 @@ roots와 BFS만 기계어로 돈다. 나머지는 JIT의 값 모형이 거르거 ### 6. 표현 (바닥이 가정한 것) -- **희소한 키로 둔 이벤트의 리스트**(해시 색인): 항목은 넣은 차례로 열에 두고, 칸 하나에 키와 위치를 함께 둔 열린 주소 색인으로 - 찾는다. 키가 정수이고 4바이트에 들면 키도 4바이트. 차례가 필요할 때(걷기, `first`, 조각) 정렬한다(런타임의 정렬: 비교가 인라인). - 정렬은 바뀌기 전까지 유효하다. 텍스트 키는 해시하고 견준다. +- **희소한 키로 둔 이벤트의 리스트**(HASHED, 했다): 수 키가 차례를 어기고 작은 정수가 아니면, 항목의 셀을 키 집합(열린 주소, + 키의 비트, 2배 넘는 칸)의 그 키의 칸에 둔다. DENSE가 키의 자리에 두듯 해서, 키로 찾기는 칸의 키와 셀을 같은 번호로 읽는다(C의 해시 + 표처럼 두 미스가 겹친다; 넣은 차례로 두고 칸에 위치를 두면 미스가 줄을 선다: 조인 129 ms에서 108). 차례가 필요할 때(걷기, 위치, + 찾은 위치, 되돌리기, 공유, 저장) 칸들을 키의 비트 순서로 여덟 비트씩 기수 정렬해 FLAT이 된다. 지우기까지 두 번이고, 그다음은 + FLAT이나 트리다(오가며 정렬하지 않게). 계층은 키로만 찾는 리스트의 비트 열 1번 비트로 HASHED를 알고(한계는 모두 1: 키의 경계 검사가 + 그대로 맞다), 찾기는 줄 밖에서 칸을 탐사한다(DENSE의 길에 분기가 늘지 않게). 텍스트 키는 아직(해시하고 칸의 셀과 견준다). - 텍스트 보간의 정수는 정수의 자릿수로 바로 쓴다(지금의 수→텍스트가 정수에서 내는 것과 같은 바이트). - 저장된 리스트는 022 그대로(트리, 많이 찾으면 편 배열). |