flat assembler
Message board for the users of flat assembler.
![]() |
Author |
|
bitRAKE 11 Jan 2008, 22:44
Looking through the FASM source code it appears to use the FNV hash algorithm and then a hash tree of depth 32. Each node in the hash tree uses 8 bytes and is potentially a cache-miss. I'm curious as to why this choice was made, and what other methods were tested?
Ideally, a hash should be a single cache miss - which easily offsets the costs of calculating the hash code. Why waste memory and time with a hash tree? Only real benefit being that it is adaptive in terms of memory use? |
|||
![]() |
|
Tomasz Grysztar 11 Jan 2008, 23:27
See this thread to see what tests were done (there were even some graphs done):
http://board.flatassembler.net/topic.php?t=854 The cache miss is just a constant coefficient, so it doesn't affect the algorithm complexity (the O() notation) - which becomes more important when dealing with so huge amounts of symbols. |
|||
![]() |
|
bitRAKE 12 Jan 2008, 00:09
So, you improved the hash function after adding the hash tree - that makes sense. Very enlightening thread, thank you.
|
|||
![]() |
|
< Last Thread | Next Thread > |
Forum Rules:
|
Copyright © 1999-2025, Tomasz Grysztar. Also on GitHub, YouTube.
Website powered by rwasa.