8000 Merge pull request #2 from funny-falcon/mtbl · funny-falcon/ruby@b68e8ed · GitHub
[go: up one dir, main page]
Skip to content

Commit b68e8ed

Browse files
ko1ko1
committed
Merge pull request ruby#2 from funny-falcon/mtbl
id_table: some improvements on coalesced and quadratic algos
2 parents ba4258e + 3c194f8 commit b68e8ed

File tree

1 file changed

+56
-31
lines changed

1 file changed

+56
-31
lines changed

‎id_table.c

Lines changed: 56 additions & 31 deletions
Original file line numberDiff line numberDiff line change
@@ -317,6 +317,20 @@ ids_bsearch(const id_key_t *keys, id_key_t key, int num)
317317
{
318318
int p, min = 0, max = num;
319319

320+
if (num <= 64) {
321+
if (num > 32) {
322+
if (keys[num/2] <= key) {
323+
min = num/2;
324+
} else {
325+
max = num/2;
326+
}
327+
}
328+
for (p = min; p<num && keys[p] < key; p++) {
329+
assert(keys[p] != 0);
330+
}
331+
return (p<num && keys[p] == key) ? p : -p-1;
332+
}
333+
320334
while (1) {
321335
p = min + (max - min) / 2;
322336

@@ -584,11 +598,7 @@ rb_id_table_memsize(sa_table *table)
584598
static inline sa_index_t
585599
calc_pos(register sa_table* table, id_key_t key)
586600
{
587-
/* this formula is empirical */
588-
/* it has no good avalance, but works well in our case */
589-
key ^= key >> 16;
590-
key *= 0x445229;
591-
return (key + (key >> 16)) % table->num_bins;
601+
return key & (table->num_bins - 1);
592602
}
593603

594604
static void
@@ -604,16 +614,19 @@ find_empty(register sa_table* table, register sa_index_t pos)
604614
{
605615
sa_index_t new_pos = table->free_pos-1;
606616
sa_entry *entry;
617+
static unsigned offsets[][3] = {
618+
{1, 2, 3},
619+
{2, 3, 0},
620+
{3, 1, 0},
621+
{2, 1, 0}
622+
};
623+
unsigned *check = offsets[pos&3];
607624
pos &= FLOOR_TO_4;
608625
entry = table->entries+pos;
609626

610-
if (entry->next == SA_EMPTY) { new_pos = pos; goto check; }
611-
pos++; entry++;
612-
if (entry->next == SA_EMPTY) { new_pos = pos; goto check; }
613-
pos++; entry++;
614-
if (entry->next == SA_EMPTY) { new_pos = pos; goto check; }
615-
pos++; entry++;
616-
if (entry->next == SA_EMPTY) { new_pos = pos; goto check; }
627+
if (entry[check[0]].next == SA_EMPTY) { new_pos = pos + check[0]; goto check; }
628+
if (entry[check[1]].next == SA_EMPTY) { new_pos = pos + check[1]; goto check; }
629+
if (entry[check[2]].next == SA_EMPTY) { new_pos = pos + check[2]; goto check; }
617630

618631
check:
619632
if (new_pos+1 == table->free_pos) fix_empty(table);
@@ -731,14 +744,13 @@ insert_into_main(register sa_table* table, id_key_t key, st_data_t value, sa_ind
731744
static sa_index_t
732745
new_size(sa_index_t num_entries)
733746
{
734-
sa_index_t msb = num_entries;
735-
msb |= msb >> 1;
736-
msb |= msb >> 2;
737-
msb |= msb >> 4;
738-
msb |= msb >> 8;
739-
msb |= msb >> 16;
740-
msb = ((msb >> 4) + 1) << 3;
741-
return (num_entries & (msb | (msb >> 1))) + (msb >> 1);
747+
sa_index_t size = num_entries >> 3;
748+
size |= size >> 1;
749+
size |= size >> 2;
750+
size |= size >> 4;
751+
size |= size >> 8;
752+
size |= size >> 16;
753+
return (size + 1) << 3;
742754
}
743755

744756
static void
@@ -902,6 +914,9 @@ rb_id_table_foreach_values(sa_table *table, enum rb_id_table_iterator_result (*f
902914

903915
typedef struct rb_id_item {
904916
id_key_t key;
917+
#if SIZEOF_VALUE == 8
918+
int collision;
919+
#endif
905920
VALUE val;
906921
} item_t;
907922

@@ -912,16 +927,27 @@ struct rb_id_table {
912927
item_t *items;
913928
};
914929

915-
#define TBL_ID_MASK (~(id_key_t)1)
930+
#if SIZEOF_VALUE == 8
931+
#define ITEM_GET_KEY(tbl, i) ((tbl)->items[i].key)
932+
#define ITEM_KEY_ISSET(tbl, i) ((tbl)->items[i].key)
933+
#define ITEM_COLLIDED(tbl, i) ((tbl)->items[i].collision)
934+
#define ITEM_SET_COLLIDED(tbl, i) ((tbl)->items[i].collision = 1)
935+
static inline void
936+
ITEM_SET_KEY(struct rb_id_table *tbl, int i, id_key_t key)
937+
{
938+
tbl->items[i].key = key;
939+
}
940+
#else
916941
#define ITEM_GET_KEY(tbl, i) ((tbl)->items[i].key >> 1)
917942
#define ITEM_KEY_ISSET(tbl, i) ((tbl)->items[i].key > 1)
918943
#define ITEM_COLLIDED(tbl, i) ((tbl)->items[i].key & 1)
919944
#define ITEM_SET_COLLIDED(tbl, i) ((tbl)->items[i].key |= 1)
920945
static inline void
921946
ITEM_SET_KEY(struct rb_id_table *tbl, int i, id_key_t key)
922947
{
923-
tbl->items[i].key = (key << 1) | ITEM_COLLIDED(tbl, i);
948+
tbl->items[i].key = (key << 1) | ITEM_COLLIDED(tbl, i);
924949
}
950+
#endif
925951

926952
static inline int
927953
round_capa(int capa) {
@@ -989,9 +1015,8 @@ table_index(struct rb_id_table* tbl, id_key_t key)
9891015
d++;
9901016
}
9911017
return ix;
992-
} else {
993-
return -1;
9941018
}
1019+
return -1;
9951020
}
9961021

9971022
static void
@@ -1000,29 +1025,30 @@ table_raw_insert(struct rb_id_table *tbl, id_key_t key, VALUE val)
10001025
int mask = tbl->capa - 1;
10011026
int ix = key & mask;
10021027
int d = 1;
1028+
assert(key != 0);
10031029
while (ITEM_KEY_ISSET(tbl, ix)) {
10041030
ITEM_SET_COLLIDED(tbl, ix);
10051031
ix = (ix + d) & mask;
10061032
d++;
10071033
}
10081034
tbl->num++;
1009-
if (ITEM_COLLIDED(tbl, ix) == 0) {
1035+
if (!ITEM_COLLIDED(tbl, ix)) {
10101036
tbl->used++;
10111037
}
10121038
ITEM_SET_KEY(tbl, ix, key);
10131039
tbl->items[ix].val = val;
10141040
}
10151041

10161042
static int
1017-
id_table_delete(struct rb_id_table *tbl, int index)
1043+
id_table_delete(struct rb_id_table *tbl, int ix)
10181044
{
1019-
if (index >= 0) {
1020-
ITEM_SET_KEY(tbl, index, 0);
1021-
tbl->items[index].val = 0;
1022-
if (ITEM_COLLIDED(tbl, index) == 0) {
1045+
if (ix >= 0) {
1046+
if (!ITEM_COLLIDED(tbl, ix)) {
10231047
tbl->used--;
10241048
}
10251049
tbl->num--;
1050+
ITEM_SET_KEY(tbl, ix, 0);
1051+
tbl->items[ix].val = 0;
10261052
return TRUE;
10271053
} else {
10281054
return FALSE;
@@ -1133,7 +1159,6 @@ rb_id_table_foreach_values(struct rb_id_table *tbl, enum rb_id_table_iterator_re
11331159
for (i=0; i<capa; i++) {
11341160
if (ITEM_KEY_ISSET(tbl, i)) {
11351161
enum rb_id_table_iterator_result ret = (*func)(tbl->items[i].val, data);
1136-
assert(key != 0);
11371162

11381163
if (ret == ID_TABLE_DELETE)
11391164
id_table_delete(tbl, i);

0 commit comments

Comments
 (0)
0