Branch data Line data Source code
1 : : // This file is a part of Julia. License is MIT: https://julialang.org/license
2 : :
3 : : #define hash_size(h) (jl_array_len(h) / 2)
4 : :
5 : : // compute empirical max-probe for a given size
6 : : #define max_probe(size) ((size) <= 1024 ? 16 : (size) >> 6)
7 : :
8 : : #define keyhash(k) jl_object_id_(jl_typeof(k), k)
9 : : #define h2index(hv, sz) (size_t)(((hv) & ((sz)-1)) * 2)
10 : :
11 : : static inline int jl_table_assign_bp(jl_array_t **pa, jl_value_t *key, jl_value_t *val);
12 : :
13 : 1945280 : JL_DLLEXPORT jl_array_t *jl_idtable_rehash(jl_array_t *a, size_t newsz)
14 : : {
15 : 1945280 : size_t sz = jl_array_len(a);
16 : : size_t i;
17 : 1945280 : jl_value_t **ol = (jl_value_t **)a->data;
18 : 1945280 : jl_array_t *newa = jl_alloc_vec_any(newsz);
19 : : // keep the original array in the original slot since we need `ol`
20 : : // to be valid in the loop below.
21 : 1945280 : JL_GC_PUSH2(&newa, &a);
22 [ + + ]: 52888000 : for (i = 0; i < sz; i += 2) {
23 [ + + ]: 50942700 : if (ol[i + 1] != NULL) {
24 : 20374600 : jl_table_assign_bp(&newa, ol[i], ol[i + 1]);
25 : : // it is however necessary here because allocation
26 : : // can (and will) occur in a recursive call inside table_lookup_bp
27 : : }
28 : : }
29 : 1945280 : JL_GC_POP();
30 : 1945280 : return newa;
31 : : }
32 : :
33 : 61663500 : static inline int jl_table_assign_bp(jl_array_t **pa, jl_value_t *key, jl_value_t *val)
34 : : {
35 : : // pa points to a **un**rooted address
36 : : uint_t hv;
37 : 61663500 : jl_array_t *a = *pa;
38 : : size_t orig, index, iter, empty_slot;
39 : 61663500 : size_t newsz, sz = hash_size(a);
40 [ + + ]: 61663500 : if (sz == 0) {
41 : 40484 : a = jl_alloc_vec_any(HT_N_INLINE);
42 : 40484 : sz = hash_size(a);
43 : 40484 : *pa = a;
44 : : }
45 [ + + ]: 61663500 : size_t maxprobe = max_probe(sz);
46 : 61663500 : _Atomic(jl_value_t*) *tab = (_Atomic(jl_value_t*)*)a->data;
47 : :
48 : 61663500 : hv = keyhash(key);
49 : : while (1) {
50 : 61978000 : iter = 0;
51 : 61978000 : index = h2index(hv, sz);
52 : 61978000 : sz *= 2;
53 : 61978000 : orig = index;
54 : 61978000 : empty_slot = -1;
55 : :
56 : : do {
57 : 266671000 : jl_value_t *k2 = jl_atomic_load_relaxed(&tab[index]);
58 [ + + ]: 266671000 : if (k2 == NULL) {
59 [ + + ]: 60704900 : if (empty_slot == -1)
60 : 60432000 : empty_slot = index;
61 : 60704900 : break;
62 : : }
63 [ + + ]: 205966000 : if (jl_egal(key, k2)) {
64 [ + - ]: 955159 : if (jl_atomic_load_relaxed(&tab[index + 1]) != NULL) {
65 : 955159 : jl_atomic_store_release(&tab[index + 1], val);
66 : 955159 : jl_gc_wb(a, val);
67 : 955159 : return 0;
68 : : }
69 : : // `nothing` is our sentinel value for deletion, so need to keep searching if it's also our search key
70 [ # # ]: 0 : assert(key == jl_nothing);
71 [ # # ]: 0 : if (empty_slot == -1)
72 : 0 : empty_slot = index;
73 : : }
74 [ + + + + ]: 205011000 : if (empty_slot == -1 && jl_atomic_load_relaxed(&tab[index + 1]) == NULL) {
75 [ - + ]: 276353 : assert(jl_atomic_load_relaxed(&tab[index]) == jl_nothing);
76 : 276353 : empty_slot = index;
77 : : }
78 : :
79 : 205011000 : index = (index + 2) & (sz - 1);
80 : 205011000 : iter++;
81 [ + + + + ]: 205011000 : } while (iter <= maxprobe && index != orig);
82 : :
83 [ + + ]: 61022800 : if (empty_slot != -1) {
84 : 60708300 : jl_atomic_store_release(&tab[empty_slot], key);
85 : 60708300 : jl_gc_wb(a, key);
86 : 60708300 : jl_atomic_store_release(&tab[empty_slot + 1], val);
87 : 60708300 : jl_gc_wb(a, val);
88 : 60708300 : return 1;
89 : : }
90 : :
91 : : /* table full */
92 : : /* quadruple size, rehash, retry the insert */
93 : : /* it's important to grow the table really fast; otherwise we waste */
94 : : /* lots of time rehashing all the keys over and over. */
95 : 314506 : sz = jl_array_len(a);
96 [ + + ]: 314506 : if (sz < HT_N_INLINE)
97 : 2070 : newsz = HT_N_INLINE;
98 [ + + + + ]: 312436 : else if (sz >= (1 << 19) || (sz <= (1 << 8)))
99 : 305154 : newsz = sz << 1;
100 : : else
101 : 7282 : newsz = sz << 2;
102 : 314506 : *pa = jl_idtable_rehash(*pa, newsz);
103 : :
104 : 314506 : a = *pa;
105 : 314506 : tab = (_Atomic(jl_value_t*)*)a->data;
106 : 314506 : sz = hash_size(a);
107 [ + + ]: 314506 : maxprobe = max_probe(sz);
108 : : }
109 : : }
110 : :
111 : : /* returns bp if key is in hash, otherwise NULL */
112 : 425855000 : inline _Atomic(jl_value_t*) *jl_table_peek_bp(jl_array_t *a, jl_value_t *key) JL_NOTSAFEPOINT
113 : : {
114 : 425855000 : size_t sz = hash_size(a);
115 [ + + ]: 425855000 : if (sz == 0)
116 : 556916 : return NULL;
117 [ + + ]: 425298000 : size_t maxprobe = max_probe(sz);
118 : 425298000 : _Atomic(jl_value_t*) *tab = (_Atomic(jl_value_t*)*)a->data;
119 : 425298000 : uint_t hv = keyhash(key);
120 : 425298000 : size_t index = h2index(hv, sz);
121 : 425298000 : sz *= 2;
122 : 425298000 : size_t orig = index;
123 : 425298000 : size_t iter = 0;
124 : :
125 : : do {
126 : 748148000 : jl_value_t *k2 = jl_atomic_load_relaxed(&tab[index]); // just to ensure the load doesn't get duplicated
127 [ + + ]: 748148000 : if (k2 == NULL)
128 : 61764400 : return NULL;
129 [ + + ]: 686384000 : if (jl_egal(key, k2)) {
130 [ + - ]: 362185000 : if (jl_atomic_load_relaxed(&tab[index + 1]) != NULL)
131 : 362185000 : return &tab[index + 1];
132 : : // `nothing` is our sentinel value for deletion, so need to keep searching if it's also our search key
133 [ # # ]: 0 : if (key != jl_nothing)
134 : 0 : return NULL; // concurrent insertion hasn't completed yet
135 : : }
136 : :
137 : 324199000 : index = (index + 2) & (sz - 1);
138 : 324199000 : iter++;
139 [ + + + + ]: 324199000 : } while (iter <= maxprobe && index != orig);
140 : :
141 : 1348810 : return NULL;
142 : : }
143 : :
144 : : JL_DLLEXPORT
145 : 41282700 : jl_array_t *jl_eqtable_put(jl_array_t *h, jl_value_t *key, jl_value_t *val, int *p_inserted)
146 : : {
147 : 41282700 : int inserted = jl_table_assign_bp(&h, key, val);
148 [ + + ]: 41282700 : if (p_inserted)
149 : 39919100 : *p_inserted = inserted;
150 : 41282700 : return h;
151 : : }
152 : :
153 : : // Note: lookup in the IdDict is permitted concurrently, if you avoid deletions,
154 : : // and assuming you do use an external lock around all insertions
155 : : JL_DLLEXPORT
156 : 424204000 : jl_value_t *jl_eqtable_get(jl_array_t *h, jl_value_t *key, jl_value_t *deflt) JL_NOTSAFEPOINT
157 : : {
158 : 424204000 : _Atomic(jl_value_t*) *bp = jl_table_peek_bp(h, key);
159 [ + + ]: 424204000 : return (bp == NULL) ? deflt : jl_atomic_load_relaxed(bp);
160 : : }
161 : :
162 : : JL_DLLEXPORT
163 : 1134240 : jl_value_t *jl_eqtable_pop(jl_array_t *h, jl_value_t *key, jl_value_t *deflt, int *found)
164 : : {
165 : 1134240 : _Atomic(jl_value_t*) *bp = jl_table_peek_bp(h, key);
166 [ + - ]: 1134240 : if (found)
167 : 1134240 : *found = (bp != NULL);
168 [ + + ]: 1134240 : if (bp == NULL)
169 : 704299 : return deflt;
170 : 429946 : jl_value_t *val = jl_atomic_load_relaxed(bp);
171 : 429946 : jl_atomic_store_relaxed(bp - 1, jl_nothing); // clear the key
172 : 429946 : jl_atomic_store_relaxed(bp, NULL); // and the value (briefly corrupting the table)
173 : 429946 : return val;
174 : : }
175 : :
176 : : JL_DLLEXPORT
177 : 99252300 : size_t jl_eqtable_nextind(jl_array_t *t, size_t i)
178 : : {
179 [ - + ]: 99252300 : if (i & 1)
180 : 0 : i++;
181 : 99252300 : size_t alen = jl_array_dim0(t);
182 [ + + + + ]: 1499900000 : while (i < alen && ((void **)t->data)[i + 1] == NULL)
183 : 1400650000 : i += 2;
184 [ + + ]: 99252300 : if (i >= alen)
185 : 87596600 : return (size_t)-1;
186 : 11655700 : return i;
187 : : }
188 : :
189 : : #undef hash_size
190 : : #undef max_probe
|
