[Dynamite] compile status / radical idea

[Ian Holmes]

On Wed, 26 Apr 2000, Guy Slater wrote:

> > > OK.  Religious preferences aside, I think a major problem
> > > with perl will be performance.
> > > 
> > > If telegraph was to be only a code generation system, then I reckon
> > > it would be viable, however I imagine having runtime code in C will
> > > incur quite a performance hit, and in perl it could be prohibitive.
> > > 
> > > I know that practical performance isn't a major issue for a prototype
> > > implementation, but it will impede development if it is too slow.
> > > 
> > > Maybe the perl interpreter is better than that.
> > > Can either of you convince me with a short DP example in perl?
> > 
> > Attached is a dummy SW implementation. It takes about a second of user
> > time to do a 100*100 matrix on my 450MHz box.
> >
> > This _is_ too slow for end users, but I think it will be OK for
> > development of core ideas. By the time we start trying to implement
> > Genewise, we should be calling C routines from Perl for the DP.
> 
> I've had a play with this now.  The brevity of the code is impressive.
> (but I can't believe I'm editing perl.  hmmff.)
> 
> I'm not sure if it is fast enough for core ideas
> - many of them will require longer sequences.
> Anything requiring longer sequences, like intron modelling,
> 7tms etc will be difficult.
> 
> Even at seqlen=1000, the performance and memory usage turns to shit.
> Comparison running on laptop with PII-400, 128Mb:
> 
>       ssearch3 :   1.1Mb,  0.9 seconds
>     sw-demo.pl : 117.0Mb 112.2 seconds
> 
> I know this is a linear space vs quadratic space implementations,
> but the memory usage is still really bad.  Is this a bug ?

Not sure...
I suspect it's partly because I was lazy and used dynamically growable
arrays. So things will start being at least O(N*log(N)) where they should
be at most O(N). Also, Perl arrays are not the best way to handle a DP
matrix (although they do make the code read cleanly). A better way would
be to pack the matrix into a fixed-length vec().

> I still think that this problem (and many others) could be solved
> elegantly and flexibly by having some sort of language layer
> between the model/algorithms and the compute (maybe even XML).
> Something that just describing arrays, matrices and the values that need
> to be maxed over.  Just enough to get dp scores and tracebacks.

YesyesYES..

> I think this would make the whole system a lot more modular.
> It would be much easier to slot in different parts either side of
> the language layer.  Things to come later like distributed calculation
> or specialised hardware ports would be a lot easier.

This philosophy is cool. I've started storing all the scoring parameters
(substitution matrices etc) as 32-bit integer arrays, packed using perl's
"vec" function. The layout of these arrays is strongly defined, so they
can be passed directly into C. (See the Value.pm module for this code.)

I still regard a perl implementation as useful, at first for prototyping,
then later for numerical sanity checks and also completeness / clarity of
exposition. Probably more than one perl implementation (one for
readability, one for the-fastest-I-can-make-it-go-in-perl). But this is
not a substitute for doing the DP in C. It's more a case of the golden
rule of getting a working test up & running as early as possible, and
building from there.

I agree strongly with Guy's idea of some kind of internal microcode to
communicate between Perl and C, so that the C DP routines do not have to
make calls back to the Perl. We need to talk through the details in
person, perhaps when I'm in the UK in June, as I anticipate I'll end up
implementing Perl-side microcode generation.

Ian

> 
> Guy.
> --
> %!PS % <------ Guy St.C. Slater ------> http://www.ebi.ac.uk/~guy/  <------
> 210 297/a{def}def/b{translate}a b 36/c{rotate}a c 0 1 0 1 12/d{exch moveto}
> a/e{closepath stroke}a/f{index}a/g{0 0 0 0 4 f}a/h{setlinewidth newpath dup
> g}a{pop exch 1 f add 0 h neg d lineto 72 c lineto e 2 h d 3 f 0 108 arc d e
> 18 c 0 2 f neg b 18 c}for 72 c newpath add g 0 7 arc d e pop showpage
> 
>