Changeset 14625


Ignore:
Timestamp:
Feb 2, 2011, 4:26:43 AM (9 years ago)
Author:
gb
Message:

REMHASH: it's not our job to effectively rehash the table when
the last key's removed. (That should happen in grow/rehash code,
anyway.)

%GROW-HASH-TABLE now calls new function %GROW-HASH-TABLE-IN-PLACE-P
to decide whether or not to grow the table or do an in-place rehash.
We might want to make this customizable; the default implementation
suggests an in-place rehash if there are at least half as many deleted
entries, and that seems to give good results for the test in ticket:809.

Fixes ticket:809, AFAICT.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/source/level-0/l0-hash.lisp

    r14119 r14625  
    997997               (setf (%svref vector vector-index) deleted-hash-key-marker
    998998                     (%svref vector (the fixnum (1+ vector-index))) nil)
    999                (setq foundp t))))
    1000          (when (and foundp
    1001                     (zerop (the fixnum (nhash.vector.count vector))))
    1002            (do* ((i $nhash.vector_overhead (1+ i))
    1003                  (n (uvsize vector)))
    1004                 ((= i n))
    1005              (declare (fixnum i n))
    1006              (setf (%svref vector i) free-hash-marker))
    1007            (setf (nhash.grow-threshold hash)
    1008                  (+ (nhash.vector.deleted-count vector)
    1009                     (nhash.vector.weak-deletions-count vector)
    1010                     (nhash.grow-threshold hash))
    1011                  (nhash.vector.deleted-count vector) 0
    1012                  (nhash.vector.weak-deletions-count vector) 0)))
     999               (setq foundp t)))))
    10131000       ;; Return T if we deleted something
    10141001       (%unlock-gc-lock)
     
    11341121  (%grow-hash-table hash))
    11351122
     1123(defun %grow-hash-table-in-place-p (hash)
     1124  ;; Arbitrarily: if the number of deleted entries is > half
     1125  ;; the number of used entries, do an in-place rehash.
     1126  (let* ((vec (nhash.vector hash)))
     1127    (> (the fixnum (nhash.vector.deleted-count vec))
     1128       (the fixnum (ash (the fixnum (nhash.vector.count vec)) -1)))))
     1129           
     1130
    11361131;;; Interrupts are disabled, and the caller has an exclusive
    11371132;;; lock on the hash table.
     
    11461141           (weak-flags nil))
    11471142      (declare (fixnum old-total-size flags flags-sans-weak))
    1148       (when (> (nhash.vector.deleted-count old-vector) 0)
     1143      (when (%grow-hash-table-in-place-p hash)
    11491144        ;; There are enough deleted entries. Rehash to get rid of them
    11501145        (%rehash hash)
     
    11641159              (setf (nhash.vector.flags old-vector) flags-sans-weak)      ; disable GC weak stuff
    11651160              (%normalize-hash-table-count hash)
    1166               (when (> (nhash.vector.deleted-count old-vector) 0)
     1161              (when (%grow-hash-table-in-place-p hash)
    11671162                (setf (nhash.vector.flags old-vector) flags)
    11681163                (setq weak-flags nil)
Note: See TracChangeset for help on using the changeset viewer.