Algorithm Selection Lab

Background

This lab is to help understanding software optimize. As technique developing, the contents a software can be represented are rich. We use more high quality images, audios and videos. High quality means more space need, less battery usage. The mission is to find the balance between them.

Example: Basic Sound Program aarchie server

vol.h

#define SAMPLES 5000000

vol1.c

// Function to scale a sound sample using a volume_factor
// in the range of 0.00 to 1.00.
static inline int16_t scale_sample(int16_t sample, float volume_factor) {
        return (int16_t) (volume_factor * (float) sample);
}

int main() {

        // Allocate memory for large in and out arrays
        int16_t*        data;
        data = (int16_t*) calloc(SAMPLES, sizeof(int16_t));

        int             x;
        int             ttl = 0;

        // Seed the pseudo-random number generator
        srand(1);

        // Fill the array with random data
        for (x = 0; x < SAMPLES; x++) {
                data[x] = (rand()%65536)-32768;
        }

        // ######################################
        // This is the interesting part!
        // Scale the volume of all of the samples
        for (x = 0; x < SAMPLES; x++) {
                data[x] = scale_sample(data[x], 0.75);
        }
        // ######################################

        // Sum up the data
        for (x = 0; x < SAMPLES; x++) {
                ttl = (ttl+data[x])%1000;
        }

        // Print the sum
        printf("Result: %d\n", ttl);

        return 0;

}

$ make test

bash -c "time ./vol1"
Result: 94

real    0m0.526s
user    0m0.494s
sys     0m0.030s

bash -c "time ./vol1"
Result: 94

real    0m0.526s
user    0m0.504s
sys     0m0.021s

bash -c "time ./vol1"
Result: 94

real    0m0.525s
user    0m0.514s
sys     0m0.010s

Time use are different, but the differences are tiny.

range
real: 0.525s-0.527s
user: 0.504s-0.524s
sys: 0.000s-0.030s

Pre-calculate a lookup table (array) of all possible sample values multiplied by the volume factor, and look up each sample in that table to get the scaled values. (You'll have to handle the fact that the input values range from -32768 to +32767, while C arrays accept only a positive index).
vol2.c

#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>
#include "vol.h"

// Function to scale a sound sample using a volume_factor
// in the range of 0.00 to 1.00.
static inline int16_t scale_sample(int16_t sample, float volume_factor) {
        return (int16_t) (volume_factor * (float) sample);
}

int main() {
        //
        int16_t* lookup;
        lookup = (int16_t*) calloc(65536, sizeof(int16_t));

        for (int i = 0; i < 65536; i++) {
                lookup[i] = (-32768+i)*0.75;
        }
        // Allocate memory for large in and out arrays
        int16_t*        data;
        data = (int16_t*) calloc(SAMPLES, sizeof(int16_t));

        int             x;
        int             ttl = 0;

        // Seed the pseudo-random number generator
        srand(1);

        // Fill the array with random data
        for (x = 0; x < SAMPLES; x++) {
                data[x] = (rand()%65536)-32768;
        }

        // ######################################
        // This is the interesting part!
        // Scale the volume of all of the samples
        for (x = 0; x < SAMPLES; x++) {
                data[x] = lookup[data[x]+32768];
        }
        // ######################################

        // Sum up the data
        for (x = 0; x < SAMPLES; x++) {
                ttl = (ttl+data[x])%1000;
        }

        // Print the sum
        printf("Result: %d\n", ttl);

        return 0;

}

$ bash -c "time ./vol2"

Result: 94

real    0m0.650s
user    0m0.642s
sys     0m0.000s

Result: 94

real    0m0.644s
user    0m0.631s
sys     0m0.010s

Result: 94

real    0m0.644s
user    0m0.612s
sys     0m0.029s



Convert the volume factor 0.75 to a fix-point integer by multiplying by a binary number representing a fixed-point value "1". For example, you could use 0b100000000 (= 256 in decimal) to represent 1.00, and therefore use 0.75 * 256 = 192 for your volume factor. Multiply this fixed-point integer volume factor by each sample, then shift the result to the right the required number of bits after the multiplication (>>8 if you're using 256 as the multiplier).

vol3.c
#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>
#include "vol.h"

// Function to scale a sound sample using a volume_factor
// in the range of 0.00 to 1.00.
static inline int16_t scale_sample(int16_t sample, float volume_factor) {
        return (int16_t) (volume_factor * (float) sample);
}

int main() {

        // Allocate memory for large in and out arrays
        int16_t*        data;
        data = (int16_t*) calloc(SAMPLES, sizeof(int16_t));

        int             x;
        int             ttl = 0;

        // Seed the pseudo-random number generator
        srand(1);

        // Fill the array with random data
        for (x = 0; x < SAMPLES; x++) {
                data[x] = (rand()%65536)-32768;
        }

        // ######################################
        // This is the interesting part!
        // Scale the volume of all of the samples
        int cul = 0.75*0b100000000;
        for (x = 0; x < SAMPLES; x++) {
                data[x] = data[x]*192>>8;
        }
        // ######################################

        // Sum up the data
        for (x = 0; x < SAMPLES; x++) {
                ttl = (ttl+data[x])%1000;
        }

        // Print the sum
        printf("Result: %d\n", ttl);

        return 0;

}
Result: 873

real    0m0.526s
user    0m0.509s
sys     0m0.011s

Result: 873

real    0m0.520s
user    0m0.498s
sys     0m0.021s

Result: 873

real    0m0.521s
user    0m0.499s
sys     0m0.020s