diff options
| -rw-r--r-- | core/module-list.c | 53 | ||||
| -rw-r--r-- | core/test-module.c | 2 | ||||
| -rw-r--r-- | docs/design/020-computing-faster.md | 10 |
3 files changed, 28 insertions, 37 deletions
diff --git a/core/module-list.c b/core/module-list.c index 99d19ab..ea15fb1 100644 --- a/core/module-list.c +++ b/core/module-list.c @@ -107,35 +107,25 @@ typedef struct { static uint64_t lists_made; -/* The leaves a thread read last, and where they start, a few lists' (one - * each): a list read position by position (a view's rows, a fold, a walk) - * finds each next item there, and an item found by key is read there, while - * the thread reads other lists between (a search reads three). Each holds - * for its list (its id) as it was (its version) and no other. */ -enum { FINGERS = 4 }; +/* The leaf a thread read last, and where it starts: a list read position + * by position (a view's rows, a fold, a walk) finds each next item there, + * and an item found by key is read there. It holds for its list (its id) as + * it was (its version) and no other. (Four, one a list, cost the bank's + * queries more than they saved and a search no time: research 121.) */ typedef struct { uint64_t id, version; const Node *leaf; size_t start; } Finger; -static _Thread_local Finger fingers[FINGERS]; -static _Thread_local unsigned finger_turn; +static _Thread_local Finger finger; -/* The leaf a finger keeps that holds position at of the list as it is, or NULL. */ +/* The finger's leaf when it holds position at of the list as it is, or NULL. */ static const Node *fingered(const PureList *list, size_t at, size_t *within) { - for (unsigned i = 0; i < FINGERS; ++i) { - const Finger *f = &fingers[i]; - if (f->leaf && f->id == list->id && f->version == list->version && at >= f->start && at < f->start + f->leaf->count) { - *within = at - f->start; - if (i) { Finger hit = *f; fingers[i] = fingers[0]; fingers[0] = hit; } /* first looked at next */ - return fingers[0].leaf; - } - } - return NULL; + if (!finger.leaf || finger.id != list->id || finger.version != list->version || at < finger.start || + at >= finger.start + finger.leaf->count) + return NULL; + *within = at - finger.start; + return finger.leaf; } -/* A leaf of the list as it is, from start: kept in the list's finger, or the one used longest ago. */ static void finger_keep(const PureList *list, const Node *leaf, size_t start) { - unsigned at = FINGERS; - for (unsigned i = 0; i < FINGERS && at == FINGERS; ++i) if (fingers[i].id == list->id) at = i; - if (at == FINGERS) at = finger_turn++ % FINGERS; - fingers[at] = (Finger){list->id, list->version, leaf, start}; + finger = (Finger){list->id, list->version, leaf, start}; } /* ---- A keyed list's keys as a set @@ -1432,16 +1422,15 @@ size_t pure_list_seek(const PureList *list, unsigned field, PureCell key, bool * *found = false; if (!node || !list->count) return 0; if ((int)field == l->key) { - /* A leaf a finger keeps whose keys reach round key holds its place + /* The finger's leaf, when its keys reach round key, holds its place * (a slice's high bound is near its low one, found just before). */ - for (unsigned i = 0; i < FINGERS; ++i) { - const Finger *f = &fingers[i]; - if (!f->leaf || f->id != list->id || f->version != list->version || !f->leaf->count) continue; - const double *keys = numbers(l, f->leaf, field); - if (!(keys[0] <= key.num && key.num <= keys[f->leaf->count - 1])) continue; - unsigned low = lower(keys, f->leaf->count, key.num); - *found = low < f->leaf->count && keys[low] == key.num; - return f->start + low; + if (finger.leaf && finger.id == list->id && finger.version == list->version && finger.leaf->count) { + const double *keys = numbers(l, finger.leaf, field); + if (keys[0] <= key.num && key.num <= keys[finger.leaf->count - 1]) { + unsigned low = lower(keys, finger.leaf->count, key.num); + *found = low < finger.leaf->count && keys[low] == key.num; + return finger.start + low; + } } /* Each level: the last child whose lead is at or below key (the * first when none is); then the leaf's items below key. */ diff --git a/core/test-module.c b/core/test-module.c index 35a154f..3721c28 100644 --- a/core/test-module.c +++ b/core/test-module.c @@ -1251,7 +1251,7 @@ static void key_sets(void) { CHECK(same_item(&model, i, k.num, (PureSpan){t.text, t.size})); } } - /* Another list read between (fingers for five lists, four kept). */ + /* Another list read between: the finger is another's then. */ unsigned o = next_random(&seed) % OTHERS, i = next_random(&seed) % 2000; CHECK(pure_list_get(others[o], i, 0).num == i + o); CHECK(pure_list_seek(others[o], 0, (PureCell){.num = i + o + 0.5}, &found) == i + 1 && !found); diff --git a/docs/design/020-computing-faster.md b/docs/design/020-computing-faster.md index 35cc071..14f3a57 100644 --- a/docs/design/020-computing-faster.md +++ b/docs/design/020-computing-faster.md @@ -59,13 +59,15 @@ 비우면 64 KiB까지의 비트는 지우고 남긴다(다음 이벤트가 다시 쓴다). `-0`과 `+0`은 한 키다. - **키로 넣기는 한 번 내려간다**(`pure_list_add`). 찾고 나서 넣으면 두 번이다. 저장되는 키 있는 리스트의 덧붙이기도 이 길로 가고, 기록과 되돌리기는 `pure_list_insert`의 것과 같다. -- **손가락은 스레드마다 넷이다**(리스트 하나가 아니라: 걷기와 큐와 `seen`이 번갈아 읽는다). 리스트의 번호와 판이 맞을 때만 쓴다. - 스냅숏의 사본은 리스트와 번호가 같고 판이 다르다. 키로 찾기도 손가락의 잎에서 먼저 본다. +- **손가락은 스레드마다 하나다.** 리스트 하나에 하나가 아니라 스레드가 마지막으로 읽은 잎이다(이미 있던 것). 넷(리스트마다 하나, + 앞으로 옮기기)으로 늘려 봤지만 BFS는 빨라지지 않았고(183 대 185 ms) 은행 질의의 명령 수는 늘었다(`field` +2.9%, 하나로는 + −0.3%): 되돌렸다. 리스트의 번호와 판이 맞을 때만 쓴다. 스냅숏의 사본은 리스트와 번호가 같고 판이 다르다. 새로 더한 것은 키로 + 찾기도 손가락의 잎에서 먼저 보는 것이다. - 설계에 없던 넷: 항목의 필드가 text인지를 로드할 때 명령에 적기(실행할 때마다 찾지 않게), 각 단에서 자식 찾기를 이분 탐색이 아니라 세기로(가지 32개를 모두 비교해 센다, 벡터가 된다), 실행기의 루프를 재귀 없이(루프 기록의 스택), `module-list.c`를 `-O3`로(`Makefile`의 `LIST_OPTIMIZE`). 넷의 몫은 204 ms에서 186 ms이고 거의 다 `-O3`다. -- 해 보고 뺀 것: 잎의 울타리(키로 찾은 잎의 다음 잎의 첫 키, 손가락이 키 범위를 더 넓게 알게) — 185.5 대 185.5 ms. 손가락의 - 앞으로 옮기기는 남겼지만 차이는 재지 못했다(206 대 204 ms). +- 해 보고 뺀 것: 잎의 울타리(키로 찾은 잎의 다음 잎의 첫 키, 손가락이 키 범위를 더 넓게 알게) — 185.5 대 185.5 ms. 손가락 넷 + (위). ## 단계 |