Goto Chapter: Top 1 2 3 4 5 Bib Ind
 Top of Book   Previous Chapter   Next Chapter 

5 Performance Issues
 5.1 Time and Space Complexity
 5.2 Performance Penalty for non-C(4) Monoids and Semigroups.

5 Performance Issues

This chapter briefly discusses some performance issues with the use of the SmallOverlap package.

5.1 Time and Space Complexity

Most of the routines implemented require time and space which is quadratic in the presentation lengths, and linear in the element lengths. For a detailed complexity analysis of the algorithms see [Kam07].

5.2 Performance Penalty for non-C(4) Monoids and Semigroups.

We have already remarked that the small overlap equality test method is not automatically installed, since testing whether small overlap methods are applicable inevitably imposes a slight performance overhead when computing with monoids in which they turn out not to be applicable. More precisely, when the equality test method is installed:

In addition, one could almost certainly construct examples of C(4) monoids where the standard GAP equality test algorithm (reduction to normal form using a confluent rewriting system created by Knuth-Bendix completion) runs even faster than the small overlap algorithm. In practice the latter is so fast that in such a case it is unlikely to matter much which algorithm is used but, once again, performing very large numbers of equality tests in such a monoid could in principle be slower with the small overlap routines.

For most purposes these penalties are negliglible, and since the vast majority of monoids do satisfy C(4), likely to be vastly outweighed by the time saved by using small overlap methods where applicable. Hence, unless you are performing very large numbers of equality tests, and moreover have definite reason to believe that a large proportion of these will be in monoids not satisfying C(4), we strongly recommend that you call PreferSmallOverlapEqualityTest.

 Top of Book   Previous Chapter   Next Chapter 
Goto Chapter: Top 1 2 3 4 5 Bib Ind

generated by GAPDoc2HTML