[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
scratch/hash-table-perf 6ffbccbf1dd 15/37: Represent hash table weakness
From: |
Mattias Engdegård |
Subject: |
scratch/hash-table-perf 6ffbccbf1dd 15/37: Represent hash table weakness as an enum internally |
Date: |
Sun, 7 Jan 2024 12:41:11 -0500 (EST) |
branch: scratch/hash-table-perf
commit 6ffbccbf1dd928bdfa5d8f15458f00946fc44c34
Author: Mattias Engdegård <mattiase@acm.org>
Commit: Mattias Engdegård <mattiase@acm.org>
Represent hash table weakness as an enum internally
This takes less space (saves an entire word) and is more type-safe.
No change in behaviour.
* src/lisp.h (hash_table_weakness_t): New.
(struct Lisp_Hash_Table): Replace Lisp object `weak` with enum
`weakness`.
* src/fns.c
(keep_entry_p, hash_table_weakness_symbol): New.
(make_hash_table): Retype argument. All callers updated.
(sweep_weak_table, Fmake_hash_table, Fhash_table_weakness):
* src/alloc.c (purecopy_hash_table, purecopy, process_mark_stack):
* src/pdumper.c (dump_hash_table):
* src/print.c (print_object): Use retyped field.
---
src/alloc.c | 6 ++---
src/category.c | 2 +-
src/emacs-module.c | 2 +-
src/fns.c | 77 ++++++++++++++++++++++++++++++++++++------------------
src/frame.c | 2 +-
src/image.c | 2 +-
src/lisp.h | 24 ++++++++++++-----
src/lread.c | 8 +++---
src/pdumper.c | 1 +
src/pgtkterm.c | 3 ++-
src/print.c | 5 ++--
src/profiler.c | 2 +-
src/xfaces.c | 2 +-
src/xterm.c | 2 +-
14 files changed, 89 insertions(+), 49 deletions(-)
diff --git a/src/alloc.c b/src/alloc.c
index 53c7c84ec1a..be20dc6e5e7 100644
--- a/src/alloc.c
+++ b/src/alloc.c
@@ -5917,7 +5917,7 @@ make_pure_vector (ptrdiff_t len)
static struct Lisp_Hash_Table *
purecopy_hash_table (struct Lisp_Hash_Table *table)
{
- eassert (NILP (table->weak));
+ eassert (table->weakness == Weak_None);
eassert (table->purecopy);
struct Lisp_Hash_Table *pure = pure_alloc (sizeof *pure, Lisp_Vectorlike);
@@ -5990,7 +5990,7 @@ purecopy (Lisp_Object obj)
/* Do not purify hash tables which haven't been defined with
:purecopy as non-nil or are weak - they aren't guaranteed to
not change. */
- if (!NILP (table->weak) || !table->purecopy)
+ if (table->weakness != Weak_None || !table->purecopy)
{
/* Instead, add the hash table to the list of pinned objects,
so that it will be marked during GC. */
@@ -7263,7 +7263,7 @@ process_mark_stack (ptrdiff_t base_sp)
mark_stack_push_value (h->test.name);
mark_stack_push_value (h->test.user_hash_function);
mark_stack_push_value (h->test.user_cmp_function);
- if (NILP (h->weak))
+ if (h->weakness == Weak_None)
mark_stack_push_value (h->key_and_value);
else
{
diff --git a/src/category.c b/src/category.c
index dac5c78b5af..d4f10746a42 100644
--- a/src/category.c
+++ b/src/category.c
@@ -53,7 +53,7 @@ hash_get_category_set (Lisp_Object table, Lisp_Object
category_set)
(table, 1,
make_hash_table (hashtest_equal, DEFAULT_HASH_SIZE,
DEFAULT_REHASH_SIZE, DEFAULT_REHASH_THRESHOLD,
- Qnil, false));
+ Weak_None, false));
struct Lisp_Hash_Table *h = XHASH_TABLE (XCHAR_TABLE (table)->extras[1]);
Lisp_Object hash;
ptrdiff_t i = hash_lookup (h, category_set, &hash);
diff --git a/src/emacs-module.c b/src/emacs-module.c
index ac3d244d395..b7713d7e6c0 100644
--- a/src/emacs-module.c
+++ b/src/emacs-module.c
@@ -1699,7 +1699,7 @@ syms_of_module (void)
Vmodule_refs_hash
= make_hash_table (hashtest_eq, DEFAULT_HASH_SIZE,
DEFAULT_REHASH_SIZE, DEFAULT_REHASH_THRESHOLD,
- Qnil, false);
+ Weak_None, false);
DEFSYM (Qmodule_load_failed, "module-load-failed");
Fput (Qmodule_load_failed, Qerror_conditions,
diff --git a/src/fns.c b/src/fns.c
index 7cccabe74a2..71fac12813a 100644
--- a/src/fns.c
+++ b/src/fns.c
@@ -4541,8 +4541,7 @@ hash_index_size (struct Lisp_Hash_Table *h, ptrdiff_t
size)
be resized when the approximate ratio of table entries to table
size exceeds REHASH_THRESHOLD.
- WEAK specifies the weakness of the table. If non-nil, it must be
- one of the symbols `key', `value', `key-or-value', or `key-and-value'.
+ WEAK specifies the weakness of the table.
If PURECOPY is non-nil, the table can be copied to pure storage via
`purecopy' when Emacs is being dumped. Such tables can no longer be
@@ -4551,7 +4550,7 @@ hash_index_size (struct Lisp_Hash_Table *h, ptrdiff_t
size)
Lisp_Object
make_hash_table (struct hash_table_test test, EMACS_INT size,
float rehash_size, float rehash_threshold,
- Lisp_Object weak, bool purecopy)
+ hash_table_weakness_t weak, bool purecopy)
{
struct Lisp_Hash_Table *h;
Lisp_Object table;
@@ -4571,7 +4570,7 @@ make_hash_table (struct hash_table_test test, EMACS_INT
size,
/* Initialize hash table slots. */
h->test = test;
- h->weak = weak;
+ h->weakness = weak;
h->rehash_threshold = rehash_threshold;
h->rehash_size = rehash_size;
h->count = 0;
@@ -4869,6 +4868,23 @@ hash_clear (struct Lisp_Hash_Table *h)
Weak Hash Tables
************************************************************************/
+/* Whether to keep an entry whose key and value are known to be retained
+ if STRONG_KEY and STRONG_VALUE, respectively, are true. */
+static inline bool
+keep_entry_p (hash_table_weakness_t weakness,
+ bool strong_key, bool strong_value)
+{
+ switch (weakness)
+ {
+ case Weak_None: return true;
+ case Weak_Key: return strong_key;
+ case Weak_Value: return strong_value;
+ case Weak_Key_Or_Value: return strong_key || strong_value;
+ case Weak_Key_And_Value: return strong_key && strong_value;
+ }
+ emacs_abort();
+}
+
/* Sweep weak hash table H. REMOVE_ENTRIES_P means remove
entries from the table that don't survive the current GC.
!REMOVE_ENTRIES_P means mark entries that are in use. Value is
@@ -4890,18 +4906,9 @@ sweep_weak_table (struct Lisp_Hash_Table *h, bool
remove_entries_p)
{
bool key_known_to_survive_p = survives_gc_p (HASH_KEY (h, i));
bool value_known_to_survive_p = survives_gc_p (HASH_VALUE (h, i));
- bool remove_p;
-
- if (EQ (h->weak, Qkey))
- remove_p = !key_known_to_survive_p;
- else if (EQ (h->weak, Qvalue))
- remove_p = !value_known_to_survive_p;
- else if (EQ (h->weak, Qkey_or_value))
- remove_p = !(key_known_to_survive_p || value_known_to_survive_p);
- else if (EQ (h->weak, Qkey_and_value))
- remove_p = !(key_known_to_survive_p && value_known_to_survive_p);
- else
- emacs_abort ();
+ bool remove_p = !keep_entry_p (h->weakness,
+ key_known_to_survive_p,
+ value_known_to_survive_p);
next = HASH_NEXT (h, i);
@@ -5367,15 +5374,20 @@ usage: (make-hash-table &rest KEYWORD-ARGS) */)
/* Look for `:weakness WEAK'. */
i = get_key_arg (QCweakness, nargs, args, used);
- Lisp_Object weak = i ? args[i] : Qnil;
- if (EQ (weak, Qt))
- weak = Qkey_and_value;
- if (!NILP (weak)
- && !EQ (weak, Qkey)
- && !EQ (weak, Qvalue)
- && !EQ (weak, Qkey_or_value)
- && !EQ (weak, Qkey_and_value))
- signal_error ("Invalid hash table weakness", weak);
+ Lisp_Object weakness = i ? args[i] : Qnil;
+ hash_table_weakness_t weak;
+ if (NILP (weakness))
+ weak = Weak_None;
+ else if (EQ (weakness, Qkey))
+ weak = Weak_Key;
+ else if (EQ (weakness, Qvalue))
+ weak = Weak_Value;
+ else if (EQ (weakness, Qkey_or_value))
+ weak = Weak_Key_Or_Value;
+ else if (EQ (weakness, Qt) || EQ (weakness, Qkey_and_value))
+ weak = Weak_Key_And_Value;
+ else
+ signal_error ("Invalid hash table weakness", weakness);
/* Now, all args should have been used up, or there's a problem. */
for (i = 0; i < nargs; ++i)
@@ -5449,13 +5461,26 @@ DEFUN ("hash-table-test", Fhash_table_test,
Shash_table_test, 1, 1, 0,
return check_hash_table (table)->test.name;
}
+Lisp_Object
+hash_table_weakness_symbol (hash_table_weakness_t weak)
+{
+ switch (weak)
+ {
+ case Weak_None: return Qnil;
+ case Weak_Key: return Qkey;
+ case Weak_Value: return Qvalue;
+ case Weak_Key_And_Value: return Qkey_and_value;
+ case Weak_Key_Or_Value: return Qkey_or_value;
+ }
+ emacs_abort ();
+}
DEFUN ("hash-table-weakness", Fhash_table_weakness, Shash_table_weakness,
1, 1, 0,
doc: /* Return the weakness of TABLE. */)
(Lisp_Object table)
{
- return check_hash_table (table)->weak;
+ return hash_table_weakness_symbol (check_hash_table (table)->weakness);
}
diff --git a/src/frame.c b/src/frame.c
index b6f92d6f9f5..47b00f5077b 100644
--- a/src/frame.c
+++ b/src/frame.c
@@ -1041,7 +1041,7 @@ make_frame (bool mini_p)
fset_face_hash_table
(f, make_hash_table (hashtest_eq, DEFAULT_HASH_SIZE, DEFAULT_REHASH_SIZE,
- DEFAULT_REHASH_THRESHOLD, Qnil, false));
+ DEFAULT_REHASH_THRESHOLD, Weak_None, false));
if (mini_p)
{
diff --git a/src/image.c b/src/image.c
index 651ec0b34e5..f05567ca03c 100644
--- a/src/image.c
+++ b/src/image.c
@@ -6071,7 +6071,7 @@ xpm_make_color_table_h (void (**put_func) (Lisp_Object,
const char *, int,
*get_func = xpm_get_color_table_h;
return make_hash_table (hashtest_equal, DEFAULT_HASH_SIZE,
DEFAULT_REHASH_SIZE, DEFAULT_REHASH_THRESHOLD,
- Qnil, false);
+ Weak_None, false);
}
static void
diff --git a/src/lisp.h b/src/lisp.h
index 669ca3a8626..6e3f86672e3 100644
--- a/src/lisp.h
+++ b/src/lisp.h
@@ -2403,6 +2403,18 @@ struct hash_table_test
Lisp_Object (*hashfn) (Lisp_Object, struct Lisp_Hash_Table *);
};
+typedef enum {
+ Weak_None, /* No weak references. */
+ Weak_Key, /* Reference to key is weak. */
+ Weak_Value, /* Reference to value is weak. */
+ Weak_Key_Or_Value, /* References to key or value are weak:
+ element kept as long as strong reference to
+ either key or value remains. */
+ Weak_Key_And_Value, /* References to key and value are weak:
+ element kept as long as strong references to
+ both key and value remain. */
+} hash_table_weakness_t;
+
struct Lisp_Hash_Table
{
/* Change pdumper.c if you change the fields here. */
@@ -2410,10 +2422,6 @@ struct Lisp_Hash_Table
/* This is for Lisp; the hash table code does not refer to it. */
union vectorlike_header header;
- /* Nil if table is non-weak. Otherwise a symbol describing the
- weakness of the table. */
- Lisp_Object weak;
-
/* Vector of hash codes, or nil if the table needs rehashing.
If the I-th entry is unused, then hash[I] should be nil. */
Lisp_Object hash;
@@ -2440,6 +2448,9 @@ struct Lisp_Hash_Table
/* Index of first free entry in free list, or -1 if none. */
ptrdiff_t next_free;
+ /* Weakness of the table. */
+ hash_table_weakness_t weakness : 8;
+
/* True if the table can be purecopied. The table cannot be
changed afterwards. */
bool purecopy;
@@ -2476,7 +2487,7 @@ struct Lisp_Hash_Table
} GCALIGNED_STRUCT;
/* Sanity-check pseudovector layout. */
-verify (offsetof (struct Lisp_Hash_Table, weak) == header_size);
+verify (offsetof (struct Lisp_Hash_Table, hash) == header_size);
/* Key value that marks an unused hash table entry. */
#define HASH_UNUSED_ENTRY_KEY Qunbound
@@ -3995,7 +4006,8 @@ EMACS_UINT hash_string (char const *, ptrdiff_t);
EMACS_UINT sxhash (Lisp_Object);
Lisp_Object hashfn_user_defined (Lisp_Object, struct Lisp_Hash_Table *);
Lisp_Object make_hash_table (struct hash_table_test, EMACS_INT, float, float,
- Lisp_Object, bool);
+ hash_table_weakness_t, bool);
+Lisp_Object hash_table_weakness_symbol (hash_table_weakness_t weak);
ptrdiff_t hash_lookup (struct Lisp_Hash_Table *, Lisp_Object, Lisp_Object *);
ptrdiff_t hash_put (struct Lisp_Hash_Table *, Lisp_Object, Lisp_Object,
Lisp_Object);
diff --git a/src/lread.c b/src/lread.c
index a7ee0cb739c..9a30f43ff3e 100644
--- a/src/lread.c
+++ b/src/lread.c
@@ -2546,13 +2546,13 @@ readevalloop (Lisp_Object readcharfun,
read_objects_map
= make_hash_table (hashtest_eq, DEFAULT_HASH_SIZE,
DEFAULT_REHASH_SIZE, DEFAULT_REHASH_THRESHOLD,
- Qnil, false);
+ Weak_None, false);
if (! HASH_TABLE_P (read_objects_completed)
|| XHASH_TABLE (read_objects_completed)->count)
read_objects_completed
= make_hash_table (hashtest_eq, DEFAULT_HASH_SIZE,
DEFAULT_REHASH_SIZE, DEFAULT_REHASH_THRESHOLD,
- Qnil, false);
+ Weak_None, false);
if (!NILP (Vpurify_flag) && c == '(')
val = read0 (readcharfun, false);
else
@@ -2797,12 +2797,12 @@ read_internal_start (Lisp_Object stream, Lisp_Object
start, Lisp_Object end,
|| XHASH_TABLE (read_objects_map)->count)
read_objects_map
= make_hash_table (hashtest_eq, DEFAULT_HASH_SIZE, DEFAULT_REHASH_SIZE,
- DEFAULT_REHASH_THRESHOLD, Qnil, false);
+ DEFAULT_REHASH_THRESHOLD, Weak_None, false);
if (! HASH_TABLE_P (read_objects_completed)
|| XHASH_TABLE (read_objects_completed)->count)
read_objects_completed
= make_hash_table (hashtest_eq, DEFAULT_HASH_SIZE, DEFAULT_REHASH_SIZE,
- DEFAULT_REHASH_THRESHOLD, Qnil, false);
+ DEFAULT_REHASH_THRESHOLD, Weak_None, false);
if (STRINGP (stream)
|| ((CONSP (stream) && STRINGP (XCAR (stream)))))
diff --git a/src/pdumper.c b/src/pdumper.c
index 0492e51a774..2353e3fbbeb 100644
--- a/src/pdumper.c
+++ b/src/pdumper.c
@@ -2726,6 +2726,7 @@ dump_hash_table (struct dump_context *ctx, Lisp_Object
object)
them as close to the hash table as possible. */
DUMP_FIELD_COPY (out, hash, count);
DUMP_FIELD_COPY (out, hash, next_free);
+ DUMP_FIELD_COPY (out, hash, weakness);
DUMP_FIELD_COPY (out, hash, purecopy);
DUMP_FIELD_COPY (out, hash, mutable);
DUMP_FIELD_COPY (out, hash, rehash_threshold);
diff --git a/src/pgtkterm.c b/src/pgtkterm.c
index 9a87820f82b..68325d166c1 100644
--- a/src/pgtkterm.c
+++ b/src/pgtkterm.c
@@ -7181,7 +7181,8 @@ If set to a non-float value, there will be no wait at
all. */);
DEFVAR_LISP ("pgtk-keysym-table", Vpgtk_keysym_table,
doc: /* Hash table of character codes indexed by X keysym codes. */);
Vpgtk_keysym_table = make_hash_table (hashtest_eql, 900, DEFAULT_REHASH_SIZE,
- DEFAULT_REHASH_THRESHOLD, Qnil, false);
+ DEFAULT_REHASH_THRESHOLD,
+ Weak_None, false);
window_being_scrolled = Qnil;
staticpro (&window_being_scrolled);
diff --git a/src/print.c b/src/print.c
index 3c7e496bb51..568835fa7a9 100644
--- a/src/print.c
+++ b/src/print.c
@@ -2583,10 +2583,11 @@ print_object (Lisp_Object obj, Lisp_Object
printcharfun, bool escapeflag)
print_object (h->test.name, printcharfun, escapeflag);
}
- if (!NILP (h->weak))
+ if (h->weakness != Weak_None)
{
print_c_string (" weakness ", printcharfun);
- print_object (h->weak, printcharfun, escapeflag);
+ print_object (hash_table_weakness_symbol (h->weakness),
+ printcharfun, escapeflag);
}
print_c_string (" rehash-size ", printcharfun);
diff --git a/src/profiler.c b/src/profiler.c
index c88600c5397..8ee45b107a5 100644
--- a/src/profiler.c
+++ b/src/profiler.c
@@ -568,7 +568,7 @@ export_log (struct profiler_log *plog)
Lisp_Object h = make_hash_table (hashtest_equal, DEFAULT_HASH_SIZE,
DEFAULT_REHASH_SIZE,
DEFAULT_REHASH_THRESHOLD,
- Qnil, false);
+ Weak_None, false);
for (int i = 0; i < log->size; i++)
{
int count = get_log_count (log, i);
diff --git a/src/xfaces.c b/src/xfaces.c
index a6a20389f7d..97bd963f3c8 100644
--- a/src/xfaces.c
+++ b/src/xfaces.c
@@ -7334,7 +7334,7 @@ only for this purpose. */);
Vface_new_frame_defaults =
/* 33 entries is enough to fit all basic faces */
make_hash_table (hashtest_eq, 33, DEFAULT_REHASH_SIZE,
- DEFAULT_REHASH_THRESHOLD, Qnil, false);
+ DEFAULT_REHASH_THRESHOLD, Weak_None, false);
DEFVAR_LISP ("face-default-stipple", Vface_default_stipple,
doc: /* Default stipple pattern used on monochrome displays.
diff --git a/src/xterm.c b/src/xterm.c
index 4aad78dc47b..80112223a1b 100644
--- a/src/xterm.c
+++ b/src/xterm.c
@@ -32558,7 +32558,7 @@ If set to a non-float value, there will be no wait at
all. */);
Vx_keysym_table = make_hash_table (hashtest_eql, 900,
DEFAULT_REHASH_SIZE,
DEFAULT_REHASH_THRESHOLD,
- Qnil, false);
+ Weak_None, false);
DEFVAR_BOOL ("x-frame-normalize-before-maximize",
x_frame_normalize_before_maximize,
- scratch/hash-table-perf 9f94796b657 05/37: ; * src/fns.c (collect_interval): Move misplaced function., (continued)
- scratch/hash-table-perf 9f94796b657 05/37: ; * src/fns.c (collect_interval): Move misplaced function., Mattias Engdegård, 2024/01/07
- scratch/hash-table-perf 594152bf667 01/37: Add internal hash-table debug functions, Mattias Engdegård, 2024/01/07
- scratch/hash-table-perf 3d2042c48a6 07/37: Refactor: extract hash index computation to a function, Mattias Engdegård, 2024/01/07
- scratch/hash-table-perf 9141966be51 09/37: ; * src/alloc.c (purecopy_hash_table): Simplify, Mattias Engdegård, 2024/01/07
- scratch/hash-table-perf 31950946290 04/37: Refactor: less egregious layering violation in composite.h, Mattias Engdegård, 2024/01/07
- scratch/hash-table-perf 4e8d7725fd4 11/37: ; * src/fns.c (Fmake_hash_table): ensure `test` is a bare symbol, Mattias Engdegård, 2024/01/07
- scratch/hash-table-perf 4b5d9f92abe 13/37: * src/print.c (print_object): Don't print empty hash-table data, Mattias Engdegård, 2024/01/07
- scratch/hash-table-perf 3e9e68333ae 16/37: Remove rehash-threshold and rehash-size struct members, Mattias Engdegård, 2024/01/07
- scratch/hash-table-perf c188b9f2bf5 08/37: Refactor hash table vector reallocation, Mattias Engdegård, 2024/01/07
- scratch/hash-table-perf fdc390f8dc0 10/37: Abstract predicate and constant for unused hash keys, Mattias Engdegård, 2024/01/07
- scratch/hash-table-perf 6ffbccbf1dd 15/37: Represent hash table weakness as an enum internally,
Mattias Engdegård <=
- scratch/hash-table-perf e69035c6ef5 17/37: Leaner hash table dumping and thawing, Mattias Engdegård, 2024/01/07
- scratch/hash-table-perf f3e985a16ba 14/37: Don't print or read the hash table size parameter, Mattias Engdegård, 2024/01/07
- scratch/hash-table-perf e2a6ce36d83 03/37: Decouple profiler from Lisp hash table internals, Mattias Engdegård, 2024/01/07
- scratch/hash-table-perf c4df6041de8 12/37: * src/print.c (print_object): Don't print hash table test if `eql`., Mattias Engdegård, 2024/01/07
- scratch/hash-table-perf 2d28042f56a 19/37: Use non-Lisp allocation for internal hash-table vectors, Mattias Engdegård, 2024/01/07
- scratch/hash-table-perf 54807fee4d0 23/37: Use hash_idx_t for storing hash indices, Mattias Engdegård, 2024/01/07
- scratch/hash-table-perf fc68176120f 24/37: Use hash_hash_t for storing hash values, Mattias Engdegård, 2024/01/07
- scratch/hash-table-perf 310f6584ccb 18/37: Allow zero hash table size, Mattias Engdegård, 2024/01/07
- scratch/hash-table-perf 8e80d1930e3 20/37: Store hash values as EMACS_UINT instead of Lisp_Object, Mattias Engdegård, 2024/01/07
- scratch/hash-table-perf 1ebd00f6d0a 21/37: Retype hash interfaces to use EMACS_UINT instead of Lisp fixnum, Mattias Engdegård, 2024/01/07