Keep one finger a thread, as before: four cost the bank's queries instructions and a search no time (020)

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. 손가락 넷
+  (위).
 
 ## 단계