hamstergem/hamster — pull request #89 by alexdowad (2014-06-02 08:15:56+00:00)
Title: Much faster Hamster::Hash.new (use destructive operations while initiali...

This patch gives about a ~4x speed boost to initialization of a new `Hamster::Hash` using an existing `Array` or Ruby `Hash`.

Currently, `Hamster::Hash.new` builds a new structure using `#put`, which (necessarily) copies trie nodes. If you pass in 10,000 key-value pairs, it has to copy more than 20,000 nodes, most of which become eligible for garbage collection almost immediately.

As a user of the library, I am happy to receive an immutable structure, but I don't care if only immutable operations were used to build that structure. Rather than generating 9,999 intermediate `Hamster::Hash` objects, I would be quite happy if just one is created and mutated into the state which I want. This way, there is less pressure on the garbage collector and things happen much more quickly.

Don't take my word for it, see for yourself:

```
~/Programming/Ruby/hamster $ pry
[1] pry(main)> h = Hash[*(1..10000)];
[2] pry(main)> require 'hamster'
=> true
[3] pry(main)> require 'benchmark'
=> true
[4] pry(main)> puts Benchmark.measure { Hamster::Hash.new(h) }
0.020000 0.000000 0.020000 ( 0.016986)
=> nil
[5] pry(main)> exit
~/Programming/Ruby/hamster $ git stash
Saved working directory and index state WIP on master: f34f3e2 We want to be able to pre-release the gem.
HEAD is now at f34f3e2 We want to be able to pre-release the gem.
~/Programming/Ruby/hamster $ pry
[1] pry(main)> h = Hash[*(1..10000)];
[2] pry(main)> require 'benchmark'
=> true
[3] pry(main)> require 'hamster'
=> true
[4] pry(main)> puts Benchmark.measure { Hamster::Hash.new(h) }
0.060000 0.000000 0.060000 ( 0.074720)
=> nil
```