Hashie::Mash deep_merge is super O(2^n) slow

[davemitchell]

Mash's deep_merge is recursively invoked 2^n times, where n is the depth of the other_hash parameter. For instance,

 x = Hashie::Mash.new()
 x.a!.b!.c!.d!.e!.f!.g!.h!.i!.j!.k!.l!.m!.n!.o!.p!.q!.r!.s!.t = 0
 y = Hashie::Mash.new(x)

...will call deep_merge over a million times (2^20), taking 10-15 seconds to complete.

I've made an a O(n) fix in which deep_merge is only invoked 20 times for the above example, with sub-millisecond response. Will submit a pull request momentarily.

[masatomo]

This issue is actually critical. Without this patch, a request with just 10 elements of array takes more than 30 seconds.

I strongly recommend to merge this patch and release new version of Hashie asap. We are using the @davemitchell's forked repo until this is merged. (thank you so much for this patch, @davemitchell !)

[johnae]

Yeah I second that. Just did a bundle update on another gem and along came Hashie 2.0.5 - specs became 10x slower all because of Hashie. Took me two hours to understand what happened.

[johnae]

@jch @wapcaplet @markiz @craiglittle @7even @jimeh @davemitchell hey guys this issue is a big one really, this pull request shouldn't just be sitting here for months. 2.0.5 is unusable in it's current state.

[jch]

Sorry, I was helping, but I lost access after leaving Intridea. The project
doesn't seem actively maintained, perhaps it's time to find a new
maintainer?

On Tuesday, October 8, 2013, John Axel Eriksson wrote:

@jch https://github.com/jch @wapcaplet https://github.com/wapcaplet
@markiz https://github.com/markiz @craiglittlehttps://github.com/craiglittle
@7even https://github.com/7even @jimeh https://github.com/jimeh
@davemitchell https://github.com/davemitchell hey guys this issue is a
big one really, this pull request shouldn't just be sitting here for
months. 2.0.5 is unusable in it's current state.

—
Reply to this email directly or view it on GitHubhttps://github.com//issues/106#issuecomment-25883756
.

-Jerry
@whatcodecraves http://twitter.com/whatcodecraves
github http://github.com/jch

[dblock]

I am taking over. The fix has now been merged on master and I will make a release this week after I've gone through all the pending PRs.

[davemitchell]

sweet!