Developer forums (C::B DEVELOPMENT STRICTLY!) > CodeCompletion redesign

patch : from std::map replace to hashmap

<< < (9/9)

koso:

--- Quote from: thomas on March 27, 2010, 10:31:12 pm ---2. is correct, but 1. is not. If you have collisions, there is either a linked list in the respective slot or some other scheme (linear/quadratic probing) is used to place values in different slots.
In either case, this is guaranteed to take more than one string comparison and more than one cache miss on the average. A string compare is a triple dereference, which usually means 3 cache misses if you have enough different strings. Three cache misses are approximately 1500 cpu cycles gone, and this isn't event taking the actual compare in account. You can run a lot of hash function in 1500 cycles :)

--- End quote ---

You have probably missed my assumption that mapped strings (strings stored in hash table) have all different hash values. There are most probably linked lists (called tokens), but all with only one string. This assumption is broken once user adds some custom replacing rules with "not good" strings.

And about cache I must confess I don't understand what you think with "cache" ... it is something related to wxString? I have not much  experience with wx programming, only with standard "direct memory" accessible c/c++ strings ...

And you are right, that multiplication with 33 is not as complex, as i wrote. Now I realized that 33 has hamming weight only 2. Your hash function usable as a general purpose hash function for wxString, but I still thinks It can be more effective, once hash function is optimized to C::B needs (i.e. use knowledge, that mapped string are mostly uppercase, and searched string are mostly lowercase, and at least in my case, they are much shorter).

PS: but even quiet bad hash function seems to by much faster, than used <map>. Used hash function is only detail which can be tweaked later. It will be even easier with testing on real projects, than using synthetic tests and theoretical assumptions ;)

Navigation

[0] Message Index

[*] Previous page