From e2fdd53d8c015913e8be4ff708fc3488558c8906 Mon Sep 17 00:00:00 2001 From: bfredl Date: Sun, 14 May 2023 18:45:56 +0200 Subject: refactor(map): avoid duplicated khash_t types for values This reduces the total number of khash_t instantiations from 22 to 8. Make the khash internal functions take the size of values as a runtime parameter. This is abstracted with typesafe Map containers which are still specialized for both key, value type. Introduce `Set(key)` type for when there is no value. Refactor shada.c to use Map/Set instead of khash directly. This requires `map_ref` operation to be more flexible. Return pointers to both key and value, plus an indicator for new_item. As a bonus, `map_key` is now redundant. Instead of Map(cstr_t, FileMarks), use a pointer map as the FileMarks struct is humongous. Make `event_strings` actually work like an intern pool instead of wtf it was doing before. --- src/nvim/map.h | 104 ++++++++++++++++++++++++++++++++++++++------------------- 1 file changed, 69 insertions(+), 35 deletions(-) (limited to 'src/nvim/map.h') diff --git a/src/nvim/map.h b/src/nvim/map.h index 92f0b32255..cc32a20740 100644 --- a/src/nvim/map.h +++ b/src/nvim/map.h @@ -7,39 +7,71 @@ #include "klib/khash.h" #include "nvim/api/private/defs.h" -#include "nvim/extmark_defs.h" -#include "nvim/gettext.h" +#include "nvim/assert.h" #include "nvim/highlight_defs.h" -#include "nvim/map_defs.h" -#include "nvim/tui/input_defs.h" #include "nvim/types.h" -#include "nvim/ui_client.h" #if defined(__NetBSD__) # undef uint64_t # define uint64_t uint64_t #endif +typedef const char *cstr_t; +typedef void *ptr_t; + +#define Map(T, U) Map_##T##_##U +#define PMap(T) Map(T, ptr_t) + +#define KEY_DECLS(T) \ + KHASH_DECLARE(T) \ + static inline bool set_put_##T(Set(T) *set, T key, T **key_alloc) { \ + int kh_ret; \ + khiter_t k = kh_put(T, set, key, &kh_ret, 0); \ + if (key_alloc) { \ + *key_alloc = &kh_key(set, k); \ + } \ + return kh_ret; \ + } \ + static inline void set_del_##T(Set(T) *set, T key) \ + { \ + khiter_t k; \ + if ((k = kh_get(T, set, key)) != kh_end(set)) { \ + kh_del(T, set, k); \ + } \ + } \ + static inline bool set_has_##T(Set(T) *set, T key) { \ + return (kh_get(T, set, key) != kh_end(set)); \ + } \ + #define MAP_DECLS(T, U) \ - KHASH_DECLARE(T##_##U##_map, T, U) \ typedef struct { \ - khash_t(T##_##U##_map) table; \ + khash_t(T) table; \ } Map(T, U); \ - Map(T, U) *map_##T##_##U##_new(void); \ - void map_##T##_##U##_free(Map(T, U) *map); \ - void map_##T##_##U##_destroy(Map(T, U) *map); \ U map_##T##_##U##_get(Map(T, U) *map, T key); \ - bool map_##T##_##U##_has(Map(T, U) *map, T key); \ - T map_##T##_##U##_key(Map(T, U) *map, T key); \ + static inline bool map_##T##_##U##_has(Map(T, U) *map, T key) \ + { \ + return kh_get(T, &map->table, key) != kh_end(&map->table); \ + } \ U map_##T##_##U##_put(Map(T, U) *map, T key, U value); \ - U *map_##T##_##U##_ref(Map(T, U) *map, T key, bool put); \ - U map_##T##_##U##_del(Map(T, U) *map, T key); \ - void map_##T##_##U##_clear(Map(T, U) *map); + U *map_##T##_##U##_ref(Map(T, U) *map, T key, T **key_alloc); \ + U *map_##T##_##U##_put_ref(Map(T, U) *map, T key, T **key_alloc, bool *new_item); \ + U map_##T##_##U##_del(Map(T, U) *map, T key, T *key_alloc); \ -// // NOTE: Keys AND values must be allocated! khash.h does not make a copy. -// + +#define Set(type) khash_t(type) + +KEY_DECLS(int) +KEY_DECLS(cstr_t) +KEY_DECLS(ptr_t) +KEY_DECLS(uint64_t) +KEY_DECLS(uint32_t) +KEY_DECLS(String) +KEY_DECLS(HlEntry) +KEY_DECLS(ColorKey) + MAP_DECLS(int, int) +MAP_DECLS(int, ptr_t) MAP_DECLS(int, cstr_t) MAP_DECLS(cstr_t, ptr_t) MAP_DECLS(cstr_t, int) @@ -49,48 +81,50 @@ MAP_DECLS(uint64_t, ptr_t) MAP_DECLS(uint64_t, ssize_t) MAP_DECLS(uint64_t, uint64_t) MAP_DECLS(uint32_t, uint32_t) - -MAP_DECLS(handle_T, ptr_t) MAP_DECLS(HlEntry, int) MAP_DECLS(String, handle_T) MAP_DECLS(String, int) MAP_DECLS(int, String) - MAP_DECLS(ColorKey, ColorItem) -MAP_DECLS(KittyKey, cstr_t) - -#define MAP_INIT { { 0, 0, 0, 0, NULL, NULL, NULL } } -#define map_init(k, v, map) do { *(map) = (Map(k, v)) MAP_INIT; } while (false) +#define SET_INIT { 0, 0, 0, 0, NULL, NULL, NULL } +#define MAP_INIT { SET_INIT } -#define map_destroy(T, U) map_##T##_##U##_destroy #define map_get(T, U) map_##T##_##U##_get #define map_has(T, U) map_##T##_##U##_has -#define map_key(T, U) map_##T##_##U##_key #define map_put(T, U) map_##T##_##U##_put #define map_ref(T, U) map_##T##_##U##_ref +#define map_put_ref(T, U) map_##T##_##U##_put_ref #define map_del(T, U) map_##T##_##U##_del -#define map_clear(T, U) map_##T##_##U##_clear +#define map_destroy(T, map) kh_dealloc(T, &(map)->table) +#define map_clear(T, map) kh_clear(T, &(map)->table) #define map_size(map) ((map)->table.size) -#define pmap_destroy(T) map_destroy(T, ptr_t) #define pmap_get(T) map_get(T, ptr_t) #define pmap_has(T) map_has(T, ptr_t) -#define pmap_key(T) map_key(T, ptr_t) #define pmap_put(T) map_put(T, ptr_t) #define pmap_ref(T) map_ref(T, ptr_t) +#define pmap_put_ref(T) map_put_ref(T, ptr_t) /// @see pmap_del2 #define pmap_del(T) map_del(T, ptr_t) -#define pmap_clear(T) map_clear(T, ptr_t) -#define pmap_init(k, map) map_init(k, ptr_t, map) -#define map_foreach(map, key, value, block) \ - kh_foreach(&(map)->table, key, value, block) +#define map_foreach(U, map, key, value, block) kh_foreach(U, &(map)->table, key, value, block) -#define map_foreach_value(map, value, block) \ - kh_foreach_value(&(map)->table, value, block) +#define map_foreach_value(U, map, value, block) kh_foreach_value(U, &(map)->table, value, block) +#define map_foreach_key(map, key, block) kh_foreach_key(&(map)->table, key, block) +#define set_foreach(set, key, block) kh_foreach_key(set, key, block) + +#define pmap_foreach_value(map, value, block) map_foreach_value(ptr_t, map, value, block) +#define pmap_foreach(map, key, value, block) map_foreach(ptr_t, map, key, value, block) void pmap_del2(PMap(cstr_t) *map, const char *key); +#define set_has(T, set, key) set_has_##T(set, key) +#define set_put(T, set, key) set_put_##T(set, key, NULL) +#define set_put_ref(T, set, key, key_alloc) set_put_##T(set, key, key_alloc) +#define set_del(T, set, key) set_del_##T(set, key) +#define set_destroy(T, set) kh_dealloc(T, set) +#define set_clear(T, set) kh_clear(T, set) + #endif // NVIM_MAP_H -- cgit From 5970157e1d22fd5e05ae5d3bd949f807fb7a744c Mon Sep 17 00:00:00 2001 From: bfredl Date: Wed, 17 May 2023 16:08:06 +0200 Subject: refactor(map): enhanced implementation, Clean Code™, etc etc MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit This involves two redesigns of the map.c implementations: 1. Change of macro style and code organization The old khash.h and map.c implementation used huge #define blocks with a lot of backslash line continuations. This instead uses the "implementation file" .c.h pattern. Such a file is meant to be included multiple times, with different macros set prior to inclusion as parameters. we already use this pattern e.g. for eval/typval_encode.c.h to implement different typval encoders reusing a similar structure. We can structure this code into two parts. one that only depends on key type and is enough to implement sets, and one which depends on both key and value to implement maps (as a wrapper around sets, with an added value[] array) 2. Separate the main hash buckets from the key / value arrays Change the hack buckets to only contain an index into separate key / value arrays This is a common pattern in modern, state of the art hashmap implementations. Even though this leads to one more allocated array, it is this often is a net reduction of memory consumption. Consider key+value consuming at least 12 bytes per pair. On average, we will have twice as many buckets per item. Thus old implementation: 2*12 = 24 bytes per item New implementation 1*12 + 2*4 = 20 bytes per item And the difference gets bigger with larger items. One might think we have pulled a fast one here, as wouldn't the average size of the new key/value arrays be 1.5 slots per items due to amortized grows? But remember, these arrays are fully dense, and thus the accessed memory, measured in _cache lines_, the unit which actually matters, will be the fully used memory but just rounded up to the nearest cache line boundary. This has some other interesting properties, such as an insert-only set/map will be fully ordered by insert only. Preserving this ordering in face of deletions is more tricky tho. As we currently don't use ordered maps, the "delete" operation maintains compactness of the item arrays in the simplest way by breaking the ordering. It would be possible to implement an order-preserving delete although at some cost, like allowing the items array to become non-dense until the next rehash. Finally, in face of these two major changes, all code used in khash.h has been integrated into map.c and friends. Given the heavy edits it makes no sense to "layer" the code into a vendored and a wrapper part. Rather, the layered cake follows the specialization depth: code shared for all maps, code specialized to a key type (and its equivalence relation), and finally code specialized to value+key type. --- src/nvim/map.h | 177 ++++++++++++++++++++++++++++++++++++++++----------------- 1 file changed, 125 insertions(+), 52 deletions(-) (limited to 'src/nvim/map.h') diff --git a/src/nvim/map.h b/src/nvim/map.h index cc32a20740..a84d533262 100644 --- a/src/nvim/map.h +++ b/src/nvim/map.h @@ -5,7 +5,6 @@ #include #include -#include "klib/khash.h" #include "nvim/api/private/defs.h" #include "nvim/assert.h" #include "nvim/highlight_defs.h" @@ -19,47 +18,106 @@ typedef const char *cstr_t; typedef void *ptr_t; -#define Map(T, U) Map_##T##_##U +#define Set(type) Set_##type +#define Map(T, U) Map_##T##U #define PMap(T) Map(T, ptr_t) +static const int value_init_int = 0; +static const ptr_t value_init_ptr_t = NULL; +static const ssize_t value_init_ssize_t = -1; +static const uint32_t value_init_uint32_t = 0; +static const uint64_t value_init_uint64_t = 0; +static const String value_init_String = STRING_INIT; +static const ColorItem value_init_ColorItem = COLOR_ITEM_INITIALIZER; + +// layer 0: type non-specific code + +typedef struct { + uint32_t n_buckets; + uint32_t size; + uint32_t n_occupied; + uint32_t upper_bound; + uint32_t n_keys; // this is almost always "size", but keys[] could contain ded items.. + uint32_t keys_capacity; + uint32_t *hash; +} MapHash; + +#define MAPHASH_INIT { 0, 0, 0, 0, 0, 0, NULL } +#define SET_INIT { MAPHASH_INIT, NULL } +#define MAP_INIT { SET_INIT, NULL } + +#define MH_TOMBSTONE UINT32_MAX + +#define mh_is_empty(h, i) ((h)->hash[i] == 0) +#define mh_is_del(h, i) ((h)->hash[i] == MH_TOMBSTONE) +#define mh_is_either(h, i) ((uint32_t)((h)->hash[i] + 1U) <= 1U) + +typedef enum { + kMHExisting = 0, + kMHNewKeyDidFit, + kMHNewKeyRealloc, +} MhPutStatus; + +void mh_clear(MapHash *h); +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) \ - KHASH_DECLARE(T) \ + typedef struct { \ + MapHash h; \ + T *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); \ + void mh_rehash_##T(Set(T) *set); \ + uint32_t mh_put_##T(Set(T) *set, T key, MhPutStatus *new); \ + uint32_t mh_delete_##T(Set(T) *set, T *key); \ + \ static inline bool set_put_##T(Set(T) *set, T key, T **key_alloc) { \ - int kh_ret; \ - khiter_t k = kh_put(T, set, key, &kh_ret, 0); \ + MhPutStatus status; \ + uint32_t k = mh_put_##T(set, key, &status); \ if (key_alloc) { \ - *key_alloc = &kh_key(set, k); \ + *key_alloc = &set->keys[k]; \ } \ - return kh_ret; \ + return status != kMHExisting; \ } \ - static inline void set_del_##T(Set(T) *set, T key) \ + static inline T set_del_##T(Set(T) *set, T key) \ { \ - khiter_t k; \ - if ((k = kh_get(T, set, key)) != kh_end(set)) { \ - kh_del(T, set, k); \ - } \ + mh_delete_##T(set, &key); \ + return key; \ } \ static inline bool set_has_##T(Set(T) *set, T key) { \ - return (kh_get(T, set, key) != kh_end(set)); \ + return mh_get_##T(set, key) != MH_TOMBSTONE; \ } \ +// layer 2: key+value specific defs +// now we finally get Maps + #define MAP_DECLS(T, U) \ typedef struct { \ - khash_t(T) table; \ + Set(T) set; \ + U *values; \ } Map(T, U); \ - U map_##T##_##U##_get(Map(T, U) *map, T key); \ - static inline bool map_##T##_##U##_has(Map(T, U) *map, T key) \ + static inline U map_get_##T##U(Map(T, U) *map, T key) \ { \ - return kh_get(T, &map->table, key) != kh_end(&map->table); \ + uint32_t k = mh_get_##T(&map->set, key); \ + return k == MH_TOMBSTONE ? value_init_##U : map->values[k]; \ } \ - U map_##T##_##U##_put(Map(T, U) *map, T key, U value); \ - U *map_##T##_##U##_ref(Map(T, U) *map, T key, T **key_alloc); \ - U *map_##T##_##U##_put_ref(Map(T, U) *map, T key, T **key_alloc, bool *new_item); \ - U map_##T##_##U##_del(Map(T, U) *map, T key, T *key_alloc); \ + U *map_ref_##T##U(Map(T, U) *map, T key, T **key_alloc); \ + U *map_put_ref_##T##U(Map(T, U) *map, T key, T **key_alloc, bool *new_item); \ + static inline void map_put_##T##U(Map(T, U) *map, T key, U value) \ + { \ + U *val = map_put_ref_##T##U(map, key, NULL, NULL); \ + *val = value; \ + } \ + U map_del_##T##U(Map(T, U) *map, T key, T *key_alloc); \ -// NOTE: Keys AND values must be allocated! khash.h does not make a copy. +// NOTE: Keys AND values must be allocated! Map and Set does not make a copy. -#define Set(type) khash_t(type) +#define quasiquote(x, y) x##y KEY_DECLS(int) KEY_DECLS(cstr_t) @@ -72,7 +130,6 @@ KEY_DECLS(ColorKey) MAP_DECLS(int, int) MAP_DECLS(int, ptr_t) -MAP_DECLS(int, cstr_t) MAP_DECLS(cstr_t, ptr_t) MAP_DECLS(cstr_t, int) MAP_DECLS(ptr_t, ptr_t) @@ -82,49 +139,65 @@ MAP_DECLS(uint64_t, ssize_t) MAP_DECLS(uint64_t, uint64_t) MAP_DECLS(uint32_t, uint32_t) MAP_DECLS(HlEntry, int) -MAP_DECLS(String, handle_T) MAP_DECLS(String, int) MAP_DECLS(int, String) MAP_DECLS(ColorKey, ColorItem) -#define SET_INIT { 0, 0, 0, 0, NULL, NULL, NULL } -#define MAP_INIT { SET_INIT } - -#define map_get(T, U) map_##T##_##U##_get -#define map_has(T, U) map_##T##_##U##_has -#define map_put(T, U) map_##T##_##U##_put -#define map_ref(T, U) map_##T##_##U##_ref -#define map_put_ref(T, U) map_##T##_##U##_put_ref -#define map_del(T, U) map_##T##_##U##_del -#define map_destroy(T, map) kh_dealloc(T, &(map)->table) -#define map_clear(T, map) kh_clear(T, &(map)->table) - -#define map_size(map) ((map)->table.size) +#define set_has(T, set, key) set_has_##T(set, key) +#define set_put(T, set, key) set_put_##T(set, key, NULL) +#define set_put_ref(T, set, key, key_alloc) set_put_##T(set, key, key_alloc) +#define set_del(T, set, key) set_del_##T(set, key) +#define set_destroy(T, set) (xfree((set)->keys), xfree((set)->h.hash)) +#define set_clear(T, set) mh_clear(&(set)->h) +#define set_size(set) ((set)->h.size) + +#define map_get(T, U) map_get_##T##U +#define map_has(T, map, key) set_has(T, &(map)->set, key) +#define map_put(T, U) map_put_##T##U +#define map_ref(T, U) map_ref_##T##U +#define map_put_ref(T, U) map_put_ref_##T##U +#define map_del(T, U) map_del_##T##U +#define map_destroy(T, map) (set_destroy(T, &(map)->set), xfree((map)->values)) +#define map_clear(T, map) set_clear(T, &(map)->set) +#define map_size(map) set_size(&(map)->set) #define pmap_get(T) map_get(T, ptr_t) -#define pmap_has(T) map_has(T, ptr_t) #define pmap_put(T) map_put(T, ptr_t) #define pmap_ref(T) map_ref(T, ptr_t) #define pmap_put_ref(T) map_put_ref(T, ptr_t) /// @see pmap_del2 #define pmap_del(T) map_del(T, ptr_t) -#define map_foreach(U, map, key, value, block) kh_foreach(U, &(map)->table, key, value, block) +#define set_foreach(set, key, block) \ + { \ + uint32_t __i; \ + for (__i = 0; __i < (set)->h.n_keys; __i++) { \ + (key) = (set)->keys[__i]; \ + block; \ + } \ + } -#define map_foreach_value(U, map, value, block) kh_foreach_value(U, &(map)->table, value, block) -#define map_foreach_key(map, key, block) kh_foreach_key(&(map)->table, key, block) -#define set_foreach(set, key, block) kh_foreach_key(set, key, block) +#define map_foreach_key(map, key, block) set_foreach(&(map)->set, key, block) + +#define map_foreach(map, key, value, code) \ + { \ + uint32_t __i; \ + for (__i = 0; __i < (map)->set.h.n_keys; __i++) { \ + (key) = (map)->set.keys[__i]; \ + (value) = (map)->values[__i]; \ + code; \ + } \ + } -#define pmap_foreach_value(map, value, block) map_foreach_value(ptr_t, map, value, block) -#define pmap_foreach(map, key, value, block) map_foreach(ptr_t, map, key, value, block) +#define map_foreach_value(map, value, code) \ + { \ + uint32_t __i; \ + for (__i = 0; __i < (map)->set.h.n_keys; __i++) { \ + (value) = (map)->values[__i]; \ + code; \ + } \ + } void pmap_del2(PMap(cstr_t) *map, const char *key); -#define set_has(T, set, key) set_has_##T(set, key) -#define set_put(T, set, key) set_put_##T(set, key, NULL) -#define set_put_ref(T, set, key, key_alloc) set_put_##T(set, key, key_alloc) -#define set_del(T, set, key) set_del_##T(set, key) -#define set_destroy(T, set) kh_dealloc(T, set) -#define set_clear(T, set) kh_clear(T, set) - #endif // NVIM_MAP_H -- cgit From 87cde88c41d003988e7d5dbc4ddb26687d24923d Mon Sep 17 00:00:00 2001 From: bfredl Date: Fri, 25 Aug 2023 23:00:29 +0200 Subject: refactor(memfile): change mf_trans and mf_hash from ad-hoc hashtable to Map Memfile used a private implementation of an open hash table with intrusive collision chains, but there is no reason to assume the standard khash_t based Map won't work just fine. Yes, we are taking full ownership and maintenance over memline and memfile. No one is going to maintain it for us. Trust the plan. --- src/nvim/map.h | 4 ++++ 1 file changed, 4 insertions(+) (limited to 'src/nvim/map.h') diff --git a/src/nvim/map.h b/src/nvim/map.h index a84d533262..bfba014736 100644 --- a/src/nvim/map.h +++ b/src/nvim/map.h @@ -27,6 +27,7 @@ static const ptr_t value_init_ptr_t = NULL; static const ssize_t value_init_ssize_t = -1; static const uint32_t value_init_uint32_t = 0; static const uint64_t value_init_uint64_t = 0; +static const int64_t value_init_int64_t = 0; static const String value_init_String = STRING_INIT; static const ColorItem value_init_ColorItem = COLOR_ITEM_INITIALIZER; @@ -123,6 +124,7 @@ KEY_DECLS(int) KEY_DECLS(cstr_t) KEY_DECLS(ptr_t) KEY_DECLS(uint64_t) +KEY_DECLS(int64_t) KEY_DECLS(uint32_t) KEY_DECLS(String) KEY_DECLS(HlEntry) @@ -137,6 +139,8 @@ MAP_DECLS(uint32_t, ptr_t) MAP_DECLS(uint64_t, ptr_t) MAP_DECLS(uint64_t, ssize_t) MAP_DECLS(uint64_t, uint64_t) +MAP_DECLS(int64_t, int64_t) +MAP_DECLS(int64_t, ptr_t) MAP_DECLS(uint32_t, uint32_t) MAP_DECLS(HlEntry, int) MAP_DECLS(String, int) -- cgit From a6d745865a7f8b17f016b1879ed28376fed7b6b2 Mon Sep 17 00:00:00 2001 From: bfredl Date: Tue, 12 Sep 2023 11:54:36 +0200 Subject: refactor(highlight): merge redundant attr_entries and attr_entry_ids structs An insert-only set now defines a monotonically increasing ordering by itself. It can be used to both lookup the key from index, and vice versa. --- src/nvim/map.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/nvim/map.h') diff --git a/src/nvim/map.h b/src/nvim/map.h index bfba014736..23a5ea36a3 100644 --- a/src/nvim/map.h +++ b/src/nvim/map.h @@ -142,7 +142,6 @@ MAP_DECLS(uint64_t, uint64_t) MAP_DECLS(int64_t, int64_t) MAP_DECLS(int64_t, ptr_t) MAP_DECLS(uint32_t, uint32_t) -MAP_DECLS(HlEntry, int) MAP_DECLS(String, int) MAP_DECLS(int, String) MAP_DECLS(ColorKey, ColorItem) @@ -150,6 +149,7 @@ MAP_DECLS(ColorKey, ColorItem) #define set_has(T, set, key) set_has_##T(set, key) #define set_put(T, set, key) set_put_##T(set, key, NULL) #define set_put_ref(T, set, key, key_alloc) set_put_##T(set, key, key_alloc) +#define set_put_idx(T, set, key, status) mh_put_##T(set, key, status) #define set_del(T, set, key) set_del_##T(set, key) #define set_destroy(T, set) (xfree((set)->keys), xfree((set)->h.hash)) #define set_clear(T, set) mh_clear(&(set)->h) -- cgit 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.h | 38 ++++++++++++++++++++++++++++++-------- 1 file changed, 30 insertions(+), 8 deletions(-) (limited to 'src/nvim/map.h') 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) -- cgit From 4f8941c1a5f1ef6caa410feeb52e343db22763ce Mon Sep 17 00:00:00 2001 From: dundargoc Date: Fri, 10 Nov 2023 12:23:42 +0100 Subject: refactor: replace manual header guards with #pragma once It is less error-prone than manually defining header guards. Pretty much all compilers support it even if it's not part of the C standard. --- src/nvim/map.h | 5 +---- 1 file changed, 1 insertion(+), 4 deletions(-) (limited to 'src/nvim/map.h') diff --git a/src/nvim/map.h b/src/nvim/map.h index 2d5517c552..3251a53fdc 100644 --- a/src/nvim/map.h +++ b/src/nvim/map.h @@ -1,5 +1,4 @@ -#ifndef NVIM_MAP_H -#define NVIM_MAP_H +#pragma once #include #include @@ -225,5 +224,3 @@ MAP_DECLS(ColorKey, ColorItem) } void pmap_del2(PMap(cstr_t) *map, const char *key); - -#endif // NVIM_MAP_H -- cgit From 6c14ae6bfaf51415b555e9a6b85d1d280976358d Mon Sep 17 00:00:00 2001 From: dundargoc Date: Mon, 27 Nov 2023 20:27:32 +0100 Subject: refactor: rename types.h to types_defs.h --- src/nvim/map.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/nvim/map.h') diff --git a/src/nvim/map.h b/src/nvim/map.h index 3251a53fdc..38f9107efd 100644 --- a/src/nvim/map.h +++ b/src/nvim/map.h @@ -7,7 +7,7 @@ #include "nvim/api/private/defs.h" #include "nvim/assert.h" #include "nvim/highlight_defs.h" -#include "nvim/types.h" +#include "nvim/types_defs.h" #if defined(__NetBSD__) # undef uint64_t -- 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.h | 226 --------------------------------------------------------- 1 file changed, 226 deletions(-) delete mode 100644 src/nvim/map.h (limited to 'src/nvim/map.h') diff --git a/src/nvim/map.h b/src/nvim/map.h deleted file mode 100644 index 38f9107efd..0000000000 --- a/src/nvim/map.h +++ /dev/null @@ -1,226 +0,0 @@ -#pragma once - -#include -#include -#include - -#include "nvim/api/private/defs.h" -#include "nvim/assert.h" -#include "nvim/highlight_defs.h" -#include "nvim/types_defs.h" - -#if defined(__NetBSD__) -# undef uint64_t -# define uint64_t uint64_t -#endif - -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) - -static const int value_init_int = 0; -static const ptr_t value_init_ptr_t = NULL; -static const ssize_t value_init_ssize_t = -1; -static const uint32_t value_init_uint32_t = 0; -static const uint64_t value_init_uint64_t = 0; -static const int64_t value_init_int64_t = 0; -static const String value_init_String = STRING_INIT; -static const ColorItem value_init_ColorItem = COLOR_ITEM_INITIALIZER; - -// layer 0: type non-specific code - -typedef struct { - uint32_t n_buckets; - uint32_t size; - uint32_t n_occupied; - uint32_t upper_bound; - uint32_t n_keys; // this is almost always "size", but keys[] could contain ded items.. - uint32_t keys_capacity; - uint32_t *hash; -} MapHash; - -#define MAPHASH_INIT { 0, 0, 0, 0, 0, 0, NULL } -#define SET_INIT { MAPHASH_INIT, NULL } -#define MAP_INIT { SET_INIT, NULL } - -#define MH_TOMBSTONE UINT32_MAX - -#define mh_is_empty(h, i) ((h)->hash[i] == 0) -#define mh_is_del(h, i) ((h)->hash[i] == MH_TOMBSTONE) -#define mh_is_either(h, i) ((uint32_t)((h)->hash[i] + 1U) <= 1U) - -typedef enum { - kMHExisting = 0, - kMHNewKeyDidFit, - kMHNewKeyRealloc, -} MHPutStatus; - -void mh_clear(MapHash *h); -void mh_realloc(MapHash *h, uint32_t n_min_buckets); - -// layer 1: key type specific defs -// This is all need for sets. - -#define MH_DECLS(T, K, K_query) \ - typedef struct { \ - MapHash h; \ - K *keys; \ - } Set(T); \ - \ - 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, 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; \ - uint32_t k = mh_put_##T(set, key, &status); \ - if (key_alloc) { \ - *key_alloc = &set->keys[k]; \ - } \ - return status != kMHExisting; \ - } \ - static inline T set_del_##T(Set(T) *set, T key) \ - { \ - mh_delete_##T(set, &key); \ - return key; \ - } \ - static inline bool set_has_##T(Set(T) *set, T key) { \ - return mh_get_##T(set, key) != MH_TOMBSTONE; \ - } \ - -// layer 2: key+value specific defs -// now we finally get Maps - -#define MAP_DECLS(T, U) \ - typedef struct { \ - Set(T) set; \ - U *values; \ - } Map(T, U); \ - static inline U map_get_##T##U(Map(T, U) *map, T key) \ - { \ - uint32_t k = mh_get_##T(&map->set, key); \ - return k == MH_TOMBSTONE ? value_init_##U : map->values[k]; \ - } \ - U *map_ref_##T##U(Map(T, U) *map, T key, T **key_alloc); \ - U *map_put_ref_##T##U(Map(T, U) *map, T key, T **key_alloc, bool *new_item); \ - static inline void map_put_##T##U(Map(T, U) *map, T key, U value) \ - { \ - U *val = map_put_ref_##T##U(map, key, NULL, NULL); \ - *val = value; \ - } \ - U map_del_##T##U(Map(T, U) *map, T key, T *key_alloc); \ - -// NOTE: Keys AND values must be allocated! Map and Set does not make a copy. - -#define quasiquote(x, y) x##y - -MH_DECLS(glyph, char, String) -KEY_DECLS(int) -KEY_DECLS(cstr_t) -KEY_DECLS(ptr_t) -KEY_DECLS(uint64_t) -KEY_DECLS(int64_t) -KEY_DECLS(uint32_t) -KEY_DECLS(String) -KEY_DECLS(HlEntry) -KEY_DECLS(ColorKey) - -MAP_DECLS(int, int) -MAP_DECLS(int, ptr_t) -MAP_DECLS(cstr_t, ptr_t) -MAP_DECLS(cstr_t, int) -MAP_DECLS(ptr_t, ptr_t) -MAP_DECLS(uint32_t, ptr_t) -MAP_DECLS(uint64_t, ptr_t) -MAP_DECLS(uint64_t, ssize_t) -MAP_DECLS(uint64_t, uint64_t) -MAP_DECLS(int64_t, int64_t) -MAP_DECLS(int64_t, ptr_t) -MAP_DECLS(uint32_t, uint32_t) -MAP_DECLS(String, int) -MAP_DECLS(int, String) -MAP_DECLS(ColorKey, ColorItem) - -#define set_has(T, set, key) set_has_##T(set, key) -#define set_put(T, set, key) set_put_##T(set, key, NULL) -#define set_put_ref(T, set, key, key_alloc) set_put_##T(set, key, key_alloc) -#define set_put_idx(T, set, key, status) mh_put_##T(set, key, status) -#define set_del(T, set, key) set_del_##T(set, key) -#define set_destroy(T, set) (xfree((set)->keys), xfree((set)->h.hash)) -#define set_clear(T, set) mh_clear(&(set)->h) -#define set_size(set) ((set)->h.size) - -#define map_get(T, U) map_get_##T##U -#define map_has(T, map, key) set_has(T, &(map)->set, key) -#define map_put(T, U) map_put_##T##U -#define map_ref(T, U) map_ref_##T##U -#define map_put_ref(T, U) map_put_ref_##T##U -#define map_del(T, U) map_del_##T##U -#define map_destroy(T, map) (set_destroy(T, &(map)->set), xfree((map)->values)) -#define map_clear(T, map) set_clear(T, &(map)->set) -#define map_size(map) set_size(&(map)->set) - -#define pmap_get(T) map_get(T, ptr_t) -#define pmap_put(T) map_put(T, ptr_t) -#define pmap_ref(T) map_ref(T, ptr_t) -#define pmap_put_ref(T) map_put_ref(T, ptr_t) -/// @see pmap_del2 -#define pmap_del(T) map_del(T, ptr_t) - -#define set_foreach(set, key, block) \ - { \ - uint32_t __i; \ - for (__i = 0; __i < (set)->h.n_keys; __i++) { \ - (key) = (set)->keys[__i]; \ - block; \ - } \ - } - -#define map_foreach_key(map, key, block) set_foreach(&(map)->set, key, block) - -#define map_foreach(map, key, value, code) \ - { \ - uint32_t __i; \ - for (__i = 0; __i < (map)->set.h.n_keys; __i++) { \ - (key) = (map)->set.keys[__i]; \ - (value) = (map)->values[__i]; \ - code; \ - } \ - } - -#define map_foreach_value(map, value, code) \ - { \ - uint32_t __i; \ - for (__i = 0; __i < (map)->set.h.n_keys; __i++) { \ - (value) = (map)->values[__i]; \ - code; \ - } \ - } - -void pmap_del2(PMap(cstr_t) *map, const char *key); -- cgit