aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorDaniel Eklöf <daniel@ekloef.se>2019-08-22 15:33:23 +0000
committerDaniel Eklöf <daniel@ekloef.se>2019-08-22 15:33:23 +0000
commit7c7720a3ab314e471499194f114797ca7a40afde (patch)
tree1113380cb5fa7456ccebf71ed72c1b9d9d672c14
parentgenerate-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.c6
-rw-r--r--grid.c37
-rw-r--r--grid.h28
-rw-r--r--render.c17
-rw-r--r--terminal.c63
5 files changed, 101 insertions, 50 deletions
diff --git a/commands.c b/commands.c
index 4fe50a8f..01e73981 100644
--- a/commands.c
+++ b/commands.c
@@ -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);
diff --git a/grid.c b/grid.c
index 2ff82bd7..e0cc9482 100644
--- a/grid.c
+++ b/grid.c
@@ -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;
}
diff --git a/grid.h b/grid.h
index 4a25d218..a421a5c0 100644
--- a/grid.h
+++ b/grid.h
@@ -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);
diff --git a/render.c b/render.c
index 170f6bfe..028bb193 100644
--- a/render.c
+++ b/render.c
@@ -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,
diff --git a/terminal.c b/terminal.c
index b80093a0..a7fc9923 100644
--- a/terminal.c
+++ b/terminal.c
@@ -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);
}