Changeset 15608


Ignore:
Timestamp:
Jan 28, 2013, 5:22:16 PM (6 years ago)
Author:
gz
Message:

Maintain nhash.vector.count in the lock-free case

File:
1 edited

Legend:

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

    r15606 r15608  
    582582  (setq hash (require-type hash 'hash-table))
    583583  (when (hash-lock-free-p hash)
    584     ;; We don't try to maintain a running total, so just count.
    585     (return-from hash-table-count (lock-free-count-entries hash)))
     584    (return-from hash-table-count (lock-free-hash-table-count hash)))
    586585  (the fixnum (nhash.vector.count (nhash.vector hash))))
    587586
     
    736735        (compute-hash-size count 1 (nhash.rehash-ratio hash))))
    737736    (setq new-vector (%cons-nhash-vector vector-size inherited-flags))
    738     (loop ;; with full-count = grow-threshold
     737    (loop with full-count = grow-threshold
    739738          for i from $nhash.vector_overhead below (uvsize old-vector) by 2
    740739          do (let* ((value (atomic-swap-gvector (%i+ i 1) old-vector rehashing-value-marker))
     
    769768                         (setq full-count bigger-threshold)
    770769                         (setq new-vector bigger-vector)
    771                          (setq vector-size bigger-vector-size))))))))
     770                         (setq vector-size bigger-vector-size)))))))
     771          finally (setf (nhash.vector.count new-vector) (- full-count grow-threshold)))
     772
    772773    (when (%needs-rehashing-p new-vector) ;; keys moved, but at least can use the same new-vector.
    773774      (%lock-free-rehash-in-place hash new-vector))
     
    864865               (unless (%needs-rehashing-p vector)
    865866                 (return-from lock-free-remhash nil)))
    866               (t (let ((old-value (%svref vector (%i+ vector-index 1))))
     867              (t (let ((old-value (%svref vector (%i+ vector-index 1)))
     868                       (old-key (%svref vector vector-index)))
    867869                   (unless (eq old-value rehashing-value-marker)
    868870                     (when (or (eq old-value deleted-hash-value-marker) ;; deleted
    869                                (eq old-value free-hash-marker)) ;; or about to be added
     871                               (eq old-value free-hash-marker) ;; or about to be added
     872                               (eq old-key deleted-hash-key-marker)) ;; or in clrhash...
    870873                       (return-from lock-free-remhash nil))
    871                      (when (set-hash-value-conditional vector-index vector old-value deleted-hash-value-marker)
    872                        ;; Clear the key slot so can be gc'd.
    873                        (setf (%svref vector vector-index) deleted-hash-key-marker)
     874                     (when (without-interrupts
     875                             (when (set-hash-value-conditional vector-index vector old-value deleted-hash-value-marker)
     876                               (atomic-decf (nhash.vector.count vector))
     877                               t))
     878                       ;; Clear the key slot so can be gc'd.
     879                       (setf (%svref vector vector-index) deleted-hash-key-marker)
    874880                       (return-from lock-free-remhash t)))))))
    875881      ;; We're here because the table needs rehashing or it was getting rehashed while we
     
    891897         unless (or (eq val free-hash-marker) (eq val deleted-hash-value-marker))
    892898         do (setf (%svref vector (%i- i 1)) deleted-hash-key-marker
    893                   (%svref vector i) deleted-hash-value-marker))
     899                  (%svref vector i) deleted-hash-value-marker)
     900         finally (setf (nhash.vector.count vector) 0))
    894901       (%unlock-recursive-lock-object lock))))
    895902  hash)
     
    929936                            (not (eq address (strip-tag-to-fixnum key))))
    930937                     (setf (%svref vector vector-index) deleted-hash-key-marker)                       ;; Back out and try again.
    931                      (when (set-hash-value-conditional vector-index vector free-hash-marker value)
     938                     (when (without-interrupts
     939                             (when (set-hash-value-conditional vector-index vector free-hash-marker value)
     940                               (atomic-incf (nhash.vector.count vector))
     941                               t))
    932942                       (return-from lock-free-puthash value))))))
    933943              (t (let ((old-value (%svref vector (%i+ vector-index 1))))
     
    935945                               ;; In theory, could reuse the deleted slot since we know it had this key
    936946                               ;; initially, but that would complicate the state machine for very little gain.
    937                                (eq old-value deleted-hash-value-marker))
     947                               (eq old-value deleted-hash-value-marker)
     948                               ;; This means we're competing with someone inserting this key.  We could continue
     949                               ;; except then would have to sync up nhash.vector.count, so don't.
     950                               (eq old-value free-hash-marker))
    938951                     (when (set-hash-value-conditional vector-index vector old-value value)
    939952                       (return-from lock-free-puthash value))))))))
     
    943956    ;; it's not worth checking for).  Take care of it and try again.
    944957    (lock-free-rehash hash)))
     958
     959(defun lock-free-hash-table-count (hash)
     960  (let* ((vector (nhash.vector hash))
     961         (count (nhash.vector.count vector)))
     962    #+debug-hash
     963    (let ((entries (lock-free-count-entries hash)))
     964           (unless (eq entries count)
     965             (error "hash count mismatch, count=~s actual ~s" count entries)))
     966    count))
    945967
    946968(defun lock-free-count-entries (hash)
     
    953975    with vector = (nhash.vector hash)
    954976    for i fixnum from $nhash.vector_overhead below (uvsize vector) by 2
    955     count (let ((value (%svref vector (%i+ i 1))))
     977    count (let ((value (%svref vector (%i+ i 1)))
     978                (key (%svref vector i)))
    956979            (when (eq value rehashing-value-marker)
    957980              ;; This table is being rehashed.  Wait for it to be
     
    959982              (lock-free-rehash hash)
    960983              (return-from lock-free-count-entries (lock-free-count-entries hash)))
    961             (and (neq value free-hash-marker)
    962                  (neq value deleted-hash-value-marker)))))
     984            (and (neq value free-hash-marker)
     985                 (neq value deleted-hash-value-marker)
     986                 (neq key deleted-hash-key-marker)))))
    963987
    964988;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
Note: See TracChangeset for help on using the changeset viewer.