hamstergem/hamster — pull request #153 by dubek (2014-10-31 00:12:05+00:00)
Title: Optimize Set#difference by using Trie#bulk_delete

Implemented Trie#bulk_delete which deletes several entries at once
without creating new temporary Trie objects on every delete operation.
This method is then used in Set#difference in order to its performance.

Benchmarks: https://gist.github.com/dubek/b3232b91dff2d33ae948 (in those benchmarks `old_difference` is the old implementation which performs successive calls to `Trie#delete`).

Let me know If you have ideas where this method can be used besides `Set#difference`.

As with the `bulk_put` implementation, this helps a lot with smaller sets (2x faster) and a bit less with larger sets (only 1.3x faster), because after the first level of entries we resort to the original `find_and_delete` method which creates temporary `Trie` for each entry deleted.

Also the `bulk_delete` came out pretty big, but it holds local state throughout its entire run (`new_entries, new_children`). Let me know if you can think of a good refactoring here to make it clearer (even though it's "internal").

One more thing: while testing earlier versions of it I found a bug that failed the specs only in about 1/10th of the runs. It was related to specific hash values for the keys (and those are seeded with a random value for each invocation of `ruby`). I wrote a script to run the specs in a loop until they fail so I'll be sure there are no such hidden bugs elsewhere).