This post is about the optimization of the FreeTiger hashing algorithm.
FreeTiger hasn’t been updated in over 6 years and its C++ implementation was based on an even older version. I had high hopes that I’ll be able to make it more efficient and optimized but I haven’t been able to.
The algorithm mainly uses memory copy with aligned memory to hash a given string. I have been unable to get any performance improvement over the current design of the algorithm.
The function I was focusing on for the optimization was tiger_1025. Vectorization was out of the question because of the really limited use of loops. Memory copy is sensitive and I didn’t have much success with that either. However, using the compilation flags, I did see and improvement in the numbers. The improvement was really small and substantial enough only when dealing with really large strings, such as strings which were 2MB in size.
Here are the results:
|Optimization level||O0 (O-zero)||O3 (O-three)|
|Time taken (secs)||13.31463184||13.12705364|
Now it was at all possible that the numbers I got were just within margin of error. So, to avoid that I used a large data set. The results posted above above are averages of 50,000 runs of the tester.
The tests were also run on a Rasberry Pi 3 on Fedora, and the results were basically same with similar improvement when using large strings in the data set.
The algorithm is already really nicely implemented and I couldn’t find anything that I could do to make it better. I did find another version of the Tiger algorithm, Cryptonite Tiger, this version has added support for multi-processor support for up-to 8 cores and also rectifies several cases of unaligned access but still doesn’t have any changes to the original working algorithm, other than some streamlining in the code by efficiently separating out declarations for different functions.
No changes were made to the code, so upstream requests don’t make sense and even if they were viable, there is no one maintaining the original repository.
This concludes my work on the project for SPO600.