SPO600 - Lab 5 - Algorithm Selection Lab

For this lab we were required to write a program to multiply a large set of 16-bit signed integers by one floating point value, between 0.0 and 1.0. This simulates how volume scaling works, and it was used to show how the code we write is optimized by the compiler, and also how you can format your code for the compiler to better optimize it.

The lab itself asked us to write two separate implementations, a naive implementation, and a potentially more optimized solution, where we chose to write one using a lookup table. To assist us with our benchmarking,  we created a struct called "Result", and it looks something like this:

struct Result{
        double elapsed, elapsed_middle;
        struct timeval time_start,time_end;
        double sum;
};


Our naive implementation was about as efficient as expected, taking 2768ms to process a set of 500,000,000 pseudo-random data (from /dev/urandom, and using gcc's -O3 flag). Whereas our custom implementation takes 1852ms. That's a difference of 916ms, or a 33% increase in speed. When compiling without any optimizations, our naive function takes 18080ms, whereas our custom one takes 11756ms, or an improvement of 6324ms, or a 65% improvement.

For reference, here is our naive and custom functions:

struct Result sum_custom() {
        int i;
        struct Result res;
        int16_t table[0xFFFF];
        int idx;

        gettimeofday(&res.time_start, NULL);
        res.sum = 0;
        for(i = -32767; i <=32767;i++){
                table[i & 0xFFFF] = i * VOL;
        }

        int sz = SIZE;
        for(i = 0; i < sz ; i++){
                idx = (unsigned short) data[i];
                res.sum += output[i] = table[idx];

        }
        gettimeofday(&res.time_end, NULL);
        return res;
}

struct Result sum_naive(){
        size_t i;
        struct Result res;
        int16_t val;

        gettimeofday(&res.time_start, NULL);
        res.sum = 0;
        for(i = 0; i < SIZE;i++){
                val = data[i] * VOL;
                output[i] = val;
                res.sum += val; // we're adding here to prevent the compiler from optimizing
// our whole loop out.
        }
        gettimeofday(&res.time_end, NULL);
        return res;
}