\(5.2.\)Expressing Program Performance

  We introduce the metric cycles per element, abbreviated CPE, to express program performance in a way that can guide us in improving the code.

---

  The time required by a iteration procedure can be characterized as a constant plus a factor proportional to the number of elements processed. Take the following two C programs as an example:

/* Compute prefix sum of vector a */
void psum1(float a[], float p[], long n) {
    long i;
    p[0] = a[0];
    for (i = 1; i < n; i++)
        p[i] = p[i-1] + a[i];
}

void psum2(float a[], float p[], long n) {
    long i;
    p[0] = a[0];
    for (i = 1; i < n-1; i+=2) {
        float mid_val = p[i-1] + a[i];
        p[i] = mid_val;
        p[i+1] = mid_val + a[i+1];
    }
    /* For even n, finish remaining element */
    if (i < n)
        p[i] = p[i-1] + a[i];
}