From 7207b63c8e290ddec33908ce8d38be5793388318 Mon Sep 17 00:00:00 2001 From: Paul Eggert Date: Tue, 21 Feb 2017 15:31:29 -0800 Subject: [PATCH] Hash table threshold is now float, not double Change default from 0.8 to 0.8125 so it fits in float without rounding glitches. * doc/lispref/hash.texi (Creating Hash): * doc/lispref/objects.texi (Hash Table Type): * etc/NEWS: Document change. * src/fns.c (make_hash_table, maybe_resize_hash_table) (Fmake_hash_table): Threshold is now float, not double. Be consistent about how this is rounded. * src/lisp.h (struct Lisp_Hash_Table.rehash_threshold): Change back to float, now that the other code rounds consistently. (DEFAULT_REHASH_THRESHOLD): Now float 0.8125 instead of double 0.8. --- doc/lispref/hash.texi | 5 +++-- doc/lispref/objects.texi | 2 +- etc/NEWS | 4 ++++ src/fns.c | 24 +++++++++++++----------- src/lisp.h | 6 +++--- 5 files changed, 24 insertions(+), 17 deletions(-) diff --git a/doc/lispref/hash.texi b/doc/lispref/hash.texi index 725d19c3bdc..4ba3258d189 100644 --- a/doc/lispref/hash.texi +++ b/doc/lispref/hash.texi @@ -144,8 +144,9 @@ The default value is 1.5. This specifies the criterion for when the hash table is full (so it should be made larger). The value, @var{threshold}, should be a positive floating-point number, no greater than 1. The hash table is -full whenever the actual number of entries exceeds this fraction -of the nominal size. The default for @var{threshold} is 0.8. +full whenever the actual number of entries exceeds the nominal size +multiplied by an approximation to this value. The default for +@var{threshold} is 0.8125. @end table @end defun diff --git a/doc/lispref/objects.texi b/doc/lispref/objects.texi index fbb66582f29..56049af60a1 100644 --- a/doc/lispref/objects.texi +++ b/doc/lispref/objects.texi @@ -1251,7 +1251,7 @@ and contents, like this: @example (make-hash-table) @result{} #s(hash-table size 65 test eql rehash-size 1.5 - rehash-threshold 0.8 data ()) + rehash-threshold 0.8125 data ()) @end example @noindent diff --git a/etc/NEWS b/etc/NEWS index 143e4655def..9355dff7a08 100644 --- a/etc/NEWS +++ b/etc/NEWS @@ -904,6 +904,10 @@ consistency with the new functions. For compatibility, 'sxhash' remains as an alias to 'sxhash-equal'. +++ +** 'make-hash-table' now defaults to a rehash threshold of 0.8125 +instead of 0.8, to avoid rounding glitches. + ++++ ** New function 'add-variable-watcher' can be used to call a function when a symbol's value is changed. This is used to implement the new debugger command 'debug-on-variable-change'. diff --git a/src/fns.c b/src/fns.c index 3fed92dfec1..2a6653144bc 100644 --- a/src/fns.c +++ b/src/fns.c @@ -3663,8 +3663,8 @@ allocate_hash_table (void) REHASH_SIZE. REHASH_THRESHOLD must be a float <= 1.0, and > 0. The table will - be resized when the ratio of (number of entries in the table) / - (table size) is >= REHASH_THRESHOLD. + 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'. @@ -3676,7 +3676,7 @@ allocate_hash_table (void) Lisp_Object make_hash_table (struct hash_table_test test, Lisp_Object size, Lisp_Object rehash_size, - double rehash_threshold, Lisp_Object weak, + float rehash_threshold, Lisp_Object weak, bool pure) { struct Lisp_Hash_Table *h; @@ -3690,13 +3690,14 @@ make_hash_table (struct hash_table_test test, eassert (INTEGERP (size) && XINT (size) >= 0); eassert ((INTEGERP (rehash_size) && XINT (rehash_size) > 0) || (FLOATP (rehash_size) && 1 < XFLOAT_DATA (rehash_size))); - eassert (0 < rehash_threshold && rehash_threshold <= 1.0); + eassert (0 < rehash_threshold && rehash_threshold <= 1); if (XFASTINT (size) == 0) size = make_number (1); sz = XFASTINT (size); - index_float = sz / rehash_threshold; + double threshold = rehash_threshold; + index_float = sz / threshold; index_size = (index_float < INDEX_SIZE_BOUND + 1 ? next_almost_prime (index_float) : INDEX_SIZE_BOUND + 1); @@ -3795,7 +3796,8 @@ maybe_resize_hash_table (struct Lisp_Hash_Table *h) else new_size = INDEX_SIZE_BOUND + 1; } - index_float = new_size / h->rehash_threshold; + double threshold = h->rehash_threshold; + index_float = new_size / threshold; index_size = (index_float < INDEX_SIZE_BOUND + 1 ? next_almost_prime (index_float) : INDEX_SIZE_BOUND + 1); @@ -4370,8 +4372,8 @@ amount. If it is a float, it must be > 1.0, and the new size is the old size multiplied by that factor. Default is 1.5. :rehash-threshold THRESHOLD -- THRESHOLD must a float > 0, and <= 1.0. -Resize the hash table when the ratio (number of entries / table size) -is greater than or equal to THRESHOLD. Default is 0.8. +Resize the hash table when the ratio (table entries / table size) +exceeds an approximation to THRESHOLD. Default is 0.8125. :weakness WEAK -- WEAK must be one of nil, t, `key', `value', `key-or-value', or `key-and-value'. If WEAK is not nil, the table @@ -4390,7 +4392,6 @@ usage: (make-hash-table &rest KEYWORD-ARGS) */) (ptrdiff_t nargs, Lisp_Object *args) { Lisp_Object test, size, rehash_size, weak; - double rehash_threshold; bool pure; struct hash_table_test testdesc; ptrdiff_t i; @@ -4445,8 +4446,9 @@ usage: (make-hash-table &rest KEYWORD-ARGS) */) /* Look for `:rehash-threshold THRESHOLD'. */ i = get_key_arg (QCrehash_threshold, nargs, args, used); - rehash_threshold = (!i ? DEFAULT_REHASH_THRESHOLD - : FLOATP (args[i]) ? XFLOAT_DATA (args[i]) : 0); + float rehash_threshold = (!i ? DEFAULT_REHASH_THRESHOLD + : !FLOATP (args[i]) ? 0 + : (float) XFLOAT_DATA (args[i])); if (! (0 < rehash_threshold && rehash_threshold <= 1)) signal_error ("Invalid hash table rehash threshold", args[i]); diff --git a/src/lisp.h b/src/lisp.h index be42b3354e2..6e0252621a6 100644 --- a/src/lisp.h +++ b/src/lisp.h @@ -2004,7 +2004,7 @@ struct Lisp_Hash_Table /* Resize hash table when number of entries / table size is >= this ratio. */ - double rehash_threshold; + float rehash_threshold; /* Vector of keys and values. The key of item I is found at index 2 * I, the value is found at index 2 * I + 1. @@ -2088,7 +2088,7 @@ enum DEFAULT_HASH_SIZE { DEFAULT_HASH_SIZE = 65 }; value gives the ratio of current entries in the hash table and the size of the hash table. */ -static double const DEFAULT_REHASH_THRESHOLD = 0.8; +static float const DEFAULT_REHASH_THRESHOLD = 0.8125; /* Default factor by which to increase the size of a hash table. */ @@ -3363,7 +3363,7 @@ EMACS_UINT hash_string (char const *, ptrdiff_t); EMACS_UINT sxhash (Lisp_Object, int); Lisp_Object make_hash_table (struct hash_table_test test, Lisp_Object size, Lisp_Object rehash_size, - double rehash_threshold, Lisp_Object weak, + float rehash_threshold, Lisp_Object weak, bool pure); ptrdiff_t hash_lookup (struct Lisp_Hash_Table *, Lisp_Object, EMACS_UINT *); ptrdiff_t hash_put (struct Lisp_Hash_Table *, Lisp_Object, Lisp_Object, -- 2.11.4.GIT