[ruby-core:64952] [ruby-trunk - Feature #9614] ordering of non-Hash items which use st_ internally

Issue #9614 has been updated by Eric Wong.


 I forget, ordering is easy to add to ihash with ccan/list.
 
 Work-in-progress, this is only for method entries with ihash ordered
 doing "ruby -e exit" (loading rubygems)
 
 Numbers from valgrind, so "bytes allocated" does not take into account malloc
 overhead of particular malloc implementations:
 
 st (original):
   total heap usage: 48,119 allocs, 19,169 frees, 8,106,443 bytes allocated
 
 ihash-unordered
   total heap usage: 45,571 allocs, 19,501 frees, 8,038,885 bytes allocated
 
 ihash-ordered:
   total heap usage: 45,571 allocs, 19,501 frees, 8,089,941 bytes allocated
 
 The reduction in overall malloc/free calls is nice; but bytes allocated
 is small because we're dealing with small elements.  This makes method
 entries much bigger (1 pointer for hash chaining, 2 pointers for
 list_node), but reduces the need to make separate allocations for
 st_table_entry.
 
 1. http://bogomips.org/ruby.git/patch/?id=3930d8172dea41cd
    ihash: initial implementation
 2. http://bogomips.org/ruby.git/patch/?id=02334f26a0c2a1f5
    convert method entries to unordered ihash
 3. http://bogomips.org/ruby.git/patch/?id=fcf8e764bcd5a1c1
    preserve ordering in method entries
 
 git clone git://bogomips.org/ruby.git branch=ihash7
 
 (I also started working on constants, but haven't added ordering, yet).
 
 Running benchmark suite now, I expect uncached method entries for larger
 classes/modules should be faster due to reduced indirection as described
 in [ruby-core:62578]
 
 For small (currently <=5) element tables, it is like st-packed and does a
 linear search (which will cross cache lines, unfortunately)

----------------------------------------
Feature #9614: ordering of non-Hash items which use st_ internally
https://bugs.ruby-lang.org/issues/9614#change-48839

* Author: Eric Wong
* Status: Open
* Priority: Normal
* Assignee: Yukihiro Matsumoto
* Category: core
* Target version: current: 2.2.0
----------------------------------------
Hi matz, I would like your permission to remove the order preservation from
any or all of the following currently implemented using `st_table`:

* method tables
* global symbols (`Symbol.all_symbols`)
* constant tables
* instance variable tables
* `global_variables` method
* `Thread#keys`
* anything besides the `Hash` class

I am currently working on a patch series to reduce internal memory usage,
so far I have only converted three pieces:

1. method tables (~200K reduction)
2. symbol table (`global_symbols.`{`id_str`,`sym_id`}) (~200K)
3. `frozen_strings` (~100K)

n.b. `frozen_strings` ordering is never exposed to users, so I expect
it to be OK.

Memory reduction is just based on "`ruby -e exit`" (which loads RubyGems);
bigger programs with more methods/symbols will save more memory.

Work-in-progress patches attached (0002 describes implementation details)


---Files--------------------------------
0001-adjust-tests-to-account-for-unsorted-methods.patch (1.87 KB)
0002-ihash-initial-implementation-method-table-conversion.patch (32.8 KB)
0004-ihash-implement-rb_ihash_update-to-support-rb_fstrin.patch (7.84 KB)
0003-parse.y-switch-to-ihash-saves-200K-out-of-the-box.patch (9.51 KB)


-- 
https://bugs.ruby-lang.org/