Project

General

Profile

Actions
Copy link

Feature #4914

closed

Optimize CS implementation with C++14

Added by Junxiao Shi over 5 years ago. Updated over 5 years ago.

Status:
Closed
Priority:
Normal
Assignee:
Junxiao Shi
Category:
Tables
Target version:
v0.7
Start date:
Due date:
% Done:

100%

Estimated time:
3.00 h

Description

Currently, CS is implemented as an std::set<EntryImpl>, and name lookup involves constructing a "query" EntryImpl for comparison with "real" EntryImpl.
Since C++14, std::set<T>::lower_bound method supports querying with a different type than the key.
Thus, CS implementation can be optimized with this feature.

Actions
Copy link
 #1

Updated by Junxiao Shi over 5 years ago

  • Status changed from New to In Progress
  • Assignee set to Junxiao Shi
Actions
Copy link
 #2

Updated by Junxiao Shi over 5 years ago

  • % Done changed from 0 to 50

https://gerrit.named-data.net/5482
It works in Ubuntu 16. I'll let Jenkins confirm it works everywhere before proceeding with further optimization.
Without "query Entry", I plan to merge EntryImpl type into Entry type.

Actions
Copy link
 #3

Updated by Junxiao Shi over 5 years ago

  • Status changed from In Progress to Code review
  • % Done changed from 50 to 100
Actions
Copy link
 #4

Updated by Junxiao Shi over 5 years ago

  • Status changed from Code review to In Progress
  • % Done changed from 100 to 70

https://gerrit.named-data.net/5482 patchset4 renames a few things:

  • unsetUnsolicited becomes clearUnsolicited. A suggestion was setSolicited but there isn't a definition of "solicited" in forwarding pipelines, so I'd like to keep "unsolicited".
  • "stale" becomes "non-fresh", following terminology used in v0.3 protocol.

There's concern about confusing nfd::cs::iterator typedef. This typedef is extensively used in Policy implementations, so I'll change that in another commit.

Actions
Copy link
 #5

Updated by Davide Pesavento over 5 years ago

cs-benchmark shows no difference in performance before and after this patch.

Actions
Copy link
 #6

Updated by Junxiao Shi over 5 years ago

  • Status changed from In Progress to Code review
  • % Done changed from 70 to 100

https://gerrit.named-data.net/c/NFD/+/5597 renames cs::iterator to cs::Iterator, following previous suggestions.
cs::Iterator is the basis for cache replacement policy implementations, so that it cannot be eliminated.
However, I'm able to simplify some declarations in policy implementations.

Actions
Copy link
 #7

Updated by Davide Pesavento over 5 years ago

Junxiao Shi wrote:

https://gerrit.named-data.net/c/NFD/+/5597 renames cs::iterator to cs::Iterator, following previous suggestions.

If you're talking about my comment, that's definitely NOT what I suggested. I was complaining about aliasing cs::Table::const_iterator to cs::iterator, because I've never seen an iterator type in a namespace, so that alias is very confusing. The implicit suggestion was to drop the using declaration altogether, not to capitalize iterator. Moreover, I have a slight preference for the lowercase name. The casing is a bit inconsistent in NFD at the moment, while ndn-cxx exclusively uses lowercase. If we want to improve consistency, we should converge toward lowercase.

Actions
Copy link
 #8

Updated by Junxiao Shi over 5 years ago

  • Status changed from Code review to Closed
Actions
Copy link

Also available in: Atom PDF