Project

General

Profile

Actions

Feature #6962

closed

Use lighter hash structure for methods table, instance variable positions, constants

Added by funny_falcon (Yura Sokolov) over 11 years ago. Updated over 8 years ago.

Status:
Closed
Target version:
-
[ruby-core:47396]

Description

I've experimented with replacing struct st_table with lighter hash structure.

I were inspired by Lua tables, so that hash were created similar:

  • open addressing but with elements chaining instead of any kind of probing
  • there is sibling probing on insert, to ensure cache locality
  • on insert, already inserted collision item which is not in main position is moved to free place,
    so that chains started from different main positions are not joined.
    This allows to keep chains short.
  • struct header is 24 bytes on 64bit platform (compared with 40 bytes for st_table), so that i've
    placed them directly into rb_classext_struct instead of separate allocation.

Since keys are integers (ID), there is no separate field for hash. And I used unsigned int instead of
unsigned long for key, cause ID almost never reach 2**32. It allows to pack whole entry into 16 bytes
on 64bit platform (compared to 48 bytes for st_table_entry).

Such structure gives about 6% improvement without GC tuning, and 10% improvement when GC is tuned
(I've used RUBY_GC_MALLOC_LIMIT=60000000 RUBY_FREE_MIN=200000)

Also I add per class method cache instead of single global hash array. It has advantage over global
cache cause there is no collision over different classes and methods. But it seems that Rails applications
too often creates singleton classes, so that improvement is not very big (but no slowdown too).

Currently I have patch for Ruby 1.9.3 https://github.com/funny-falcon/ruby/compare/ruby_1_9_3...sparse_array/ruby_1_9_3

Single incompatible external api change is almost neglible, cause rb_generic_ivar_table methos is not very usefull
https://github.com/funny-falcon/ruby/compare/ruby_1_9_3...sparse_array/ruby_1_9_3#L5L852

Silly, but there is too many changes in trunk, so that, I could not simply rebase it, but ought to make whole work again.
I'll try to do it shortly.

With regards, Sokolov Yura aka funny-falcon.


Related issues 1 (0 open1 closed)

Related to Ruby master - Feature #11420: Introduce ID key table into MRIClosedko1 (Koichi Sasada)Actions

Updated by funny_falcon (Yura Sokolov) over 11 years ago

It seems that I'm using "Coalesced Hashing" http://en.wikipedia.org/wiki/Coalesced_hashing
with some improvements:

  • moving collision items which is not in its main position (as in Lua tables)
  • sibling probing for free items (test 4 closest items before using tablewise pointer to free position)

Updated by mame (Yusuke Endoh) over 11 years ago

  • Status changed from Open to Assigned
  • Assignee changed from matz (Yukihiro Matsumoto) to ko1 (Koichi Sasada)
  • Target version set to 2.6

ko1 or nobu, please check this (towards next minor).

--
Yusuke Endoh

Actions #4

Updated by ko1 (Koichi Sasada) over 8 years ago

Actions #5

Updated by ko1 (Koichi Sasada) over 8 years ago

  • Status changed from Assigned to Closed

Continue on Feature #11420.

Actions

Also available in: Atom PDF

Like0
Like0Like0Like0Like0Like0