perf(highlight): use a hashtable for highlight group names

bfredl · bfredl · commit bb4b4d79a8dd · 2021-08-19T15:08:50.000+02:00
syn_name2id and syn_check_group go brr.

Note: this has impact mostly when using multiple filetypes,
as the old syn_name2id was optimized to return latest
added groups quickly (which will be the latest filetype)
diff --git a/src/nvim/main.c b/src/nvim/main.c
@@ -166,6 +166,7 @@ void early_init(mparm_T *paramp)
   init_path(argv0 ? argv0 : "nvim");
   init_normal_cmds();   // Init the table of Normal mode commands.
   highlight_init();
+  syntax_init();
 
 #ifdef WIN32
   OSVERSIONINFO ovi;
diff --git a/src/nvim/map.c b/src/nvim/map.c
@@ -194,6 +194,7 @@ static inline bool ColorKey_eq(ColorKey ae1, ColorKey ae2)
 
 MAP_IMPL(int, int, DEFAULT_INITIALIZER)
 MAP_IMPL(cstr_t, ptr_t, DEFAULT_INITIALIZER)
+MAP_IMPL(cstr_t, int, DEFAULT_INITIALIZER)
 MAP_IMPL(ptr_t, ptr_t, DEFAULT_INITIALIZER)
 MAP_IMPL(uint64_t, ptr_t, DEFAULT_INITIALIZER)
 MAP_IMPL(uint64_t, ssize_t, SSIZE_INITIALIZER)
diff --git a/src/nvim/map.h b/src/nvim/map.h
@@ -36,6 +36,7 @@
 //
 MAP_DECLS(int, int)
 MAP_DECLS(cstr_t, ptr_t)
+MAP_DECLS(cstr_t, int)
 MAP_DECLS(ptr_t, ptr_t)
 MAP_DECLS(uint64_t, ptr_t)
 MAP_DECLS(uint64_t, ssize_t)
diff --git a/src/nvim/syntax.c b/src/nvim/syntax.c
@@ -53,9 +53,9 @@ static bool did_syntax_onoff = false;
 /// Structure that stores information about a highlight group.
 /// The ID of a highlight group is also called group ID.  It is the index in
 /// the highlight_ga array PLUS ONE.
-struct hl_group {
+typedef struct hl_group {
   char_u      *sg_name;         ///< highlight group name
-  char_u      *sg_name_u;       ///< uppercase of sg_name
+  char        *sg_name_u;       ///< uppercase of sg_name
   bool sg_cleared;              ///< "hi clear" was used
   int sg_attr;                  ///< Screen attr @see ATTR_ENTRY
   int sg_link;                  ///< link to this highlight group ID
@@ -80,7 +80,7 @@ struct hl_group {
   char *sg_rgb_sp_name;         ///< RGB special color name
 
   int sg_blend;                 ///< blend level (0-100 inclusive), -1 if unset
-};
+} HlGroup;
 
 /// \addtogroup SG_SET
 /// @{
@@ -91,6 +91,7 @@ struct hl_group {
 
 // builtin |highlight-groups|
 static garray_T highlight_ga = GA_EMPTY_INIT_VALUE;
+Map(cstr_t, int) *highlight_unames;
 
 static inline struct hl_group * HL_TABLE(void)
 {
@@ -384,6 +385,11 @@ static int current_line_id = 0;             // unique number for current line
 static int syn_time_on = FALSE;
 # define IF_SYN_TIME(p) (p)
 
+void syntax_init(void)
+{
+  highlight_unames = map_new(cstr_t, int)();
+}
+
 // Set the timeout used for syntax highlighting.
 // Use NULL to reset, no timeout.
 void syn_set_timeout(proftime_T *tm)
@@ -7113,6 +7119,7 @@ void free_highlight(void)
     xfree(HL_TABLE()[i].sg_name_u);
   }
   ga_clear(&highlight_ga);
+  map_free(cstr_t, int)(highlight_unames);
 }
 
 #endif
@@ -7474,7 +7481,6 @@ int syn_name2id(const char_u *name)
   FUNC_ATTR_NONNULL_ALL
 {
   return syn_name2id_len(name, STRLEN(name));
-
 }
 
 /// Lookup a highlight group name and return its ID.
@@ -7484,25 +7490,22 @@ int syn_name2id(const char_u *name)
 int syn_name2id_len(const char_u *name, size_t len)
   FUNC_ATTR_NONNULL_ALL
 {
-  int i;
-  char_u name_u[201];
+  char name_u[201];
 
   if (len == 0 || len > 200) {
+    // ID names over 200 chars don't deserve to be found!
     return 0;
   }
 
   // Avoid using stricmp() too much, it's slow on some systems */
-  // Avoid alloc()/free(), these are slow too.  ID names over 200 chars
-  // don't deserve to be found!
+  // Avoid alloc()/free(), these are slow too.
   memcpy(name_u, name, len);
   name_u[len] = '\0';
-  vim_strup(name_u);
-  // TODO(bfredl): what is a hash table?
-  for (i = highlight_ga.ga_len; --i >= 0; )
-    if (HL_TABLE()[i].sg_name_u != NULL
-        && STRCMP(name_u, HL_TABLE()[i].sg_name_u) == 0)
-      break;
-  return i + 1;
+  vim_strup((char_u *)name_u);
+
+  // map_get(..., int) returns 0 when no key is present, which is
+  // the expected value for missing highlight group.
+  return map_get(cstr_t, int)(highlight_unames, name_u);
 }
 
 /// Lookup a highlight group name and return its attributes.
@@ -7592,7 +7595,7 @@ static int syn_add_group(char_u *name)
     return 0;
   }
 
-  char_u *const name_up = vim_strsave_up(name);
+  char *const name_up = (char *)vim_strsave_up(name);
 
   // Append another syntax_highlight entry.
   struct hl_group* hlgp = GA_APPEND_VIA_PTR(struct hl_group, &highlight_ga);
@@ -7604,16 +7607,22 @@ static int syn_add_group(char_u *name)
   hlgp->sg_blend = -1;
   hlgp->sg_name_u = name_up;
 
-  return highlight_ga.ga_len;               /* ID is index plus one */
+  int id = highlight_ga.ga_len;  // ID is index plus one
+
+  map_put(cstr_t, int)(highlight_unames, name_up, id);
+
+  return id;
 }
 
 /// When, just after calling syn_add_group(), an error is discovered, this
 /// function deletes the new name.
 static void syn_unadd_group(void)
 {
   highlight_ga.ga_len--;
-  xfree(HL_TABLE()[highlight_ga.ga_len].sg_name);
-  xfree(HL_TABLE()[highlight_ga.ga_len].sg_name_u);
+  HlGroup *item = &HL_TABLE()[highlight_ga.ga_len];
+  map_del(cstr_t, int)(highlight_unames, item->sg_name_u);
+  xfree(item->sg_name);
+  xfree(item->sg_name_u);
 }
 
 
