flat assembler
Message board for the users of flat assembler.

Index > Compiler Internals > Hashing within FASM...

Author
Thread Post new topic Reply to topic
bitRAKE



Joined: 21 Jul 2003
Posts: 4249
Location: vpcmpistri
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?
Post 11 Jan 2008, 22:44
View user's profile Send private message Visit poster's website Reply with quote
Tomasz Grysztar



Joined: 16 Jun 2003
Posts: 8428
Location: Kraków, Poland
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.
Post 11 Jan 2008, 23:27
View user's profile Send private message Visit poster's website Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 4249
Location: vpcmpistri
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.
Post 12 Jan 2008, 00:09
View user's profile Send private message Visit poster's website Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  


< Last Thread | Next Thread >
Forum Rules:
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum


Copyright © 1999-2025, Tomasz Grysztar. Also on GitHub, YouTube.

Website powered by rwasa.