Task #2781
closed
Fib and FaceMap should be implemented using std::map instead of std::list
Added by Vince Lehman over 9 years ago.
Updated about 8 years ago.
Description
Currently, the Fib holds a collection of FibEntries in an std::list and FaceMap holds a collection of FaceMapEntries in an std::list.
Lookup could be optimized by using std::map.
- Subject changed from Fib should be implemented using std::map instead of std::list to Fib and FaceMap should be implemented using std::map instead of std::list
- Description updated (diff)
- Target version set to v0.3.0
- Assignee set to Vince Lehman
- Assignee deleted (
Vince Lehman)
- Target version changed from v0.3.0 to v0.3.1
- Assignee set to Nicholas Gordon
It seems to me that map is overkill. std::map orders the elements, and I'm not sure that's useful to us. If we are looking to optimize lookup and order is irrelevant, then std::unordered_map is best. It is essentially a hash map.
Can anyone comment if there would be some reason to order the FIB entries?
- Status changed from New to Code review
- % Done changed from 0 to 90
I have taken the liberty of assuming that lookup will always be more important in these cases. I have pushed my patch to gerrit. It compiles and passes the tests.
https://gerrit.named-data.net#/c/3239/
Consulting with Vince has revealed to me that unordered_map has some issues when using strings as the key type, and overcoming these costs incurs a significant memory cost. As such, the patch has been refactored to use std::map. (as per the original specification!)
- Status changed from Code review to Closed
- % Done changed from 90 to 100
Also available in: Atom
PDF
Updated by 
Updated by