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 : 57272 : JL_DLLEXPORT jl_array_t *jl_idtable_rehash(jl_array_t *a, size_t newsz)
14 : : {
15 : 57272 : size_t sz = jl_array_len(a);
16 : : size_t i;
17 : 57272 : jl_value_t **ol = (jl_value_t **)a->data;
18 : 57272 : 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 : 57272 : JL_GC_PUSH2(&newa, &a);
22 [ + + ]: 1532990 : for (i = 0; i < sz; i += 2) {
23 [ + + ]: 1475720 : if (ol[i + 1] != NULL) {
24 : 761600 : 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 : 57272 : JL_GC_POP();
30 : 57272 : return newa;
31 : : }
32 : :
33 : 3155870 : 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 : 3155870 : jl_array_t *a = *pa;
38 : : size_t orig, index, iter, empty_slot;
39 : 3155870 : size_t newsz, sz = hash_size(a);
40 [ + + ]: 3155870 : if (sz == 0) {
41 : 13433 : a = jl_alloc_vec_any(HT_N_INLINE);
42 : 13433 : sz = hash_size(a);
43 : 13433 : *pa = a;
44 : : }
45 [ + + ]: 3155870 : size_t maxprobe = max_probe(sz);
46 : 3155870 : _Atomic(jl_value_t*) *tab = (_Atomic(jl_value_t*)*)a->data;
47 : :
48 : 3155870 : hv = keyhash(key);
49 : : while (1) {
50 : 3178270 : iter = 0;
51 : 3178270 : index = h2index(hv, sz);
52 : 3178270 : sz *= 2;
53 : 3178270 : orig = index;
54 : 3178270 : empty_slot = -1;
55 : :
56 : : do {
57 : 5312230 : jl_value_t *k2 = jl_atomic_load_relaxed(&tab[index]);
58 [ + + ]: 5312230 : if (k2 == NULL) {
59 [ + + ]: 3110920 : if (empty_slot == -1)
60 : 3101690 : empty_slot = index;
61 : 3110920 : break;
62 : : }
63 [ + + ]: 2201300 : if (jl_egal(key, k2)) {
64 [ + - ]: 44950 : if (jl_atomic_load_relaxed(&tab[index + 1]) != NULL) {
65 : 44950 : jl_atomic_store_release(&tab[index + 1], val);
66 : 44950 : jl_gc_wb(a, val);
67 : 44950 : 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 [ + + + + ]: 2156350 : if (empty_slot == -1 && jl_atomic_load_relaxed(&tab[index + 1]) == NULL) {
75 [ - + ]: 9234 : assert(jl_atomic_load_relaxed(&tab[index]) == jl_nothing);
76 : 9234 : empty_slot = index;
77 : : }
78 : :
79 : 2156350 : index = (index + 2) & (sz - 1);
80 : 2156350 : iter++;
81 [ + + + + ]: 2156350 : } while (iter <= maxprobe && index != orig);
82 : :
83 [ + + ]: 3133320 : if (empty_slot != -1) {
84 : 3110920 : jl_atomic_store_release(&tab[empty_slot], key);
85 : 3110920 : jl_gc_wb(a, key);
86 : 3110920 : jl_atomic_store_release(&tab[empty_slot + 1], val);
87 : 3110920 : jl_gc_wb(a, val);
88 : 3110920 : 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 : 22397 : sz = jl_array_len(a);
96 [ + + ]: 22397 : if (sz < HT_N_INLINE)
97 : 541 : newsz = HT_N_INLINE;
98 [ + - + + ]: 21856 : else if (sz >= (1 << 19) || (sz <= (1 << 8)))
99 : 21531 : newsz = sz << 1;
100 : : else
101 : 325 : newsz = sz << 2;
102 : 22397 : *pa = jl_idtable_rehash(*pa, newsz);
103 : :
104 : 22397 : a = *pa;
105 : 22397 : tab = (_Atomic(jl_value_t*)*)a->data;
106 : 22397 : sz = hash_size(a);
107 [ + + ]: 22397 : maxprobe = max_probe(sz);
108 : : }
109 : : }
110 : :
111 : : /* returns bp if key is in hash, otherwise NULL */
112 : 105007000 : inline _Atomic(jl_value_t*) *jl_table_peek_bp(jl_array_t *a, jl_value_t *key) JL_NOTSAFEPOINT
113 : : {
114 : 105007000 : size_t sz = hash_size(a);
115 [ + + ]: 105007000 : if (sz == 0)
116 : 85564 : return NULL;
117 [ + + ]: 104922000 : size_t maxprobe = max_probe(sz);
118 : 104922000 : _Atomic(jl_value_t*) *tab = (_Atomic(jl_value_t*)*)a->data;
119 : 104922000 : uint_t hv = keyhash(key);
120 : 104922000 : size_t index = h2index(hv, sz);
121 : 104922000 : sz *= 2;
122 : 104922000 : size_t orig = index;
123 : 104922000 : size_t iter = 0;
124 : :
125 : : do {
126 : 147765000 : jl_value_t *k2 = jl_atomic_load_relaxed(&tab[index]); // just to ensure the load doesn't get duplicated
127 [ + + ]: 147765000 : if (k2 == NULL)
128 : 10652900 : return NULL;
129 [ + + ]: 137112000 : if (jl_egal(key, k2)) {
130 [ + - ]: 93410900 : if (jl_atomic_load_relaxed(&tab[index + 1]) != NULL)
131 : 93410900 : 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 : 43700800 : index = (index + 2) & (sz - 1);
138 : 43700800 : iter++;
139 [ + + + + ]: 43700800 : } while (iter <= maxprobe && index != orig);
140 : :
141 : 857811 : return NULL;
142 : : }
143 : :
144 : : JL_DLLEXPORT
145 : 2394270 : jl_array_t *jl_eqtable_put(jl_array_t *h, jl_value_t *key, jl_value_t *val, int *p_inserted)
146 : : {
147 : 2394270 : int inserted = jl_table_assign_bp(&h, key, val);
148 [ + + ]: 2394270 : if (p_inserted)
149 : 2270510 : *p_inserted = inserted;
150 : 2394270 : 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 : 104926000 : jl_value_t *jl_eqtable_get(jl_array_t *h, jl_value_t *key, jl_value_t *deflt) JL_NOTSAFEPOINT
157 : : {
158 : 104926000 : _Atomic(jl_value_t*) *bp = jl_table_peek_bp(h, key);
159 [ + + ]: 104926000 : return (bp == NULL) ? deflt : jl_atomic_load_relaxed(bp);
160 : : }
161 : :
162 : : JL_DLLEXPORT
163 : 16796 : jl_value_t *jl_eqtable_pop(jl_array_t *h, jl_value_t *key, jl_value_t *deflt, int *found)
164 : : {
165 : 16796 : _Atomic(jl_value_t*) *bp = jl_table_peek_bp(h, key);
166 [ + - ]: 16796 : if (found)
167 : 16796 : *found = (bp != NULL);
168 [ + + ]: 16796 : if (bp == NULL)
169 : 6382 : return deflt;
170 : 10414 : jl_value_t *val = jl_atomic_load_relaxed(bp);
171 : 10414 : jl_atomic_store_relaxed(bp - 1, jl_nothing); // clear the key
172 : 10414 : jl_atomic_store_relaxed(bp, NULL); // and the value (briefly corrupting the table)
173 : 10414 : return val;
174 : : }
175 : :
176 : : JL_DLLEXPORT
177 : 7730990 : size_t jl_eqtable_nextind(jl_array_t *t, size_t i)
178 : : {
179 [ - + ]: 7730990 : if (i & 1)
180 : 0 : i++;
181 : 7730990 : size_t alen = jl_array_dim0(t);
182 [ + + + + ]: 121611000 : while (i < alen && ((void **)t->data)[i + 1] == NULL)
183 : 113880000 : i += 2;
184 [ + + ]: 7730990 : if (i >= alen)
185 : 7149550 : return (size_t)-1;
186 : 581439 : return i;
187 : : }
188 : :
189 : : #undef hash_size
190 : : #undef max_probe
|
