NFD

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.

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.

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.

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.

20141203 conference call approves to continue with this Task.

A new code branch is needed for ContentStore work.

Branch feature-cs is created for this effort.

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.

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.

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.

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.

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.

I somewhat agree with note-18.

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

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

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>

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".

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.

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

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.