Task #1305
closed
NameTree optimization
100%
Description
Refine and optimize NameTree implementation:
- implement better hash function for ndn::Name
- investigate
boost::unordered_map - implement shrinking of hashtable nBuckets when utilization is low
Updated by Haowei Yuan over 10 years ago
- % Done changed from 0 to 40
Optimization 1: Hash Function
The new hash functions takes a second parameter, which specifies how many components should be used for calculating the hash value, this way, functions like Longest Prefix Matching won't need to make n copies of the name.
Updated by Haowei Yuan over 10 years ago
I am trying to use city hash functionsfor the optimized hash function, this would require adding city.hpp and city.cpp to the repository.
- At the current stage of the project, shall I place these two files under the /table directory?
- I tried to put these two files under namespace nfd, but there were some errors. Would it be OK if these two files are not under nfd?
Updated by Junxiao Shi over 10 years ago
city-hash and other third-party code can be placed in core/, and can be kept in its original namespace.
They are also exempt from CodeStyle except that using namespace is not allowed in header files.
Please make sure the code is usable under GPL3.
Updated by Haowei Yuan over 10 years ago
I see. CityHash is using MIT license, which is GPL compatible.
Updated by Junxiao Shi over 10 years ago
- Status changed from In Progress to Code review
- % Done changed from 40 to 80
Updated by Junxiao Shi over 10 years ago
- Status changed from Code review to Closed
- % Done changed from 80 to 100
Updated by Alex Afanasyev over 10 years ago
What about the second item in the description? Has this been investigated or we abandoning it?
Updated by Haowei Yuan over 10 years ago
Alex Afanasyev wrote:
What about the second item in the description? Has this been investigated or we abandoning it?
I haven't looked into using boost::unordered_map. The original idea was using unordered_map as an optimization, although it was not clear if unordered_map can be used efficiently. I think it is beneficial to look into this problem, so maybe we could create another task, and (probably) this will not be included for the first release.
Updated by Alex Afanasyev over 10 years ago
I'm ok with it. Just wanted to double check.
Technically, just boost::unordered_map may have limitation, but there is also boost::intrusive::unordered_map, that may be a better option, given that we store the same item in multiple places (do we?). In any case, this is a separate issue.
Updated by Haowei Yuan over 10 years ago
Alex Afanasyev wrote:
I'm ok with it. Just wanted to double check.
Technically, just boost::unordered_map may have limitation, but there is also boost::intrusive::unordered_map, that may be a better option, given that we store the same item in multiple places (do we?). In any case, this is a separate issue.
I don't think we store the same item in multiple places. Do you have an example? Some information is stored "multiple times", for example, if we have prefixes /A and /A/B, then we have to store /A and /A/B in two hash buckets (ideally, we need to store only /A and /B, where /B is a suffix of /A). This behavior will not be changed by using boost hash table implementation.