Some Notes on Testing

Test Code

There are several areas of test code:

• C++ functional tests.
• C++ performance tests.
• Python functional tests.

C++ Functional Tests.

The functional tests are run with a debug build of the C++ binary. In a debug build every operation on a skip list is checked before and afterwards with an integrity check. These integrity checks are thorough but expensive, see template <typename T> IntegrityCheck HeadNode<T>::lacksIntegrity() const in HeadNode.h for what checks are done.

Running these tests is as follows:

$ cd src/cpp
$ make debug
$ ./SkipList_D.exe
Running skip list tests...
                 test_very_simple_insert(): PASS
                      test_simple_insert(): PASS
             test_insert_and_remove_same(): PASS
             test_insert_remove_multiple(): PASS
                       test_ins_rem_rand(): PASS
              test_insert_n_numbers_same(): PASS
                                 test_at(): PASS
...
                doc_insert_remove_repeat(): PASS
Final result: PASS
Exec time: 19.5811 (s)
Bye, bye!

C++ Performance Tests.

Running the release version of the C++ code introduces some performance tests where the results are sent to stdout.

$ cd src/cpp
$ make release
$ ./SkipList_R.exe
Running skip list tests...
                 test_very_simple_insert(): PASS
                      test_simple_insert(): PASS
             test_insert_and_remove_same(): PASS
             test_insert_remove_multiple(): PASS
                       test_ins_rem_rand(): PASS
              test_insert_n_numbers_same(): PASS
                                 test_at(): PASS
               perf_single_insert_remove(): 451.554 (ms) rate x.xe+06 /s
                                                    ...
            perf_roll_med_odd_index_wins(): vectors length:  1000000 window width: 524288 time: x.x (ms)
                            perf_size_of(): size_of(       1):      216 bytes ratio:      216 /sizeof(T):       x
...
                doc_insert_remove_repeat(): PASS
Final result: PASS
Exec time: 127.5 (s)
Bye, bye!

This data is scraped from stdout to describe the Skip List Performance

Python Functional Tests.

There are some tests for the Python API in tests/. One of the reasons for creating a Python API was to use the most excellent Hypothesis to test the underlying C++ code.

Testing a Probabilistic Structure

One problem with probabilistic data structures like a skip list is deterministic testing. Along the way you discover particular corner cases that are worthy of testing the implementation against. Each case is completely prescribed by the order of insertion and the order of head/tail results generated by the virtual coin toss function. Whilst the former can be controlled by the test case the latter depends on the state of the pseudo random number generator and there lies the problem.

In this project this is solved in a novel way by seeding the random number generator with a value and seeing what head/tail sequence results. The random number generator is then brute forced with different seeds until every possible head/tail sequence of a certain length is obtained. A map is constructed that has {sequence : seed, ...} which can be use by any test to find the seed that will create the desired sequence. The random number generator is seeded with that value and the test is now deterministic.

The function that creates a dictionary is find_seeds_for_sequences() in tests/unit/seed_tree.py. It is tested in tests/unit/test_seed_tree.py. You can see it at work in tests/unit/test_cSkipList.py where SEED_DICT is created using the C rand() function exposed through cSkipList.seed_rand() and cSkipList.toss_coin(). There are various tests in there that specify a sequence of coin tosses and inject nodes that require that sequence.