## 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**

## 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.

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 `REAL64`s (say) and `sum`
is a single `REAL64` variable.

Now, suppose `a` is a 2-D array of `REAL64`s and we need
to add up each of its rows into corresponding elements of `sum`
(which is now a 1-D array of `REAL64`s). 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)

This work is licensed under a Creative Commons Attribution-Share Alike 3.0 Unported License. |