-
-
Notifications
You must be signed in to change notification settings - Fork 63
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
add performance tests #9
Comments
I could imagine implementing these tests by using a profiler to count the total number of bytecode instructions required when using bidict to accomplish some basic tasks, and then compare this to using two dicts kept in sync manually (baseline). (Wall clock times could be measured too.) The tests could then either pass or fail depending on whether bidict's results are within some threshold of the baseline results. Running these tests could also generate a more detailed report that would allow seeing how much a change to the code improves or degrades performance on the tests. Any suggestions on how to add something like this to our test suite, @tomviner? |
Would also be cool to see how performance with pypy compares to cpython. |
Put up a general note about performance at https://bidict.readthedocs.org/en/master/performance.html (in part to address some more or less well-founded concern from potential users -- see here and #1 + #1 (comment). Once we have performance tests running as part of CI, I can link to our results from various of those places. |
You can just use pytest-benchmark for performance tests. |
Thanks for the tip, @thedrow. Look forward to checking that out. |
You can see an example of the results I'm getting e.g. here. /cc @lordmauve in case this is of interest |
Yes. Looks correct. |
Thanks for taking a look @thedrow. Before I profile, I'd first like to adapt the current benchmarks to demonstrate the performance not just of a 10-item bidict, but rather the asymptotic behavior as number of elements increases. I'd like to confirm that bidict's space and time complexity is on the same order of the space and time complexity of manually keeping two inverse dicts in sync. Please let me know if you have any other suggestions, and thanks again! |
You can check out the latest work on this here: Check out the "benchmark" branch on Travis for the latest benchmark results. With these, I was able to make some micro-optimizations to The benchmarks are currently pretty crude, and I have doubts about how representative they are of real-world workloads (not to mention pytest-benchmark advises against running in a VM, which there's no way around on Travis). I'd love to work together with someone on this to check over and improve on this work. Anyone interested? @lordmauve, would love your take on this. Anyone interested, please ping me on Gitter and I'll look forward to getting these landed. |
Function call overhead is pretty high in Python. Maintaining two dicts manually, incline in your own code, would be pretty hard to beat due to the elimination of function call overhead. We're unlikely to get down to performance comparable to that without a C implementation. However, that's not to say that big improvements can't be made. The overhead of bidict for reads could be minimal. Inlining _put would help for writes. |
Thanks for taking a look, @lordmauve. I think the read performance is already good enough. As for the write performance, inlining While I was looking at this, I decided bidict's We could also consider adding a way to perform a bulk update that ignores new mappings that would clobber existing keys or values, rather than either allowing them to succeed or causing the entire update to fail. Does anyone think that would be worth it? Also, after doing the above, it made sense to change Could you please take a look at #33 and let me know what you think? I also left some questions in the benchmark tests I'd love some comments on. Thanks in advance, and hope you find these latest changes helpful. |
I just switched from the "overwrite" flags to the "collision behavior" abstraction, allowing for a third option besides "overwrite" or "raise": "ignore". PTAL! a039c42 |
As of f6227e9, got the test_bidict_init benchmark down to only ~3.5x slower on average than the test_invdict_init benchmark -- down from ~13x slower before. This is the fastest it's ever been, even compared to before the new atomicity guarantees were added. ✨ 🚀 ✨ |
Fixed in 0.12.0. |
...to verify that bidict performance is comparable to manually managing two dicts and catch any performance regressions.
The text was updated successfully, but these errors were encountered: