From: murphy <murphy@...>
Date: 2007-10-09T11:41:50+09:00
Subject: Re: Ordered Hashes in 1.9?

Yukihiro Matsumoto schrieb:
> |It really seems that 1.9 got ordered hashes by default. Can anyone 
> |confirm my observations?
> Yes, it preserves order of keys inserted.
Very nice!

Does it affect speed? I would expect:
* deletion and insertion to be a bit slower (more pointers to set);
* travering a hash (which is more common) to be faster;
* fetching a value by key to be as fast as before (no list involved).

I see that the actual values are defined in st_table_entry:

  struct st_table_entry {
      unsigned int hash;
      st_data_t key;
      st_data_t record;
      st_table_entry *next;
      st_table_entry *fore, *back;
  };

(Mostly described in http://rhg.rubyforge.org/chapter03.html.)

In st_table, only the *head is stored...so it is actually a
doubly-circularly-linked list:

* table->head is the first element, or 0 for empty tables.
* table->head->fore is the second element, and so on.
* table->head->back is the last element (and tail of the list.)
* for each element: el->back->fore == el and el->fore->back == el.

So, the st_table isn't really ordered, but st_foreach() makes use of the
fore and back pointers so that items are traversed in insertion order.

If st_table is ordered now, we also have the nice effect that method
lists are ordered, first by inheritance, then by definition order:

  class Foo
    def first; end
    def second; end
  end
  Foo.new.methods[1]   # => :second

Hooray for Ruby 1.9 :)
[murphy]