From 8da986ea877b07a5eb117446f410f2a7fc8cd9cb Mon Sep 17 00:00:00 2001 From: bfredl Date: Wed, 13 Sep 2023 13:39:18 +0200 Subject: 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. --- src/nvim/map_glyph_cache.c | 102 +++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 102 insertions(+) create mode 100644 src/nvim/map_glyph_cache.c (limited to 'src/nvim/map_glyph_cache.c') diff --git a/src/nvim/map_glyph_cache.c b/src/nvim/map_glyph_cache.c new file mode 100644 index 0000000000..6dcbfe0532 --- /dev/null +++ b/src/nvim/map_glyph_cache.c @@ -0,0 +1,102 @@ +// This is an open source non-commercial project. Dear PVS-Studio, please check +// it. PVS-Studio Static Code Analyzer for C, C++ and C#: http://www.viva64.com + +// Specialized version of Set() where interned strings is stored in a compact, +// NUL-separated char array. +// `String key` lookup keys don't need to be NULL terminated, but they +// must not contain embedded NUL:s. When reading a key from set->keys, they +// are always NUL terminated, though. Thus, it is enough to store an index into +// this array, and use strlen(), to retrive an interned key. + +#include "nvim/api/private/helpers.h" +#include "nvim/map.h" + +uint32_t mh_find_bucket_glyph(Set(glyph) *set, String key, bool put) +{ + MapHash *h = &set->h; + uint32_t step = 0; + uint32_t mask = h->n_buckets - 1; + uint32_t k = hash_String(key); + uint32_t i = k & mask; + uint32_t last = i; + uint32_t site = put ? last : MH_TOMBSTONE; + while (!mh_is_empty(h, i)) { + if (mh_is_del(h, i)) { + if (site == last) { + site = i; + } + } else if (equal_String(cstr_as_string(&set->keys[h->hash[i] - 1]), key)) { + return i; + } + i = (i + (++step)) & mask; + if (i == last) { + abort(); + } + } + if (site == last) { + site = i; + } + return site; +} + +/// @return index into set->keys if found, MH_TOMBSTONE otherwise +uint32_t mh_get_glyph(Set(glyph) *set, String key) +{ + if (set->h.n_buckets == 0) { + return MH_TOMBSTONE; + } + uint32_t idx = mh_find_bucket_glyph(set, key, false); + return (idx != MH_TOMBSTONE) ? set->h.hash[idx] - 1 : MH_TOMBSTONE; +} + +void mh_rehash_glyph(Set(glyph) *set) +{ + // assume the format of set->keys, i e NUL terminated strings + for (uint32_t k = 0; k < set->h.n_keys; k += (uint32_t)strlen(&set->keys[k]) + 1) { + uint32_t idx = mh_find_bucket_glyph(set, cstr_as_string(&set->keys[k]), true); + // there must be tombstones when we do a rehash + if (!mh_is_empty((&set->h), idx)) { + abort(); + } + set->h.hash[idx] = k + 1; + } + set->h.n_occupied = set->h.size = set->h.n_keys; +} + +uint32_t mh_put_glyph(Set(glyph) *set, String key, MHPutStatus *new) +{ + MapHash *h = &set->h; + // Might rehash ahead of time if "key" already existed. But it was + // going to happen soon anyway. + if (h->n_occupied >= h->upper_bound) { + mh_realloc(h, h->n_buckets + 1); + mh_rehash_glyph(set); + } + + uint32_t idx = mh_find_bucket_glyph(set, key, true); + + if (mh_is_either(h, idx)) { + h->size++; + h->n_occupied++; + + uint32_t size = (uint32_t)key.size + 1; // NUL takes space + uint32_t pos = h->n_keys; + h->n_keys += size; + if (h->n_keys > h->keys_capacity) { + h->keys_capacity = MAX(h->keys_capacity * 2, 64); + set->keys = xrealloc(set->keys, h->keys_capacity * sizeof(char)); + *new = kMHNewKeyRealloc; + } else { + *new = kMHNewKeyDidFit; + } + memcpy(&set->keys[pos], key.data, key.size); + set->keys[pos + key.size] = NUL; + h->hash[idx] = pos + 1; + return pos; + } else { + *new = kMHExisting; + uint32_t pos = h->hash[idx] - 1; + assert(equal_String(cstr_as_string(&set->keys[pos]), key)); + return pos; + } +} -- cgit From cf8b2c0e74fd5e723b0c15c2ce84e6900fd322d3 Mon Sep 17 00:00:00 2001 From: zeertzjq Date: Sat, 30 Sep 2023 12:05:28 +0800 Subject: build(iwyu): add a few more _defs.h mappings (#25435) --- src/nvim/map_glyph_cache.c | 10 ++++++++++ 1 file changed, 10 insertions(+) (limited to 'src/nvim/map_glyph_cache.c') diff --git a/src/nvim/map_glyph_cache.c b/src/nvim/map_glyph_cache.c index 6dcbfe0532..0d0f5ddd73 100644 --- a/src/nvim/map_glyph_cache.c +++ b/src/nvim/map_glyph_cache.c @@ -8,8 +8,18 @@ // are always NUL terminated, though. Thus, it is enough to store an index into // this array, and use strlen(), to retrive an interned key. +#include +#include +#include +#include +#include + +#include "nvim/api/private/defs.h" #include "nvim/api/private/helpers.h" +#include "nvim/ascii.h" +#include "nvim/macros.h" #include "nvim/map.h" +#include "nvim/memory.h" uint32_t mh_find_bucket_glyph(Set(glyph) *set, String key, bool put) { -- cgit From 2dc9ceb99c018b15dcf0c443cad46efecccaf94e Mon Sep 17 00:00:00 2001 From: dundargoc <33953936+dundargoc@users.noreply.github.com> Date: Sun, 29 Oct 2023 09:02:32 +0100 Subject: docs: small fixes (#25585) Co-authored-by: tmummert Co-authored-by: parikshit adhikari --- src/nvim/map_glyph_cache.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/nvim/map_glyph_cache.c') diff --git a/src/nvim/map_glyph_cache.c b/src/nvim/map_glyph_cache.c index 0d0f5ddd73..e79c8ecee8 100644 --- a/src/nvim/map_glyph_cache.c +++ b/src/nvim/map_glyph_cache.c @@ -6,7 +6,7 @@ // `String key` lookup keys don't need to be NULL terminated, but they // must not contain embedded NUL:s. When reading a key from set->keys, they // are always NUL terminated, though. Thus, it is enough to store an index into -// this array, and use strlen(), to retrive an interned key. +// this array, and use strlen(), to retrieve an interned key. #include #include -- cgit From 353a4be7e84fdc101318215bdcc8a7e780d737fe Mon Sep 17 00:00:00 2001 From: dundargoc Date: Sun, 12 Nov 2023 13:13:58 +0100 Subject: build: remove PVS We already have an extensive suite of static analysis tools we use, which causes a fair bit of redundancy as we get duplicate warnings. PVS is also prone to give false warnings which creates a lot of work to identify and disable. --- src/nvim/map_glyph_cache.c | 3 --- 1 file changed, 3 deletions(-) (limited to 'src/nvim/map_glyph_cache.c') diff --git a/src/nvim/map_glyph_cache.c b/src/nvim/map_glyph_cache.c index e79c8ecee8..ba3ee49499 100644 --- a/src/nvim/map_glyph_cache.c +++ b/src/nvim/map_glyph_cache.c @@ -1,6 +1,3 @@ -// This is an open source non-commercial project. Dear PVS-Studio, please check -// it. PVS-Studio Static Code Analyzer for C, C++ and C#: http://www.viva64.com - // Specialized version of Set() where interned strings is stored in a compact, // NUL-separated char array. // `String key` lookup keys don't need to be NULL terminated, but they -- cgit From 79b6ff28ad1204fbb4199b9092f5c578d88cb28e Mon Sep 17 00:00:00 2001 From: dundargoc Date: Tue, 28 Nov 2023 20:31:00 +0100 Subject: refactor: fix headers with IWYU --- src/nvim/map_glyph_cache.c | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) (limited to 'src/nvim/map_glyph_cache.c') diff --git a/src/nvim/map_glyph_cache.c b/src/nvim/map_glyph_cache.c index ba3ee49499..5efa87b960 100644 --- a/src/nvim/map_glyph_cache.c +++ b/src/nvim/map_glyph_cache.c @@ -13,9 +13,9 @@ #include "nvim/api/private/defs.h" #include "nvim/api/private/helpers.h" -#include "nvim/ascii.h" -#include "nvim/macros.h" -#include "nvim/map.h" +#include "nvim/ascii_defs.h" +#include "nvim/macros_defs.h" +#include "nvim/map_defs.h" #include "nvim/memory.h" uint32_t mh_find_bucket_glyph(Set(glyph) *set, String key, bool put) -- cgit