Lab 5: Algorithm Selection

     For this lab I was tasked with comparing the performance of three different volume scaling algorithms under various conditions. Instead of true volume scaling this lab will create an array of 10 million integers which will then be scaled by 0.75 and stored in a new array. The three approaches for this are:

- Multiply each value by a float of 0.75

- Pre-Calculate all possible values multiplied by the scaling factor (0.75) and run a look-up for each      value

- Convert the scaling factor into an integer by multiplying it binary number representing a fixed-point value 1

 To isolate the scaling loop I will run each method once without scaling and then once again with the scaling loop included and take the difference as a representation of time spent on that algorithm.

 Method 1:

 Method 1 is the naive implementation that was provided to us initially in the lab. It simply runs through each value and multiplies it storing the new value in the output array. The slowdown here is multiplication of a floating point number which is relatively resource intensive so I would expect this to be the slowest implementation.

real   0m0.520s - 0m0.496s  = 0.024s
user   0m0.490s - 0m0.495s  = -0.005s

sys    0m0.030s - 0m0.000s  = 0.030s

Method 2:

Method 2 pre-calculates all the possible scaled values given the -32768 to 32768 range of possible values. This means it only has to perform 65536 floating point multiplications followed by 10 million table look-ups. I would expect this to be faster than method 1 as a cached table look-up should be faster than floating point multiplication.

real    0m0.541s - 0m0.493s  = 0.048s
user    0m0.521s - 0m0.472s  = 0.049s
sys     0m0.020s - 0m0.020s  = 0.000s

To my surprise it seems like this method timed out slower than method. I suspect that the table look-ups couldn't be done exclusively in cache so it had to access memory which was slowing it down.

Method 3:

Method 3 changes the scaling constant from a floating point number to a fixed point number by multiplying it by a binary representation of 1, in this case 256, and using that to multiply the scale then bit shifting 8 bits to get the same result as a floating multiplication. The one cautionary part of this algorithm is the potential for losing some bits in the shift which impacts the final tally of results.
I would also expect this method to be significantly faster than method 1 as a bit shift operation is very lightweight and fixed vs floating multiplication heavily favors fixed.

real    0m0.511s - 0m0.497s  = 0.014s
user    0m0.471s - 0m0.486s  = -0.015s

sys     0m0.040s - 0m0.010s  = 0.030s

No surprises here, eliminating floating point multiplication reduces the time cost significantly.

Conclusions:

Choosing the right algorithm for the right scenario has clearly been demonstrated to be critical in this lab, as well as fully understanding the context of your options. While I assumed that table look-ups would automatically be faster than the naive approach, repeated memory access proves to have slowed down the program. Considering everything you need out of your program is also crucial. The table look-up method also comes with the added overhead of allocating and storing a large array which might not be ideal in all situations. The shifting method has a chance to slightly alter the results of your program which means it wouldn't be a functional approach for lossless audio.


Comments

Post a Comment

Popular posts from this blog

Lab 1: Investigating Open Source Development

     While most people today have at least heard of Open Source software, many people, myself included, don't know a lot about how the development process works or how these communities are structured and managed. Today's post will explore these topics in reference to two Open Source projects from different licences, Privacy Badger under the GNU General Public License and Deeplearning4j under the Apache2.0 License. Privacy Badger:      Privacy Badger is a browser extension aimed at striking a balance between a user's right to privacy and content providers' business interest. By only blocking ads and cookies that ignore the Do Not Track setting of the user's browser, thus as long as a content provider isn't hosting those types of ads they won't lose out on ad revenues.      Privacy Badger is run primarily off of its GitHub repository (link below) and it seeks to make contribution easy by keeping a list of desired issues to tackle that are publicly avail
Read more

Lab 3: Compiled C Code

Image
     In this lab I investigated the transformation of my code from source C code to C compiler output to learn exactly what the compiler is doing when I call it. My initial program was a simple Hello World program: #include <stdio> int main(){         printf("Hello World!"); }      My first compilation was a simple gcc with most of the optimization and fancy tricks stripped out. This was done with the -O0 and -fno-builtin flags, -O0 meaning do not use any optimizations when compiling and -fno-builtin meaning do use any built in function optimizations. So : gcc -g -O0 -fno-builtin -o hello1 hello.c.       The compiler then returns an Executable and Linkable Format file (ELF for short) named hello1 which I used to examine what it had done to my code. The first thing I noticed after using objdump to look at the assembly code that was output was that my simple four line program had ballooned out to 199 lines which led me to wonder how much bigger my elf fi
Read more

Lab 4: Assembler

     When first starting this lab I was excited to dive in to assembler as it gives a granular understanding of all steps involved in processes that are taken for granted in higher level languages. So after reading through the basic instructions used in assembler I began on the task of writing a program that loops from 0 - 30 printing "Loop: X" with X being the current loop count.      I immediately realized the significant difference between assembler and every other language I have coded with before. Instead of simply declaring variables and doing calculations however I want and dumping the results to the screen, its important to line all of the data I want up before executing any command and this lab really highlights this process. So we know the end result is a printed string 30 times, step 1 of which is getting a string to print. I created a .data section to hold both my string and the length of that string. This is important because unlike in C I can't replace X w
Read more