optimising code in Pop11 
Author Message
 optimising code in Pop11

I know that this is a very general question but:

What kinds of techniques can be used when programming in pop11 to make
it run as fast as possible. How much difference does using the inbuilt
procedures make over coding loops/recursion yourself.

--

Cheers, Ed Sykes.

3rd Year of BSc Psychology/Artificial Intelligence
University of Birmingham



Tue, 14 May 2002 03:00:00 GMT  
 optimising code in Pop11

Quote:
Ed writes:
>I know that this is a very general question but:

>What kinds of techniques can be used when programming in pop11 to make
>it run as fast as possible. How much difference does using the inbuilt
>procedures make over coding loops/recursion yourself.

My simplest suggestion is to read my chapter 5 in "Pop11 Comes of Age".
(If there is enough interest, I will post it on http://www.*-*-*.com/ )
You can also read HELP * EFFICIENCY, which is somewhat easier to get
hold of.

The in-built procedures are compiled in a different way to the normal
user-defined code - and they are noticeably faster in general.  It is
rarely worth coding your own stuff because the system programmers are
very concerned about efficiency on your behalf.

My easy speed tips are to make good use of the open stack and use
lots of properties (see * NEWPROPERTY, * NEWASSOC, * NEWMAPPING and
the more general * NEWANYPROPERTY.)

For example, this is the best way to convert a list to a vector ...

     define list_to_vector = destlist <> consvector enddefine;

This makes excellent idiomatic use of the open stack.  But
many programmers, coming from a OO background, would have been
tempted to write this code ...

WARNING: THE REMAINDER OF THIS MESSAGE SHOWS BAD PROGRAMMING STYLE

     define list_to_vector( L );
         lvars n = L.length;      ;;; pointless O(n) cost.
         lvars v = initv( n );    ;;; pointless O(n) initialisation to undef.
         lvars i;
         for i from 1 to n do
             L( i ) -> v( i )     ;;; whoops, list indexing is O(i) so this
         endfor                   ;;; expression has cost O( n**2 )
     enddefine;

Even if the programmer realises that L(i) has to walk all the way down
the "spine" of the list, and code the loop like this ...

     for i from 1 to n do
         L.hd -> v( i );          ;;; doing a hd and then a tl is silly
         L.tl -> L                ;;; because dest does it in one go with
     endfor                       ;;; one check.

although there is a real improvement this is still terrible.  In particular,
calculating the length of the list is costly (and the programmer should have
used listlength, anyway, for stylistic reasons), setting all the vector
elements to undef is pointless, and getting the head and tail components
of a list element separately is poor style.  In addition, there is an
enormous amount of wasted run-time type-checking.  The loop can be
safely coded as follows :-

     ;;; Well, it is safe but now it is ugly.  This is our big clue
     ;;; that we have lost the plot.
     fast_for i from 1 to n do
         dest( L ) -> L -> fast_subscrv( i, v )
     endfor

This kind of thinking would eventually lead to this kind of bad code ...

     define list_to_vector( L );
         lvars n = L.listlength;     ;;; pointless O(n) cost.
         lvars v = initv( n );       ;;; pointless O(n) initialisation to undef.
         lvars i;
         fast_for i from 1 to n do
             dest( L ) -> L -> fast_subscrv( i, v )
         endfor
      enddefine;

This code is an improvement in that it now only accepts lists and does
far less run-time type-checking.  However, compared to the beautiful
destlist <> consvector, it is not merely ugly and slower (by about 50%)
but noticeably less efficient in its store use.  That is because the
explicitly coded loop grabs all the resources it needs and never lets
go.

By contrast, destlist will not hang on to the entire list as it executes.
At any point in its execution there will only be "n" values
retained.  In fact, at the i'th element there will be i + 3 * ( n - i )
long words in use i.e. the store in use declines from 3*n longwords
to n longwords.  This is because pairs require 3 longwords per element
but the stack and vectors only need 1.  Then destlist is exited (via a
chain) and consvector is entered, reducing the amount of callstack space
employed.  And consvector simply shifts the stack store elements into
the heap, adding an appropriate 2 word header.

Fast.  Small.  Beautiful.

You'll find my chapter 5 is called "Speed, Space and Style".

M{*filter*}

The m{*filter*}of this tale is that Pop11, like all languages, has a design
philosophy that, once grasped, makes efficient programming very easy.
It is easier to write efficient code than inefficient code - by design.
But finding anyone who can articulate that philosophy is not so easy!
Let's add this to the list of documents required for the Poplog web
site.

Steve



Tue, 14 May 2002 03:00:00 GMT  
 
 [ 2 post ] 

 Relevant Pages 

1. PROPEL 0.2+ (pop11 for windows) (pop11 4 windows)

2. Optimising pentium code

3. Optimising a function with constraints (PD Fortran code)

4. Optimising code using CLOS in CMUCL

5. Improving or optimising Lisp code

6. Pop11 code

7. POP11 code sources

8. Pop11 code

9. Help optimising AWK script

10. GPF on optimising

11. Optimising Browse Load with Buffering using STREAM and FLUSH

12. CapeSoft Tip of the Week - Optimising Clarion Applications for Speed

 

 
Powered by phpBB® Forum Software