From bd8222e615134c3ec5e7a07b6b1fa97c9bd4a471 Mon Sep 17 00:00:00 2001 From: Berke Güzel Date: Thu, 15 Oct 2026 12:53:42 +0300 Subject: Convert each changed snapshot row once The atomic update counted arena words by converting every changed row in phase 1, then converted it again in apply(). A history row is decoded on each conversion, so paging through history took 74% longer, and a full redraw 20% longer. A changed row is now converted once. Small updates reserve the arena for the most their rows can add, then convert in apply() straight into the cells, as before. Larger updates and rebuilds convert into a stage in phase 1, with cluster records after the live ones or in a spare arena, and apply() copies the smaller of the kept and staged parts, swapping the stage in when that saves the copy. A failed update still changes nothing a reader sees. A row that scrolls in from below no longer counts as kept when its new key is 0. Co-Authored-By: Claude Opus 5.5 --- src/snapshot.c | 203 +++++++++++++++++++++++++++++++++++++++------------------ 1 file changed, 140 insertions(+), 63 deletions(-) diff --git a/src/snapshot.c b/src/snapshot.c index 78c66b0..6f396e2 100644 --- a/src/snapshot.c +++ b/src/snapshot.c @@ -16,6 +16,7 @@ struct term_snapshot { uint64_t source; /* serial of the terminal it copied */ struct term_cell *cells; /* rows * cols */ + struct term_cell *stage; /* rows * cols: changed rows, before apply() */ uint64_t *keys; /* per row */ uint32_t *row_clusters; /* arena records each row holds */ struct term_span *selection; /* per row */ @@ -24,6 +25,9 @@ struct term_snapshot { uint32_t *arena; uint32_t arena_len, arena_cap, arena_dead; + /* A rebuild writes its records here, then swaps it with arena. */ + uint32_t *spare; + uint32_t spare_cap; }; struct term_snapshot *term_snapshot_new(void) @@ -39,10 +43,12 @@ void term_snapshot_free(struct term_snapshot *s) if (!s) return; free(s->cells); + free(s->stage); free(s->keys); free(s->row_clusters); free(s->selection); free(s->arena); + free(s->spare); free(s); } @@ -56,6 +62,10 @@ static bool reserve(struct term_snapshot *s, int cols, int rows) if (!c) return false; s->cells = c; + struct term_cell *st = realloc(s->stage, cells * sizeof(*st)); + if (!st) + return false; + s->stage = st; s->cell_cap = cells; } if (rows > s->row_cap) { @@ -75,50 +85,67 @@ static bool reserve(struct term_snapshot *s, int cols, int rows) return true; } -/* Append a cluster record. The caller reserved room for it. */ -static uint32_t arena_add(struct term_snapshot *s, const struct gstore *g, uint32_t handle) +/* The arena that phase 1 appends cluster records to: the live arena after + * its records, or the spare arena for a rebuild. Records past arena_len are + * not visible, so a failed update leaves nothing behind. */ +struct arena_out { + uint32_t **buf; + uint32_t *cap; + uint32_t len; +}; + +/* Make room for need words. False when memory runs out or an offset would not + * fit below TERM_TEXT_CLUSTER. */ +static bool arena_reserve(struct arena_out *a, uint64_t need) { - uint32_t cps[TERM_GRAPHEME_MAX_LEN]; - int n = term_gstore_expand(g, handle, cps, TERM_GRAPHEME_MAX_LEN); - if (n <= 0) - return ' '; - uint32_t off = s->arena_len; - s->arena[off] = (uint32_t)n; - memcpy(&s->arena[off + 1], cps, (size_t)n * sizeof(*cps)); - s->arena_len += (uint32_t)n + 1; - return TERM_TEXT_CLUSTER | off; + if (need > TERM_TEXT_CLUSTER) + return false; + if (need <= *a->cap) + return true; + uint32_t cap = term_grow_cap32(*a->cap ? *a->cap * 2 : 256, (uint32_t)need); + uint32_t *grown = realloc(*a->buf, cap * sizeof(*grown)); + if (!grown) + return false; + *a->buf = grown; + *a->cap = cap; + return true; } -/* Arena words that converting src adds. Counts what arena_add() writes. */ -static uint64_t row_words(const struct gstore *g, const struct cell *src, int cols) +/* Append a cluster record and set *text to it. False when arena_reserve() + * fails. */ +static bool arena_add(struct arena_out *a, const struct gstore *g, uint32_t handle, + uint32_t *text) { uint32_t cps[TERM_GRAPHEME_MAX_LEN]; - uint64_t words = 0; - for (int x = 0; x < cols; x++) { - uint32_t text = src[x].c; - if (!term_grapheme_is_handle(text)) - continue; - int n = term_gstore_expand(g, text, cps, TERM_GRAPHEME_MAX_LEN); - if (n > 0) - words += (uint64_t)n + 1; + int n = term_gstore_expand(g, handle, cps, TERM_GRAPHEME_MAX_LEN); + if (n <= 0) { + *text = ' '; + return true; } - return words; + uint64_t need = (uint64_t)a->len + (uint32_t)n + 1; + if (!arena_reserve(a, need)) + return false; + uint32_t off = a->len; + (*a->buf)[off] = (uint32_t)n; + memcpy(&(*a->buf)[off + 1], cps, (size_t)n * sizeof(*cps)); + a->len = (uint32_t)need; + *text = TERM_TEXT_CLUSTER | off; + return true; } -/* Convert one stored row; returns the number of arena words it added. */ -static uint32_t convert_row(struct term_snapshot *s, const struct gstore *g, - struct term_cell *dst, - const struct cell *src, int cols) +/* Convert one stored row into dst. False when a cluster record does not fit. */ +static bool convert_row(struct arena_out *a, const struct gstore *g, + struct term_cell *dst, const struct cell *src, int cols) { - uint32_t before = s->arena_len; for (int x = 0; x < cols; x++) { const struct cell *c = &src[x]; uint16_t f = c->flags; uint32_t text = c->c; if (TERM_EXPECT(text < 0x20, 0)) text = text ? ' ' : 0; - else if (TERM_EXPECT(term_grapheme_is_handle(text), 0)) - text = arena_add(s, g, text); + else if (TERM_EXPECT(term_grapheme_is_handle(text), 0) && + !arena_add(a, g, text, &text)) + return false; dst[x] = (struct term_cell){ .text = text, .fg = c->fg, @@ -127,14 +154,23 @@ static uint32_t convert_row(struct term_snapshot *s, const struct gstore *g, .width = (f & CELL_TRAIL) ? 0 : (f & CELL_WIDE) ? 2 : 1, }; } - return s->arena_len - before; + return true; } +/* A row that keeps its old copy. */ +#define ROW_KEPT UINT32_MAX +/* The most arena words reserved so that apply() can convert rows directly. */ +#define DIRECT_MAX_WORDS (1u << 16) + /* What one update does. Phase 1 fills it in and changes no snapshot field. */ struct plan { - bool all; /* rebuild every row and reset the arena */ + bool all; /* rebuild every row and swap in the spare arena */ int scrolled; /* rows the content moved up */ + uint32_t arena_len; /* arena length with the new records */ const uint64_t *keys; /* key of each new row */ + const uint32_t *words; /* arena words of each staged row, or ROW_KEPT */ + int staged; /* rows that are not ROW_KEPT */ + bool direct; /* apply() converts the rows; the arena has room */ const int *c0, *c1; /* selected columns of each row */ }; @@ -144,16 +180,34 @@ static void apply(struct term_snapshot *s, const struct term *t, const struct pl int cols = t->cols, rows = t->rows; int k = p->scrolled; if (p->all) { - s->arena_len = 0; + uint32_t *arena = s->arena, cap = s->arena_cap; + s->arena = s->spare; + s->arena_cap = s->spare_cap; + s->spare = arena; + s->spare_cap = cap; s->arena_dead = 0; } + s->arena_len = p->arena_len; bool changed = p->all; + size_t row_bytes = (size_t)cols * sizeof(struct term_cell); + /* Staged rows: copy the smaller part. Either the kept rows go into the + * stage, which then becomes the cells, or the staged rows go into the + * cells. A scroll moves every kept row anyway, so it swaps. */ + bool swap = !p->direct && (k > 0 || p->staged * 2 > rows); + if (p->direct && k > 0) + memmove(s->cells, s->cells + (size_t)k * cols, (size_t)(rows - k) * row_bytes); + if (swap) { + for (int y = 0; y < rows; y++) + if (p->words[y] == ROW_KEPT) + memcpy(s->stage + (size_t)y * cols, s->cells + (size_t)(y + k) * cols, row_bytes); + struct term_cell *cells = s->cells; + s->cells = s->stage; + s->stage = cells; + } if (k > 0) { for (int y = 0; y < k; y++) s->arena_dead += s->row_clusters[y]; - memmove(s->cells, s->cells + (size_t)k * cols, - (size_t)(rows - k) * cols * sizeof(struct term_cell)); memmove(s->row_clusters, s->row_clusters + k, (size_t)(rows - k) * sizeof(uint32_t)); memmove(s->keys, s->keys + k, @@ -163,15 +217,23 @@ static void apply(struct term_snapshot *s, const struct term *t, const struct pl } for (int y = 0; y < rows; y++) { - uint64_t key = p->keys[y]; - if (!p->all && s->keys[y] == key) + if (p->words[y] == ROW_KEPT) continue; if (!p->all) s->arena_dead += s->row_clusters[y]; - const struct cell *src = term_screen_view_row(t, y); - s->row_clusters[y] = convert_row(s, t->gstore, s->cells + (size_t)y * cols, - src, cols); - s->keys[y] = key; + if (p->direct) { + /* Phase 1 reserved room for the worst case, so this cannot fail. */ + struct arena_out a = { &s->arena, &s->arena_cap, s->arena_len }; + (void)convert_row(&a, t->gstore, s->cells + (size_t)y * cols, + term_screen_view_row(t, y), cols); + s->row_clusters[y] = a.len - s->arena_len; + s->arena_len = a.len; + } else { + if (!swap) + memcpy(s->cells + (size_t)y * cols, s->stage + (size_t)y * cols, row_bytes); + s->row_clusters[y] = p->words[y]; + } + s->keys[y] = p->keys[y]; changed = true; } @@ -222,25 +284,28 @@ static bool term_snapshot_update_inner(struct term_snapshot *s, struct term *t) bool resized = s->view.size.x != cols || s->view.size.y != rows; bool all = resized || s->source != t->serial; int scrolled = 0; - uint64_t need = 0; if (!reserve(s, cols, rows)) return false; - /* Scratch for rows above 256: new keys, then the selection spans. */ + /* Scratch for rows above 256: new keys, staged arena words, then the + * selection spans. */ uint64_t stack_keys[256]; + uint32_t stack_words[256]; int stack[2][256]; uint64_t *new_keys = stack_keys; + uint32_t *words = stack_words; int *c0 = stack[0], *c1 = stack[1]; void *heap = NULL; if (rows > 256) { - heap = malloc((size_t)rows * (sizeof(*new_keys) + 2 * sizeof(*c0))); + heap = malloc((size_t)rows * (sizeof(*new_keys) + sizeof(*words) + 2 * sizeof(*c0))); if (!heap) return false; new_keys = heap; - c0 = (int *)(new_keys + rows); + words = (uint32_t *)(new_keys + rows); + c0 = (int *)(words + rows); c1 = c0 + rows; } - struct plan p = { .keys = new_keys, .c0 = c0, .c1 = c1 }; + struct plan p = { .keys = new_keys, .words = words, .c0 = c0, .c1 = c1 }; /* Reclaim cluster records once most of the arena is garbage. */ if (s->arena_dead > 4096 && s->arena_dead * 2 > s->arena_len) @@ -295,33 +360,45 @@ static bool term_snapshot_update_inner(struct term_snapshot *s, struct term *t) } } - /* Arena words for the rows that apply() converts. Count them before - * anything changes, then grow the arena once so apply() cannot fail. */ - need = all ? 0 : s->arena_len; + /* Mark the rows that change. A row that scrolled in from below has no + * old copy. */ for (int y = 0; y < rows; y++) { - uint64_t kept = s->keys[y]; - if (scrolled) - kept = y + scrolled < rows ? s->keys[y + scrolled] : 0; - if (!all && kept == new_keys[y]) - continue; - need += row_words(t->gstore, term_screen_view_row(t, y), cols); + if (!all && y + scrolled < rows && s->keys[y + scrolled] == new_keys[y]) { + words[y] = ROW_KEPT; + } else { + words[y] = 0; + p.staged++; + } } - /* Offsets must fit below TERM_TEXT_CLUSTER. */ - if (need > TERM_TEXT_CLUSTER) - goto done; - if (need > s->arena_cap) { - uint32_t cap = term_grow_cap32(s->arena_cap ? s->arena_cap * 2 : 256, (uint32_t)need); - uint32_t *a = realloc(s->arena, cap * sizeof(*a)); - if (!a) + + /* Nothing a reader sees may change before apply(). A few rows convert in + * apply(), straight into the cells, once the arena has room for the most + * they can add. More rows convert here into the stage, with their cluster + * records after the live ones, or in the spare arena for a rebuild. */ + struct arena_out a = all ? (struct arena_out){ &s->spare, &s->spare_cap, 0 } + : (struct arena_out){ &s->arena, &s->arena_cap, s->arena_len }; + uint64_t worst = (uint64_t)p.staged * (uint64_t)cols * (1 + TERM_GRAPHEME_MAX_LEN); + if (!all && worst <= DIRECT_MAX_WORDS) { + if (!arena_reserve(&a, a.len + worst)) goto done; - s->arena = a; - s->arena_cap = cap; + p.direct = true; + } else { + for (int y = 0; y < rows; y++) { + if (words[y] == ROW_KEPT) + continue; + uint32_t before = a.len; + if (!convert_row(&a, t->gstore, s->stage + (size_t)y * cols, + term_screen_view_row(t, y), cols)) + goto done; + words[y] = a.len - before; + } } if (!term_selection_view_spans(t, c0, c1)) goto done; p.all = all; p.scrolled = scrolled; + p.arena_len = a.len; apply(s, t, &p); ok = true; -- cgit v1.2.3