Project

General

Profile

Feature #13174 ยป improve_id_table.patch

funny_falcon (Yura Sokolov), 01/31/2017 02:05 PM

View differences:

id_table.c
6 6
#define ID_TABLE_DEBUG 0
7 7
#endif
8 8

  
9
#if ID_TABLE_DEBUG == 0
10
#define NDEBUG
11
#endif
12
#include "ruby_assert.h"
13

  
14 9
typedef rb_id_serial_t id_key_t;
15 10

  
16 11
static inline ID
......
29 24
   uses mark-bit on collisions - need extra 1 bit,
30 25
   ID is strictly 3 bits larger than rb_id_serial_t */
31 26

  
32
typedef struct rb_id_item {
33
    id_key_t key;
34
#if SIZEOF_VALUE == 8
35
    int      collision;
36
#endif
37
    VALUE    val;
38
} item_t;
39

  
40 27
struct rb_id_table {
41 28
    int capa;
42 29
    int num;
43 30
    int used;
44
    item_t *items;
31
    id_key_t *keys;
45 32
};
46 33

  
47
#if SIZEOF_VALUE == 8
48
#define ITEM_GET_KEY(tbl, i) ((tbl)->items[i].key)
49
#define ITEM_KEY_ISSET(tbl, i) ((tbl)->items[i].key)
50
#define ITEM_COLLIDED(tbl, i) ((tbl)->items[i].collision)
51
#define ITEM_SET_COLLIDED(tbl, i) ((tbl)->items[i].collision = 1)
34
#define ITEM_GET_KEY(tbl, i) ((tbl)->keys[i] >> 1)
35
#define ITEM_KEY_ISSET(tbl, i) ((tbl)->keys[i] > 1)
36
#define ITEM_COLLIDED(tbl, i) ((tbl)->keys[i] & 1)
37
#define ITEM_SET_COLLIDED(tbl, i) ((tbl)->keys[i] |= 1)
52 38
static inline void
53 39
ITEM_SET_KEY(struct rb_id_table *tbl, int i, id_key_t key)
54 40
{
55
    tbl->items[i].key = key;
41
    tbl->keys[i] = (key << 1) | ITEM_COLLIDED(tbl, i);
56 42
}
57
#else
58
#define ITEM_GET_KEY(tbl, i) ((tbl)->items[i].key >> 1)
59
#define ITEM_KEY_ISSET(tbl, i) ((tbl)->items[i].key > 1)
60
#define ITEM_COLLIDED(tbl, i) ((tbl)->items[i].key & 1)
61
#define ITEM_SET_COLLIDED(tbl, i) ((tbl)->items[i].key |= 1)
43
#define ID_TABLE_VALUES(tbl) ((VALUE*)((tbl)->keys+(tbl)->capa))
44
#define ITEM_GET_VALUE(tbl, i) (ID_TABLE_VALUES(tbl)[i])
62 45
static inline void
63
ITEM_SET_KEY(struct rb_id_table *tbl, int i, id_key_t key)
46
ITEM_SET_VALUE(struct rb_id_table *tbl, int i, VALUE val)
64 47
{
65
    tbl->items[i].key = (key << 1) | ITEM_COLLIDED(tbl, i);
48
    ID_TABLE_VALUES(tbl)[i] = val;
66 49
}
67
#endif
50
#define ITEM_SIZE (sizeof(id_key_t) + sizeof(VALUE))
68 51

  
69 52
static inline int
70 53
round_capa(int capa)
......
86 69
    if (capa > 0) {
87 70
	capa = round_capa(capa);
88 71
	tbl->capa = (int)capa;
89
	tbl->items = ZALLOC_N(item_t, capa);
72
	tbl->keys = (id_key_t*)ruby_xcalloc(capa, ITEM_SIZE);
90 73
    }
91 74
    return tbl;
92 75
}
......
101 84
void
102 85
rb_id_table_free(struct rb_id_table *tbl)
103 86
{
104
    xfree(tbl->items);
87
    xfree(tbl->keys);
105 88
    xfree(tbl);
106 89
}
107 90

  
......
110 93
{
111 94
    tbl->num = 0;
112 95
    tbl->used = 0;
113
    MEMZERO(tbl->items, item_t, tbl->capa);
96
    memset(tbl->keys, 0, tbl->capa * ITEM_SIZE);
114 97
}
115 98

  
116 99
size_t
......
122 105
size_t
123 106
rb_id_table_memsize(const struct rb_id_table *tbl)
124 107
{
125
    return sizeof(item_t) * tbl->capa + sizeof(struct rb_id_table);
108
    return ITEM_SIZE * (size_t)tbl->capa + sizeof(struct rb_id_table);
126 109
}
127 110

  
128 111
static int
......
149 132
    int mask = tbl->capa - 1;
150 133
    int ix = key & mask;
151 134
    int d = 1;
152
    assert(key != 0);
135
#if ID_TABLE_DEBUG
136
    assert(key > 0);
137
#endif
153 138
    while (ITEM_KEY_ISSET(tbl, ix)) {
154 139
	ITEM_SET_COLLIDED(tbl, ix);
155 140
	ix = (ix + d) & mask;
......
160 145
	tbl->used++;
161 146
    }
162 147
    ITEM_SET_KEY(tbl, ix, key);
163
    tbl->items[ix].val = val;
148
    ITEM_SET_VALUE(tbl, ix, val);
164 149
}
165 150

  
166 151
static int
......
172 157
	}
173 158
	tbl->num--;
174 159
	ITEM_SET_KEY(tbl, ix, 0);
175
	tbl->items[ix].val = 0;
160
	ITEM_SET_VALUE(tbl, ix, 0);
176 161
	return TRUE;
177 162
    } else {
178 163
	return FALSE;
......
182 167
static void
183 168
hash_table_extend(struct rb_id_table* tbl)
184 169
{
170
    /* fill rate 66% */
185 171
    if (tbl->used + (tbl->used >> 1) >= tbl->capa) {
186
	int new_cap = round_capa(tbl->num + (tbl->num >> 1));
172
	struct rb_id_table tmp_tbl;
187 173
	int i;
188
	item_t* old;
189
	struct rb_id_table tmp_tbl = {0, 0, 0};
190
	if (new_cap < tbl->capa) {
191
	    new_cap = round_capa(tbl->used + (tbl->used >> 1));
192
	}
193
	tmp_tbl.capa = new_cap;
194
	tmp_tbl.items = ZALLOC_N(item_t, new_cap);
174
	id_key_t* old;
175
	VALUE* values = ID_TABLE_VALUES(tbl);
176
	rb_id_table_init(&tmp_tbl, tbl->num + (tbl->num >> 1) + 1);
195 177
	for (i = 0; i < tbl->capa; i++) {
196 178
	    id_key_t key = ITEM_GET_KEY(tbl, i);
197 179
	    if (key != 0) {
198
		hash_table_raw_insert(&tmp_tbl, key, tbl->items[i].val);
180
		hash_table_raw_insert(&tmp_tbl, key, values[i]);
199 181
	    }
200 182
	}
201
	old = tbl->items;
183
	old = tbl->keys;
202 184
	*tbl = tmp_tbl;
203 185
	xfree(old);
204 186
    }
......
228 210
    int index = hash_table_index(tbl, key);
229 211

  
230 212
    if (index >= 0) {
231
	*valp = tbl->items[index].val;
213
	*valp = ITEM_GET_VALUE(tbl, index);
232 214
	return TRUE;
233 215
    }
234 216
    else {
......
242 224
    const int index = hash_table_index(tbl, key);
243 225

  
244 226
    if (index >= 0) {
245
	tbl->items[index].val = val;
227
	ITEM_SET_VALUE(tbl, index, val);
246 228
    }
247 229
    else {
248 230
	hash_table_extend(tbl);
......
273 255
    for (i=0; i<capa; i++) {
274 256
	if (ITEM_KEY_ISSET(tbl, i)) {
275 257
	    const id_key_t key = ITEM_GET_KEY(tbl, i);
276
	    enum rb_id_table_iterator_result ret = (*func)(key2id(key), tbl->items[i].val, data);
277
	    assert(key != 0);
258
	    const VALUE val = ITEM_GET_VALUE(tbl, i);
259
	    enum rb_id_table_iterator_result ret = (*func)(key2id(key), val, data);
278 260

  
279 261
	    if (ret == ID_TABLE_DELETE)
280 262
		hash_delete_index(tbl, i);
......
291 273

  
292 274
    for (i=0; i<capa; i++) {
293 275
	if (ITEM_KEY_ISSET(tbl, i)) {
294
	    enum rb_id_table_iterator_result ret = (*func)(tbl->items[i].val, data);
276
	    const VALUE val = ITEM_GET_VALUE(tbl, i);
277
	    enum rb_id_table_iterator_result ret = (*func)(val, data);
295 278

  
296 279
	    if (ret == ID_TABLE_DELETE)
297 280
		hash_delete_index(tbl, i);
symbol.c
14 14
#include "symbol.h"
15 15
#include "gc.h"
16 16
#include "probes.h"
17
#include "ruby_assert.h"
17 18

  
18 19
#ifndef SYMBOL_DEBUG
19 20
# define SYMBOL_DEBUG 0
......
569 570
{
570 571
    rb_id_serial_t next_serial = global_symbols.last_id + 1;
571 572

  
572
    if (next_serial == 0) {
573
    if (sizeof(next_serial) >= sizeof(ID) &&
574
	    next_serial >= (rb_id_serial_t)(~(ID)0 >> (ID_SCOPE_SHIFT + RUBY_SPECIAL_SHIFT))) {
575
	return (ID)-1;
576
    }
577
    /* need at lest 1 bit for collision mark in id_table */
578
    else if (sizeof(next_serial) < sizeof(ID) &&
579
	    next_serial >= ~(rb_id_serial_t)0 >> 1) {
573 580
	return (ID)-1;
574 581
    }
575 582
    else {
......
708 715
	    VALUE fstr = RSYMBOL(sym)->fstr;
709 716
	    ID num = next_id_base();
710 717

  
718
	    if (num == (ID)-1) {
719
		fstr = rb_str_ellipsize(fstr, 20);
720
		rb_raise(rb_eRuntimeError,
721
				"symbol table overflow (symbol %"PRIsVALUE")",
722
				fstr);
723
	    }
724

  
711 725
	    RSYMBOL(sym)->id = id |= num;
712 726
	    /* make it permanent object */
713 727
	    set_id_entry(rb_id_to_serial(num), fstr, sym);
......
767 781
ID
768 782
rb_make_internal_id(void)
769 783
{
770
    return next_id_base() | ID_INTERNAL | ID_STATIC_SYM;
784
    ID nid = next_id_base();
785
    /* make_internal_id called very rarely during initialization,
786
     * so don't bother with exception */
787
    assert(nid != (ID)-1);
788
    return nid | ID_INTERNAL | ID_STATIC_SYM;
771 789
}
772 790

  
773 791
static int
774
- 
id_table.c
114 114
    if (tbl->capa > 0) {
115 115
	int mask = tbl->capa - 1;
116 116
	int ix = key & mask;
117
	id_key_t mix = tbl->capa > 64 ? key : 0;
117 118
	int d = 1;
118 119
	while (key != ITEM_GET_KEY(tbl, ix)) {
119 120
	    if (!ITEM_COLLIDED(tbl, ix))
120 121
		return -1;
121 122
	    ix = (ix + d) & mask;
122
	    d++;
123
	    d += 1 + (mix >>= 7);
123 124
	}
124 125
	return ix;
125 126
    }
......
131 132
{
132 133
    int mask = tbl->capa - 1;
133 134
    int ix = key & mask;
135
    id_key_t mix = tbl->capa > 64 ? key : 0;
134 136
    int d = 1;
135 137
#if ID_TABLE_DEBUG
136 138
    assert(key > 0);
......
138 140
    while (ITEM_KEY_ISSET(tbl, ix)) {
139 141
	ITEM_SET_COLLIDED(tbl, ix);
140 142
	ix = (ix + d) & mask;
141
	d++;
143
	d += 1 + (mix >>= 7);
142 144
    }
143 145
    tbl->num++;
144 146
    if (!ITEM_COLLIDED(tbl, ix)) {