How to write an automatic test for algorithmic complexity?

Initially, the task arose more from academic interest than from practical considerations. After I learned about Mock objects, I wondered if there was a situation for which you could write a test using a Mock object, but not using state tests. Literally the first thought that came to mind was about the computational complexity of the algorithms. Is it possible to write an automatic test verifying that an algorithm of a certain complexity is used in a specific situation?



The idea of ​​the solution is very simple: Suppose some algorithm processes the input data set. Then its algorithmic complexity is determined by the number and composition of operations performed on this set. If we apply Mock-objects to the input, which will count each call of its method, then after the algorithm is completed, we will be able to calculate the exact number and type of actions that were required for its work. It only remains to write the Assert statement.
')
Restriction: for this method it is essential to use static or dynamic polymorphism in order to make a substitution with a Mock object.

Let us demonstrate how this works on the example of C ++.

Let's start with the mock object. When working with data structures in C ++, it is required that the object has defined definition operations <and ==, as well as an assignment operator and a copy operator. The first two operations are object reading, and the last two are records. We write a class that will separately read read and write operations.

class Mock { public: Mock(): someValue(0){} Mock(int value): someValue(value) {} Mock(Mock const& other) { ++Mock::writeCounter; //    ++Mock::readCounter; //    this->someValue = other.someValue; } Mock& operator=(Mock const& other) { ++Mock::writeCounter; //    ++Mock::readCounter; //    this->someValue = other.someValue; return *this; } static int HasBeenRead() { return readCounter; } static int HasBeenWritten() { return writeCounter; } static void Clear() { readCounter = 0; writeCounter = 0; } private: int someValue; static int readCounter; //   static int writeCounter; //   friend bool operator==(Mock const& m1, Mock const & m2); friend bool operator<(Mock const& m1, Mock const & m2); }; int Mock::readCounter = 0; int Mock::writeCounter = 0; bool operator==(Mock const& m1, Mock const & m2) { Mock::readCounter += 2; //    return m1.someValue == m2.someValue; } bool operator<(Mock const& m1, Mock const & m2) { Mock::readCounter +=2; //    return m1.someValue < m2.someValue; } 

Let's test our idea with our idea on algorithms and data structures of the STL library of C ++ language.

The complexity of the bet in the list of O (Const).

 list<Mock> list; for(int i = 999; i >= 0; --i) list.insert(list.begin(), Mock(i)); cout << "Insert to list: read " << Mock::HasBeenRead() << " write " << Mock::HasBeenWritten() << endl; 

Output to console:

 Insert to list: read 1000 write 1000 

In the worst case, the complexity of the search in the linear array O (n).

 find(list.begin(), list.end(), Mock(999)); cout << "Find in list: read " << Mock::HasBeenRead() << " write " << Mock::HasBeenWritten() << endl; 

Output to console:

 Find in list: read 3000 write 1000 

Inserting n elements into a binary balanced tree has complexity of order O (n * log_2 (n)). I don’t know if there is any requirement in the C ++ standard about this, but in the STL library from Microsoft, the map is implemented on the basis of a binary balanced tree.
Calculate:

 map<Mock,int> map; for(int i = 0; i < 1024; ++i) map[Mock(i)] = i; cout << "Insert to map 1024 items: read " << Mock::HasBeenRead() << " write " << Mock::HasBeenWritten() << endl; 

Output to console:

 Insert to map 1024 items: read 65704 write 2048 

What can be said from this conclusion: first, there are two write operations to one object! This can be expensive for large objects without state separation. Secondly, of course, about 60 read operations per object are completely predictable - log_2 (1024) = 10, but you begin to feel the scale and understand why hash tables are good.

Could this be useful in practice?

Honestly, in my practice there were only three cases when it really came in handy, and then two of them were more needed to detect the problem than for the test itself.

1. About eight years ago I had to debug an application on Qt 4.0. The problem was this: when opening a certain form, the whole application started to slow down a lot. As soon as you close the form - the application works fine. The technique described in the article allowed me to find out that in Qt 4.0 all the controls that can receive and process events are in a linear list. When an event occurs, it goes through the entire list. Of course, if some control decides that it has processed the message, the message is not transmitted further along the chain. But, if there is no one willing to process the message, then it goes through the whole chain. As for example, an event about moving the mouse cursor over an application. So, the form that led to the brakes consisted of more than 400 controls! Externally, the form resembled a table of 20 columns and 20 rows, but this is only externally! The table was emulated using separate controls.
2. About 5 years ago we were approached by a new client with approximately the same complaint, but this application was already in the DevExpress library under C #. Unfortunately I forgot the details - but the problem was that there was a component inside the library that had complexity of the order of O (n ^ 4), instead of O (n ^ 2).
3. The server part of one of the projects we are currently engaged in is built on the model of actors . The system turned out to be rather complicated, therefore, in order to control the efficiency of processing incoming messages, tests are used that replace the original message with a special message that counts access to the message fields.