diff options
| author | Daniel Eklöf <daniel@ekloef.se> | 2019-08-22 15:33:23 +0000 |
|---|---|---|
| committer | Daniel Eklöf <daniel@ekloef.se> | 2019-08-22 15:33:23 +0000 |
| commit | 7c7720a3ab314e471499194f114797ca7a40afde (patch) | |
| tree | 1113380cb5fa7456ccebf71ed72c1b9d9d672c14 | |
| parent | generate-alt-random-writes: generate color, scroll and scroll region sequences (diff) | |
scrolling: optimize row access by assuming number of rows is a power of 2
With this assumption, we can replace 'a % b' with 'a & (b - 1)'. In
terms of instructions, this means a fast 'and' instead of a slow
'div'.
Further optimize scrolling by:
* not double-initializing empty rows. Previously, grid_row_alloc()
called calloc(), which was then followed by a memset() when
scrolling. This is of course unnecessary.
* Don't loop the entire set of visible rows (this was done to ensure
all visible rows had been allocated, and to prefetch the cell
contents).
This isn't necessary; only newly pulled in rows can be NULL. For
now, don't prefetch at all.
| -rw-r--r-- | commands.c | 6 | ||||
| -rw-r--r-- | grid.c | 37 | ||||
| -rw-r--r-- | grid.h | 28 | ||||
| -rw-r--r-- | render.c | 17 | ||||
| -rw-r--r-- | terminal.c | 63 |
5 files changed, 101 insertions, 50 deletions
@@ -19,7 +19,11 @@ cmd_scrollback_up(struct terminal *term, int rows) rows = min(rows, term->rows); assert(term->grid->offset >= 0); - int new_view = (term->grid->view + term->grid->num_rows - rows) % term->grid->num_rows; + int new_view = term->grid->view - rows; + while (new_view < 0) + new_view += term->grid->num_rows; + new_view %= term->grid->num_rows; + assert(new_view >= 0); assert(new_view < term->grid->num_rows); @@ -8,30 +8,39 @@ #include "log.h" void -grid_swap_row(struct grid *grid, int row_a, int row_b) +grid_swap_row(struct grid *grid, int row_a, int row_b, bool initialize) { assert(grid->offset >= 0); assert(row_a != row_b); - int real_a = (grid->offset + row_a + grid->num_rows) % grid->num_rows; - int real_b = (grid->offset + row_b + grid->num_rows) % grid->num_rows; + int real_a = (grid->offset + row_a) & (grid->num_rows - 1); + int real_b = (grid->offset + row_b) & (grid->num_rows - 1); - assert(real_a >= 0); - assert(real_b >= 0); - - struct row *tmp = grid->rows[real_a]; - grid->rows[real_a] = grid->rows[real_b]; - grid->rows[real_b] = tmp; + struct row *a = grid->rows[real_a]; + struct row *b = grid->rows[real_b]; +#if 0 + if (a == NULL) + a = grid_row_alloc(grid->num_cols, initialize); + if (b == NULL) + b = grid_row_alloc(grid->num_cols, initialize); +#endif + grid->rows[real_a] = b; + grid->rows[real_b] = a; } struct row * -grid_row_alloc(int cols) +grid_row_alloc(int cols, bool initialize) { struct row *row = malloc(sizeof(*row)); - row->cells = calloc(cols, sizeof(row->cells[0])); - for (size_t c = 0; c < cols; c++) - row->cells[c].attrs.clean = 1; - row->dirty = false; /* TODO: parameter? */ + row->dirty = false; + + if (initialize) { + row->cells = calloc(cols, sizeof(row->cells[0])); + for (size_t c = 0; c < cols; c++) + row->cells[c].attrs.clean = 1; + } else + row->cells = malloc(cols * sizeof(row->cells[0])); + return row; } @@ -3,33 +3,45 @@ #include <stddef.h> #include "terminal.h" -void grid_swap_row(struct grid *grid, int row_a, int row_b); -struct row *grid_row_alloc(int cols); +void grid_swap_row(struct grid *grid, int row_a, int row_b, bool initialize); +struct row *grid_row_alloc(int cols, bool initialize); void grid_row_free(struct row *row); static inline struct row * -grid_row(struct grid *grid, int row_no) +_grid_row_maybe_alloc(struct grid *grid, int row_no, bool alloc_if_null) { assert(grid->offset >= 0); - int real_row = (grid->offset + row_no + grid->num_rows) % grid->num_rows; + int real_row = (grid->offset + row_no) & (grid->num_rows - 1); struct row *row = grid->rows[real_row]; - if (row == NULL) { - row = grid_row_alloc(grid->num_cols); + if (row == NULL && alloc_if_null) { + row = grid_row_alloc(grid->num_cols, false); grid->rows[real_row] = row; } - __builtin_prefetch(row->cells, 1, 3); + assert(row != NULL); return row; } static inline struct row * +grid_row(struct grid *grid, int row_no) +{ + return _grid_row_maybe_alloc(grid, row_no, false); +} + +static inline struct row * +grid_row_and_alloc(struct grid *grid, int row_no) +{ + return _grid_row_maybe_alloc(grid, row_no, true); +} + +static inline struct row * grid_row_in_view(struct grid *grid, int row_no) { assert(grid->view >= 0); - int real_row = (grid->view + row_no + grid->num_rows) % grid->num_rows; + int real_row = (grid->view + row_no) & (grid->num_rows - 1); struct row *row = grid->rows[real_row]; assert(row != NULL); @@ -568,8 +568,8 @@ grid_render(struct terminal *term) * could be hidden. Or it could have been scrolled out of view. */ bool cursor_is_visible = false; - int view_end = (term->grid->view + term->rows - 1) % term->grid->num_rows; - int cursor_row = (term->grid->offset + term->cursor.row) % term->grid->num_rows; + int view_end = (term->grid->view + term->rows - 1) & (term->grid->num_rows - 1); + int cursor_row = (term->grid->offset + term->cursor.row) & (term->grid->num_rows - 1); if (view_end >= term->grid->view) { /* Not wrapped */ if (cursor_row >= term->grid->view && cursor_row <= view_end) @@ -595,8 +595,7 @@ grid_render(struct terminal *term) /* Remember cursor coordinates so that we can erase it next * time. Note that we need to re-align it against the view. */ int view_aligned_row - = (cursor_row - term->grid->view + term->grid->num_rows) - % term->grid->num_rows; + = (cursor_row - term->grid->view + term->grid->num_rows) & (term->grid->num_rows - 1); term->render.last_cursor.actual = term->cursor; term->render.last_cursor.in_view = (struct coord) { @@ -680,7 +679,7 @@ reflow(struct row **new_grid, int new_cols, int new_rows, continue; if (new_grid[r] == NULL) - new_grid[r] = grid_row_alloc(new_cols); + new_grid[r] = grid_row_alloc(new_cols, false); struct cell *new_cells = new_grid[r]->cells; const struct cell *old_cells = old_grid[r]->cells; @@ -730,8 +729,8 @@ render_resize(struct terminal *term, int width, int height) const int new_cols = term->width / term->cell_width; const int new_rows = term->height / term->cell_height; - const int new_normal_grid_rows = new_rows + scrollback_lines; - const int new_alt_grid_rows = new_rows; + const int new_normal_grid_rows = 1 << (32 - __builtin_clz(new_rows + scrollback_lines - 1)); + const int new_alt_grid_rows = 1 << (32 - __builtin_clz(new_rows)); term->normal.offset %= new_normal_grid_rows; term->normal.view %= new_normal_grid_rows; @@ -742,12 +741,12 @@ render_resize(struct terminal *term, int width, int height) /* Allocate new 'normal' grid */ struct row **normal = calloc(new_normal_grid_rows, sizeof(normal[0])); for (int r = 0; r < new_rows; r++) - normal[(term->normal.view + r) % new_normal_grid_rows] = grid_row_alloc(new_cols); + normal[(term->normal.view + r) & (new_normal_grid_rows - 1)] = grid_row_alloc(new_cols, true);; /* Allocate new 'alt' grid */ struct row **alt = calloc(new_alt_grid_rows, sizeof(alt[0])); for (int r = 0; r < new_rows; r++) - alt[(term->alt.view + r) % new_alt_grid_rows] = grid_row_alloc(new_cols); + alt[(term->alt.view + r) & (new_alt_grid_rows - 1)] = grid_row_alloc(new_cols, true); /* Reflow content */ reflow(normal, new_cols, new_normal_grid_rows, @@ -254,36 +254,47 @@ term_scroll_partial(struct terminal *term, struct scroll_region region, int rows LOG_DBG("scroll: rows=%d, region.start=%d, region.end=%d", rows, region.start, region.end); - assert(rows < term->rows && "unimplemented"); +#if 0 + if (rows > region.end - region.start) { + /* For now, clamp */ + rows = region.end - region.start; + } +#endif bool view_follows = term->grid->view == term->grid->offset; term->grid->offset += rows; - term->grid->offset %= term->grid->num_rows; + term->grid->offset &= term->grid->num_rows - 1; if (view_follows) term->grid->view = term->grid->offset; +#if 0 /* * This loop serves two purposes: * 1) ensure all visible lines are *allocated* * 2) prefetch the cells - this makes life easier for erase_line() below */ + /* TODO: optimize this to not loop over *all* rows */ for (int r = max(region.end - rows, 0); r < term->rows; r++) { - struct row *row __attribute__((unused)) = grid_row(term->grid, r); - //__builtin_prefetch(row->cells, 1, 3); + int real_row = (term->grid->offset + r) & (term->grid->num_rows - 1); + struct row *row = term->grid->rows[real_row]; + if (row == NULL) { + row = grid_row_alloc(term->grid->num_cols, false); + term->grid->rows[real_row] = row; + } } - +#endif /* Top non-scrolling region. */ for (int i = region.start - 1; i >= 0; i--) - grid_swap_row(term->grid, i - rows, i); + grid_swap_row(term->grid, i - rows, i, false); /* Bottom non-scrolling region */ for (int i = term->rows - 1; i >= region.end; i--) - grid_swap_row(term->grid, i - rows, i); + grid_swap_row(term->grid, i - rows, i, false); /* Erase scrolled in lines */ - for (int r = max(region.end - rows, 0); r < region.end; r++) { - erase_line(term, grid_row(term->grid, r)); + for (int r = max(region.end - rows, region.start); r < region.end; r++) { + erase_line(term, grid_row_and_alloc(term->grid, r)); if (selection_on_row_in_view(term, r)) selection_cancel(term); } @@ -305,31 +316,47 @@ term_scroll_reverse_partial(struct terminal *term, LOG_DBG("scroll reverse: rows=%d, region.start=%d, region.end=%d", rows, region.start, region.end); - assert(rows < term->rows && "unimplemented"); +#if 0 + if (rows > region.end - region.start) { + /* For now, clamp */ + rows = region.end - region.start; + } +#endif bool view_follows = term->grid->view == term->grid->offset; - term->grid->offset += term->grid->num_rows - rows; - term->grid->offset %= term->grid->num_rows; + term->grid->offset -= rows; + while (term->grid->offset < 0) + term->grid->offset += term->grid->num_rows; + term->grid->offset &= term->grid->num_rows - 1; + + assert(term->grid->offset >= 0); + assert(term->grid->offset < term->grid->num_rows); if (view_follows) term->grid->view = term->grid->offset; +#if 0 + /* TODO: optimize this to not loop over *all* rows */ for (int r = 0; r < min(region.start + rows, region.end); r++) { - struct row *row __attribute__((unused)) = grid_row(term->grid, r); - //__builtin_prefetch(row->cells, 1, 3); + int real_row = (term->grid->offset + r) & (term->grid->num_rows - 1); + struct row *row = term->grid->rows[real_row]; + if (row == NULL) { + row = grid_row_alloc(term->grid->num_cols, false); + term->grid->rows[real_row] = row; + } } - +#endif /* Bottom non-scrolling region */ for (int i = region.end + rows; i < term->rows + rows; i++) - grid_swap_row(term->grid, i, i - rows); + grid_swap_row(term->grid, i, i - rows, false); /* Top non-scrolling region */ for (int i = 0 + rows; i < region.start + rows; i++) - grid_swap_row(term->grid, i, i - rows); + grid_swap_row(term->grid, i, i - rows, false); /* Erase scrolled in lines */ for (int r = region.start; r < min(region.start + rows, region.end); r++) { - erase_line(term, grid_row(term->grid, r)); + erase_line(term, grid_row_and_alloc(term->grid, r)); if (selection_on_row_in_view(term, r)) selection_cancel(term); } |
