HOWTO Create performance kata and tests for them

[hobovsky]

Motivated by #233

Create a HOWTO on how to write performance kata and how to verify them.

JohanWiltink here: #233 (comment)

I would like to see a little more technical explanation of the why and the how of performance testing. Too often authors, even experienced ones, think stress testing a solution simply means running tests for 9 seconds. If you're testing for O(n) as opposed to O(n^2), testing can succeed in milliseconds for a compliant solution, and consistently time out for an uncompliant one, if your ( few ) inputs are big enough ( but not too big, obviously ).

JohanWiltink on Gitter:

Hi!

I appreciate that you don't want to make mistakes ( I don't either! ), but in places the documentation now feels like you're traipsing around the hot sticky mess to prevent having to actually mention O(n) or O(n^2). As the text stands, you very much have to read into it how to do adequate performance testing. I think having one specific example might require less interpretation by people who already don't know what they're doing very well. This is a bit of a general feeling, and there is one place where you actually mention the actual words "time complexity", but it's all so vague and general.

I think allowing that some guidelines will not apply to some kata, but being more specific, would work better than just writing guidelines, and just in such a way, that everything is applicable to everything. I don't think there is an expectation that all of the documentation will fully apply to all of the kata.

[XRFXLP]

Time complexity alone doesn't capture the performance required in any kata, in reality constant factors and other subtleties should be considered.

Two O(n) solution, one with single pass of entire data structure and other having multiple but constant passes will have different running time, it would be better if author mentions the maximum number of passes over the data structure one can do.

---

I've found many of the time that author has created a performance kata but his own solution is very slow, I think in this case the problem is obvious to author, but it would be better if this point is stressed in the documentatons.