From 6c641903b089d81fb193c3949ccc677b701bc55b Mon Sep 17 00:00:00 2001 From: eunhhu Date: Mon, 5 Oct 2026 07:53:22 +0100 Subject: Read a tree's items in compiled code from a run the frame keeps, start a run at the finger's leaf, and move indices only for a list an index refers to (021) - The frame keeps the run compiled code read a tree's item from last (the list as it was: its version); an item it holds is read from its column, else pure_run_item takes the item's run and steps. - pure_list_run starts at the leaf the finger keeps when it holds the position (a slice found by key just before): no second descent; the run after it is found from the root (PureRun.pathless). - LIST_APPEND and LIST_REMOVE move index states only for a list one refers to. - A search (core only): 89 ms compiled (answers the executor's). --- core/module-jit.c | 31 ++++++++++++++++++++++++++++--- core/module-list.c | 32 +++++++++++++++++++++++++++++++- core/module-list.h | 5 ++++- core/module-run.h | 8 +++++++- core/module.c | 20 ++++++++++++++++++-- 5 files changed, 88 insertions(+), 8 deletions(-) (limited to 'core') diff --git a/core/module-jit.c b/core/module-jit.c index a6ab7f1..8e50eb0 100644 --- a/core/module-jit.c +++ b/core/module-jit.c @@ -557,13 +557,38 @@ static void compile_op(Block *k, uint32_t pc) { bind(e, done); return; } - case PURE_OP_ITEM_GET: { /* a FLAT list's cell by its column */ + case PURE_OP_ITEM_GET: { /* a FLAT list's cell by its column, a tree's from the run kept */ if (op->plan & PLAN_TEXT) break; - int slow = new_label(e), done = new_label(e); + int slow = new_label(e), done = new_label(e), flat = new_label(e), refill = new_label(e); + size_t field = item_field(arg) * sizeof(void *); load64(e, X10, X24, list_of(arg) * sizeof(PureList *)); load8(e, X12, X10, pure_list_layout[LIST_FORM_AT]); cmp_w_imm(e, X12, 1); /* FLAT */ - b_cond(e, NE, slow); + b_cond(e, EQ, flat); + cbnz_w(e, X12, slow); /* DENSE */ + load_d(e, D0, X20, AT(height - 1)); + fp2(e, FCVTZU_X, X13, D0); + load64(e, X11, X19, offsetof(Frame, run.list)); + cmp_reg(e, X11, X10); + b_cond(e, NE, refill); + load64(e, X11, X19, offsetof(Frame, run.version)); + load64(e, X12, X10, pure_list_layout[LIST_VERSION_AT]); + cmp_reg(e, X11, X12); + b_cond(e, NE, refill); + load64(e, X11, X19, offsetof(Frame, run.start)); + sub_reg(e, X14, X13, X11); + load64(e, X11, X19, offsetof(Frame, run.count)); + cmp_reg(e, X14, X11); + b_cond(e, HS, refill); + load64(e, X15, X19, offsetof(Frame, run.columns) + field); + load64_index(e, X9, X15, X14); + store64(e, X9, X20, AT(height - 1)); + b(e, done); + bind(e, refill); + call_step(k, (uintptr_t)pure_run_item, pc, height); + cbnz_w(e, X0, k->exit); + b(e, done); + bind(e, flat); load_d(e, D0, X20, AT(height - 1)); fp2(e, FCVTZU_X, X13, D0); load64(e, X12, X10, pure_list_layout[LIST_COUNT_AT]); diff --git a/core/module-list.c b/core/module-list.c index 7bf05e1..b3a9ed3 100644 --- a/core/module-list.c +++ b/core/module-list.c @@ -1137,7 +1137,8 @@ unsigned pure_list_form(const PureList *list) { return list->form; } const size_t pure_list_layout[] = { [LIST_COUNT_AT] = offsetof(PureList, count), [LIST_MEMBERS_AT] = offsetof(PureList, members), [LIST_MEMBER_CAPACITY_AT] = offsetof(PureList, member_capacity), [LIST_BITMAP_AT] = offsetof(PureList, bitmap), - [LIST_FORM_AT] = offsetof(PureList, form), [LIST_COLUMNS_AT] = offsetof(PureList, columns)}; + [LIST_FORM_AT] = offsetof(PureList, form), [LIST_COLUMNS_AT] = offsetof(PureList, columns), + [LIST_VERSION_AT] = offsetof(PureList, version)}; bool pure_list_lookup(const PureList *list, unsigned key_field, PureCell key, unsigned field, PureCell *cell) { bool found; @@ -1757,6 +1758,7 @@ static void open_array_run(const PureList *list, size_t at, PureRun *run) { run->start = at; run->count = list->form == DENSE ? 1 : (unsigned)(list->count - at < PURE_LIST_RUN ? list->count - at : PURE_LIST_RUN); run->depth = 0; + run->pathless = false; for (unsigned f = 0; f < l->fields; ++f) if (pure_cell_text(l->kinds[f])) run->column[f].texts = (const PureSpan *)list->columns[f] + row; else if (l->kinds[f] == PURE_CELL_INTEGER) run->column[f].integers = (const int64_t *)list->columns[f] + row; @@ -1772,6 +1774,16 @@ bool pure_list_run(const PureList *list, size_t at, PureRun *run) { return true; } } + size_t within; + const Node *kept = fingered(list, at, &within); /* a slice's first item, found by key just before */ + if (kept) { + run->path[0] = kept; + run->depth = 0; + run->pathless = true; /* the run after it found from the root */ + run->start = at - within; + open_run(&list->layout, kept, run); + return true; + } const Node *node = list->root; size_t start = 0; unsigned depth = 0; @@ -1785,6 +1797,7 @@ bool pure_list_run(const PureList *list, size_t at, PureRun *run) { run->path[depth] = node; run->depth = depth; run->start = start; + run->pathless = false; open_run(&list->layout, node, run); return true; } @@ -1798,6 +1811,23 @@ bool pure_list_next(const PureList *list, PureRun *run) { open_array_run(list, run->start + run->count, run); return true; } + if (run->pathless) { /* the next from the root, with its path */ + size_t at = run->start + run->count; + if (at >= list->count) return false; + const Node *node = list->root; + size_t start = 0; + unsigned depth = 0; + while (!node->leaf) { + unsigned i = child_at(node, at - start); + start += guide(node)->before[i]; + run->path[depth] = node; + run->taken[depth++] = (uint8_t)i; + node = child(node, i); + } + run->path[depth] = node, run->depth = depth, run->start = start, run->pathless = false; + open_run(&list->layout, node, run); + return true; + } size_t start = run->start + run->count; unsigned depth = run->depth; while (depth && run->taken[depth - 1] + 1u >= ((const Node *)run->path[depth - 1])->count) --depth; diff --git a/core/module-list.h b/core/module-list.h index 0addcf0..6251786 100644 --- a/core/module-list.h +++ b/core/module-list.h @@ -37,10 +37,13 @@ typedef struct { size_t start; unsigned count; union { const double *numbers; const int64_t *integers; const PureSpan *texts; } column[16]; - /* Where the run is in the list's tree, for the next one. */ + /* Where the run is in the list's tree, for the next one (path[depth] + * its leaf); pathless: its leaf alone is known (the next is found from + * the root). */ const void *path[16]; uint8_t taken[16]; unsigned depth; + bool pathless; } PureRun; /* A list holds up to PURE_LIST_ITEMS items, a run up to PURE_LIST_RUN. */ diff --git a/core/module-run.h b/core/module-run.h index 453c342..8844685 100644 --- a/core/module-run.h +++ b/core/module-run.h @@ -64,6 +64,9 @@ typedef struct { PureResult status; /* what refused or stopped it */ uint32_t fault_pc; /* the instruction that faulted or refused */ Loop *loops; /* PURE_MODULE_NESTING of them, apart: a walk points into its loop */ + /* The run of a tree compiled code read an item from last (pure_run_item): + * the list as it was (its version), its positions and each field's cells. */ + struct { const PureList *list; uint64_t version; size_t start, count; const void *columns[16]; } run; } Frame; /* How a step went: on to the next instruction; a fault (kind at fault_pc); @@ -87,11 +90,14 @@ int pure_run_each(Frame *, uint32_t pc); int pure_run_loop(Frame *, uint32_t pc); void pure_run_break(Frame *); int pure_run_iterate(Frame *); +/* ITEM_GET at pc whose list is a tree its kept run does not hold: the + * item's run kept, then the step. */ +int pure_run_item(Frame *, uint32_t pc); /* Where a list keeps what compiled code reads of it (module-list.c owns the * layout and says where): its item count, its key set (the words, how many, * whether they are bits), its form (pure_list_form) and its arrays. */ -enum { LIST_COUNT_AT, LIST_MEMBERS_AT, LIST_MEMBER_CAPACITY_AT, LIST_BITMAP_AT, LIST_FORM_AT, LIST_COLUMNS_AT }; +enum { LIST_COUNT_AT, LIST_MEMBERS_AT, LIST_MEMBER_CAPACITY_AT, LIST_BITMAP_AT, LIST_FORM_AT, LIST_COLUMNS_AT, LIST_VERSION_AT }; extern const size_t pure_list_layout[]; /* A module's code compiled (AArch64 Linux; elsewhere, or with PURE_JIT=0 in diff --git a/core/module.c b/core/module.c index ff6f131..c486d45 100644 --- a/core/module.c +++ b/core/module.c @@ -2788,7 +2788,7 @@ static inline __attribute__((always_inline)) int step(Frame *frame, const PureOp if (status == PURE_INVALID) status = pure_list_insert(list, at, cells, undo_for(app, arg)); arena->used = mark; if (status != PURE_OK) REFUSED; - move_indices(m, values, arg, pure_list_count(list), at, true); + if (m->state_indexed[arg]) move_indices(m, values, arg, pure_list_count(list), at, true); if (!grows(app, before, list_held(app, list))) { kind = PURE_FAULT_MEMORY; FAILED; } NEXT; } @@ -2798,7 +2798,7 @@ static inline __attribute__((always_inline)) int step(Frame *frame, const PureOp if ((status = pure_list_remove(app->lists[arg], at, undo_for(app, arg))) != PURE_OK) REFUSED; /* the item goes, its cells kept to undo and its record to save */ if (!grows(app, before, list_held(app, app->lists[arg]))) { kind = PURE_FAULT_MEMORY; FAILED; } - move_indices(m, values, arg, pure_list_count(app->lists[arg]), at, false); + if (m->state_indexed[arg]) move_indices(m, values, arg, pure_list_count(app->lists[arg]), at, false); if (ev->walk && ev->walk->list == arg) { /* the walk goes on with the item after */ if (at < ev->walk->at) --ev->walk->at; else if (at == ev->walk->at) ev->walk->removed = true; @@ -3049,6 +3049,22 @@ int pure_run_loop(Frame *frame, uint32_t pc) { void pure_run_break(Frame *frame) { (void)leave_loop(frame); } +int pure_run_item(Frame *frame, uint32_t pc) { + const PureOp *op = &frame->m->code[pc]; + const PureList *list = frame->app->lists[list_of(op->arg)]; + size_t at = (size_t)frame->stack[frame->sp - 1].num; + PureRun run; + if (at < pure_list_count(list) && !pure_list_form(list) && pure_list_run(list, at, &run)) { + uint64_t id; + frame->run.list = list; + pure_list_stamp(list, &id, &frame->run.version); + frame->run.start = run.start, frame->run.count = run.count; + for (unsigned f = 0; f < 16; ++f) frame->run.columns[f] = run.column[f].numbers; + } + uint32_t next; + return step(frame, op, pc, &next); +} + int pure_run_iterate(Frame *frame) { uint32_t next = UINT32_MAX; int how = iterate(frame, &next); -- cgit v1.2.3