From: bwc@raven.mbir.bcm.tmc.edu (Robert Cottingham)
Newsgroups: bionet.molbio.gene-linkage
Subject: LINKAGE speed up
Date: 14 Apr 1992 19:45:47 GMT
Reply-To: bwc@raven.mbir.bcm.tmc.edu (Robert Cottingham)
Originator: bwc@raven.mbir.bcm.tmc.edu



First I want to thank all of the people who responded to my request
last month for information regarding LINKAGE in C.  The upshot is that
using p2c to translate the code seems to be totally successful in our
experience so far.  Several of the respondents also related their
surprize at how well p2c worked.  To date I am unaware of any human
modification necessary to use the C code out of p2c.  We are working
in a Sun environment.

Although my goal is to apply the programs to some type of parallel
architecture, so far we have been only looking at the sequential code
performance, since carrying over any problems here into a parallel
environment would only amplify the inefficiencies.  Also, this is an
exercise that helps us become more familiar with how the code
functions.  The main reason for wanting the code in C, was so that we
could use performance analysis tools which do not work with Pascal.

The most significant performance problem we found so far is the
following

      PROCEDURE segdown;

      VAR
        here:1..maxfem;
        gene:genotype;
        val,temp1,temp2:real;
        f1,f2,s1,s2,i,j,first,second:integer;

      BEGIN
        initseg;
        FOR here:=1 TO fgeno DO gene[here]:=0.0;
        with gennustruct^ DO
          with censorstruct^ DO
            with p^.gen^ DO
              FOR first:=1 TO mgeno DO
                IF genarray[first]<>0.0
                THEN BEGIN
                  fstart:=probstart[first];
                  fend:=probend[first];
                  fseg:=segstart[first];
                  with q^.gen^ DO
                    FOR second:=1 TO fgeno DO
                      IF genarray[second]<>0.0          ***
                      THEN BEGIN
                        ...

The line *** and its equivalents in the various seg routines is
executed more than any other line of code.  By its nature genarray is
going to be a sparse array, so this test is going to fail most of the
time.  Yet as you can see, the inner loop is executed repeatedly for
each instance of the outer loop controlled by first.  This can be
improved as follows

      PROCEDURE segdown;

      VAR
        here:1..maxfem;
        gene:genotype;
        val,temp1,temp2:real;
        f1,f2,s1,s2,i,j,first,second:integer;

        nonzero : genotype;
        count, loop1, loop2 : integer;

      BEGIN
        initseg;
        FOR here:=1 TO fgeno DO gene[here]:=0.0;
        with gennustruct^ DO
          with censorstruct^ DO

            count := 0;         { Determine which q^.gen^.genarray      }
            with q^.gen^ do     { elements are non-zero.                }
              for loop1 := 1 to fgeno do
                if genarray[loop1] <> 0.0 then begin
                  count := count+1;
                  nonzero[count] := loop1;
                end{if};

            with p^.gen^ DO
              FOR first:=1 TO mgeno DO
                IF genarray[first]<>0.0
                THEN BEGIN
                  fstart:=probstart[first];
                  fend:=probend[first];
                  fseg:=segstart[first];
                  with q^.gen^ DO

                    for loop2 := 1 to count do begin
                      second := nonzero[loop2];
                      ...


Dont take my word for the accuracy of this code as I havent tried it
in Pascal yet, but it works in C.  This one change makes about a
factor of 2 speed improvement.  Again, keep in mind that this code
change needs to be made in all of the various -seg--- routines that
contain the *** line of code, in order to see the speed up in all
situations.

If you are going to try p2c and/or the above code changes, I recommend
that you rerun any final results with the original programs before
publishing them.

Regards,
Bob

	------------------------------------------------------------
	Bob Cottingham          	Phone:  713/798-4275
	Cell Biology, M301          	Fax:        798-5386
	Baylor College of Medicine	Email: bwc@bcm.tmc.edu
	Houston, TX   77030
	------------------------------------------------------------