Project

General

Profile

Task #2254

Rewrite ContentStore based on ContentStore stub

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

Status:
Closed
Priority:
Normal
Assignee:
Category:
Tables
Target version:
Start date:
Due date:
% Done:

100%

Estimated time:
9.00 h

Description

Refine ContentStore stub and make it the primary ContentStore.

Background

"ContentStore stub" is an alternate ContentStore implementation which focuses on correctness.
It has been used to cross-validate ContentStore matching test cases (#1321 #2118).

The current ContentStore (#1211) bypassed code review due to scheduling reasons.
It is tightly coupled with a custom SkipList data structure.
It's hard to extend it with new features.

There is a possibility of refining the stub so that it can replace the primary ContentStore, and then use this as a basis for future extensions.

This Task contains:

  • investigate the feasibility of use the stub as primary ContentStore
  • identify what needs refinement / improvements
  • refine those areas
  • merge into master branch

Related issues

Blocks NFD - Task #1706: Reduce implicit digest computation in ContentStoreClosed

Blocks NFD - Feature #1207: CS policy interfaceClosed2015-02-26

History

#1 Updated by Junxiao Shi over 4 years ago

  • Status changed from New to In Progress

The current ContentStore uses a custom SkipList as the Name index, while the stub uses std::set as the Name index.
I've performed a benchmark using cs-smoketest tool, to compare their performance.

"current CS" refers to commit 60607c734d6a4699f2921e6e0ba2ac418f0f8c50;
"CS stub" refers to commit 3d6c8583175c5aea76f542c63d754c09ca98c975.

OS nIterations current CS CS stub
Ubuntu 12.04 4000 0.473s 118us/op 0.467s 117us/op
Ubuntu 12.04 256000 23.2s 90us/op 39.7s 155us/op
Ubuntu 12.04 8192000 743s 91us/op 1308s 160us/op
OSX 10.9 4000 0.201s 50us/op 0.290s 72us/op
OSX 10.9 256000 12.1s 48us/op 23.9s 94us/op
OSX 10.9 8192000 396s 48us/op 776s 95us/op

CS stub is more than 50% slower than current CS, thus lookup performance is definitely a necessary improvement.

I plan to replace std::set with repo-ng's templated SkipList implementation, and redo the benchmark after that.

I've sent a request for permission of importing code to the author of repo-ng skiplist.hpp.

#2 Updated by Junxiao Shi over 4 years ago

I realize that the benchmark in note-1 is performed with --debug option, which cannot reflect the performance of release builds.
Thus I'm redoing the benchmark with release builds, where both ndn-cxx and NFD are compiled without --debug option.

I also imported repo-ng skiplist with permission, and altered CS stub to use skiplist.

"current CS" refers to commit 75ab6b765f573812fe2deceddabf0b9e5da870eb;

"CS stub std::set" refers to commit 3d6c8583175c5aea76f542c63d754c09ca98c975;

"CS stub skiplist" refers to commit b671977ad728bf88b396ae8c10eb296ec787eba6.

OS nIterations current CS CS stub std::set CS stub skiplist
Ubuntu 12.04 4000 0.104s 26us/op 0.123s 31us/op 0.159s 40us/op
Ubuntu 12.04 32000 0.833s 26us/op 1.10s 34us/op 1.46s 46us/op
Ubuntu 12.04 256000 6.26s 24us/op 9.76s 38us/op 12.8s 50us/op
Ubuntu 12.04 8192000 210s 26us/op 320s 39us/op 397s 49us/op
OSX 10.9 4000 0.0496s 12us/op 0.0699s 17us/op 0.0865s 22us/op
OSX 10.9 32000 0.396s 12us/op 0.634s 20us/op 0.783s 24us/op
OSX 10.9 256000 3.01s 12us/op 5.36s 21us/op 7.13s 28us/op
OSX 10.9 8192000 93.8s 11us/op 179s 22us/op 211s 26us/op

Undoubtedly, CS stub is still slower than current CS, but CS stub skiplist is even slower.

repo::SkipList is designed to be same as current CS's skip list and uses the same algorithm.

Either there's a problem in repo::SkipList implementation, or the bottleneck is somewhere else in CS stub.

#3 Updated by Junxiao Shi over 4 years ago

Then I recall a serious problem: "current ContentStore" has a default capacity of 10 entries, but "CS stub" has a default capacity of 50000 entries.

Thus the comparison in note-2 is unfair, because "current ContentStore" has a much smaller index size.

I'm modifying "current CS" and redoing this particular benchmark.

"current CS" refers to commit 75ab6b765f573812fe2deceddabf0b9e5da870eb, modified as nMaxPackets = 50000;

"CS stub std::set" refers to commit 3d6c8583175c5aea76f542c63d754c09ca98c975;

"CS stub skiplist" refers to commit b671977ad728bf88b396ae8c10eb296ec787eba6.

OS nIterations current CS CS stub std::set CS stub skiplist
Ubuntu 12.04 4000 0.123s 31us/op 0.123s 31us/op 0.159s 40us/op
Ubuntu 12.04 32000 1.19s 37us/op 1.10s 34us/op 1.46s 46us/op
Ubuntu 12.04 256000 13.0s 51us/op 9.76s 38us/op 12.8s 50us/op
Ubuntu 12.04 8192000 454s 55us/op 320s 39us/op 397s 49us/op
OSX 10.9 4000 0.0635s 16us/op 0.0699s 17us/op 0.0865s 22us/op
OSX 10.9 32000 0.568s 18us/op 0.634s 20us/op 0.783s 24us/op
OSX 10.9 256000 5.18s 20us/op 5.36s 21us/op 7.13s 28us/op
OSX 10.9 8192000 175s 21us/op 179s 22us/op 211s 26us/op

The new conclusion is: CS stub std::set is somewhat faster than current CS on Ubuntu 12.04, and has comparable performance on OSX 10.9;

using repo::SkipList is slower than using std::set.

#4 Updated by Junxiao Shi over 4 years ago

20141203 conference call approves to continue with this Task.

A new code branch is needed for ContentStore work.

#5 Updated by Junxiao Shi over 4 years ago

Branch feature-cs is created for this effort.

#6 Updated by Junxiao Shi over 4 years ago

  • % Done changed from 0 to 50
  • Estimated time set to 6.00 h

First commit: http://gerrit.named-data.net/1543

Upcoming commits:

  • improve ChildSelector=rightmost processing (in this Task)
  • eliminate implicit digest computation (in #1706)
  • split cache replacement policy into a separate module (in #1207)

#7 Updated by Junxiao Shi over 4 years ago

  • Blocks Task #1706: Reduce implicit digest computation in ContentStore added

#8 Updated by Junxiao Shi over 4 years ago

#9 Updated by Junxiao Shi over 4 years ago

  • Assignee changed from Junxiao Shi to Shashwat Vidhu Sher

First commit is merged to feature-cs branch. Remaining work of this Task is reassigned to @Shashwat.

#10 Updated by Shashwat Vidhu Sher over 4 years ago

  • Assignee deleted (Shashwat Vidhu Sher)

Not able to work on the development of new CS lookup logic due to other circumstances. Kindly reassign the task

#11 Updated by Junxiao Shi over 4 years ago

  • Assignee set to Junxiao Shi

#12 Updated by Junxiao Shi over 4 years ago

  • % Done changed from 50 to 70

http://gerrit.named-data.net/1605 implements a more efficient algorithm for ChildSelector=rightmost.

Upcoming commits in this Task:

  • allow iteration over CS entries; public API shall be compatible with master branch
  • merge into master branch

#13 Updated by Junxiao Shi over 4 years ago

From fb1243a48fdba196bd2915f56b86e13e1f466d2a review:

Can you provide some performance comparison between previous version and this one? Specifically for the case of usage of rightmost selector.

There is no reasonable benchmark for ChildSelector=rightmost, and I don't have resource to create one.

I can only provide the calculations below.

Commit fb1243a48fdba196bd2915f56b86e13e1f466d2a, previous commit a93881804758e297674f68e2b8354d3a9096c7af, and the ContentStore currently in master branch have same worst case performance: all Data packets in the ContentStore will be visited.

The worst case scenario happens when Interest Name=ndn:/, simple selectors reject all Data packets.

However, this commit fb1243a48fdba196bd2915f56b86e13e1f466d2a is expected to have better performance in expected case: there exists one or more Data packets under the prefix of Interest Name which are accepted by simple selectors, and the last of such Data packets is near the right end of the sub tree.

Given the following 1000 Data packets,

  • /A/v0/s0, /A/v0/s1, ... , /A/v0/s99
  • /A/v1/s0, /A/v1/s1, ... , /A/v1/s99
  • ...
  • /A/v9/s0, /A/v9/s1, ... , /A/v9/s99

and given an Interest Name=ndn:/A, ChildSelector=rightmost, Exclude=[v8,Infinity), the correct answer is /A/v7/s0.

Previous commit a93881804758e297674f68e2b8354d3a9096c7af and the ContentStore currently in master branch will visit all 1000 Data packets, from left to right.

This commit fb1243a48fdba196bd2915f56b86e13e1f466d2a will visit 201 Data packets:

  • /A/v9/s0, /A/v9/s1, ... , /A/v9/s99
  • /A/v8/s0, /A/v8/s1, ... , /A/v8/s99
  • /A/v7/s0

The overhead of the new design is more lower_bound calls.

In the example above, lower_bound is invoked 5 times on /A, /B, /A/v9, /A/v8, /A/v7.

#14 Updated by Junxiao Shi over 4 years ago

  • % Done changed from 70 to 80

#15 Updated by Junxiao Shi over 4 years ago

In the other commit we separated implementation of the cs entry from generaic cs entry. I want to have exactly the same separation. In other words, daemon/table/cs-entry.(hpp|cpp) should be exactly as in the other branch. Here you can create a specific cs entry (e.g., cs-std-map-entry.hpp).

It's unfeasible to do so because the memory allocation model is completely different.

"current CS" pre-allocates all Entry objects, and reuses them. However, there is no benchmark supporting this usage.

My design lets std::map allocate and deallocate Entry objects. This means: Entry must be copyable, and 'reset' operation doesn't make sense.

CS is the most volatile data structure and I would prefer to keep it as flexible as possible, given that we already did that in the other branch.

cs::Entry, as dereferenced from CS iterator, just needs to satisfy a concept.
I don't see the necessity for a fixed type.

Also. What is motivation behind moving Cs into cs namespace?

This is how things are supposed to be: declare in inner namespace, and expose with using.

One practical benefit is to simplify implementation: I can write TableIt instead of cs::TableIt in declaration of a function in Cs class.

Boost has many instances of this practice.

#16 Updated by Alex Afanasyev over 4 years ago

Junxiao Shi wrote:

In the other commit we separated implementation of the cs entry from generaic cs entry. I want to have exactly the same separation. In other words, daemon/table/cs-entry.(hpp|cpp) should be exactly as in the other branch. Here you can create a specific cs entry (e.g., cs-std-map-entry.hpp).

It's unfeasible to do so because the memory allocation model is completely different.

"current CS" pre-allocates all Entry objects, and reuses them. However, there is no benchmark supporting this usage.

My design lets std::map allocate and deallocate Entry objects. This means: Entry must be copyable, and 'reset' operation doesn't make sense.

What I was talking has no relationship to memory allocation. It is separates the base interface from the rest.

CS is the most volatile data structure and I would prefer to keep it as flexible as possible, given that we already did that in the other branch.

cs::Entry, as dereferenced from CS iterator, just needs to satisfy a concept.
I don't see the necessity for a fixed type.

You pushed for this in the other branch, therefore I would insist in doing the same thing again in the new branch.

#17 Updated by Junxiao Shi over 4 years ago

What I asked for was: do not expose details of CS entry to caller of CS enumeration functionality.

My suggested design was:

  • the iterator is dereferenced to Entry type
  • the internal entry type is convertible to Entry type, but does not have to inherit from Entry

"current CS" implements:

  • the iterator is dereferenced to Entry type
  • skip_list::Entry is used internally
  • skip_list::Entry inherits from Entry type, but Entry type still contains methods that are specific to this particular implementation and may or may not make sense for other implementations

Commit db194ebb62353a38095cf38106509f4a91a2d3c2 implements:

  • the iterator is dereferenced to Entry type
  • Entry type is also used internally, but internal APIs are private and made accessible by a friend class declaration

This design satisfies the original requirement of not exposing internal details to caller of CS enumeration functionality.

#18 Updated by Alex Afanasyev over 4 years ago

The proposed design is not general enough for me and is not fully object-oriented.

As I mentioned before, CS is most volatile data structure in NFD and one would want to experiment with, potentially, completely different implementation that will co-exist with the current CS. Not having general-purpose cs::Entry prevents this to happen without actually making such class.

Making CS a friend of entry exposes all internals of the CS entry to a specific CS implementation, while all it needs is to have an interface to do implementation-specific access. Having base cs::Entry class and child cs::::Entry allows exactly this behavior in purely objective oriented way without the friend hacks.

#19 Updated by Junxiao Shi over 4 years ago

I somewhat agree with note-18.

But I'll have to delete 'noncopyable' on cs::Entry to make it work.

#20 Updated by Alex Afanasyev over 4 years ago

I'm ok with that.

However, why do you need to remove? C++11 std::set should be happy with classes that cannot be copyable, but just movable (I could be wrong here though).

#21 Updated by Junxiao Shi over 4 years ago

  • Estimated time changed from 6.00 h to 9.00 h

I will rework the Change to make internal cs::EntryImpl inherit from public cs::Entry.

I'll keep noncopyable on cs::Entry if feasible.

#22 Updated by Junxiao Shi over 4 years ago

Commit 11e54217c28265d8bb86cd421493baeee446970b imports cs::Entry from master branch, with the following changes:

  • reorganize methods into "exposed through enumeration" and "used by CS implementation" categories
  • improve documentation
  • add bool canSatisfy(const Interest& interest) const
  • add bool hasData() const
  • add void setData(shared_ptr<const Data> data, bool isUnsolicited)
  • delete noncopyable: gcc46 doesn't like std::set<noncopyable>

#23 Updated by Junxiao Shi over 4 years ago

CS benchmark http://gerrit.named-data.net/1659

ContentStore capacity is set to 50000. Each test case has 200000 iterations.
Total time in microseconds is reported.
"improvement" column is calculated as "100% - newCS / oldCS".

test case platform old CS new CS improvement
find(miss)-insert Ubuntu 14.10 9500438 7100286 +25%
find(miss)-insert OSX 10.9 3115232 2990302 + 4%
insert-find(hit) Ubuntu 14.10 8441608 6891072 +18%
insert-find(hit) OSX 10.9 3123356 2976145 + 4%
find(leftmost,hit) Ubuntu 14.10 173714 183760 - 5%
find(leftmost,hit) OSX 10.9 121608 130841 - 7%
find(rightmost,hit) Ubuntu 14.10 470980 256403 +45%
find(rightmost,hit) OSX 10.9 338288 188953 +44%

Benchmark results show that:

  • New ContentStore has a major performance improvement for insert+find test cases on Ubuntu, and a minor improvement on OSX.
  • New ContentStore has a major performance improvement for find with ChildSelector=rightmost. This test case has 10 Data packets under Interest prefix.
  • New ContentStore has a minor performance disadvantage for find with ChildSelector=leftmost.

Despite the minor disadvantage in one test case, I think the new ContentStore is ready to be used as the default.

#24 Updated by Alex Afanasyev over 4 years ago

I would not call 20% a major performance change, but I am happy with the results and have no objections of merging. I hope we are keeping the benchmark in the repository (I saw some commits are abandoned)?

#25 Updated by Junxiao Shi over 4 years ago

The benchmark is in the Change referenced in note-23, which shall be merged.

cs-smoketest.cpp is deleted as part of this Change, because it has two problems:

  • The same Data is reused on multiple insertions. If a CS implementation computes implicit digest, such computation only occurs once for each Data. Overhead is under represented.
  • ContentStore capacity isn't set, so it's testing a CS with 10 entries.

#26 Updated by Junxiao Shi over 4 years ago

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

http://gerrit.named-data.net/1663 is the final commit of this Task: merge new ContentStore into master.

The correctness of new ContentStore is guaranteed by test cases.

The performance of new ContentStore is no worse than the old ContentStore in most case, as shown in note-23.

Thus, it can replace old ContentStore.

After this Change is merged, feature-cs branch can be deleted, and #2193 can be abandoned.

#27 Updated by Junxiao Shi over 4 years ago

  • Status changed from Code review to Closed

#28 Updated by Junxiao Shi over 4 years ago

  • Status changed from Closed to In Progress

Reopening: nfd::cs::skip_list::Entry belongs to the old ContentStore implementation, but it's not deleted during the merge.

#29 Updated by Junxiao Shi over 4 years ago

  • Status changed from In Progress to Code review

#30 Updated by Junxiao Shi over 4 years ago

  • Status changed from Code review to Closed

Also available in: Atom PDF