The task was to write HashTable on my list, check, how storage of lists changes with different hash and optimize it with inline assembly. There were seven hash-functions:
- Returns 1
- Returns word's length
- Returns sum of ASCII symbols
- Returns sum of ASCII symbols divided by word's length
- MurMur Hash
- Fletcher Hash
First of all I saw what functions are the slowest
As you can see the most part of runtime takes strcmp and strlen, so I decided to optimize them.
I could use xmm or sse, but I tried another way, because it could be rational, if all words were long.
Firstly I wrote the simplest algorithms of these functions
Strcmp:
Strlen:
and I was surprised by the results:
As you see I won compiler option -O3, so I ended my optimization
Coefficents:
Type | -O0 | -O2 | -O3 |
---|---|---|---|
Without inline asm | 0.57 | 0.88 | 1.00 |
Inline asm | 1.09 | 1.23 | 1.26 |