| The next time you sort a list of items in your computer, try this experiment. Put an AM radio next to the computer, tuned away from any station. With this, you can actually hear the computer ‘think’. |
| If you try this, you will find that during the sort, a large amount of time will be spent doing something which changes the pattern of the sound completely. This change is the bane of most sorting techniques on the TRS-80, and it is called “Memory Management”. |
| Memory Management |
| To understand memory management, we have to look at how the computer stores information. For numbers this is simple since each variable is assigned space in memory for its value, resetting it doesn’t change where it is. |
| However, strings are handled differently. When we read in strings, the computer stores them starting at the top of free string memory (remember CLEAR N, it sets aside N bites for strings. RUN automatically does a CLEAR 50). The beginning of each string is recorded along with the length of the string in a location in memory provided for this. The VARPTR function gives you that location |
| If you have a string in memory called A$, its location is given by: |
PEEK(VARPTR(A$)+1) + PEEK(VARPTR(A$)+2)*256
|
| (see the Level II Reference Manual. p8/9). |
| The length of the string is: |
PEEK (VARPTR(A$))
|
| As you add strings into string space, they are added one after another as shown in the diagram. |
| When you reset the value of a string, the pointers to the string in memory are reset to their new values by the interpreter. But this is not all, since the string is treated as a new string and the old location of the string is not recovered. |
| A typical statement in a sorting program which changes one string for another is: |
| TS=A$(I):A$(l)=A$(J):A$(J)=TS |
| Even though the strings are already occupying space in memory, this statement generates THREE NEW STRINGS and adds them into the string space at the bottom. |
| When you fill up the string space (which will happen very quickly), the computer pauses to reorganize the memory and compact the string space by getting rid of unused space. During this time, your program just waits. |
| Even with the best sorting algorithm, as much as 90% of the computing time for the sort will be in memory management. In order to get efficient sorts we have to get rid of this wasted time. |
| Sorting with VARPTR |
| A significant improvement in sorting time (from 4 hrs to 8 ½ minutes, for 450 items), is gained by redoing the program statement above that swaps strings as follows: |
I1= PEEK (VARPTR(A$(I))):
I2= PEEK (VARPTR(A$(I))+1):
I3= PEEK (VARPTR(A$(I))+2)
J1=PEEK (VARPTR(A$(J))):
J2=PEEK (VARPTR(A$(J))+1):
J3=PEEK (VARPTR(A$(J))+2)
POKE (VARPTR(A$(I))),J1:
POKE (VARPTR(A$(I))+1),J2:
POKE (VARPTR(A$(I))+2),J3
POKE (VARPTR(A$(J))),I1:
POKE (VARPTR(A$(J))+1 ),I2:
POKE (VARPTR(A$(J))+2),I3
|
| This set of statements creates no new strings in memory. It only changes the pointers to the strings. On large sorts, the improvement by using this technique is phenomenal. On a sort of 450 items in a mailing list, we had an improvement from 4 hours without this technique, to 8½ minutes with it. This sort has now been included in our own mailing list program as well as Peripheral People’s Mailroom. |
| As this is being typed up for publication, we have seen an article elsewhere giving essentially the same sorting technique. We discovered only one minor problem with the way that it accomplishes the switch. |
| It uses the following statements to switch the pointers: |
T1=VARPTR(A$(I))
T2=VARPTR(A$(J))
FOR Z=0 TO 2
A1=PEEK(T1 + Z)
A2=PEEK(T2 + Z)
POKE (T1+Z),A2
POKE (T2+Z),A1
NEXT Z
|
| I found that the technique works well on long sorts, but that the pointers were dynamically allocated (a 25 cent buzzword for saying that they can move) on short sorts, say less than 10 items. |
| For short sorts, setting the values T1 and T2 resulted in not getting the pointer correctly. This has disastrous results since the pointers become random and you soon find that your strings begin to take on a funny look. |
| On one sort, some of the pointers actually wound up saying that the strings they referred to were in Level II ROM! In order to prevent this, the statements can be changed to be equivalent with mine. |
FOR Z = 0 TO 2
Al = PEEK(VARPTR(A$(I))+Z)
A2 = PEEK(VARPTR(A$(J))+Z)
POKE (VARPTR(A$(I)) + Z), A2
POKE (VARPTR(A$(J)) + Z), A1
NEXT Z
|
| Further Improvements |
| Still another improvement comes from changing all of the variables in the program to integers, except those that must be real or string variables. |
![[Model I]](../../../../images/computer-model1bx150.png)
![[Model III]](../../../../images/computer-model3x250.gif)
![[Model IV]](../../../../images/computer-model4x250.gif)
![[Model 100]](../../../../images/computer-model100x250.gif)