Changeset 9999


Ignore:
Timestamp:
Jul 10, 2008, 11:12:28 AM (11 years ago)
Author:
gz
Message:

Propagate r9930,r9931 (faster mod for hash) to trunk

Location:
trunk/source
Files:
3 edited

Legend:

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

    r4415 r9999  
    3737  (single-value-return))
    3838
     39
     40;; Faster mod based on Bruce Hoult's Dylan version, modified to use a branch-free max.
     41(defx86lapfunction fast-mod-3 ((number arg_x) (divisor arg_y) (recip arg_z))
     42  (mov (% number) (% imm0))
     43  (shrq ($ target::fixnumshift) (% imm0))
     44  (mov (% recip) (% imm1))
     45  (mul (% imm1)) ;; -> hi word in imm1 (unboxed)
     46  (mov (% divisor) (% imm0))
     47  (mul (% imm1)) ;; -> lo word in imm0 (boxed)
     48  (subq (% imm0) (% number))
     49  (subq (% divisor) (% number))
     50  (mov (% number) (% arg_z))
     51  (mov (% number) (% imm0))
     52  (sar ($ (1- target::nbits-in-word)) (% imm0))
     53  (andq (% imm0) (% divisor))
     54  (addq (% divisor) (% arg_z))
     55  (single-value-return))
    3956
    4057(defx86lapfunction %dfloat-hash ((key arg_z))
  • trunk/source/level-0/l0-hash.lisp

    r9912 r9999  
    213213 
    214214(defun nhash.vector-size (vector)
    215   (ash (the fixnum (- (the fixnum (uvsize vector)) $nhash.vector_overhead)) -1))
     215  (nhash.vector.size vector))
     216
     217(eval-when (:compile-toplevel :execute) (declaim (inline hash-mod)))
     218(defun hash-mod (hash entries vector)
     219  (fast-mod-3 hash entries (nhash.vector.size-reciprocal vector)))
    216220
    217221;;; Is KEY something which can be EQL to something it's not EQ to ?
     
    430434              (setq flags (bitset $nhash_component_address_bit flags))))
    431435          (setf (nhash.vector.flags vector) flags))))
    432     (let* ((length (- (the fixnum (uvsize  vector)) $nhash.vector_overhead))
    433            (entries (ash length -1)))
    434       (declare (fixnum length entries))
     436    (let* ((entries (nhash.vector-size vector)))
     437      (declare (fixnum entries))
    435438      (values primary
    436               (fast-mod primary entries)
     439              (hash-mod primary entries vector)
    437440              entries))))
    438441
     
    10911094                  (%hash-symbol key)
    10921095                  (mixup-hash-code (strip-tag-to-fixnum key)))))))
    1093          (length (uvsize vector))
    1094          (count (- length $nhash.vector_overhead))
    1095          (entries (ash count -1))
    1096          (vector-index (index->vector-index (fast-mod hash-code entries)))
     1096         (entries (nhash.vector-size vector))
     1097         (vector-index (index->vector-index (hash-mod hash-code entries vector)))
    10971098         (table-key (%svref vector vector-index)))
    1098     (declare (fixnum hash-code  entries vector-index count length))
     1099    (declare (fixnum hash-code  entries vector-index))
    10991100    (if (or (eq key table-key)
    11001101            (eq table-key free-hash-key-marker))
     
    11041105             (initial-index vector-index)             
    11051106             (first-deleted-index (if (eq table-key deleted-hash-key-marker)
    1106                                     vector-index)))
    1107         (declare (fixnum secondary-hash initial-index))
     1107                                    vector-index))
     1108             (count (+ entries entries))
     1109             (length (+ count $nhash.vector_overhead)))
     1110        (declare (fixnum secondary-hash initial-index count length))
    11081111        (loop
    11091112          (incf vector-index secondary-hash)
     
    11451148                              (logior $nhash-track-keys-mask flags))))
    11461149                    (mixup-hash-code (strip-tag-to-fixnum key))))))))
    1147          (length (uvsize  vector))
    1148          (count (- length $nhash.vector_overhead))
    1149          (vector-index (index->vector-index (fast-mod hash-code (ash count -1))))
     1150         (entries (nhash.vector-size vector))
     1151         (vector-index (index->vector-index (hash-mod hash-code entries vector)))
    11501152         (table-key (%svref vector vector-index)))
    1151     (declare (fixnum hash-code length count vector-index))
     1153    (declare (fixnum hash-code vector-index))
    11521154    (if (or (eq key table-key)
    11531155            (eq table-key free-hash-key-marker))
     
    11571159             (initial-index vector-index)             
    11581160             (first-deleted-index (if (eq table-key deleted-hash-key-marker)
    1159                                     vector-index)))
    1160         (declare (fixnum secondary-hash initial-index))
     1161                                    vector-index))
     1162             (count (+ entries entries))
     1163             (length (+ count $nhash.vector_overhead)))
     1164        (declare (fixnum secondary-hash initial-index count length))
    11611165        (loop
    11621166          (incf vector-index secondary-hash)
     
    11791183    (let* ((vector (nhash.vector hash))
    11801184           (hash-code (%%eqlhash-internal key))
    1181            (length (uvsize  vector))
    1182            (count (- length $nhash.vector_overhead))
    1183            (entries (ash count -1))
    1184            (vector-index (index->vector-index (fast-mod hash-code entries)))
     1185           (entries (nhash.vector-size vector))
     1186           (vector-index (index->vector-index (hash-mod hash-code entries vector)))
    11851187           (table-key (%svref vector vector-index)))
    1186       (declare (fixnum hash-code length entries count vector-index))
     1188      (declare (fixnum hash-code entries vector-index))
    11871189      (if (or (eql key table-key)
    11881190              (eq table-key free-hash-key-marker))
     
    11921194               (initial-index vector-index)
    11931195               (first-deleted-index (if (eq table-key deleted-hash-key-marker)
    1194                                       vector-index)))
    1195           (declare (fixnum secondary-hash initial-index))
     1196                                      vector-index))
     1197               (count (+ entries entries))
     1198               (length (+ count $nhash.vector_overhead)))
     1199          (declare (fixnum secondary-hash initial-index count length))
    11961200          (loop
    11971201            (incf vector-index secondary-hash)
     
    12151219    (let* ((vector (nhash.vector hash))
    12161220           (hash-code (%%eqlhash-internal key))
    1217            (length (uvsize  vector))
    1218            (count (- length $nhash.vector_overhead))
    1219            (entries (ash count -1))
    1220            (vector-index (index->vector-index (fast-mod hash-code entries)))
     1221           (entries (nhash.vector-size vector))
     1222           (vector-index (index->vector-index (hash-mod hash-code entries vector)))
    12211223           (table-key (%svref vector vector-index)))
    1222       (declare (fixnum hash-code length entries vector-index))
     1224      (declare (fixnum hash-code entries vector-index))
    12231225      (if (or (eql key table-key)
    12241226              (eq table-key free-hash-key-marker))
     
    12281230               (initial-index vector-index)
    12291231               (first-deleted-index (if (eq table-key deleted-hash-key-marker)
    1230                                       vector-index)))
    1231           (declare (fixnum secondary-hash initial-index))
     1232                                      vector-index))
     1233               (count (+ entries entries))
     1234               (length (+ count $nhash.vector_overhead)))
     1235          (declare (fixnum secondary-hash initial-index count length))
    12321236          (loop
    12331237            (incf vector-index secondary-hash)
     
    16841688          (nhash.vector.cache-key vector) (%unbound-marker)
    16851689          (nhash.vector.cache-value vector) nil
    1686           (nhash.vector.cache-idx vector) nil)
     1690          (nhash.vector.cache-idx vector) nil
     1691          (nhash.vector.size vector) size
     1692          (nhash.vector.size-reciprocal vector) (floor (ash 1 (- target::nbits-in-word target::fixnumshift)) size))
    16871693    vector))
    16881694
  • trunk/source/xdump/hashenv.lisp

    r7959 r9999  
    3232(defconstant $nhash.lock-not-while-rehashing #x-20001)
    3333
    34 ; The hash.vector cell contains a vector with 8 longwords of overhead
     34; The hash.vector cell contains a vector with some longwords of overhead
    3535; followed by alternating keys and values.
    3636; A key of $undefined denotes an empty or deleted value
     
    4747  nhash.vector.cache-key                ; cached key
    4848  nhash.vector.cache-value              ; cached value
     49  nhash.vector.size                     ; number of entries in table
     50  nhash.vector.size-reciprocal          ; shifted reciprocal of nhash.vector.size
    4951  )
     52
    5053
    5154; number of longwords of overhead in nhash.vector.
    5255; Must be a multiple of 2 or INDEX parameters in LAP code will not be tagged as fixnums.
    53 (defconstant $nhash.vector_overhead 10)
     56(defconstant $nhash.vector_overhead 12)
    5457
    5558(defconstant $nhash_weak_bit 12)        ; weak hash table
Note: See TracChangeset for help on using the changeset viewer.