The following is my Nasm modified version of the FNV-1 hash algorithm for use in both 32-bit and 64-bit systems. That way, the routines may be used to hold objects of all types for any purpose ( token processing, game world objects, in-memory databases, caching, etc. Thus the routines being developed do not depend on simple character strings (although you can indeed supply them to the functions). I want the hashing function and the hash map to be capable of holding arbitrary types and data sizes. Thus I begin by defining a hash map to contain the key/value pairs and develop the hashing function. I've settled on using hash maps and the hash function algorithm FNV-1 which, according to the authors, provides for a nice dispersion across a hash map. One of the things that I need is a fast way of performing lookups of defines and typedefs. After creating the initial program outline I am now ready to begin adding in the preprocessing support. QuoteOk, I've started working on my own version of h2incn - a program that will parse C header files and convert them into Nasm compatible. which I'll try over the next few days.Īttached are the sources and a log-log chart comparing performance between the dictionary and the SortedStrCollection. There are many possible improvements like testing other hashing algorithms, in-place allocation, close addressing, etc. The SortedCollection does not suffer from this effect, since all item pointers remain in place when the internal table is resized. Still, looking at the results, searching and deleting outperforms the binary search, even for very small element counts.Ī major disadvantage comes into play when a HashTable needs to be resized, which requires all elements to be reinserted by hashing them again. The overhead of the hash calculation is significant when there are only a few elements in the containers.Hash collisions degrade the performance of the HashTable.In theory, a dictionary should perform with O(1) while the SortedStrCollection using the binary search should perform with O(n). This combination results in 126 collisions for 512 items.Īs a performance reference, I used a binary tree in form of a highly optimized object called SortedStrCollection(W). My first attempt was to use the well-known FNV-1a hashing algorithm and a naive deletion strategy using tombstones, which are widely used in the literature. I intentionally left aside all the necessary memory allocations to just focus on inserting, searching and deleting the dictionary entries. I've chosen a DWORD that I've initialized with an incrementing index for demonstration purposes. It handles string keys of any length and a payload of any kind. In this case I created a Dictionary from the HashTable using open addressing. This has the advantage that different classes can be created using different strategies.Īs I mentioned before, I took some inspiration from Python, but at the end, I came with a slightly different approach, which maybe is not better, but is good enough as a starting point. The HashTable is defined such that the hashing and collision handler are implemented in a derived object. It took some effort but finally I got it working.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |