Tuning tables and file access

A tuning change is worth making when it removes work, not when it makes the same work slightly faster. Two such changes are in every COBOL program that handles more than a few hundred records: a lookup that walks a table one entry at a time where a binary search would do, and a file that is read again for every record where one pass would do. Both are measured here with the method of the previous lesson.

Two shapes of one lookup

The table holds a thousand customers. A serial search reads entries from the first until it finds the key, so it reads five hundred on average. A binary search halves the range on every comparison, so it needs about ten. The work is the same; the number of comparisons is not.

COBOL spells the second one SEARCH ALL, and the price of it is a declaration: the table must be sorted on the key, and the program must say so with ASCENDING KEY IS.

SEARCH ALL against SEARCH

The two programs differ in one word of the declaration and one word of the search. Both fill the table with keys one to a thousand, then look up a hundred thousand keys and count the hits:

IDENTIFICATION DIVISION. PROGRAM-ID. SERIAL. DATA DIVISION. WORKING-STORAGE SECTION. 01 T-AREA. 05 T-ROW OCCURS 1000 TIMES ASCENDING KEY IS T-KEY INDEXED BY T-IDX. 10 T-KEY PIC 9(4). 10 T-VAL PIC 9(4). 01 I PIC 9(6) COMP-5. 01 K PIC 9(4) COMP-5. 01 HITS PIC 9(7) COMP-5. PROCEDURE DIVISION. PERFORM VARYING I FROM 1 BY 1 UNTIL I IS GREATER THAN 1000 MOVE I TO T-KEY(I) COMPUTE T-VAL(I) = I * 3 END-PERFORM. PERFORM VARYING I FROM 1 BY 1 UNTIL I IS GREATER THAN 100000 COMPUTE K = FUNCTION MOD(I * 7, 1000) + 1 SET T-IDX TO 1 SEARCH T-ROW AT END CONTINUE WHEN T-KEY(T-IDX) = K ADD 1 TO HITS END-SEARCH END-PERFORM. DISPLAY "hits " HITS. STOP RUN.

binary.cob is the same file with PROGRAM-ID. BINARY. and SEARCH ALL T-ROW. Both print the same hit count, which is the check that matters before a timing means anything:

cobc -x -free -Wall -o serial serial.cob
cobc -x -free -Wall -o binary binary.cob
./serial
./binary
hyperfine --warmup 2 --runs 8 ./serial ./binary

hits 0000100000
hits 0000100000
Benchmark 1: ./serial
  Time (mean ± σ): 765.7 ms ± 171.5 ms [User: 754.3 ms, System: 2.8 ms]
  Range (min … max): 639.9 ms … 1051.6 ms 8 runs

Benchmark 2: ./binary
  Time (mean ± σ): 108.6 ms ± 12.3 ms [User: 106.6 ms, System: 2.0 ms]
  Range (min … max): 101.0 ms … 138.6 ms 8 runs

Summary
  ./binary ran
  7.05 ± 1.77 times faster than ./serial

Six times by the minimum (639.9 against 101.0 ms) and seven by the mean. The factor is not the ten comparisons against five hundred: the serial search stops at the hit, and a hundred thousand keys spread over a thousand entries average five hundred comparisons each, while the binary search also pays for the loop and the setup. The gain of a real program will be somewhere between the two, and it is always worth measuring instead of calculating.

A table that is not sorted

SEARCH ALL does not check that the table is sorted. It halves the range as if it were, so an unsorted table gives wrong answers, quietly and quickly. Fill the same table backwards, with key 1000 first and key 1 last, keep the declaration and run the binary search:

cobc -x -free -Wall -o unsorted unsorted.cob
./unsorted

hits 0000000100

One hundred hits where there should be a hundred thousand, and no error, no warning, no status. The hundred are the keys the halving happened to land on. This is the most expensive kind of tuning bug: the program got faster and stopped being right, and nothing in the language says so.

Three habits keep it right. Sort the table with a table sort before the first search, or fill it from a source that is already in key order. Test a lookup of the first, the last and a missing key, which is where a broken search fails first. And keep one SEARCH program in the test set as the reference answer: if the binary search and the serial search disagree, the binary one is wrong.

A file read per record

The second shape is a file reopened for every key. It is what a program looks like when a lookup was written before the table was: for each of five hundred keys, OPEN INPUT, READ until the record, CLOSE. The other version reads the file once into a table and searches the table.

IDENTIFICATION DIVISION. PROGRAM-ID. RESCAN. ENVIRONMENT DIVISION. INPUT-OUTPUT SECTION. FILE-CONTROL. SELECT CUS-F ASSIGN TO "cus.dat" ORGANIZATION IS LINE SEQUENTIAL FILE STATUS IS WS-STATUS. DATA DIVISION. FILE SECTION. FD CUS-F. 01 CUS-REC. 05 CUS-ID PIC 9(4). 05 CUS-BAL PIC 9(7)V99. WORKING-STORAGE SECTION. 01 WS-STATUS PIC XX. 01 WS-I PIC 9(4) COMP-5. 01 WS-KEY PIC 9(4) COMP-5. 01 WS-EOF PIC X. 01 WS-HITS PIC 9(7) COMP-5. 01 WS-DEMO PIC 9(7)V99. PROCEDURE DIVISION. OPEN OUTPUT CUS-F PERFORM VARYING WS-I FROM 1 BY 1 UNTIL WS-I IS GREATER THAN 500 MOVE WS-I TO CUS-ID COMPUTE WS-DEMO = WS-I * 10 MOVE WS-DEMO TO CUS-BAL WRITE CUS-REC END-PERFORM CLOSE CUS-F. PERFORM VARYING WS-I FROM 1 BY 1 UNTIL WS-I IS GREATER THAN 500 COMPUTE WS-KEY = FUNCTION MOD(WS-I * 7, 500) + 1 MOVE "N" TO WS-EOF OPEN INPUT CUS-F PERFORM UNTIL WS-EOF = "Y" READ CUS-F AT END MOVE "Y" TO WS-EOF NOT AT END IF CUS-ID = WS-KEY ADD 1 TO WS-HITS MOVE "Y" TO WS-EOF END-IF END-READ END-PERFORM CLOSE CUS-F END-PERFORM. DISPLAY "hits " WS-HITS. STOP RUN.

IDENTIFICATION DIVISION. PROGRAM-ID. ONEPASS. ENVIRONMENT DIVISION. INPUT-OUTPUT SECTION. FILE-CONTROL. SELECT CUS-F ASSIGN TO "cus.dat" ORGANIZATION IS LINE SEQUENTIAL FILE STATUS IS WS-STATUS. DATA DIVISION. FILE SECTION. FD CUS-F. 01 CUS-REC. 05 CUS-ID PIC 9(4). 05 CUS-BAL PIC 9(7)V99. WORKING-STORAGE SECTION. 01 WS-STATUS PIC XX. 01 WS-I PIC 9(4) COMP-5. 01 WS-N PIC 9(4) COMP-5 VALUE 0. 01 WS-KEY PIC 9(4) COMP-5. 01 WS-EOF PIC X. 01 WS-HITS PIC 9(7) COMP-5. 01 WS-DEMO PIC 9(7)V99. 01 T-AREA. 05 T-CUS OCCURS 500 TIMES INDEXED BY T-IDX. 10 T-ID PIC 9(4). 10 T-BAL PIC 9(7)V99. PROCEDURE DIVISION. OPEN OUTPUT CUS-F PERFORM VARYING WS-I FROM 1 BY 1 UNTIL WS-I IS GREATER THAN 500 MOVE WS-I TO CUS-ID COMPUTE WS-DEMO = WS-I * 10 MOVE WS-DEMO TO CUS-BAL WRITE CUS-REC END-PERFORM CLOSE CUS-F. OPEN INPUT CUS-F PERFORM UNTIL WS-EOF = "Y" READ CUS-F AT END MOVE "Y" TO WS-EOF NOT AT END ADD 1 TO WS-N MOVE CUS-ID TO T-ID(WS-N) MOVE CUS-BAL TO T-BAL(WS-N) END-READ END-PERFORM CLOSE CUS-F. PERFORM VARYING WS-I FROM 1 BY 1 UNTIL WS-I IS GREATER THAN 500 COMPUTE WS-KEY = FUNCTION MOD(WS-I * 7, 500) + 1 SET T-IDX TO 1 SEARCH T-CUS AT END CONTINUE WHEN T-ID(T-IDX) = WS-KEY ADD 1 TO WS-HITS END-SEARCH END-PERFORM. DISPLAY "hits " WS-HITS. STOP RUN.

The two blocks above are the whole of both programs: the first is the reopen loop with its file and its declarations, the second is the same job with one pass into a table and a SEARCH inside it. Both write the file they read, five hundred records of two fields, and both print the same count. The difference is the number of times the file is opened and the number of records read:

cobc -x -free -Wall -o rescan rescan.cob
cobc -x -free -Wall -o onepass onepass.cob
./rescan
./onepass
hyperfine --warmup 1 --runs 5 ./rescan ./onepass

hits 0000000500
hits 0000000500
Benchmark 1: ./rescan
  Time (mean ± σ): 51.2 ms ± 9.7 ms [User: 34.2 ms, System: 16.9 ms]
  Range (min … max): 42.6 ms … 62.0 ms 5 runs

Benchmark 2: ./onepass
  Time (mean ± σ): 6.5 ms ± 0.1 ms [User: 4.2 ms, System: 2.3 ms]
  Range (min … max): 6.4 ms … 6.8 ms 5 runs

Summary
  ./onepass ran
  7.83 ± 1.50 times faster than ./rescan

Look at the system time of the first: 16.9 ms of the 51.2 is the operating system, because every OPEN is a system call and every close a flush. That is the part a faster machine does not fix. The one-pass version reads two thousand records once and then does its lookups in memory, and it is nearly eight times faster with a spread small enough to see on the page.

What to change first

The two changes above are worth more than any compiler flag, and they share a property: both remove work rather than speed it up. The order to try them in a slow program:

  1. Count the file reads. A file opened inside a loop is almost always the largest cost in a batch program, and one pass into a table removes it.
  2. Count the comparisons. A serial search over a table of thousands is the next largest, and SEARCH ALL removes all but ten of them, at the price of a sorted table and a test.
  3. Then look at the compiler. -O2 from the previous lesson is a factor on arithmetic-heavy code and much less on code that waits for a disk.
  4. Only then look at the code inside the loop. A MOVE of a large group, a STRING that could be a reference modification and a decimal conversion in the middle of a million-record loop are the usual small ones.

Each step needs the measurement of the previous lesson around it: the same output before and after, the same program, and a number with the machine and the compiler named. A tuning change nobody measured is a rewrite.

Exercises

  1. Sort the unsorted table with the bubble sort of lesson 064 and run SEARCH ALL again. How many hits now?
  2. Change the serial search to stop at the first key greater than the target, which is legal on a sorted table. How much does that gain without SEARCH ALL?
  3. Give rescan.cob a table and keep the reopen loop for the first hundred keys only. Which of the two costs disappears first?
  4. Time onepass with a table of five thousand records and a file of five thousand. Where does the serial search inside it start to matter?

Questions

A new set of questions in a new order every time. Choose one answer for each, then check.

  1. What does SEARCH ALL require of the table?

    Answer

    That it is sorted on the key the search uses

    The declaration says ASCENDING KEY IS, and the program must keep the order.

  2. What happened when the descending table was searched with SEARCH ALL?

    Answer

    It found a hundred keys instead of a hundred thousand, and reported nothing

    The page shows hits 0000000100 from the unsorted run.

  3. What is the largest cost of reopening a file for every key?

    Answer

    The OPEN and CLOSE system calls, and the reads of records already seen

    The system time of the rescan is 16.9 ms of its 51.2 ms.

  4. Which change is worth trying first in a slow batch program?

    Answer

    Remove the repeated file opens and reads

    The order in the lesson puts file access before comparisons and the compiler.

  5. What does this program print? IDENTIFICATION DIVISION. PROGRAM-ID. Q5. DATA DIVISION. WORKING-STORAGE SECTION. 01 T. 05 T-K PIC 9(2) OCCURS 4 TIMES ASCENDING KEY IS T-K INDEXED BY T-I. 01 J PIC 9(2). 01 H PIC 9(2) VALUE 0. PROCEDURE DIVISION. MOVE 10 TO T-K(1) MOVE 20 TO T-K(2) MOVE 30 TO T-K(3) MOVE 40 TO T-K(4) SET T-I TO 1 SEARCH ALL T-K AT END CONTINUE WHEN T-K(T-I) = 30 MOVE 1 TO H END-SEARCH. DISPLAY H. STOP RUN.

    Answer

    01

    The sorted table holds 30 at the third entry and the search finds it.

  6. What does this program print? IDENTIFICATION DIVISION. PROGRAM-ID. Q6. DATA DIVISION. WORKING-STORAGE SECTION. 01 N PIC 9(3) VALUE 0. 01 I PIC 9(2). PROCEDURE DIVISION. PERFORM VARYING I FROM 1 BY 1 UNTIL I IS GREATER THAN 5 IF FUNCTION MOD(I, 2) = 0 ADD I TO N END-IF END-PERFORM. DISPLAY N. STOP RUN.

    Answer

    006

    Only the even numbers two and four are added.

  7. What does this program print? IDENTIFICATION DIVISION. PROGRAM-ID. Q7. DATA DIVISION. WORKING-STORAGE SECTION. 01 W PIC X(7) VALUE "tuning ". PROCEDURE DIVISION. DISPLAY "[" FUNCTION TRIM(W) "]". STOP RUN.

    Answer

    [tuning]

    TRIM removes the trailing space.

  8. What does this program print? IDENTIFICATION DIVISION. PROGRAM-ID. Q8. DATA DIVISION. WORKING-STORAGE SECTION. 01 A PIC 9(4) VALUE 1000. 01 B PIC 9(4) VALUE 8. 01 C PIC 9(4). PROCEDURE DIVISION. COMPUTE C = A / B DISPLAY C. STOP RUN.

    Answer

    0125

    A thousand divided by eight is a hundred and twenty-five.

  9. Why is a faster wrong answer worse than a slow right one?

    Answer

    The program keeps failing silently while looking healthy in the timings

    The unsorted table gave a hundred hits with no error at all.

  10. Which pair of numbers is the honest way to quote the search result?

    Answer

    The minimum of each build with the machine and compiler named

    The lesson quotes minimum and mean, and names the machine.

The code on this page was built with cobc (GnuCOBOL) 3.2.0 and timed with hyperfine on Alpine Linux 3.24.3 (x86_64) in a Docker container.

Article author: Arthur Isaev