Selected topics in software development

Quarter 3, 2008

Testing assignment

The purpose of this assignment is to produce a release of the main components of the CPH STL (www.cphstl.dk). The idea is that the groups created in connection with the previous assignment will continue their work with the component inspected. (If you for some reason want to take another component, this is also possible.)

The focus in this assignment is on (unit, component, regression, and system) testing. For most components it is necessary to correct some minor design errors and to refactor the code. Of course, defects found during the inspection should also be corrected. In particular, the following improvements have been proposed by other developers:

1. Every container should be implemented as a bridge class that calls the functions available in the actual realization which is given as a template parameter to the bridge. (Examples how these bridges are to be implemented can be found in [3,4].)
2. In the CPH STL, the running-time requirements stated in the C++ standard should be fulfilled in the worst case, not only in the amortized sense or in the average case. (This may be relevant for some operations on vector, deque, and iterators.)
3. In the CPH STL, each component should use at most linear space, linear on the number of elements currently stored. (This may be a problem for some vector implementations.)
4. In the cphstl namespace, name pollution should be avoided so the subcomponents used should be packaged inside another namespace.
5. Property maps should not be used any more, but the methods inside the property maps should be moved to the node class which is given as a configuration parameter for the realization, i.e. the "move method" refactoring should be done. (This is relevant for the existing search-tree and priority-queue realizations.)
6. As of now, most implementations in the CPH STL use allocator::construct and allocator::destroy for construction of both simple types (e.g. pointers) as well as elements. A drawback to this approach is that constructors are not used and the efficiency of initializer lists is lost. Evidence suggests that using placement new instead results in large performance gains, at the cost of not supporting side effects of allocator::construct and allocator::destroy---the support of which is not required by the C++ standard (see §20.1.5). Types size_type, difference_type, pointer, const_pointer, reference, and const_reference should be set by default to size_t, ptrdiff_t, value_type*, value_type const*, value_type&, and value_type const&, respectively, as allowed by the C++ standard (instead of just using the types passed by the given allocator). This restriction is already posed by most STL implementations (GNU, Microsoft, Borland, and SGI to name a few). (This light-weight usage of allocators is already used in [2,5].)

7. Many of our current implementations use a hierarchy of base classes for allocators and comparators to avoid the extra memory of making them member variables. Incorrectly, it was assumed that this would allow empty-base-class-optimization to take place. It has been shown that this hierarchy of base classes introduce the same memory burden as the member-variable approach, so reverting to the old approach would be preferable due to the clarity of code---and most likely due to the efficiency.

When determining which other improvements may be relevant for your component, you are welcome to contact the original authors of the component and/or the teachers of this course.

When testing the component and when improving its quality, the tools introduced on the page [7] may be relevant for you. In addition to extensive black-box testing, you may consider using the Boost concept archetypes [6] for checking the concept correctness, DDD [9] for debugging, Valgrind [8] for finding memory leaks and for profiling, and Benz [1] for benchmarking. It may also be relevant to perform a static analysis of the coding style and the coverage analysis of the test cases used. At the moment, we do not know any tools to test whether iterator-validity and exception-safety requirements are fulfilled. At all times try to use (or develop) tools that could be used by other developers as well.

The output of your work should be a test report written using the LaTeX style DIKU-article.sty. The length of this report should at most 12 pages, excluding the appendix which should contain the code developed during the course of this work. (You may use the listings package as in [3,4] for presenting the code.) Check in all relevant files into the CPH STL repository under the module Release. (Do frequent commits!) Name the directory clearly such that one immediately knows which component/realization is in it. Inside your directory use four subdirectories Report, Code, Test, and Benchmark that contain the test report, the source code, the tests run, and the benchmarks performed. In general, the repository should not contain any auto-generated files (like PDF files), but makefiles that can be used to reproduce the auto-generated files from the original sources. Also, all tests and benchmarks should be easily reproducible.

Recall that the weight of this assignment is 20% of the whole course credit. Additionally, in the first half of the exam (individual) you are expected to present the outcome of this assignment. That is, this will give an additional weight of 15% for this assignment (including your presentation at the exam). The evaluation will be based on the thoroughness of your work and the progress you make during the assignment period.

References

[1]

CPH STL: Tools used in the project [html]

[2]

Kasper Egdø: 2-3 heaps, Internal CPH STL progress report available at Report/Meldable-priority-queues/Kasper-2-3-heaps

[3]

Jyrki Katajainen: Project proposal: A meldable, iterator-valid priority queue, CPH STL report 2005-1 [pdf]

[4]

Jyrki Katajainen: Project proposal: Associative containers with strong guarantees, CPH STL report 2007-4 [pdf]

[5]

Jens Rasmussen: Implementing relaxed weak queues, CPH STL report 2008-1 [pdf]

[6]

Jeremy Siek and Andrew Lumsdaine: The Boost concept check library [html]

[7]

Students of the course "Generic programming and library development": Essays on tools [html]

[8]

Valgrind developers: Valgrind [html]

[9]

Andreas Zeller and Andrew Gaylard: Data display debugger [html]