faster Hash#except and only
Reported by Grant Hollingworth | May 31st, 2008 @ 09:01 PM | in 0.9.4
The current version of Hash#except (and Hash#only) uses include?, which is incredibly slow if a long list of keys is patched.
This isn't important for the way Merb itself uses the methods, but I think it's still a worthwhile patch given that these are core extensions.
Comments and changes to this ticket
-
Cheah Chu Yeow May 31st, 2008 @ 11:57 PM
Can you post benchmarks? Something that shows performance before and after your patch and for small number of keys vs. large number of keys would be awesome (and I imagine would speed your patch on its way to inclusion in merb).
-
Grant Hollingworth June 1st, 2008 @ 08:54 PM
The _reject methods are the current ones; _each is from my patch. The big problem is that include? has to run == on most of the keys, for every key given. It's been a while since I used big-O notation, but I think it's O(n) vs O(n²).
small hash, 100 000 times
user system total real
except_reject 0.580000 0.000000 0.580000 ( 0.594527)
except_each 0.320000 0.000000 0.320000 ( 0.325864)
only_reject 0.580000 0.000000 0.580000 ( 0.581387)
only_each 0.240000 0.000000 0.240000 ( 0.239557)
big hash, 1000 times
user system total real
except_reject 7.390000 0.050000 7.440000 ( 7.507204)
except_each 1.740000 0.020000 1.760000 ( 1.794145)
only_reject 7.850000 0.050000 7.900000 ( 7.999839)
only_each 0.150000 0.000000 0.150000 ( 0.154863)
-
Grant Hollingworth June 1st, 2008 @ 08:58 PM
Maybe better formatting:
small hash, 100 000 times
user system total real
except_reject 0.580000 0.000000 0.580000 ( 0.594527)
except_each 0.320000 0.000000 0.320000 ( 0.325864)
only_reject 0.580000 0.000000 0.580000 ( 0.581387)
only_each 0.240000 0.000000 0.240000 ( 0.239557)
big hash, 1000 times
user system total real
except_reject 7.390000 0.050000 7.440000 ( 7.507204)
except_each 1.740000 0.020000 1.760000 ( 1.794145)
only_reject 7.850000 0.050000 7.900000 ( 7.999839)
only_each 0.150000 0.000000 0.150000 ( 0.154863)
-
Michael Klishin (antares) June 2nd, 2008 @ 09:34 AM
- → Milestone changed from “” to “0.9.4”
- → State changed from “new” to “resolved”
- → Assigned user changed from “” to “Michael Klishin (antares)”
I get even more boost for some reason. Thank you, applied and pushed to wycats' tree.
Please Login or create a free account to add a new comment.
You can update this ticket by sending an email to from your email client. (help)
Create your profile
Help contribute to this project by taking a few moments to create your personal profile. Create your profile »
