From e66870400d45e3d08265df9f6acd4631a5712139 Mon Sep 17 00:00:00 2001 From: Mattias Engdegård Date: Mon, 15 Jan 2024 09:25:02 +0100 Subject: Change hash range reduction from remainder to multiplication This makes both lookups and rehashing cheaper. The index vector size is now always a power of 2. The first table size is reduced to 6 (from 8), because index vectors would become excessively big otherwise. * src/lisp.h (struct Lisp_Hash_Table): Replace index_size with index_bits. All references adapted. (hash_table_index_size): New accessor; use it where applicable. * src/fns.c (hash_index_size): Replace with... (compute_hash_index_bits): ...this new function, returning the log2 of the index size. All callers adapted. (hash_index_index): Knuth multiplicative hashing instead of remainder. (maybe_resize_hash_table): Reduce first table size from 8 to 6. --- src/alloc.c | 7 ++++--- 1 file changed, 4 insertions(+), 3 deletions(-) (limited to 'src/alloc.c') diff --git a/src/alloc.c b/src/alloc.c index 15bb65cf74f..6abe9e28650 100644 --- a/src/alloc.c +++ b/src/alloc.c @@ -3443,7 +3443,7 @@ cleanup_vector (struct Lisp_Vector *vector) struct Lisp_Hash_Table *h = PSEUDOVEC_STRUCT (vector, Lisp_Hash_Table); if (h->table_size > 0) { - eassert (h->index_size > 1); + eassert (h->index_bits > 0); xfree (h->index); xfree (h->key_and_value); xfree (h->next); @@ -3451,7 +3451,7 @@ cleanup_vector (struct Lisp_Vector *vector) ptrdiff_t bytes = (h->table_size * (2 * sizeof *h->key_and_value + sizeof *h->hash + sizeof *h->next) - + h->index_size * sizeof *h->index); + + hash_table_index_size (h) * sizeof *h->index); hash_table_allocated_bytes -= bytes; } } @@ -5959,7 +5959,8 @@ purecopy_hash_table (struct Lisp_Hash_Table *table) for (ptrdiff_t i = 0; i < nvalues; i++) pure->key_and_value[i] = purecopy (table->key_and_value[i]); - ptrdiff_t index_bytes = table->index_size * sizeof *table->index; + ptrdiff_t index_bytes = hash_table_index_size (table) + * sizeof *table->index; pure->index = pure_alloc (index_bytes, -(int)sizeof *table->index); memcpy (pure->index, table->index, index_bytes); } -- cgit v1.2.1 From 188fe6bffa69e08b60a7d65709998bd803b7ada5 Mon Sep 17 00:00:00 2001 From: Mattias Engdegård Date: Mon, 19 Feb 2024 11:44:53 +0100 Subject: Replace XSET_HASH_TABLE with make_lisp_hash_table * src/lisp.h (XSET_HASH_TABLE): Remove, replace with... (make_lisp_hash_table): ...this. All callers adapted. --- src/alloc.c | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-) (limited to 'src/alloc.c') diff --git a/src/alloc.c b/src/alloc.c index 6abe9e28650..8c94c7eb33c 100644 --- a/src/alloc.c +++ b/src/alloc.c @@ -6034,8 +6034,7 @@ purecopy (Lisp_Object obj) return obj; /* Don't hash cons it. */ } - struct Lisp_Hash_Table *h = purecopy_hash_table (table); - XSET_HASH_TABLE (obj, h); + obj = make_lisp_hash_table (purecopy_hash_table (table)); } else if (COMPILEDP (obj) || VECTORP (obj) || RECORDP (obj)) { -- cgit v1.2.1 From 462d8ba813e07a25b71f5c1b38810a29e21f784c Mon Sep 17 00:00:00 2001 From: Mattias Engdegård Date: Sat, 10 Feb 2024 21:14:09 +0100 Subject: Add a proper type for obarrays The new opaque type replaces the previous use of vectors for obarrays. `obarray-make` now returns objects of this type. Functions that take obarrays continue to accept vectors for compatibility, now just using their first slot to store an actual obarray object. obarray-size and obarray-default-size now obsolete. * lisp/obarray.el (obarray-default-size, obarray-size): Declare obsolete. (obarray-make, obarrayp, obarray-clear): Remove from here. * src/fns.c (reduce_emacs_uint_to_hash_hash): Remove from here. * src/lisp.h (struct Lisp_Obarray, OBARRAYP, XOBARRAY, CHECK_OBARRAY) (make_lisp_obarray, obarray_size, check_obarray) (obarray_iter_t, make_obarray_iter, obarray_iter_at_end) (obarray_iter_step, obarray_iter_symbol, DOOBARRAY, knuth_hash): New. (reduce_emacs_uint_to_hash_hash): Moved here. * src/lread.c (check_obarray): Renamed and reworked as... (checked_obarray_slow): ...this. (intern_sym, Funintern, oblookup, map_obarray) (Finternal__obarray_buckets): Adapt to new type. (obarray_index, allocate_obarray, make_obarray, grow_obarray) (obarray_default_bits, Fobarray_make, Fobarrayp, Fobarray_clear): New. * etc/emacs_lldb.py (Lisp_Object): * lisp/emacs-lisp/cl-macs.el (`(,type . ,pred)): * lisp/emacs-lisp/cl-preloaded.el (cl--typeof-types): * lisp/emacs-lisp/comp-common.el (comp-known-type-specifiers): * lisp/emacs-lisp/comp.el (comp-known-predicates): * src/alloc.c (cleanup_vector, process_mark_stack): * src/data.c (Ftype_of, syms_of_data): * src/minibuf.c (Ftry_completion, Fall_completions, Ftest_completion): * src/pdumper.c (dump_obarray_buckets, dump_obarray, dump_vectorlike): * src/print.c (print_vectorlike_unreadable): * test/lisp/abbrev-tests.el (abbrev-make-abbrev-table-test): * test/lisp/obarray-tests.el (obarrayp-test) (obarrayp-unchecked-content-test, obarray-make-default-test) (obarray-make-with-size-test): Adapt to new type. --- src/alloc.c | 26 ++++++++++++++++++++++---- 1 file changed, 22 insertions(+), 4 deletions(-) (limited to 'src/alloc.c') diff --git a/src/alloc.c b/src/alloc.c index 8c94c7eb33c..2ffd2415447 100644 --- a/src/alloc.c +++ b/src/alloc.c @@ -360,13 +360,13 @@ static struct gcstat object_ct total_intervals, total_free_intervals; object_ct total_buffers; - /* Size of the ancillary arrays of live hash-table objects. + /* Size of the ancillary arrays of live hash-table and obarray objects. The objects themselves are not included (counted as vectors above). */ byte_ct total_hash_table_bytes; } gcstat; -/* Total size of ancillary arrays of all allocated hash-table objects, - both dead and alive. This number is always kept up-to-date. */ +/* Total size of ancillary arrays of all allocated hash-table and obarray + objects, both dead and alive. This number is always kept up-to-date. */ static ptrdiff_t hash_table_allocated_bytes = 0; /* Points to memory space allocated as "spare", to be freed if we run @@ -3455,6 +3455,15 @@ cleanup_vector (struct Lisp_Vector *vector) hash_table_allocated_bytes -= bytes; } } + break; + case PVEC_OBARRAY: + { + struct Lisp_Obarray *o = PSEUDOVEC_STRUCT (vector, Lisp_Obarray); + xfree (o->buckets); + ptrdiff_t bytes = obarray_size (o) * sizeof *o->buckets; + hash_table_allocated_bytes -= bytes; + } + break; /* Keep the switch exhaustive. */ case PVEC_NORMAL_VECTOR: case PVEC_FREE: @@ -5632,7 +5641,8 @@ valid_lisp_object_p (Lisp_Object obj) return 0; } -/* Like xmalloc, but makes allocation count toward the total consing. +/* Like xmalloc, but makes allocation count toward the total consing + and hash table or obarray usage. Return NULL for a zero-sized allocation. */ void * hash_table_alloc_bytes (ptrdiff_t nbytes) @@ -7310,6 +7320,14 @@ process_mark_stack (ptrdiff_t base_sp) break; } + case PVEC_OBARRAY: + { + struct Lisp_Obarray *o = (struct Lisp_Obarray *)ptr; + set_vector_marked (ptr); + mark_stack_push_values (o->buckets, obarray_size (o)); + break; + } + case PVEC_CHAR_TABLE: case PVEC_SUB_CHAR_TABLE: mark_char_table (ptr, (enum pvec_type) pvectype); -- cgit v1.2.1 From de6b1e1efb1a36c69e7a6e09297e1de5b1477121 Mon Sep 17 00:00:00 2001 From: Mattias Engdegård Date: Sat, 24 Feb 2024 17:47:37 +0100 Subject: Replace XSETSYMBOL with make_lisp_symbol * src/lisp.h (XSETSYMBOL): Remove. All callers changed to use make_lisp_symbol. --- src/alloc.c | 12 ++++-------- 1 file changed, 4 insertions(+), 8 deletions(-) (limited to 'src/alloc.c') diff --git a/src/alloc.c b/src/alloc.c index 2ffd2415447..16257469aa6 100644 --- a/src/alloc.c +++ b/src/alloc.c @@ -3960,7 +3960,7 @@ Its value is void, and its function definition and property list are nil. */) if (symbol_free_list) { ASAN_UNPOISON_SYMBOL (symbol_free_list); - XSETSYMBOL (val, symbol_free_list); + val = make_lisp_symbol (symbol_free_list); symbol_free_list = symbol_free_list->u.s.next; } else @@ -3976,7 +3976,7 @@ Its value is void, and its function definition and property list are nil. */) } ASAN_UNPOISON_SYMBOL (&symbol_block->symbols[symbol_block_index]); - XSETSYMBOL (val, &symbol_block->symbols[symbol_block_index]); + val = make_lisp_symbol (&symbol_block->symbols[symbol_block_index]); symbol_block_index++; } @@ -7398,12 +7398,8 @@ process_mark_stack (ptrdiff_t base_sp) mark_stack_push_value (SYMBOL_VAL (ptr)); break; case SYMBOL_VARALIAS: - { - Lisp_Object tem; - XSETSYMBOL (tem, SYMBOL_ALIAS (ptr)); - mark_stack_push_value (tem); - break; - } + mark_stack_push_value (make_lisp_symbol (SYMBOL_ALIAS (ptr))); + break; case SYMBOL_LOCALIZED: { struct Lisp_Buffer_Local_Value *blv = SYMBOL_BLV (ptr); -- cgit v1.2.1