Below is a screenshot of the callgrind results visualized with the help of KCachegrind tool. Functions sorted by the cost of the function itself. Total instruction fetch cost: 29 541 735.
As we can see one of the most time-consuming function is hash table contain (is_in_list()). So in order to expedite it move the elements of linked lists in __m256i vectors and get the opportunity to use intrinsics. Total instruction fetch cost: 9 481 740. Optimization efficiency ~ 70%.
After first optimization most expensive function if linked list data verificator. Expedite it by rewriting it in ASM. Total instruction fetch cost: 9 019 168 Optimization efficiency ~ 5%.
Five hash functions were tested for training purposes:
- Constant hash function
- First's byte ASCII code function
- Length of object function
- Sum of ASCII codes of object bytes function
- Crc32
Below are graphs of dependence of linked list loading on its number.
