14

Let's say I am implementing something simple like searching a sorted list/array. The function (in c#) would look similar to:

static int FindIndex(int[] sortedList, int i);

I could implement and test this in terms of functionality, but for obvious reasons I would usually prefer a binary search over a linear search or something intentionally stupid.

So my question is: Should we attempt to write tests that guarantee performance in terms of algorithmic complexity and if so, how?

I have started making arguments on both sides of the "should you" part of this question, but I'd like to see what people say without my arguments to prompt them.

In terms of "how", that gets very interesting:) You could see parameterizing the comparison operator and having a test whose comparison operator counts comparisons or something like that. But just because you can doesn't mean you should...

Has anyone else considered this (probably)? Thanks.

Improve this question
2
  • @steenhulthin--I'll let this simmer here and check that out. I hadn't ever been there. Commented Aug 10, 2011 at 19:47
  • btw, nice question. +1 Commented Aug 10, 2011 at 20:11

5 Answers 5

Reset to default
13

Algorithmic complexity is a theoretical construct and as such it's best "tested" with a pencil and paper. It can't be usefully tested mechanically.

Absolute performance can be tested mechanically and can make useful unit tests. If performance matters, then you can specify a threshold: "this query should take no more than 50ms to run on 106 numbers, and no more than 60ms on 107 numbers." That you can build a unit test for.

The end user doesn't care whether your algorithm is linear or logarithmic; they care whether their UI still responds instantly even when they've got a year's worth of data in the app.

Improve this answer
4
  • This is my instinct as well. But what got me thinking about it is when performance gaurantees on frameworks. Example: if I recall correctly, the stl has some gaurantees around algorithmic complexity (could be off here). Commented Aug 10, 2011 at 22:48
  • Just because a library provides some guarantees doesn't mean they have to be unit-testable. Commented Aug 10, 2011 at 23:14
  • @Tobias Brick: Testing something and defining something are two different things. Commented Aug 11, 2011 at 15:05
  • Demonstrating performance is tough. It involves lots of sample points for varying parameters. It is easier when the individual functions are trivial, but beyond that ... Your load, your RAM, front bus speed, CPU, number of cores, compiler aggressiveness, degree of pollution of the registry will all affect the run time of a particular sample. Commented Aug 11, 2011 at 15:11
3

While I'm not sure if this tool will be particularly useful for unit tests, the paper "Empirical Computational Complexity" by Goldsmith, Aiken, and Wilkerson describes a method for instrumenting code and observing its dynamic behavior on a set of various inputs to empirically derive its asymptotic complexity. The program described in the paper is open-source and is available here.

Hope this helps!

Improve this answer
0

The main thing is try it with big data and see if it takes too long.

In my performance tuning experience, as in this example, what happens is if some algorithm is (for example) O(n^2) it may be just fine as long as the percent of time it takes never gets onto the radar.

However, when it is given a dataset of a size that might not be seen but once a year, the fraction of total time sucked up by that algorithm may become catastrophically dominant.

If you can make that happen in testing, that is a very good thing, because it's supremely easy to find the problem, just as if it were an actual infinite loop.

Improve this answer
0

I do not think what you wanna do is Unit Testing.

AFAIK, unit testing is only to make sure the code does what it should do and it does not focus on performance.

From Wikipedia: Testing cannot be expected to catch every error in the program: it is impossible to evaluate every execution path in all but the most trivial programs. The same is true for unit testing. Additionally, unit testing by definition only tests the functionality of the units themselves. Therefore, it will not catch integration errors or broader system-level errors (such as functions performed across multiple units, or non-functional test areas such as performance). Unit testing should be done in conjunction with other software testing activities. Like all forms of software testing, unit tests can only show the presence of errors; they cannot show the absence of errors.

There are other kinds of tools and patterns to measure performance. One of that I can remember now is Acceptance testing focused on non functional requirements.

There are few others like performance testing (which uses stress testing, load testing, etc).

You also could use some stress tools together with a build tool (ant, automated build studio) as part of your deployment steps (that is what I do).

So the short answer is no, you should not worry about that when unit testing a code.

Improve this answer
0

Passing in the comparator and having that keep track of the number of times it is called will work for simple purposes such as checking that the number of comparisons when doing a search in a fixed input (say new int[] { 1,2,3, ... , 1024 }) stays below 10. That'll at least make clear your intentions about how the algorithm is supposed to behave.

I don't think unit tests are the right way to go to verify that your algorithm is O(log n); that would need a lot of random data generation, some curve fitting, and probably gnarly statistics to determine whether a bunch of data points fits the expected runtime. (For this algorithm it's probably doable, but if you start getting to sorting etc it will become difficult to repeatably hit the worst case scenarios).

Improve this answer

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.