From: Eric Wong <normalperson@...>
Date: 2014-05-14T06:49:42+00:00
Subject: [ruby-core:62577] Re: [ruby-trunk - Feature #9614] [Open] ordering of non-Hash items which use st_ internally

Hi, thank you for the comments!

ko1: adding flag for ordering might complicate the st code even more.
I think st should only be for implementing Hash.

My primary goals for ihash are to reduce pointer chasing and malloc use.
ihash uses container_of, like ccan/list:

  st (unpacked entries):
    st_table -> st_table->bins -> st_table_entry -> data structure

  st (packed entries):
    st_table -> st_table->packed.entries -> data structure

  ihash:
    rb_ihash_table -> data structure (via container_of)

Removing ordering requirment allows us to avoid writing/maintaining more
(new) code and also save two pointers (fore/prev).

nobu: reduction depends on what is stored

Best case so far are method table and symbol table:

    For each method entry, we save:

        sizeof(st_table_entry) - sizeof(rb_ihash_node) + malloc_overhead

    On 64-bit with glibc malloc: 48 - 8 + 16 = 56 bytes saved.

    AFAIK, jemalloc has less overhead for small allocations, but even
    without malloc overhead, saving 40 bytes per method entry is great.

Symbol table is a big win, too, one single struct has membership
in both sym_id and id_str tables:

    struct rb_idsym {
        struct rb_ihash_node id_str_node; /* sizeof(void *) */
        ID id;
        struct rb_ihash_node sym_id_node;
        VALUE symstr;
        st_index_t hashval;
    };

    On 64-bit:
    Before: 48 + 48 = 96  (+ 32 bytes on glibc malloc)
    After:  40            (+ 16 bytes on glibc malloc)

    If we add ordering to Symbol.all_symbols, we only need one pair
    of list pointers and not two.  But I prefer to not need any :)

Worst case is only saving two pointers (ivar table); but I may look at
funny-falcon's sparse array for the ivar table.  I have not looked at
the local variable table, but it may be in the same class as ivar
tables and be better with a sparse array.


P.S.: I am also considering truncating rb_idsym.hashval to use as ID.
This will:
a) reduce per-symbol overhead by sizeof(st_index_t)
b) (hopefully) improve distribution for global method cach
   Measuring the effect of b) may be hard, though.