(2013/05/20 16:23), funny_falcon (Yura Sokolov) wrote:
> "sparse array" - is a lightweight hash structure which maps 32bit integers to st_data_t values.
> It is more compact and faster replacement for st_table for integers (aka st_init_numtable).
> It is CPU cache friendly on read, and it's hash function is tuned against ID pattern
> (tuned is a great word, I were just lucky. At least, every other "better" hash function,
>  like MurmurHash3 finalization, produce worse overall performance, and I could not explain why).
> 
> I've made it as a replacement for all usages of st_table as symbol table in my patch: methods,
> constants, ivars, - and it shows noticeable performance gain (~5-8%). When James Golick makes
> its method caching patch, I recommend him to use "sparse array", and he reports it efficiency.
> 
> It will be even better to embed sa_table into rb_classext_struct and do not allocate it separately.
> If patch will be accepted, I could made such change.

I got it (I don't check data strucuture details).

I prefer that it is similar name with st, for example, st_numtable_t, I
can associate with special case of `table'. But not strong opinion.

If st_init_numtable() returns st_table * but use sa.c functions, it
seems cool (OO-way). but additional branch cost (so high?).


> Considering uint64_t - it should be 64bit value, so that there is no need to check for overflow
> (even if one increments it 4_000_000_000 per second, it will take 70 years to overflow).
> So that, it should be
> 
>    #if HAVE_UINT64_T
>      typedef uint64_t version_t;
>    #else
>      typedef long long version_t ;
>    #endif

I understand your concern. My last suspicious is that I'm not sure `long
long' is always supported. however, i'm not sure there is such
environment, too. there is a similar discussion (we can assume 64bit
integer type or not). Experts may dicide it.

-- 
// SASADA Koichi at atdot dot net