perf(column): keep track of number of lines that hold up the 'signcolumn'

Problem:  The entire marktree needs to be traversed each time a sign is
          removed from the sentinel line.
Solution: Remove sentinel line and instead keep track of the number of
          lines that hold up the 'signcolumn' in "max_count". Adjust this
          number for added/removed signs, and set it to 0 when the
          maximum number of signs on a line changes. Only when
          "max_count" is decremented to 0 due to sign removal do we need
          to check the entire buffer.

          Also replace "invalid_top" and "invalid_bot" with a map of
          invalid ranges, further reducing the number of lines to be
          checked.

          Also improve tree traversal when counting the number of signs.
          Instead of looping over the to be checked range and counting
          the overlap for each row, keep track of the overlap in an
          array and add this to the count.

1 files changed, 4 insertions, 62 deletions

diff --git a/src/nvim/buffer.c b/src/nvim/buffer.c
index 8a594dea92..b5fac15af6 100644
--- a/src/nvim/buffer.c
+++ b/src/nvim/buffer.c
@@ -750,6 +750,8 @@ void buf_clear(void)
 {
   linenr_T line_count = curbuf->b_ml.ml_line_count;
   extmark_free_all(curbuf);   // delete any extmarks
+  map_destroy(int, curbuf->b_signcols.invalid);
+  *curbuf->b_signcols.invalid = (Map(int, SignRange)) MAP_INIT;
   while (!(curbuf->b_ml.ml_flags & ML_EMPTY)) {
     ml_delete(1, false);
   }
@@ -920,6 +922,8 @@ static void free_buffer_stuff(buf_T *buf, int free_flags)
   }
   uc_clear(&buf->b_ucmds);               // clear local user commands
   extmark_free_all(buf);                 // delete any extmarks
+  map_destroy(int, buf->b_signcols.invalid);
+  *buf->b_signcols.invalid = (Map(int, SignRange)) MAP_INIT;
   map_clear_mode(buf, MAP_ALL_MODES, true, false);  // clear local mappings
   map_clear_mode(buf, MAP_ALL_MODES, true, true);   // clear local abbrevs
   XFREE_CLEAR(buf->b_start_fenc);
@@ -1844,7 +1848,6 @@ buf_T *buflist_new(char *ffname_arg, char *sfname_arg, linenr_T lnum, int flags)
     buf = xcalloc(1, sizeof(buf_T));
     // init b: variables
     buf->b_vars = tv_dict_alloc();
-    buf->b_signcols.sentinel = 0;
     init_var_dict(buf->b_vars, &buf->b_bufvar, VAR_SCOPE);
     buf_init_changedtick(buf);
   }
@@ -4026,67 +4029,6 @@ char *buf_spname(buf_T *buf)
   return NULL;
 }
 
-/// Invalidate the signcolumn if needed after deleting a sign ranging from line1 to line2.
-void buf_signcols_del_check(buf_T *buf, linenr_T line1, linenr_T line2)
-{
-  linenr_T sent = buf->b_signcols.sentinel;
-  if (sent >= line1 && sent <= line2) {
-    // When removed sign overlaps the sentinel line, entire buffer needs to be checked.
-    buf->b_signcols.sentinel = buf->b_signcols.size = 0;
-  }
-}
-
-/// Invalidate the signcolumn if needed after adding a sign ranging from line1 to line2.
-void buf_signcols_add_check(buf_T *buf, linenr_T line1, linenr_T line2)
-{
-  if (!buf->b_signcols.sentinel) {
-    return;
-  }
-
-  linenr_T sent = buf->b_signcols.sentinel;
-  if (sent >= line1 && sent <= line2) {
-    // If added sign overlaps sentinel line, increment without invalidating.
-    if (buf->b_signcols.size == buf->b_signcols.max) {
-      buf->b_signcols.max++;
-    }
-    buf->b_signcols.size++;
-    return;
-  }
-
-  if (line1 < buf->b_signcols.invalid_top) {
-    buf->b_signcols.invalid_top = line1;
-  }
-  if (line2 > buf->b_signcols.invalid_bot) {
-    buf->b_signcols.invalid_bot = line2;
-  }
-}
-
-int buf_signcols(buf_T *buf, int max)
-{
-  if (!buf->b_signs_with_text) {
-    buf->b_signcols.size = 0;
-  } else if (max <= 1 && buf->b_signs_with_text >= (size_t)max) {
-    buf->b_signcols.size = max;
-  } else {
-    linenr_T sent = buf->b_signcols.sentinel;
-    if (!sent || max > buf->b_signcols.max) {
-      // Recheck if the window scoped maximum 'signcolumn' is greater than the
-      // previous maximum or if there is no sentinel line yet.
-      buf->b_signcols.invalid_top = sent ? sent : 1;
-      buf->b_signcols.invalid_bot = sent ? sent : buf->b_ml.ml_line_count;
-    }
-
-    if (buf->b_signcols.invalid_bot) {
-      decor_validate_signcols(buf, max);
-    }
-  }
-
-  buf->b_signcols.max = max;
-  buf->b_signcols.invalid_top = MAXLNUM;
-  buf->b_signcols.invalid_bot = 0;
-  return buf->b_signcols.size;
-}
-
 /// Get "buf->b_fname", use "[No Name]" if it is NULL.
 char *buf_get_fname(const buf_T *buf)
   FUNC_ATTR_PURE FUNC_ATTR_WARN_UNUSED_RESULT FUNC_ATTR_NONNULL_ALL