Project: Gzip Optimization

I. Introduction:

For this post, we will be discussing possible optimization approaches for Gzip. For more context, please visit building and profiling posts
To understand the code more thoroughly, we will need to have a look at the source code that consists of longest_match function. The code is located at deflate.c in the gzip project

After viewing the implementation of the function, I realize that aside from some checking process to make sure the values are not compromised, this function spent most of it’s time in a do – while loop
As for the checking flags, I noticed there are a flag constantly appears on in the function: UNALIGNED_OK. According to the comment written by the developer, this flag can help to speed up the program speed

As mentioned in the building post, I will be taking the following 2 optimization approaches:
Enable DUNALIGNED_OK debug flag
Find alternative to byte by byte comparison
Find alternative for data structure to simplify assembly code

Fortunately, it appears that this is the easiest way to optimize this program
To test this, I have ran the program before and after the flag enabled to compare the efficiency of this flag

As can be seen from the table above, the program showed a slight improvement in term of running time
Although it showed an increase in execution time, the developers of this project noted that this flag isn’t always reliable so it must be tested on your platform before being used

As for the comparison statement that takes the most time in the loop, I misunderstood the structure the comparison statement
It seems like there isn’t a whole string to perform comparison, the entire comparison were surrounding a byte or a short only so there is not reason to find the alternative to this as it will slow down the program even more
So the next step is to change the data structure to simplify the assembly code but as I look into the header file gzip.h, the data structure used in this function is unsigned char and unsigned short which is the smallest and most efficient data type can be used

On top of that, in the declaration inside longest_match, the variables were created using the register keyword which means the data is stored in the register for faster access so I believe that there is nothing more to optimize for this portion of the code

Although being called the most among all the function, I believe there is nothing more to be done for longest_match function
If we were to optimize this program, it would be wiser to target other functions that also being called more than usual
As analyzed above, longest_match function uses the most efficient data structure and even the register keyword for extra speed