Project

General

Profile

Actions

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.

Status:
Closed
Priority:
Low
Target version:
Start date:
05/01/2015
Due date:
% Done:

100%

Estimated time:

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.

Actions #1

Updated by Vince Lehman over 9 years ago

  • 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)
Actions #2

Updated by Vince Lehman over 9 years ago

  • Target version set to v0.3.0
Actions #3

Updated by Vince Lehman over 9 years ago

  • Assignee set to Vince Lehman
Actions #4

Updated by Vince Lehman over 8 years ago

  • Assignee deleted (Vince Lehman)
Actions #5

Updated by Nicholas Gordon about 8 years ago

  • Target version changed from v0.3.0 to v0.3.1
Actions #6

Updated by Nicholas Gordon about 8 years ago

  • Assignee set to Nicholas Gordon
Actions #7

Updated by Nicholas Gordon about 8 years ago

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?

Actions #8

Updated by Nicholas Gordon about 8 years ago

  • 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/

Actions #9

Updated by Nicholas Gordon about 8 years ago

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!)

Actions #10

Updated by Nicholas Gordon about 8 years ago

  • Status changed from Code review to Closed
  • % Done changed from 90 to 100
Actions

Also available in: Atom PDF