From: normalperson@...
Date: 2014-05-14T19:58:52+00:00
Subject: [ruby-core:62593] [ruby-trunk - Feature #9614] ordering of non-Hash items which use st_ internally

Issue #9614 has been updated by Eric Wong.


 ko1@atdot.net wrote:
 > Adding similar data structure can also increase complexity.
 > At least, I like same interfaces for such similar data structures.
 
 Right, I try to make ihash API like st (insert/update/foreach/lookup).
 However, there must be some differences due to data layout changes.
 
 e.g. delete could be implemented without a callback, so I call the new
 operation "unlink" instead.  Maybe "delink" is a less ambiguous name...
 
 > I think open addressing is better for such internal, small tables such as method table.
 > It doesn't need chain buckets.
 > 
 > So I wanted to extend st to introduce open addressing mode.
 
 Open addressing will probably work better for instance/local var tables
 with simple ID->(VALUE|long|ID) mapping (no struct behind the data).
 
 For larger structures like rb_method_entry/rb_const_entry, I think using
 container_of-based storage is best.  Open addressing may not make sense
 when using container_of, chaining was simpler and easier to match what
 st already does, so I chose chaining for ihash.

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

* 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/