refactor(grid): change schar_T representation to be more compact

Previously, a screen cell would occupy 28+4=32 bytes per cell
as we always made space for up to MAX_MCO+1 codepoints in a cell.

As an example, even a pretty modest 50*80 screen would consume

50*80*2*32 = 256000, i e a quarter megabyte

With the factor of two due to the TUI side buffer, and even more when
using msg_grid and/or ext_multigrid.

This instead stores a 4-byte union of either:
- a valid UTF-8 sequence up to 4 bytes
- an escape char which is invalid UTF-8 (0xFF) plus a 24-bit index to a
  glyph cache

This avoids allocating space for huge composed glyphs _upfront_, while
still keeping rendering such glyphs reasonably fast (1 hash table lookup
+ one plain index lookup). If the same large glyphs are using repeatedly
on the screen, this is still a net reduction of memory/cache
consumption. The only case which really gets worse is if you blast
the screen full with crazy emojis and zalgo text and even this case
only leads to 4 extra bytes per char.

When only <= 4-byte glyphs are used, plus the 4-byte attribute code,
i e 8 bytes in total there is a factor of four reduction of memory use.
Memory which will be quite hot in cache as the screen buffer is scanned
over in win_line() buffer text drawing

A slight complication is that the representation depends on host byte
order. I've tested this manually by compling and running this
in qemu-s390x and it works fine. We might add a qemu based solution
to CI at some point.

1 files changed, 30 insertions, 8 deletions

diff --git a/src/nvim/map.h b/src/nvim/map.h
index 23a5ea36a3..2d5517c552 100644
--- a/src/nvim/map.h
+++ b/src/nvim/map.h
@@ -18,6 +18,25 @@
 typedef const char *cstr_t;
 typedef void *ptr_t;
 
+// when used as a key, String doesn't need to be NUL terminated,
+// and can also contain embedded NUL:s as part of the data.
+static inline uint32_t hash_String(String s)
+{
+  uint32_t h = 0;
+  for (size_t i = 0; i < s.size; i++) {
+    h = (h << 5) - h + (uint8_t)s.data[i];
+  }
+  return h;
+}
+
+static inline bool equal_String(String a, String b)
+{
+  if (a.size != b.size) {
+    return false;
+  }
+  return memcmp(a.data, b.data, a.size) == 0;
+}
+
 #define Set(type) Set_##type
 #define Map(T, U) Map_##T##U
 #define PMap(T) Map(T, ptr_t)
@@ -57,7 +76,7 @@ typedef enum {
   kMHExisting = 0,
   kMHNewKeyDidFit,
   kMHNewKeyRealloc,
-} MhPutStatus;
+} MHPutStatus;
 
 void mh_clear(MapHash *h);
 void mh_realloc(MapHash *h, uint32_t n_min_buckets);
@@ -65,20 +84,22 @@ void mh_realloc(MapHash *h, uint32_t n_min_buckets);
 // layer 1: key type specific defs
 // This is all need for sets.
 
-#define KEY_DECLS(T) \
+#define MH_DECLS(T, K, K_query) \
   typedef struct { \
     MapHash h; \
-    T *keys; \
+    K *keys; \
   } Set(T); \
  \
-  uint32_t mh_find_bucket_##T(Set(T) *set, T key, bool put); \
-  uint32_t mh_get_##T(Set(T) *set, T key); \
+  uint32_t mh_find_bucket_##T(Set(T) *set, K_query key, bool put); \
+  uint32_t mh_get_##T(Set(T) *set, K_query key); \
   void mh_rehash_##T(Set(T) *set); \
-  uint32_t mh_put_##T(Set(T) *set, T key, MhPutStatus *new); \
+  uint32_t mh_put_##T(Set(T) *set, K_query key, MHPutStatus *new); \
+
+#define KEY_DECLS(T) \
+  MH_DECLS(T, T, T) \
   uint32_t mh_delete_##T(Set(T) *set, T *key); \
- \
   static inline bool set_put_##T(Set(T) *set, T key, T **key_alloc) { \
-    MhPutStatus status; \
+    MHPutStatus status; \
     uint32_t k = mh_put_##T(set, key, &status); \
     if (key_alloc) { \
       *key_alloc = &set->keys[k]; \
@@ -120,6 +141,7 @@ void mh_realloc(MapHash *h, uint32_t n_min_buckets);
 
 #define quasiquote(x, y) x##y
 
+MH_DECLS(glyph, char, String)
 KEY_DECLS(int)
 KEY_DECLS(cstr_t)
 KEY_DECLS(ptr_t)