XML CO538 Anonymous Questions and Answers Keyword Index

This page provides a keyword index to questions and answers. Clicking on a keyword will take you to a page containing all questions and answers for that keyword, grouped by year.

To submit a question, use the anonymous questions page. You may find the keyword index and/or top-level index useful for locating past questions and answers.

Keyword reference for abbreviation

Question 58 (2000):

Please could you type up the example on abbreviations you showed us in the lecture? They were on hand-drawn slides and about adding up elements of a 2-D array. Thanks.

Answer 58:

OK. Here's some code for adding up the elements of a 1-D array:

  SEQ
    sum := 0
    SEQ i = 0 FOR SIZE a
      sum := sum + a[i]

where a is an array of REAL64s (say) and sum is a single REAL64 variable.

Now, suppose a is a 2-D array of REAL64s and we need to add up each of its rows into corresponding elements of sum (which is now a 1-D array of REAL64s). The naive code, based on the above, would be:

  SEQ row = 0 FOR SIZE a
    SEQ
      sum[row] := 0
      SEQ col = 0 FOR SIZE a[row]
        sum[row] := sum[row] + a[row][col]

This code is correct but somewhat inefficient. Firstly, occam 2-D arrays live in a contiguous block of memory with all its rows having the same lengths (which is not the case for Java 2-D arrays). Therefore, it's slightly wasteful to look up the size of each row each time the inner loop starts. Instead, look this up once before doing anything else, give it a VAL name and use that name:

  VAL INT n.cols IS SIZE a[0]:
  SEQ row = 0 FOR SIZE a
    SEQ
      sum[row] := 0
      SEQ col = 0 FOR n.cols
        sum[row] := sum[row] + a[row][col]  -- innermost loop code

But the real inefficiency lies in the code of the innermost loop. That code is executed n.rows * n.cols times and involves calculating the addrresses of elements sum[row] and a[row][col]. The latter requires a multiplication and an addition - the former just an addition. Three run-time checks that row and col lie within their respective array index ranges may also be required (although a really clever optimiser may be able to deduce that they will always be within bounds and, therefore, omit these checks).

Compare the above with:

  VAL INT n.cols IS SIZE a[0]:
  SEQ row = 0 FOR SIZE a
    REAL64 sum.row IS sum[row]:             -- this is where we will do the sum
    VAL []REAL64 a.row IS a[row]:           -- this is what we are going to sum
    SEQ
      sum.row := 0
      SEQ col = 0 FOR n.cols
        sum.row := sum.row + a.row[col]     -- innermost loop code

Now, the innermost loop contains just one array reference, requiring only one addition for the address calculation and one range check on col (for which an optimiser does not have to be that clever to optimise away). Two new array references have been introduced in the abbreviations themselves - but these are not part of the innermost loop and only happen once per row. This code will execute much faster than the previous version.

The other benefit from introducing those abbreviations is that the inner code:

    SEQ
      sum.row := 0
      SEQ col = 0 FOR n.cols
        sum.row := sum.row + a.row[col]     -- innermost loop code

is as simple as the 1-D array summing code with which we started:

Keywords: abbreviation , arrays , size

Referrers: Question 69 (2010)