source: trunk/source/level-0/X86/X8632/x8632-hash.lisp @ 10731

Last change on this file since 10731 was 10731, checked in by gz, 12 years ago

Implemented "nearly-lock-free" hash tables. They are created by
calling MAKE-HASH-TABLE with :LOCK-FREE t, or by setting
CCL::*LOCK-FREE-HASH-TABLE-DEFAULT* to T. There is some documentation
in a big comment in l0-hash.lisp, but basically the idea is to try to
avoid any locking in GETHASH, getting the performance equivalent to
readonly tables, at the cost of rehashing becoming more
expensive. PUTHASH should be roughly equivalent (it avoids getting a
lock, but does sync memory a few times).

So far, I've only tested them on linuxx8664, by building ccl multiple
times with *lock-free-hash-table-default* = T on, so no real
multi-threaded testing. I will now switch to the mac and try to
build and use the IDE that way.

Other changes: moved some slots from the hash table to the hash table
vector so they can all be swapped in/out all at once. Made nhash.find
return -1 when not found, also to avoid some synchronization issues.
%needs-rehashing-p now takes a hash table vector, not the hash table.
Got rid of a bunch of unused slots and constants in hash tables.

Incremented fasl version in case there are any fasdumped hash tables out there.

File size: 4.0 KB
Line 
1(in-package "CCL")
2
3(eval-when (:compile-toplevel :execute)
4  (require "HASHENV" "ccl:xdump;hashenv"))
5
6;;; This should stay in LAP so that it's fast
7;;; Equivalent to cl:mod when both args are positive fixnums
8
9;;; We have to use edx:eax for the dividend, so we can't avoid
10;;; having to do the mark-as-imm/mark-as-node dance here.  This
11;;; may have performance implications.
12(defx8632lapfunction fast-mod ((number arg_y) (divisor arg_z))
13  (mark-as-imm temp1)                   ;aka edx
14  (let ((imm1 temp1))
15    (xorl (% imm1) (% imm1))
16    (mov (% number) (% imm0))
17    (div (% divisor))
18    (mov (% imm1) (% arg_z)))
19  (mark-as-node temp1)
20  (single-value-return))
21
22;; Faster mod based on Bruce Hoult's Dylan version, modified to use a
23;; branch-free max.
24(defx8632lapfunction fast-mod-3 ((number 4) #|(ra 0)|# (divisor arg_y) (recip arg_z))
25  (std)                                 ;temp1 now unboxed
26  (let ((imm1 temp1)
27        (n temp0))
28    (movl (@ number (% esp)) (% n))
29    (movl (% n) (% imm0))
30    (shrl ($ target::fixnumshift) (% imm0)) ;logical shift is intentional
31    (mov (% recip) (% imm1))
32    (mul (% imm1)) ;; -> hi word in imm1 (unboxed)
33    (mov (% divisor) (% imm0))
34    (mul (% imm1)) ;; -> lo word in imm0 (boxed)
35    (subl (% imm0) (% n))
36    (subl (% divisor) (% n))
37    (mov (% n) (% arg_z))
38    (mov (% n) (% imm0))
39    (sar ($ (1- target::nbits-in-word)) (% imm0))
40    (andl (% imm0) (% divisor))
41    (addl (% divisor) (% arg_z)))
42  (xorl (% temp1) (% temp1))
43  (cld)                                 ;temp1 now boxed
44  (single-value-return 3))
45
46(defx8632lapfunction %dfloat-hash ((key arg_z))
47  (movl (@ x8632::double-float.value (% key)) (% imm0))
48  (addl (@ x8632::double-float.val-high (% key)) (% imm0))
49  (box-fixnum imm0 arg_z)
50  (single-value-return))
51
52(defx8632lapfunction %sfloat-hash ((key arg_z))
53  (movl (@ x8632::single-float.value (% key)) (% imm0))
54  (box-fixnum imm0 arg_z)
55  (single-value-return))
56
57(defx8632lapfunction %macptr-hash ((key arg_z))
58  (movl (@ x8632::macptr.address (% key)) (% imm0))
59  (box-fixnum imm0 temp0)
60  (shll ($ (- 24 x8632::fixnumshift)) (% temp0))
61  (addl (% temp0) (% imm0))
62  (movl ($ (lognot x8632::fixnummask)) (% arg_z))
63  (andl (% imm0) (% arg_z))
64  (single-value-return))
65
66(defx8632lapfunction %bignum-hash ((key arg_z))
67  (mark-as-imm temp1)
68  (let ((header imm0)
69        (offset temp1)
70        (ndigits temp0))
71    (getvheader key header)
72    (header-length header ndigits)
73    (xorl (% offset) (% offset))
74    (let ((immhash header))
75      @loop
76      (roll ($ 13) (% immhash))
77      (addl (@ x8632::misc-data-offset (% key) (% offset)) (% immhash))
78      (addl ($ 4) (% offset))
79      (subl ($ '1) (% ndigits))
80      (jne @loop)
81      (box-fixnum immhash arg_z)))
82  (mark-as-node temp1)
83  (single-value-return))
84
85(defx8632lapfunction %get-fwdnum ()
86  (ref-global target::fwdnum arg_z)
87  (single-value-return))
88
89(defx8632lapfunction %get-gc-count ()
90  (ref-global target::gc-count arg_z)
91  (single-value-return))
92
93;;; Setting a key in a hash-table vector needs to
94;;; ensure that the vector header gets memoized as well
95(defx8632lapfunction %set-hash-table-vector-key ((vector 4) #|(ra 0)|# (index arg_y) (value arg_z))
96  (pop (% temp1))                       ;return address
97  (pop (% temp0))                       ;.SPset-hash-key wants arg in temp0
98  (discard-reserved-frame)
99  (push (% temp1))
100  (jmp-subprim .SPset-hash-key))
101
102;;; This needs to be done out-of-line, to handle EGC memoization.
103(defx8632lapfunction %set-hash-table-vector-key-conditional ((offset 8)
104                                                             (vector 4)
105                                                             #|(ra 0)|#
106                                                             (old arg_y)
107                                                             (new arg_z))
108  (movl (@ offset (% esp)) (% temp0))
109  (movl (@ vector (% esp)) (% temp1))
110  (save-simple-frame)
111  (call-subprim .SPset-hash-key-conditional)
112  (restore-simple-frame)
113  (single-value-return 4))
114
115
116;;; Strip the tag bits to turn x into a fixnum
117(defx8632lapfunction strip-tag-to-fixnum ((x arg_z))
118  (andb ($ (lognot x8632::fixnummask)) (%b x))
119  (single-value-return))
120
Note: See TracBrowser for help on using the repository browser.