[ruby-core:70356] Re: [Ruby trunk - Feature #11420] [Open] Introduce ID key table into MRI

On 2015/08/13 4:29, Юрий Соколов wrote:
> I thought to suggest to embed hash_id_table directly into places when it
> is used (instead of pointer to).
> It will use 24byte on 64bit platform, so not too big.
> It has benefit when used with jemalloc/tcmalloc which are good at
> allocating sizes = 2**x.
> With flexible array size will be not equal to power of 2, so that they
> will consume a bit more memory on big tables.
> 
> But I think flexible array are also very good idea.
> Let me know, if I need to fix hash variant for this.

For flexible array, I'm negative because it can conflict usage like
updating tables during foreach, and so on. Just now, we need to clear
usages first. I think impact of flexible array is not so big (compare
with current implementation), or so big?

For embedding tables, I also negative because we need to expose table
data structure for users. Just now, I want to hide it into id_table.c.
Of course, if we decide this implementation finally, we can try it.

> It will use 24byte on 64bit platform, so not too big.

struct hash_id_table {
    int capa;
    int num;
    int used;
    item_t *items;
};

Can we eliminate `used'? If we can remove it, table size will be 16B.

I understand used and num is not same (used counts delete empty,
collited entries), but `used' is used only for extension. How about to
use num for this purpose? Sorry if I misunderstood.


> btw, I'm trying to improve st_table itself by allocating items in a
> continuous array and using indices instead of pointers
> between them. It should decrease allocation pressure and improve cache
> locality, but has drawback of size limit
> (2 billion items) and not releasing space on every deletion.

like that?

 struct entry {
   hash, key, val, next;
 } entries[capa];
 struct entry *bins[capa]
#=>
 bins   : [ ... ]
 entries: [[hash1, key1, val1, next], ...]

I also consider similar idea because this structure does not need
prev/forward pointers to achieve ordered hash.

> releasing space on every deletion

Generally, deletion is not frequent. One idea is that we can fallback
from this data structure to current st implementation dynamically when
deletion count go over threshold (yes, I like mix approach).

> 'btw take 2' Dit you see new PHP7 `array` implementation ?
> https://nikic.github.io/2014/12/22/PHPs-new-hashtable-implementation.html
> PHP array is the same logical data-structure as Ruby Hash, so we could
> try their implementation decision as well.
> Most hashes are only filled, with no deletion called, so that this
> construction is really great in term of speed,
> memory locality and memory consumption.
> It has drawback for huge long-living hash with continuous insertions and
> deletions (it should be periodically reordered).

same as "first btw"?

-- 
// SASADA Koichi at atdot dot net