Compare performance to another operation about rspec-benchmark HOT 9 CLOSED

I usually take stackoverflow with a grain of salt, though its helpful in a lot of cases, it's hard to separate opinion from science. Let me dive into what I really mean.

I appreciate that a lot of people worry about halting problem, but I think that's a general computational problem not only applicable to complexity but actually a family of solvable problems.

Back to measuring complexity, I'm going to write code that will try to obtain efficiency of the code and decide what asymptotic function it resembles. You will write a matcher that will tell you whether the function under test has complexity matching, for example, linear characteristics or not.

The basic idea would be to have a family of predefined polynomials that roughly correspond to complexities. For example, f(x) = Ax + B is a linear function, and f(x) = Ax2 + Bx + C is another polynomial that can be equated with O(n2) complexity.

The algorithm would generate a power series of inputs which would be fed to function. For each input I could simply measure separately how many iterations are performed per unit of time. Then I would fit this measurements into a linear or power function.

Here is a research paper that not only provides foundations for this idea but also actually demonstrates a real tool that successfully models complexity of such tools as gzip or gcc. So in other words, yes it is possible in theory and practice.

Hopefully I will find some time round Christmas time to play around with this idea.

from rspec-benchmark.

Hi Omer,

Thank you for using the library!

How would you imagine this matcher to work? I'm not sure I fully understand the reason behind your intention for such matcher.

Currently provided matchers assume a single codebase under test. In your case you would only have one version of a method under test at any given time. Where would you keep your old codebase/method and why? If you all you want is to compare the two methods to decided if swap makes sense why don't you use Ruby inbuilt benchmark standard library?

Let us say that you have old method whose performance is asserted by the following matcher expect { ... }.to perform_under(0.2s) to be under 0.2s. If you happen to change your method implementation and it is 2x faster than previous one, you would simply change the matcher limit to at least 0.1s to prevent any regressions. In which case you would always guarantee that new method is faster than previous one and what is more important the test will ensure that it will never be slower.

from rspec-benchmark.

The test is useful for comparing between libraries for example.
Let's say I wrote a better algorithm for a certain task and I want to ensure that it is always faster than other implementations or fail the test suite.

I think the matcher should be something like: expect { foo }.to be faster_than { bar }

from rspec-benchmark.

When it comes to algorithmic complexity I was thinking of creating matchers that allow you to closely match given big O notation. For example, to say that you expect a given function foo to have performance characteristics of linear function etc... But this is very different from what you are suggesting.

I'm happy to review any code/implementation and add it to the suite of current matchers. Do you have time to work on this and submit PR? You can always look at source code and see how I've implemented the previous ones.

from rspec-benchmark.

I can try working on something soon. I'll add it to my to do list.

from rspec-benchmark.

I don't think analyzing Big O notation is possible. See http://stackoverflow.com/questions/480775/programmatically-obtaining-big-o-efficiency-of-code and http://stackoverflow.com/questions/635893/are-there-any-tools-that-can-determine-perform-code-analysis-for-big-o-complexit

from rspec-benchmark.

@thedrow Dmitry(@wilddima) has submitted a PR #3 that addresses this issue. Would you have time to review? I want to make sure what gets released is a matcher that is semantically correct and works well for everybody. Thanks

from rspec-benchmark.

Looks great and works like a charm!

from rspec-benchmark.

@thedrow @wilddima I've released v0.3.0 with the comparison matchers - enjoy!

from rspec-benchmark.