| blob | 715d2e61ecb6d4fad96de280935d5e9e4a4635a8 |
1 ;;;; that part of the implementation of HASH-TABLE which lives solely
2 ;;;; on the target system, not on the cross-compilation host
4 ;;;; This software is part of the SBCL system. See the README file for
5 ;;;; more information.
6 ;;;;
7 ;;;; This software is derived from the CMU CL system, which was
8 ;;;; written at Carnegie Mellon University and released into the
9 ;;;; public domain. The software is in the public domain and is
10 ;;;; provided with absolutely no warranty. See the COPYING and CREDITS
11 ;;;; files for more information.
14 \f
18 ;;;; utilities
20 ;;;; TODOs:
21 ;;;; - change recursive locks to nonrecursive.
22 ;;;; This will, I fear, be impossible because we've exposed and documented
23 ;;;; an API that pretty much tells users that it's ok to create a synchronized
24 ;;;; table while *also* wrapping any random operation in the table lock.
25 ;;;; Hence recursion on the lock. (commit b9a1b17b079d315c)
26 ;;;; - place the 3 or 4 vectors in a separate structure that can be atomically
27 ;;;; swapped out for a new instance with new vectors. Remove array bounds
28 ;;;; checking since all the arrays will be tied together.
29 ;;;; - As a consequence of change 3bdd4d28ed, the compiler started to
30 ;;;; emit multiple definitions of certain INLINE global functions.
31 ;;;; Just referencing #'INLINED-FOO can cause genesis failures.
33 ;;; T if and only if table has non-null weakness kind.
38 ;;; Value of :synchronized constructor argument.
43 ;;; Keep in sync with weak_ht_alivep_funs[] in gc-common
46 ;; The bits of 'weakness' are interpreted as follows:
47 ;; bit 0 : live key forces value to be live
48 ;; bit 1 : live value forces key to be live
49 ;; both : either forces the other to be live
50 ;; :KEY-AND-VALUE has two zero bits, as neither object livens the other
53 ;;; Non-NIL if this is some kind of weak hash table. For details see
54 ;;; the docstring of MAKE-HASH-TABLE.
56 "Return the WEAKNESS of HASH-TABLE which is one of NIL, :KEY,
57 :VALUE, :KEY-AND-VALUE, :KEY-OR-VALUE."
61 ;;; On 32-bit machines, the hashes are positive fixnums, but on
62 ;;; 64-bit, we use 2 more bits though must avoid conflict with
63 ;;; +MAGIC-HASH-VECTOR-VALUE+, which denotes an address-based hash in
64 ;;; HASH-TABLE-HASH-VECTOR.
75 ;;; We're using power of two tables which obviously are very sensitive
76 ;;; to the entropy in the low bits in the hash value. We used to
77 ;;; indiscriminately apply PREFUZZ-HASH to the hash value returned by
78 ;;; the real hash function to mix in the high bits. This was
79 ;;; unnecessary and wasteful, so now we only CLIP-HASH. Still, let's
80 ;;; keep this function around for a while in case we find that some
81 ;;; hash functions (e.g. user provided ones) need it.
88 \f
90 ;;; EQ hash functions
92 ;;; Define an inline function called NAME, which takes a single KEY
93 ;;; argument and returns 1. its CLIPPED-HASH and 2. whether the hash
94 ;;; is address-based. This requires a call to CLIP-HASH, which may be
95 ;;; unnecessary if the hash is then masked (e.g. to (1- N-BUCKETS))
96 ;;; anyway.
97 ;;;
98 ;;; For this reason, another function called NAME* is defined, which
99 ;;; does not clip the hash and may even return a bignum.
107 ;; It would be ok to pick off SYMBOL here and use its hash
108 ;; slot as far as semantics are concerned, but EQ-hash is
109 ;; supposed to be the lightest-weight in terms of speed, so
110 ;; I'm letting everything use address-based hashing, unlike
111 ;; the other standard hash-table hash functions which try use
112 ;; the hash slot of certain objects. Note also that as we add
113 ;; logic into the EQ-HASH function to decide whether the hash
114 ;; is address-based, we either have to replicate that logic
115 ;; into rehashing, or else actually call EQ-HASH to decide
116 ;; for us. -- DK, 2019-06-22
117 ;;
118 ;; Use GET-LISP-OBJ-ADDRESS instead of POINTER-HASH so that
119 ;; BODY can work with an unboxed word and perhaps be a bit
120 ;; faster as a result. Also, we get a bit tighter code with a
121 ;; symbol macrolet compared to binding HASH to
122 ;; (GET-LISP-OBJ-ADDRESS KEY).
132 ;;; This is equivalent to the old way of calling PREFUZZ-HASH on
133 ;;; POINTER-HASH because HASH from GET-LISP-OBJ-ADDRESS is shifted
134 ;;; here an extra SB-VM:N-FIXNUM-TAG-BITS.
141 \f
144 eql-hash equal-hash equalp-hash))
146 ;;; Note: We could somewhat easily add SAP-WIDETAG into the list of types
147 ;;; that get a stable hash for EQL tables (via SAP-HASH), however:
148 ;;; - we don't compare SAPs with SAP= when the table's test is EQL,
149 ;;; so there is no real advantage (nor requirement) to have a hash
150 ;;; derived from the object's contents.
151 ;;; - I don't imagine that users often store SAPs in hash-tables.
156 key
157 ;; SYMBOL is listed here so that we can hash symbols address-insensitively.
158 ;; We have to pick off a bunch of OTHER-POINTER objects anyway, so there
159 ;; no overhead to extending the widetag range by 1 widetag.
161 sb-vm:single-float-widetag
163 sb-vm:complex-double-float-widetag
165 ;; NON-NULL-SYMBOL-P skips a test for NIL which is sensible, and we're
166 ;; excluding NIL anyway because it's not an OTHER-POINTER.
167 ;; To produce the best code for NON-NULL-SYMBOL-P (omitting a lowtag test)
168 ;; we need to force the compiler to see that KEY is definitely an
169 ;; OTHER-POINTER (cf OTHER-POINTER-TN-REF-P) because %OTHER-POINTER-SUBTYPE-P
170 ;; doesn't suffice, though it would be nice if it did.
175 key))
178 nil)
179 ;; Consider picking off %INSTANCEP too before using EQ-HASH ?
182 ;;; Decide if WIDETAG (an OTHER-POINTER) should use SXHASH in EQUAL-HASH
205 ;;; As a consequence of change 3bdd4d28ed, the compiler started to emit multiple
206 ;;; definitions of certain INLINE global functions.
207 ;;; Genesis is so fraught with other pitfalls and traps that I want no chance
208 ;;; of seeing duplicate definitions. So no INLINE here. Tail wagging the dog?
209 ;;; Perhaps, but that was an dangerous thing to sneakily allow.
210 ;; (declaim (inline equal-hash))
213 ;; Ultimately we just need to choose between SXHASH or EQ-HASH. As to using
214 ;; INSTANCE-SXHASH, it doesn't matter, and in fact it's quicker to use EQ-HASH.
215 ;; If the outermost object passed as a key is LIST, then it descends using SXHASH,
216 ;; you will in fact get stable hashes for nested objects.
219 ;; pathnames require SXHASH, all other instances are indifferent.
232 ;; Types requiring special treatment. Note that PATHNAME and
233 ;; HASH-TABLE are caught by the STRUCTURE-OBJECT test.
237 ;; INSTANCE at this point means STANDARD-OBJECT and CONDITION,
238 ;; since STRUCTURE-OBJECT is recursed into by PSXHASH.
242 \f
243 ;;;; user-defined hash table tests
251 name))
264 name)
267 "Defines NAME as a new kind of hash table test for use with the :TEST
268 argument to MAKE-HASH-TABLE, and associates a default HASH-FUNCTION with it.
270 NAME must be a symbol naming a global two argument equivalence predicate.
271 Afterwards both 'NAME and #'NAME can be used with :TEST argument. In both
272 cases HASH-TABLE-TEST will return the symbol NAME.
274 HASH-FUNCTION must be a symbol naming a global hash function consistent with
275 the predicate, or be a LAMBDA form implementing one in the current lexical
276 environment. The hash function must compute the same hash code for any two
277 objects for which NAME returns true, and subsequent calls with already hashed
278 objects must always return the same hash code.
280 Note: The :HASH-FUNCTION keyword argument to MAKE-HASH-TABLE can be used to
281 override the specified default hash-function.
283 Attempting to define NAME in a locked package as hash-table test causes a
284 package lock violation.
286 Examples:
288 ;;; 1.
290 ;; We want to use objects of type FOO as keys (by their
291 ;; names.) EQUALP would work, but would make the names
292 ;; case-insensitive -- which we don't want.
293 (defstruct foo (name nil :type (or null string)))
295 ;; Define an equivalence test function and a hash function.
296 (defun foo-name= (f1 f2) (equal (foo-name f1) (foo-name f2)))
297 (defun sxhash-foo-name (f) (sxhash (foo-name f)))
299 (define-hash-table-test foo-name= sxhash-foo-name)
301 ;; #'foo-name would work too.
302 (defun make-foo-table () (make-hash-table :test 'foo-name=))
304 ;;; 2.
306 (defun == (x y) (= x y))
308 (define-hash-table-test ==
309 (lambda (x)
310 ;; Hash codes must be consistent with test, so
311 ;; not (SXHASH X), since
312 ;; (= 1 1.0) => T
313 ;; (= (SXHASH 1) (SXHASH 1.0)) => NIL
314 ;; Note: this doesn't deal with complex numbers or
315 ;; bignums too large to represent as double floats.
316 (sxhash (coerce x 'double-float))))
318 ;; #'== would work too
319 (defun make-number-table () (make-hash-table :test '==))
320 "
330 \f
331 ;;;; construction and simple accessors
333 ;;; The smallest table holds 7 items distributed among 8 buckets. So
334 ;;; we allocate 7 k/v pairs = 14 cells + 3 overhead = 17 cells, and at
335 ;;; maximum load the table will have a load factor of 87.5%
338 ;;; This constant is referenced via its name in cold load, so it needs to
339 ;;; be evaluable in the host.
342 ;; The GC will set this to 1 if it moves an address-sensitive key. This used
343 ;; to be signaled by a bit in the header of the kv vector, but that
344 ;; implementation caused some concurrency issues when we stopped
345 ;; inhibiting GC during hash-table lookup.
346 ;;
347 ;; This indicator properly belongs to the k/v vector for at least 2 reasons:
348 ;; - if the vector is on an already-written page but the table is not,
349 ;; it avoids a write fault when setting to true. This a boon to gencgc
350 ;; - if there were lock-free tables - which presumably operate by atomically
351 ;; changing out the vector for a new one - whether the vector is bucketized
352 ;; correctly after GC is an aspect of the vector, not the table
353 ;;
354 ;; We could do it with a single bit by implementing vops for atomic
355 ;; read/modify/write on the header. In C there's sync_or_and_fetch, etc.
360 ;;; The 'supplement' points to the hash-table if the table is weak,
361 ;;; or to the hash vector if the table is not weak.
362 ;;; Other possible values are NIL for an EQ table, or T for an EQL table.
363 ;;; For a concurrent GC, this element will not require a read barrier because
364 ;;; it must be treated as a strong reference even if the vector is weak.
372 ;;; Make a new key/value vector. Weak tables do not mark the vector as weak
373 ;;; initially, because the vector can't hold a backpointer to the table
374 ;;; since the table hasn't been made yet. (GC asserts that every weak hash-table
375 ;;; storage vector has a table pointer - no exceptions)
376 ;;; Also we can't set the HASHING bit in the header until the vector is prepared,
377 ;;; but if GC occurs meanwhile, it must not move this to a purely boxed page.
378 ;;; But we can set the ALLOC-MIXED bit. That's what it's there for.
386 nwords nwords))))
391 ;; If GC observes VECTOR-HASHING-FLAG, it needs to see a valid value
392 ;; in the 'supplement' slot. Neither 0 nor +empty-ht-slot+ is valid.
393 ;; And if we ever get non-prezeroed-memory to work, this will be even more
394 ;; important to do things in the right order.
397 v))
410 ;;; I don't want to change peoples' assumptions about what operations are threadsafe
411 ;;; on a weak table that was not created as expressly synchronized, so we continue to
412 ;;; create nearly all weak tables as synchronized. With such tables, lock acquisition
413 ;;; might be recursive, because we also told users that they can use
414 ;;; SB-EXT:WITH-LOCKED-HASH-TABLE even with tables that are self-locking.
415 ;;; This results in a really strange design in which it is exceptionally difficult
416 ;;; to plug in standard POSIX mutexes which do not default to being recursive.
417 ;;; To slightly mitigate the problem of assuming all mutexes should be recursive,
418 ;;; some of the system weak hash-table are frobbed to turn off SYNCHRONIZED.
419 ;;; Maybe I can figure out how to make concurrent weak GETHASH threadsafe,
420 ;;; but I've spent a bit of time on it and it is quite difficult.
423 %make-hash-table))
432 "Create and return a new hash table. The keywords are as follows:
434 :TEST
435 Determines how keys are compared. Must a designator for one of the
436 standard hash table tests, or a hash table test defined using
437 SB-EXT:DEFINE-HASH-TABLE-TEST. Additionally, when an explicit
438 HASH-FUNCTION is provided (see below), any two argument equivalence
439 predicate can be used as the TEST.
441 :SIZE
442 A hint as to how many elements will be put in this hash table.
444 :REHASH-SIZE
445 Indicates how to expand the table when it fills up. If an integer, add
446 space for that many elements. If a floating point number (which must be
447 greater than 1.0), multiply the size by that amount.
449 :REHASH-THRESHOLD
450 Indicates how dense the table can become before forcing a rehash. Can be
451 any positive number <=1, with density approaching zero as the threshold
452 approaches 0. Density 1 means an average of one entry per bucket.
454 :HASH-FUNCTION
455 If unsupplied, a hash function based on the TEST argument is used,
456 which then must be one of the standardized hash table test functions, or
457 one for which a default hash function has been defined using
458 SB-EXT:DEFINE-HASH-TABLE-TEST. If HASH-FUNCTION is specified, the TEST
459 argument can be any two argument predicate consistent with it. The
460 HASH-FUNCTION is expected to return a non-negative fixnum hash code.
461 If TEST is neither standard nor defined by DEFINE-HASH-TABLE-TEST,
462 then the HASH-FUNCTION must be specified.
464 :WEAKNESS
465 When :WEAKNESS is not NIL, garbage collection may remove entries from the
466 hash table. The value of :WEAKNESS specifies how the presence of a key or
467 value in the hash table preserves their entries from garbage collection.
469 Valid values are:
471 :KEY means that the key of an entry must be live to guarantee that the
472 entry is preserved.
474 :VALUE means that the value of an entry must be live to guarantee that
475 the entry is preserved.
477 :KEY-AND-VALUE means that both the key and the value must be live to
478 guarantee that the entry is preserved.
480 :KEY-OR-VALUE means that either the key or the value must be live to
481 guarantee that the entry is preserved.
483 NIL (the default) means that entries are always preserved.
485 :SYNCHRONIZED
486 If NIL (the default), the hash-table may have multiple concurrent readers,
487 but results are undefined if a thread writes to the hash-table
488 concurrently with another reader or writer. If T, all concurrent accesses
489 are safe, but note that CLHS 3.6 (Traversal Rules and Side Effects)
490 remains in force. See also: SB-EXT:WITH-LOCKED-HASH-TABLE."
506 name
507 fun)))
517 ;; It is permitted to specify a custom hash function with any of the standard predicates.
518 ;; This forces use of the generalized table methods.
522 ;; Our table sizes are capped by the 32-bit integers used as indices
523 ;; into the chains. Prevent our code from failing if the user specified
524 ;; most-positive-fixnum here. (fndb says that size is 'unsigned-byte')
527 rehash-size
531 (%make-hash-table
532 ;; compute flags. The stored KIND bits don't matter for a user-supplied hash
533 ;; and/or test fun, however we don't want to imply that it is an EQ table
534 ;; because EQ tables don't get a hash-vector allocated.
544 test test-fun hash-fun
545 size rehash-size rehash-threshold))))
550 a))
564 ;; KLUDGE: The most natural way of expressing the below is
565 ;; (round (/ (float size) rehash-threshold)), and indeed
566 ;; it was expressed like that until 0.7.0. However,
567 ;; MAKE-HASH-TABLE is called very early in cold-init, and
568 ;; the SPARC has no primitive instructions for rounding,
569 ;; but only for truncating; therefore, we fudge this issue
570 ;; a little. The other uses of truncate, below, similarly
571 ;; used to be round. -- CSR, 2002-10-01
572 ;;
573 ;; Note that this has not yet been audited for
574 ;; correctness. It just seems to work. -- CSR, 2002-11-02
579 ;; Non-weak tables created with no options other than :TEST
580 ;; are allocated at 0 size. Weak tables are complicated enough,
581 ;; so just do their usual thing.
589 ;; Needs to be the half the length of the KV vector to link
590 ;; KV entries - mapped to indices at 2i and 2i+1 -
591 ;; together.
592 ;; We don't need this to be initially 0-filled, so don't specify
593 ;; an initial element (in case we ever meaningfully distinguish
594 ;; between don't-care and 0-fill)
598 ;; For testing, preload huge values for all 'next' elements
599 ;; so that we generate an error if any is inadvertently read
600 ;; above the high-water-mark for the k/v vector.
604 ;; same here - don't care about initial contents
616 flags getter setter remover #'clrhash-impl
617 test test-fun hash-fun
618 rehash-size rehash-threshold
619 kv-vector index-vector next-vector hash-vector)))
621 ;; The trailing metadata element is either the table itself or the hash-vector
622 ;; depending on weakness. Non-weak hashing vectors can be GCed without looking
623 ;; at the table. Weak hashing vectors need the table.
624 ;; As a special-case, non-weak tables with EQL hashing put T in this slot.
625 ;; GC can't get the table kind since it doesn't have access to the table.
627 ;; Stash the desired size for the first time the vectors are grown.
629 ;; Cause the overflow logic to be invoked on the first insert.
634 table
641 table))
643 ;;; a "plain" hash-table has nothing fancy: default size, default growth rate,
644 ;;; not weak, not synchronized, not a user-defined hash fun and/or comparator.
653 test test-fun hash-fun
655 #.default-rehash-size
658 ;;; We don't expose HASH-TABLE-%COUNT directly because it is SETFable.
660 "Return the number of entries in the given HASH-TABLE."
679 "Return a size that can be used with MAKE-HASH-TABLE to create a hash
680 table that can hold however many entries HASH-TABLE can hold without
681 having to be grown."
690 ;;; Called when we detect circular chains in a hash-table.
693 multiple threads accessing the same hash-table without locking."
694 hash-table))
696 \f
697 ;;;; accessing functions
699 ;;; Clear rehash bit and bump the rolling count, wrapping around to keep it a fixnum.
700 ;;; need-to-rehash is indicated by a stamp of #b______01 ; INITIAL-STAMP
701 ;;; which is changed during rehash to #b______10 ; REHASHING-STAMP
702 ;;; rolling count --------^^^^^^ (some number of bits)
706 ;; new stamp has the "count" field bumped up by 1, and the low 2 bits are 0.
709 ;; Assigning new stamp races with GC which might set the 'rehash' (low) bit again.
710 ;; At most one more attempt is needed since no other state change can occur -
711 ;; we don't need to keep trying to achieve a state in which 'rehash' is clear.
716 ;; Bump the count field, but leave the least-significant bit on.
719 ;;; Rehash in one of two scenarios:
720 ;;; - up-sizing a table, be it weak or not
721 ;;; - rehashing a weak table due to key movement
722 ;;; Absent is the case of rehashing a non-weak table due to key movement.
723 ;;; That is special-cased in %REHASH-AND-FIND which does both at once as its name implies.
724 ;;; Note that this will never be called on a KV-VECTOR with the weakness bit set.
725 ;;; Therefore we can use SVREF in lieu of WEAK-KVV-REF for weak tables.
740 ;; If KEY-VAR is empty, then push I onto the freelist, otherwise invoke BODY
746 ;; Cases ordered for performance.
750 ;; Scan backwards so that chains are in ascending index order.
769 ;; Use the existing hash value (not
770 ;; address-based hash).
771 stored-hash
774 ;; This is identical to the calculation of next-free-kv in INSERT-AT.
775 ;;
776 ;; Note that when called from GROW-HASH-TABLE, there are no empty
777 ;; slots below HWM, so testing for them in WITH-KEY is a waste, but
778 ;; it's an almost immeasurably small one. -- MG, 2024-01-26
783 ;;; Rehash due to key movement, and find KEY at the same time.
784 ;;; Finding the key obviates the need for the rehashing thread to loop
785 ;;; testing whether to rehash. Imagine an unlucky schedule wherein each rehash
786 ;;; ends up invalid due to maximally bad timing of GC, and every reader sees
787 ;;; nothing but 'need-to-rehash', and the INDEX vector is repeatedly overwritten
788 ;;; with zeros. The -AND-FIND aspect of this ensures progress.
796 ;; Verify some invariants prior to disabling array bounds checking
798 kv-pairs-overhead-slots)))
802 ;; Empty cells must be in the free chain already, and no smashed cells exist.
805 ;; Must not permit the rehashing state to stick due to a nonlocal exit.
806 ;; All further normal use of the table would be prevented.
808 ;; Transitioning from #b01 to #b10 clears the 'rehash' bit and sets the
809 ;; rehash-in-progress bit. It also gives this thread exclusive write access
810 ;; to the bucket chains since at most one thread can win this CAS.
812 ;; Rehash in place. For the duration of the rehash, readers who otherwise
813 ;; might have seen intact chains (by which to find address-insensitive keys)
814 ;; can't. No big deal. If we were willing to cons new vectors, we could
815 ;; rehash into them and CAS them in, but the advantage would be minimal-
816 ;; obsolete chains could only work for a possibly-empty subset of keys.
817 ;; Leave the free cell chain untouched, since rehashing
818 ;; due to key movement can not possibly affect that chain.
825 ;; Process body only if KEY-VAR is nonempty, and also look
826 ;; for a probed key that is EQ to KEY.
841 stored-hash
852 ;; No hash vector and not an EQL table, so it's an EQ table
862 result))))
866 ;; Compute new vector lengths for the table, extending the table based on the
867 ;; rehash-size.
872 ;; This is the more common case by far, and we take some
873 ;; pains to tell TRUNCATE that the result fits in a
874 ;; fixnum.
876 ;; These magic constants are (FLOAT (ASH 1
877 ;; +MAX-HASH-TABLE-BITS+)).
883 ;; Ensure that the size grows, e.g. for
884 ;; (TRUNCATE (* 14 1.01)) => 14.
889 ;; If the default rehash-size was employed, let's try to keep the
890 ;; load factor (LF) within a reasonable band. Otherwise don't bother.
891 ;; The motivation for this decision is twofold:
892 ;; - if using defaults, it would be ideal to attempt to be nominally
893 ;; conscientious of the 1.5x resize amount.
894 ;; - we can't really accommodate arbitrary resize amounts, especially if small.
895 ;; (power-of-2 sizing can't do that- doubling is the only possibility)
896 ;; But we can produce the smallest table consistent with the request.
897 ;; Say e.g. REHASH-SIZE was 2 using the default initial size of 14.
898 ;; Resizing computes 16 k/v pairs which coincides exactly with
899 ;; 16 buckets (the nearest power of 2). But if we wish to avoid 100% load,
900 ;; what can we do? Re-double the bin count to 32? Decrease the k/v pair count
901 ;; to 15? Clearly neither of those make sense if the user is trying to say
902 ;; that (s)he wants 2 entries more which means "don't increase by a lot".
903 ;; Changing from 8 buckets (at the old size) to 32 buckets is a lot,
904 ;; so why do that? Conversely, it makes no sense to reduce the k/v pair
905 ;; limit just to keep the LF less than 100%. A similar problem occurs
906 ;; if you specify 1.001 or other float near 1.
907 ;; Anyway, chaining supports load factors in excess of 100%
912 ;; If we're going to decrease the size, make sure we definitely
913 ;; don't decrease below the old size.
917 pow2ceil)))
920 ;;; Cache the expensive computation of RECOMPUTE-HT-VECTOR-SIZES for
921 ;;; when REHASH-SIZE is the default.
928 #-sb-xc-host
929 (!cold-init-forms
938 v)))
953 ;;; Enlarge TABLE. If it is weak, then both the old and new vectors are temporarily
954 ;;; made non-weak so that we don't have to deal with GC-related shenanigans.
961 ;; Return KV-VECTOR NEXT-VECTOR HASH-VECTOR INDEX-VECTOR)
964 ;; for robustness testing, as explained in %MAKE-HASH-TABLE
969 ;; When the index vector is not
970 ;; growing and hashes are valid,
971 ;; rehashing _may_ not be necessary.
974 old-index-vector
979 #+system-tlabs
980 ;; If allocation was directed off the main heap when this table was made, then we assume
981 ;; that reallocation will allocate off the heap. If the old table is in dynamic space,
982 ;; then the new storage should be forced to dynamic space even if the user TLAB currently
983 ;; points outside of dynamic space.
984 ;; The reason for looking at TABLE here and not its storage, is that MAKE-HASH-TABLE can
985 ;; install a k/v pair vector that does not inform us where the table is:
986 ;; * (heap-allocated-p (sb-impl::hash-table-pairs (make-hash-table))) => :READ-ONLY
987 ;; The read-only vector is an optimization reducing the size of never-used tables
988 ;; down to the absolute minimum.
993 ;; CACHE holds the desired initial size. Read it and then set it to a bogusly high value
1018 ;; Rehash + resize only occurs when:
1019 ;; (1) every usable pair was at some point filled (so HWM = SIZE)
1020 ;; (2) no cells below HWM are available (so COUNT = SIZE)
1023 ;; If the table is not weak, then every cell pair has to be in use
1024 ;; as a precondition to resizing. If weak, this might not be true.
1027 ;; Copy over the hash-vector,
1028 ;; This is done early because when GC scans the new vector, it needs to see
1029 ;; each hash to know which keys were hashed address-sensitively.
1034 ;; The high-water-mark remains unchanged.
1035 ;; Set this before copying pairs, otherwise they would not be seen
1036 ;; in the new vector since GC scanning ignores elements below the HWM.
1038 ;; Reference the hash-vector from the KV vector.
1039 ;; Normally a weak hash-table's KV vector would reference the table
1040 ;; (because cull needs to examine the table bucket-by-bucket), and
1041 ;; not the hash-vector directly. But we can't reference the table
1042 ;; since using the table's hash-vector gets the OLD hash vector.
1043 ;; It might be OK to point the table at the new hash-vector now,
1044 ;; but I'd rather the table remain in a consistent state, in case we
1045 ;; ever devise a way to allow concurrent reads with a single writer,
1046 ;; for example.
1050 ;; Here and also in FINDHASH-WEAK, we keep the
1051 ;; SB-VM:VECTOR-ADDR-HASHING-FLAG. If a hash table is
1052 ;; address-based at any time, it'll remain so until CLRHASH even
1053 ;; if all address-based keys had been removed. This allows
1054 ;; rehashing to do less work and makes EQ hash tables a few
1055 ;; percents faster. In the rare case where the flag errs on the
1056 ;; side of conservativeness, the GC needs to do a bit more work.
1057 ;; If this ever becomes a problem, maybe the GC can detect this
1058 ;; and clear the flag. -- MG, 2023-10-13
1062 ;; Copy the k/v pairs excluding leading and trailing metadata.
1066 ;; If the index hasn't grown, try to avoid rehashing.
1071 ;; We know from REALLOC that the hashes were valid and no
1072 ;; rehashing was in progress, but a GC that happened before
1073 ;; REPLACE above might have marked only OLD-KV-VECTOR (and not
1074 ;; NEW-KV-VECTOR) as needs-rehash, in which case we must do a
1075 ;; normal rehash after all. Note that looking at the low two
1076 ;; bits of the stamp is not enough here because they could
1077 ;; have been cleared already in another thread.
1082 ;; Preserve only the 'hashing' bit on the OLD-KV-VECTOR so that
1083 ;; its high-water-mark can meaningfully be reduced to 0 when done.
1084 ;; Clearing the address-sensitivity is a performance improvement
1085 ;; since GC won't check on a per-key basis whether to flag the vector
1086 ;; for rehash (it's going to be zeroed out).
1087 ;; Clearing the weakness causes all entries to stay alive.
1088 ;; Furthermore, clearing both makes the trailing metadata ignorable.
1095 old-next-free
1099 new-index-vector new-next-vector table)))))
1108 ;; Now that the table points to the right hash-vector
1109 ;; we can set the vector's backpointer and turn it weak.
1113 ;; Zero-fill the old kv-vector. For weak hash-tables this removes the
1114 ;; strong references to each k/v. For non-weak vectors there is no technical
1115 ;; reason to do this except for safety. GC will not scavenge past the high water
1116 ;; mark, but if you had your hands on the old vector and decide to dereference
1117 ;; it (which is probably indicates a data race), you could deference a dangling
1118 ;; pointer. In other words, even if the vector were considered a root,
1119 ;; it wouldn't matter from a heap consistency perspective because it would
1120 ;; not transitively enliven anything, but you can't stop people from using
1121 ;; SVREF on it past the high water mark. To to make things safe,
1122 ;; we sort of have to zero-fill.
1123 ;; Also fwiw, it would be necessary to fix verify_range() to understand
1124 ;; that it MUST NOT verify past the hwm, and similary the low-level debugger
1125 ;; if we didn't zero-fill.
1126 ;; Or, if we could trust people not to look at the old vector, we could just
1127 ;; change the widetag into simple-array-word instead of scribbling over it.
1130 next-free))))
1133 "Finds the entry in HASH-TABLE whose key is KEY and returns the
1134 associated value and T as multiple values, or returns DEFAULT and NIL
1135 if there is no such entry. Entries can be added using SETF."
1140 ;;; Define a specialized variation of GETHASH3 for a standard test fun,
1141 ;;; or the general case.
1142 ;;; A note about in the inner loop: the secondary value of the hash function
1143 ;;; indicates whether an address was taken, which implies that we should use EQ
1144 ;;; as the comparator, but it is not an "if and only if" - other objects can be
1145 ;;; compared by EQ, for example symbols and fixnums.
1147 ;;; The code below could be further tweaked by doing a few things:
1148 ;;; - removing the probing limit check
1149 ;;; - skipping array bounds checks
1150 ;;; - eliminating some multiply-by-2 operations
1151 ;;; The first two are easy enough. The last means that we would
1152 ;;; rejigger the INDEX + NEXT vectors to contain physical elt indices.
1153 ;;; We could define safe and unsafe variants of each getter, and an "unsafe"
1154 ;;; variant of MAKE-HASH-TABLE that installs the unsafe getter.
1155 ;;; A source transform would select the variant of MAKE-HASH-TABLE by policy.
1158 ;; macroexpander helper functions. These rely on a naming convention
1159 ;; to keep things simple so that we don't have to pass in the names
1160 ;; of local variables to bind. (Being unhygienic on purpose)
1165 ;; so many warnings about generic SXHASH - who cares
1174 ;; BUCKET is the masked hash code which acts as the index into index-vector
1176 ;; INDEX is the index into the pairs vector obtained from the index-vector
1179 ;; Binding of HASH-VECTOR would be flushed for EQ and EQL tables
1180 ;; automatically, but we forcibly elide some code because "reasons"
1181 ;; so we need to avoid "unused variable warnings" by eliding this
1182 ;; binding as well.
1196 ;; EQL vs EQ only matters for numbers which aren't immediate.
1197 ;; Not worth the trouble to get single-float in here for 64-bit.
1200 ;; EQUAL and EQUALP hash function say that symbols are NOT address-sensitive
1201 ;; - which they aren't, as they use the SYMBOL-HASH slot, unlike EQ-HASH
1202 ;; which takes the address - but we want to compare symbols by EQ.
1203 ;; As to NON-NULL-SYMBOL, it's just slightly quicker than also testing for NIL,
1204 ;; because it's not an important case and SYMBOLP uses more instructions.
1205 ;; This is similar in philosophy to the EQL branch where I don't care whether
1206 ;; single float (on 64-bit) is or isn't compared by EQ.
1207 ;; A more thorough test of whether EQUALP strength-reduces to EQ
1208 ;; would be something like
1209 ;; (or (fixnump key)
1210 ;; (not (typep key '(or cons string pathname bit-vector number)))))
1211 ;; but it's unclear to me whether we should spend time up front deciding
1212 ;; to reduce everything to EQ that could be reduced. The test here
1213 ;; is about half as much code as the (not (typep ...)) expression.
1214 ;; There is diminishing payoff from listing other types.
1219 ;; Pathnames are descended into by EQUAL.
1226 ;; Structures incl. PATHNAME and HASH-TABLE are descended into.
1230 ;; If the hash-function is nonstandard, it's nonetheless possible
1231 ;; to use EQ as the comparator.
1234 ;; Keyword args:
1235 ;; - ENDP-TEST when true says that the probing loop is unrolled, and a test
1236 ;; for the end of the chain is ORed into the key comparison.
1237 ;; At worst, we compare the key against the value 0 (in the 0th element
1238 ;; of the k/v vector) which is just a dummy value, since filled indices
1239 ;; begin at 1.
1240 ;; - HASH-TEST when :STRICT (the default) says that for tables with hash vectors,
1241 ;; we can use the computed hash as a guard before calling the predicate,
1242 ;; and (AREF HASH-VECTOR i) is definitely not +MAGIC-HASH-VECTOR-VALUE+
1243 ;; in that case.
1244 ;; If HASH-TEST is :PERMISSIVE, then the stored value might be the magic
1245 ;; value which is considered a match to anything.
1246 ;;
1247 ;; GETHASH and PUTHASH always know whether to look in HASH-VECTOR or not,
1248 ;; because for any given key, either it does or does not have an address-based
1249 ;; hash. The probing loop is unswitched on that grounds. If the hash isn't an
1250 ;; address, then we compare hashes before calling a predicate. If the hash is
1251 ;; an address, then we devolve to EQ in the loop, and never compare hashes.
1252 ;; Hence, unswitching should result in a performance gain for EQUAL and EQUALP
1253 ;; that become like EQ, as well as eliding any expensive predicate call where
1254 ;; the result would be NIL.
1255 ;;
1256 ;; The :PERMISSIVE hash check is needed in REMHASH, which performs one
1257 ;; key comparison prior to unswitching the remainder of the probing loop.
1258 ;; This is due to the first entry in a chain needing to be handled separately.
1259 ;; Consider it like destructively deleting the initial cons in a list - RPLACD
1260 ;; can't do that operation. So the first comparison might be on a key whose
1261 ;; stored hash is +MAGIC-HASH-VECTOR-VALUE+. Just ignore that stored hash.
1262 ;;
1263 ;; Also, a minor exception to the above: EQL tables don't compare hashes
1264 ;; because no performance gain is obtained. The hash vector exists solely
1265 ;; to inform GC whether each key was hashed address-sensitively.
1268 ;; STD-FN = NIL says that's definitely a user-defined hash function,
1269 ;; and * says that it could be either standard or user-defined.
1275 is-same-hash
1279 ;; We do not give users a way to have some keys be address-sensitive
1280 ;; when they define their own hash function. Therefore, _any_ user-defined
1281 ;; table has a hash-vector, even if comparison is done by EQ.
1282 ;; (You might want EQ comparison on "intelligent" hashes as opposed
1283 ;; to "opaque" hashes like an address or stable randomly-assigned value.)
1284 ;; Moreover, every hash-value in the vector is something other than
1285 ;; +MAGIC-HASH-VECTOR-VALUE+, because nothing is address-based.
1286 ;; The nuance of address-based versus EQ-based is subtle,
1287 ;; but hopefully the variable naming in the code is clear enough now.
1289 ((*)
1294 ;; Use the inline EQL function
1301 ;; For standard general predicates, compare the key before checking
1302 ;; whether probing must terminate (index = 0). For user predicates
1303 ;; that might accept only strings, for example, check index first.
1304 ;; This way, a hit on the first probe avoids one test for standard
1305 ;; tests. Index is post-checked to deem it a hit or miss.
1309 ;;; CAUTION: I think this macro could falsely signal a corrupt chain.
1310 ;;; Consider what would happen if there is a reader (started first),
1311 ;;; and a rehasher. The reader didn't rehash, because if it thought it needed to,
1312 ;;; it would have. But as it's reading, a GC can occur, setting need-to-rehash.
1313 ;;; Then another reader comes along, seeing the flag, so it modifies the chains
1314 ;;; just as the first reader is following 'next' pointers.
1315 ;;; Could this cause the first reader to probe too much? Maybe.
1316 ;;; I think we should terminate probing after a number of tries determined
1317 ;;; by the length of the longest chain, which we can track in PUTHASH.
1318 ;;; If not found, examine the rehash-stamp and maybe restart.
1319 ;;; But don't draw an inference that the chains are bad.
1328 #|
1331 plus a single-bit spinlock protecting the counter from multiple writers.
1332 As the comments in frlock file explain, it is not required to have a
1334 the writer bumps up before mutation of the data guarded by the frlock.
1336 The lowest bit of the stamp is atomically set by GC if it moved a key,
1337 and atomically cleared by Lisp after refreshing the bucket chains.
1352 reason about the status bits, so restart from the top.
1354 Pre- Post- Miss
1355 loookup lookup Action
1356 ------- ------- ------
1366 |#
1369 ;; For synchronized GETHASH we've already acquired the lock,
1370 ;; so this KV-VECTOR is the most current one.
1377 ;; When INDEX is negative (implies that the hash table is
1378 ;; empty), we could return DEFAULT here, but that is an overall
1379 ;; performance loss. Maybe it's worth it to start with a
1380 ;; GETHASH/EMPTY getter. -- MG, 2023-10-12
1381 ;;
1382 ;; First check the cache using EQ, not the test fun, for speed.
1390 ;; Search next-vector chain for a matching key.
1397 ;; Optimistically assuming we hit the key, this check
1398 ;; never executes. The exact boundary case doesn't matter
1399 ;; (this might allow a few too many iterations),
1400 ;; but as long as we can detect circularity, it's fine.
1402 ;; We get too many "unreachable code" notes for my liking,
1403 ;; if this branch is unconditionally left in.
1409 ;; In the case of EQL, we get most bang-for-buck (performance per
1410 ;; line of asm code) by inlining EQL, not by loop unrolling,
1411 ;; but we might as well unroll a little bit to lessen the impact
1412 ;; of check-for-overflow.
1413 ;; You can experiment with unrolling here easily enough.
1418 ;; Taking out either of these barriers will cause failure of
1419 ;; PARALLEL-READERS-EQUAL-TABLE on relaxed memory order CPUs.
1420 ;; The paired :WRITE barrier is either in the stop-the-world handler
1421 ;; (which is effectively a full barrier), or the CAS in the regression test
1422 ;; that mocks GC touching the need-to-rehash bit.
1423 ;; That's the best explanation I can give.
1431 default))
1437 ;; the BARRIER macro sucks bigly, hence the PROGN
1442 ;; * address-based hashes were valid on entry
1443 ;; * disregarding the need-to-rehash bit, stamp is the same as on
1444 ;; entry (rehash did not occur)
1447 ;; * address-based hashes were NOT valid on entry
1448 ;; * rehash did not occur
1449 ;; Stably hashed (address-insensitive) keys are ok.
1456 ;; conflicted with other thread trying to rehash
1465 ;;;; Weak table variant.
1469 ;;; A single function acts as the core of all operations on weak tables.
1470 ;;; The advantage is that we could simulate lazy weak lists by removing smashed
1471 ;;; pairs while doing any table operation, with no GC support beyond the ability
1472 ;;; to change a cell from non-empty to smashed. Therefore if we could leverage a
1473 ;;; collector from some other language, it need not understand our weak
1474 ;;; hash-table representation in depth.
1476 ;;; TODO: it would be ideal if GETHASH/WEAK could share code with GETHASH/ANY
1477 ;;; (the general case of hash-function + predicate).
1478 ;;; The difficulty in doing so is that %REHASH-AND-FIND has trouble understanding
1479 ;;; how to treat keys that are +empty-ht-slot+ in a weak table - we don't know if
1480 ;;; a key was smashed by GC and the cell still exists in a bucket's chain,
1481 ;;; versus the cell being in the freelist. So the code diverges in at least that way.
1495 ;; An unfortunate aspect of this code is that it will liven
1496 ;; passed over keys in the case of a probe miss. It should be
1497 ;; possible to come up with a way to _conditionally_ strengthen
1498 ;; the ref to the key, i.e. only when we actually have a hit.
1502 ;; Delay fetching the value until a key match. There's a race here
1503 ;; in a weak value table. If the key is reachable but the value is
1504 ;; otherwise unreachable, the GC might win and clear the value.
1505 ;; So GETHASH has to check for that anyway.
1512 ;; Everything in an EQ table is address-based - though this is subject
1513 ;; to change, as we could stably hash symbols, because why not -
1514 ;; but the hash fun's second value is NIL on immediate objects.
1517 ;; similar to EQ except for the different comparator
1520 ;; For any other test, we assume that it is not safe to pass the
1521 ;; unbound marker to the predicate (though EQUAL and EQUALP are
1522 ;; probably OK). Also, compare hashes first.
1526 ;; Weak tables disallow concurrent GETHASH therefore we can't
1527 ;; be in the midst of fixing up obsolete address-based hashes.
1538 ;; set the stamp to rehashing. There should be no concurrent
1539 ;; access, but use CAS to be sure.
1542 ;; Set vector hashing, remove weakness, keep address-sensitivity.
1550 ;; We don't need to zero-fill the NEXT vector, just the INDEX vector.
1551 ;; Unless a key slot can be reached by a chain starting from the index
1552 ;; vector or the 'next' of a previous chain element, we don't read either
1553 ;; the key or its corresponding 'next'. So we only need to assign a
1554 ;; 'next' at the moment a slot is linked into a chain.
1559 hash-table))
1560 ;; Empty cells will have been placed in the ordinary freelist,
1561 ;; so clear the list of GC-smashed cells.
1563 ;; Re-enable weakness
1566 ;; One more try gives the definitive answer even if the hashes are
1567 ;; obsolete again. KEY's hash can't have changed, and there
1568 ;; are no concurrent readers to potentially mess up the chains.
1585 ;; It would be ideal if we were consistent about all tables NOT having
1586 ;; synchronization unless created with ":SYNCHRONIZED T"
1587 ;; but it looks tricky to support concurrent gethash on weak tables,
1588 ;; so we default to locking.
1590 ;; Use the private slot accessor for the lock because it's known
1591 ;; to have a mutex.
1600 ;; empty can occur in two cases: not found, or GC culled a pair even when
1601 ;; a key was found - consider a table with weakness kind :VALUE.
1602 ;; It's best that we be agnostic of the exact order that WITH-PAIR loads
1603 ;; the parts and the order in which GC writes the empty markers.
1614 ;;; In lieu of racing to rehash in multiple threads due to GC key movement,
1615 ;;; or blocking on a mutex to rehash, threads can perform just the FIND
1616 ;;; aspect of %REHASH-AND-FIND which is obviously less work than rehashing.
1617 ;;; It has the same computational complexity but fewer instructions,
1618 ;;; and allows forward progress in all threads.
1619 ;;; But unlike %REHASH-AND-FIND which will only be called when the key
1620 ;;; in question was hashed by its address, this search can be called for any
1621 ;;; key and hash-table-test whenever some thread is rehashing. If hash-based
1622 ;;; lookup uses EQ as the comparator for KEY, then linear search does too.
1631 ;; EQ-TEST is an optimization which says that regardless of the table test,
1632 ;; for the particular key being sought, the comparator should be EQ.
1633 ;; This would be true of INSTANCE in an EQL or EQUAL table for example.
1641 ;; EQ and EQL are fine with unbound-marker as an argument,
1642 ;; but the general case checks the key for validity first.
1660 ;; We might want to think about inlining the guts of
1661 ;; CALL-WITH-...LOCK into these methods.
1693 ;; test is specified as 0..3 for a standard fun or -1 for userfun
1706 ;;; so people can call #'(SETF GETHASH)
1707 ;;; FIXME: this function is not mandated. Why do we have it?
1713 ;; Entries culled by GC are linked into a plain old list of cons cells,
1714 ;; because we can atomically manipulate that. We can't atomically operate
1715 ;; on the array-qua-list representation, both because we don't support
1716 ;; numeric arrays in (CAS AREF) and lockfree deletion from interior nodes
1717 ;; of singly-linked lists is tricky (a concurrent insert can get lost).
1729 ;; This pair started a chain. Removing it is easy
1731 ;; Else, find the kv-index in the chain and snap it out.
1739 ;; Set the 'next' at kv-index to the head of the ordinary freelist
1740 ;; so that when INSERT-AT pops the freelist, it stays correct.
1742 kv-index)))
1744 ;;; We don't need the looping and checking for GC activiy in PUTHASH
1745 ;;; because insertion can not co-occur with any other operation,
1746 ;;; unlike GETHASH which we allow to execute in multiple threads.
1754 ;; Check the most-recently-used cell
1758 ;; Read the 'rehash' bit as soon as possible after pinning KEY,
1759 ;; but not before. The closer in time we observe the bit vs pinning,
1760 ;; the more likely it is to reflect at most the moved status of KEY
1761 ;; and not also the moved status of keys moved after KEY got pinned.
1762 ;; To illustrate:
1763 ;;
1764 ;; t0 .... t1 .... t2 .... t3 ....
1765 ;; ^ ^ ^ ^
1766 ;; | | | GC |
1767 ;; Pin Possible Actual
1768 ;; observation observation
1769 ;; of 'rehash' of 'rehash'
1770 ;;
1771 ;; If GC causes the bit to become set, and we don't read the bit
1772 ;; until t3, we're forced to conclude that KEY's hash might have been wrong.
1773 ;; Granted that the bit might have been 1 at timestamp 't1',
1774 ;; but it's best to read it at t1 and not later.
1780 ;; Search next-vector chain for a matching key.
1782 ;; Unrolling a few times like in %GETHASH doesn't seem
1783 ;; to affect even the tightest microbenchmarks.
1801 ;; Detect whether the failure to find was due to key movement.
1802 ;; Only the initial state of the 'rehash' bit is important.
1803 ;; If the bit changed from 0 to 1, then KEY's hash was good because
1804 ;; it was pinned at the time we observed the rehash status to be 0.
1806 ;; The current stamp must be the same as initial-stamp, because
1807 ;; PUTHASH is disallowed concurrently with any other operation,
1808 ;; and the 'rehash' bit can't be cleared except by rehashing
1809 ;; as part of such operation.
1813 ;; If we see NIL here, it means that some other operation is racing
1814 ;; to rehash. GETHASH can deal with that scenario, PUTHASH can't.
1818 ;; Pop a KV slot off the free list
1821 hash-table key
1822 ;; Clip the unclipped hash from EQ-HASH* or its
1823 ;; kind to be able to pass it to INSERT-AT
1824 ;; without consing.
1826 address-based-p value))))))
1834 ;; Growing the table can not make the key become found when it was not
1835 ;; found before, so we can just proceed with insertion.
1837 ;; Grab the vectors AFTER possibly growing the table
1845 ;; CPU must not buffer storing the new HWM versus the
1846 ;; stores of the K+V since they wouldn't be seen.
1856 ;; We've potentially depended on the bits of the address of KEY
1857 ;; before informing GC that we've done so, but the key is pinned,
1858 ;; so as long as the table informs GC that it has the dependency
1859 ;; by the time the key is free to move, all is well.
1863 ;; Store the hash unless an EQ table. Because the key is pinned, it is
1864 ;; OK that GC would not have seen +magic-hash-vector-value+ for this
1865 ;; key if applicable.
1870 ;; Push this slot onto the front of the chain for its bucket.
1871 ;; A chain linked to an empty cell makes no difference, as any concurrent
1872 ;; operation on this same table would constitute user error.
1877 ;; Store the pair only *after* linking the cell in. This order of operations
1878 ;; allows GC to assert that every pair in kvv is findable in a bucket.
1879 ;; Setting the kvv elements first, before chaining, would temporarily result
1880 ;; in a non-findable key which we'd have to heuristically allow based on
1881 ;; implicit pinning.
1888 value))
1895 ;; There are two kinds of freelists. Prefer a smashed cell
1896 ;; so that we might shorten the chain it belonged to.
1899 hash-table key hash address-sensitive-p value))
1901 probed-value value))
1916 ;; The cache provides no benefit to REMHASH. A hit would just mean there is work
1917 ;; to do in removing the item from a chain, whereas a miss means we don't know
1918 ;; if there is work to do, so effectively there is work to do either way.
1920 ;; See comment in DEFINE-HT-SETTER about why to read initial-stamp
1921 ;; as soon as possible after pinning KEY.
1930 ;; Removing the key at the header of the chain is exceptional
1931 ;; because it has no predecessor,
1950 ;; Detect whether the failure to find was due to key movement.
1951 ;; Only the initial state of the 'rehash' bit is important.
1952 ;; If the bit changed from 0 to 1, then KEY's hash was good because
1953 ;; it was pinned at the time we observed the rehash status to be 0.
1961 ;; Mark slot as empty.
1966 probed-key))
1971 ;; Unlink from bucket's chain
1977 ;; Push onto free chain
1981 t)))))
1985 ;; Mark slot as empty.
1989 ;; Push KV slot onto free chain.
1992 ;; On parallel accesses this may turn out to be a
1993 ;; type-error, so don't turn down the safety!
1995 t)
1998 ;; Remove KEY from BUCKET which is based on the current address
1999 ;; of key after pinning. When the key was not found initially,
2000 ;; the "problem" so to speak was that the bucket that was searched
2001 ;; did not hold the key, and not that search was done on the wrong
2002 ;; bucket. Rehashing will place the key into the expected bucket.
2003 ;;
2004 ;; The current stamp must be the same as initial-stamp, because
2005 ;; REMHASH is disallowed concurrently with any other operation,
2006 ;; and the 'rehash' bit can't be cleared except by rehashing
2007 ;; as part of such operation.
2011 ;; If we see NIL here, it means that some other operation is racing
2012 ;; to rehash. GETHASH can deal with that scenario, REMHASH can't.
2052 "Remove the entry in HASH-TABLE associated with KEY. Return T if
2053 there was such an entry, or NIL if not."
2057 "This removes all the entries from HASH-TABLE and returns the hash
2058 table itself."
2062 ;; This used to do nothing at all for tables that has a COUNT of 0,
2063 ;; but that wasn't quite right, because some steps below pertain to
2064 ;; getting the initial state back to that of a freshly made table.
2065 ;; In particular, the need-to-rehash flag should be cleared, and the freelist
2066 ;; should be reset so that we start to consume k/v cells leftmost first
2067 ;; instead of whatever random order they were left in.
2068 ;;
2069 ;; It is probably not strictly necessary for vectors marked as valid-hashing to
2070 ;; be initialized with empty-ht-slot, because GC regards the portion of the vector
2071 ;; beyond the HWM as unused. Though for weak tables, some invariants can
2072 ;; be checked by having the empty markers but couldn't be without.
2073 ;; [Reusing those elements would be a two-step process: set them to 0,
2074 ;; bump the HWM, set them to desired values - because you can't let GC
2075 ;; observe junk, but you can't put good value at higher than the HWM]
2082 ;; Remove address-sensitivity.
2084 ;; Do this only after unsetting the address-sensitive bit,
2085 ;; otherwise GC might come along and touch this bit again.
2087 ;; We always deposit empty markers into k/v pairs that are REMHASHed,
2088 ;; so a count of 0 implies no clearing need be done.
2091 ;; Fill all slots with the empty marker.
2093 ;; Clear the index-vector.
2094 ;; Don't need to clear the hash-vector or the next-vector.
2103 hash-table)
2105 \f
2106 ;;;; methods on HASH-TABLE
2108 ;;; Return an association list representing the same data as HASH-TABLE.
2109 ;;; Iterate downward so that PUSH creates the result in insertion order.
2110 ;;; One the one hand, this should not to be construed as a guarantee about
2111 ;;; the order, but on the other, it is convenient to see key/values in the
2112 ;;; same order as insertion, and moreover, preserving that order makes
2113 ;;; %STUFF-HASH-TABLE produce the same k/v vector.
2123 result))
2125 ;;; Stuff an association list, or a vector, into HASH-TABLE. Return the hash table,
2126 ;;; so that we can use this for the *PRINT-READABLY* case in PRINT-OBJECT (HASH-TABLE T)
2127 ;;; without having to worry about LET forms and readable gensyms and stuff.
2133 ;; Mark the index vector, next-vector, hash-vector (if present),
2134 ;; and even the key vector, as shareable, provided that no key is hashed
2135 ;; address-sensitively. As a first crack I'm just requiring keys to be
2136 ;; fixnum or character, but some table types would stably hash more things.
2145 hash-table)
2147 ;;; Return a list of keyword args and values to use for MAKE-HASH-TABLE
2148 ;;; when reconstructing HASH-TABLE.
2151 ;; If it has a named test function - it wasn't a lambda expression -
2152 ;; and the table's hash-function is identical to the hash function
2153 ;; dictated by *USER-HASH-TABLE-TESTS* for that test, we're OK.
2154 ;; And it's not worth the risk of trying to reverse-engineer the hash
2155 ;; function if all we have is a name.
2160 in
2170 collect key
2171 and
2173 value
2181 ;; Perhaps we should add :SYNCHRONIZED to the string?
2184 ":TEST ~S~@[ :HASH-FUNCTION ~S~] :COUNT ~S~@[ :WEAKNESS ~S~]"
2195 ctor)
2203 ;; This uses a separate initform in case the hash table contains itself
2204 ;; as either a key or value.
2205 ;; FIXME: k/v pairs would take less space as a vector, not an alist.
2209 )
2211 ;;; This assignment has to occur some time after the defstruct.
2212 ;;; We don't call EQUALP on hash-table, so as late as possible is fine.
2213 ;;; It can't go in src/code/pred whose forms execute *before* the defstruct,
2214 ;;; so its effect would just get clobbered by the defstruct.
2219 #|
2232 do
2261 len))
2263 for i from 0
2276 x))
2277 it)))))
2282 #'>
2288 ht))))
2304 ;; disregarding overhead cells and padding words
2322 ;; try to keep the load factor at full load within a certain range
2334 ;;; You can't attain an arbitrary rehash size using power-of-2 tables
2335 ;;; because all you can do is double the number of buckets.
2336 ;;; However, by doubling the count only on alternate resizings, we can
2337 ;;; approximate growing at rate slower than doubling in terms of space used.
2338 ;;; This table shows that using the default resize factor of 1.5x we see
2339 ;;; a fairly smooth increase in memory consumed at each resizing
2340 ;;; (about 1.3x to 1.6x the usage at the old size) while bounding the LF
2341 ;;; to between .6 and .85 if every k/v cell is in use at the new size.
2343 size bits LF mem
2344 7 3 0.8750 200
2401 |#