Three-Star
Team Members
Progress
Assignment 1
Image Profiling
Chosen to profile image profiling as shown here: http://www.dreamincode.net/forums/topic/76816-image-processing-tutorial/ , using the sample programs (main/image.h/image.cpp) Slightly modified main.cpp to accomodate larger images. Had to expand a PGM image (to about 83~MB size) to return any meaningful result (Using a regular sized PGM image of 11KB yielded absolutely no meaningful results to the human eye - all 0's on the flat profile/call graph)
The results of the flat profile:
Flat profile:
Each sample counts as 0.01 seconds.
% cumulative self self total time seconds seconds calls ms/call ms/call name 55.49 1.01 1.01 3 336.67 336.67 Image::Image(Image const&) 28.57 1.53 0.52 6 86.67 86.67 Image::Image(int, int, int) 9.34 1.70 0.17 1 170.00 290.00 readImage(char*, Image&) 6.59 1.82 0.12 16000000 0.00 0.00 Image::setPixelVal(int, int, int) 0.00 1.82 0.00 30 0.00 0.00 Image::getPixelVal(int, int) 0.00 1.82 0.00 9 0.00 0.00 Image::~Image() 0.00 1.82 0.00 8 0.00 0.00 std::operator|(std::_Ios_Openmode, std::_Ios_Openmode) 0.00 1.82 0.00 6 0.00 0.00 writeImage(char*, Image&) 0.00 1.82 0.00 6 0.00 0.00 Image::getImageInfo(int&,int&, int&) 0.00 1.82 0.00 6 0.00 0.00 Image::operator=(Image con 0.00 1.82 0.00 2 0.00 0.00 std::cos(float) 0.00 1.82 0.00 2 0.00 0.00 std::sin(float) 0.00 1.82 0.00 1 0.00 0.00 _GLOBAL__sub_I__ZN5ImageC2Ev 0.00 1.82 0.00 1 0.00 0.00 readImageHeader(char*, int&, int&, int&, bool&) 0.00 1.82 0.00 1 0.00 0.00 __static_initialization_and_destruction_0(int, int) 0.00 1.82 0.00 1 0.00 86.67 Image::getSubImage(int, int, int, int, Image&) 0.00 1.82 0.00 1 0.00 86.67 Image::negateImage(Image&) 0.00 1.82 0.00 1 0.00 86.67 Image::rotateImage(int, Image&) 0.00 1.82 0.00 1 0.00 86.67 Image::shrinkImage(int, Image&) 0.00 1.82 0.00 1 0.00 86.67 Image::enlargeImage(int, Image&) 0.00 1.82 0.00 1 0.00 336.67 Image::reflectImage(bool,Image&) 0.00 1.82 0.00 1 0.00 0.00 Image::inBounds(int, int)
Out of all the functions tested, reflectImage has the largest ms/call. Below is the code for reflectImage:
void Image::reflectImage(bool flag, Image& oldImage) /*Reflects the Image based on users input*/ {
int rows = oldImage.N;
int cols = oldImage.M;
Image tempImage(oldImage);
if(flag == true) //horizontal reflection
{
for(int i = 0; i < rows; i++)
{
for(int j = 0; j < cols; j++)
tempImage.pixelVal[rows - (i + 1)][j] = oldImage.pixelVal[i][j];
}
}
else //vertical reflection
{
for(int i = 0; i < rows; i++)
{
for(int j = 0; j < cols; j++)
tempImage.pixelVal[i][cols - (j + 1)] = oldImage.pixelVal[i][j];
}
}
oldImage = tempImage;
}
LZW Data Compression Algorithm
Timothy Moy profiled.
Original algorithm: https://codereview.stackexchange.com/questions/86543/simple-lzw-compression-algorithm
Summary of Profiles
| Size (MB) | Compress() time in seconds |
|---|---|
| 10 | 0.96 |
| 15 | 1.35 |
| 20 | 1.8 |
| 25 | 2.14 |
| 30 | 2.64 |
| 35 | 3.16 |
| 40 | 3.45 |
| 45 | 4.24 |
| 50 | 4.23 |
The compress function seems to have some room for improvement as can be seen in the source code below
void compress(string input, int size, string filename) {
unordered_map<string, int> compress_dictionary(MAX_DEF);
//Dictionary initializing with ASCII
for ( int unsigned i = 0 ; i < 256 ; i++ ){
compress_dictionary[string(1,i)] = i;
}
string current_string;
unsigned int code;
unsigned int next_code = 256;
//Output file for compressed data
ofstream outputFile;
outputFile.open(filename + ".lzw");
// Possible area for improvement via reduction
for(char& c: input){
current_string = current_string + c;
if ( compress_dictionary.find(current_string) ==compress_dictionary.end() ){
if (next_code <= MAX_DEF)
compress_dictionary.insert(make_pair(current_string, next_code++));
current_string.erase(current_string.size()-1);
outputFile << convert_int_to_bin(compress_dictionary[current_string]);
current_string = c;
}
}
if (current_string.size())
outputFile << convert_int_to_bin(compress_dictionary[current_string]);
outputFile.close();
}
Note the comment above the second for loop notes we can do something like this:
for (int i = 1; i < n; i+=) a[0] += a[i];
changed to
for (int s = 1; s <= n/2; s*=2) for(int j = 0; j < n; j +=2 * s) a[j] += a[j + s];
The first for loop is constant and probably won't show much improvement if we parallelize it. As such, the major hotspot in this function is the second for loop. This is especially true since the file might be very large and we may be dealing with millions of characters!