8. Evaluation

The ultimate test for A$\lambda$goVista will be

(a)

whether theoreticians will be willing to extend the database with new problem specifications, and

(b)

whether the resulting database will actually provide useful information to practicing programmers.

Two secondary concerns are

(c)

whether security breaches can be prevented, and

(d)

whether the performance of the search engine will be adequate to ensure reasonable response time.

Unfortunately, most of these questions remain unanswered at this time, since A$\lambda$goVista has yet to be fully deployed and so far the authors are its only users.

We can, however, give some preliminary timing measurements to evaluate the relative performance of the two search algorithms.

Table 1 shows the search times for some typical queries. The times were collected by running each query four times and averaging the wall clock times of the last three runs. The reason for discarding the first measurement is that Java start-up times are quite significant and unpredictable. Furthermore, in web applications such as this one, programs are typically pre-loaded into (a large) primary memory and queries are fielded without any disk accesses.

 

The five columns of Table 1 show the query, the average wall clock times for the query using the exhaustive and the precomputed search, and the average wall clock times for generating all mutated queries using the exhaustive and the precomputed algorithms. In other words, the last two columns do not include the execution times of the checklets, just the time it takes to generate the transformed queries that would be submitted to the checklets.

Looking at Table 1 it is clear, as would be expected, the precomputed search algorithm is vastly superior to the exhaustive algorithm. However, it should be stressed that the comparison is inherently unfair. The exhaustive algorithm, although slower, will sometimes report results that the precomputed algorithm will overlook. The reason is that the precomputed algorithm limits the number of transformations that can be applied to a query, while the exhaustive one does not.

In our current implementation we limit the precomputed algorithm to apply at most six transformations. The hard-coded programs generated by the algorithms in Section 7 are rather large (even limiting the search to four mutations yields roughly 1.2 million lines of code over 20000 Java classes) and current Java tools are only barely able to handle programs of this size.