Classic Computer Magazine Archive COMPUTE! ISSUE 52 / SEPTEMBER 1984 / PAGE 10

DIM On Commodore

What happens to the data when it enters a DIM statement (array) from an INPUT statement or a sequential file?

I teach computer programming part-time at Tulsa Junior College. This is my first semester with micros. I have a Commodore 64 and a VIC 1541 disk drive. In advanced BASIC, sequential files are common, and are usually used for search and sort routines. When the data is read from DATA statements into the arrays, there is no problem. The sort or search never stops, but when that same data is brought into the arrays from a sequential file, the sort or processing stops many times, making a 16 to 30 minute program run for hours.

I have written my own sequential file program, and later discovered and used the one off the demonstration disk that came with the VIC 1541 disk drive. Both have these stops. I have tried about everything. If you could give me a clue, I would appreciate it.

Darrel Henry

The pauses you see in the program are the result of a process called "garbage collection." It's caused by moving strings around.

Here's what happens: As new strings are created, the old ones are not thrown away; they lie dead in memory. Eventually, memory fills up and the computer has to stop and collect the strings that are still live. This takes time; the pauses are quite noticeable and can be time-consuming.

Strings that are completely defined within a program—from DATA statements or from an assignment statement such as X$ = "HELLO"—are used straight out of the program where they lie. These strings don't need to be collected; as you have noted, there's no garbage collection delay when you use these.

For your type of program—sorting and searching—there are two rules that will be very helpful in eliminating delays:

  1. Don't move strings. Instead of sorting by moving them around from one part of the array to another—which creates garbage—use an "index" to keep track of where a string belongs within a certain sequence. (More on this in a moment.)
  2. When you have finished with a string, set it to a null string, for example, A$(21) = "". When you have disposed of almost all strings this way, and are ready to read in another set of strings from disk or tape, force a collection by using the FRE function, for example, code X = FRE(0). Garbage collection will run quickly if you have very few strings left. When you read in the next group of strings, they will come into the newly liberated memory space.

To illustrate point 1: Here's a program to sort an array of strings. It's a bubble sort, which is not very efficient. The point is this: After the strings are created, they are never moved. Only the index (A%) values move, and they are numbers, not strings, so there won't be any garbage.

 90 REM BUBBLE SORT - INDEX DEMO
100 N = 30 : DIM A$(100)
200 REM CREATE RANDOM STRINGS
210 FOR J = 1 TO N
220 A$(J) = CHR$(RND(1)*26 + 65) + CHR$ (RND(1) * 26 + 65)
230 NEXT J
300 REM : CREATE INDEX
310 DIM A%(N)
320 FOR J = 1 TO N
330 A%(J) = J
340 NEXT J
400 REM: SORT INDEX
410 FOR J = N - 1 TO 1 STEP -1
420 FOR K = 1 TO J
430 REM: GET INDEX FOR K, K + 1
440 X = A%(K) : Y = A%(K + 1)
450 REM: FLIP IF OUT OF ORDER
460 IF A$(X) > A$(Y) THEN A%(K + 1) = X : A%(K) = Y
470 NEXT K,J
500 REM: PRINT RESULTS
510 FOR J = 1 TO N
520 PRINT A$(A%(J))
530 NEXT J

Study this program to see how the strings are sorted, but not moved.

There are other rules on how to handle garbage collection; the ones above will do the job for your application.