next up previous
Next: Discussion Up: A Study in Program Previous: Negative Results with MBPR

The Mystery Cause Unmasked


Introns are almost always possible. Whenever a subtree's return value is ignored, that subtree is an intron. There are, however, ways of making introns easier to generate, and therefore more prevalent in programs. For example, in Regression-RPBR-X (20), (WRITE X Y) not only has no effect on memory, but in simply returning Y, it makes the X subtree an intron. The (READ X) function in the RPBR-X (20) runs does not create an entire intron subtree, but merely is an intron itself.

We see the following two ways in which introns can be detrimental to the search process:

  1. They can hamper search by providing locations where crossover can happen and have no effect on behavior.
  2. They can take up space in the tree and, if tree space is limited, may cramp the actual space for solutions.

In the experiments reported in this section, we attempt to differentiate between these two types of intron effects. Allowing larger maximum tree sizes should only alleviate the cramping effect of introns and not the search degradation effect. These experiments directly compare the effects of increasing maximum tree size on two different types of introns-those created by WRITE-ANSWER in the RPBR-X (0) case, and those created by sibling coordination interference in the MBPR (0) case. We assume (though there is disagreement about this) that the first of these two problems does occur; in our opinion, a wasted search step can do nothing but slow the search process.

Table 4: Regression with increased tree size limits

The runs in table 4:1 show the results of the Gudermannian problem runs, where the tree sizes are limited to 2000 nodes per tree (as opposed to 1000 nodes per tree in table 3). Notice that the computational effort of the RPBR and MBPR runs in table 3:4 and table 4:1 increases, but their ratio does not change significantly.

The ratio of the computational effort of the RPBR-X runs to the computational effort of the RPBR runs drops from 1.67 to 1.46 when the maximum tree size is increased from 1000 to 2000. Since nothing but the maximum tree-size has changed, and the control for the experiment (RPBR) takes approximately the same amount of time, this means that larger maximum tree sizes made it easier to solve the problem. The RPBR-X runs shown in table 4 differ from the RPBR runs only in that there is a single, useless function. The inert WRITE-ANSWER, because it passes its argument back up, does not even cause introns below it. This is very significant. Adding a single function can cause a run to take 1.67 times as long to complete (table 4:4) and increasing the maximum tree-size can reduce the penalty to 1.46 (2000 node limit). The question arises, ``What is the floor for this ratio?''

We see in table 4:2 that moving the maximum tree size to 5000 again has little effect on the RPBR runs or on the MBPR runs. The computational effort of the RPBR-X runs drops to 1.41 times that of the RPBR runs. This confirms our conclusion that the useless functions take up space and force the useful program fragments into a smaller space. By increasing the maximum tree size, this problem is greatly reduced. In the runs with 10000 node maximum tree size, the computational effort of the RPBR-X runs is 1.36 times the computational effort of the RPBR runs. While this is only slightly lower than the 1.41 just mentioned, it is close to the theoretical penalty for adding one useless function (X+1/X where X is the number of useful functions) which in this case is tex2html_wrap_inline578 or 1.25. Table 4:4 summarizes this trend.

Comparing the computational effort of the RPBR and the RPBR-X runs for the experiments shown in this section, we see a gradual reduction of the difference between the two as the maximum allowed tree sizes increases. In fact, it seems asymptotic to the theoretical penalty for adding a useless function to the function set.

The computational effort using the MBPR paradigm does not improve noticeably as the maximum tree size increases (table 3:4 and table 4). Thus, the negative effects caused by using the MBPR paradigm are not the cramping effects. This leaves only the ``search degradation'' intron effect as the explanation for MBPR's higher computational expense. This corresponds with the picture we have painted of the trade-offs between RPBR and MBPR. As the tree grows, the relative importance of vertical node interference and sibling coordination interference does not change.

next up previous
Next: Discussion Up: A Study in Program Previous: Negative Results with MBPR

Eric Teller
Tue Oct 29 16:58:50 EST 1996