NFD

Can you link/reference the benchmark?

The benchmark is done with a modified version of tests/other/cs-smoketest.cpp.

• add data->getFullName() in the dataWorkload preparation loop, so that implicit digest is computed before CS insertion; or comment out this line, and CS insertion algorithm would have to compute implicit digest
• replace the loop of varying nInsertions with a single execution of 70000 insertions; this is needed because dataWorkload array would contain implicit digests after the first execution

The results are:

• CS insertion computes implicit digest: 62.0152 seconds
• pre-computed implicit digest - CS insertion does not compute implicit digest: 32.3143 seconds
• time saving: 48%

@Yi, don't hurry with the implementation of this Task. ContentStore needs a major refactoring, and this is only part of it. Do read the slides.

@Yi did a benchmark on a Macbook Pro:

• CS insertion computes implicit digest: 0.443175 seconds
• pre-computed implicit digest - CS insertion does not compute implicit digest: 0.165358 seconds
• time saving: 63%

Implicit digest computation consumes a greater percentage of time in CS insertion on Macbook.

Another observation is: the same 70000 insertions is 100+ times faster than my benchmark on a Ubuntu 12.04 VM.

It's surprising to see such a significant difference.
This difference is likely to be more than hardware.

I don't remember what compiler options I was using when doing the benchmark.
Yi should repeat the benchmark on Ubuntu using the same compiler options that were used on Macbook.

Since tables-concept-cs_20140117.pptx is written, Data::getFullName function is introduced in ndn-cxx.
This function computes the implicit digest upon first invocation, and caches the result internally.
It would be a duplicate to store a copy of full Name outside of the Data object.

A solution to this problem is: create a Compare of Data where Data::getFullName invocation is minimized, in order to establish an ordered sequence.
CS algorithms never expressly test whether implicit digest has been computed, but only obtain full Name when it's required for a comparison.

Here is my design of implementing CS:

What does not change:

• All public functions have the same name so there is no need to rewrite code outside the CS.
• I did not think of a better way to keep the cleaning index. Therefore, I am keeping the use of boost::multi_index_container.
• There is not many changes to current CS Entry. I just removed things that manipulate skiplist iterators.

Using SkipList implementation from repo-ng:

• The SkipList can be created with a type and a comparator of that type. Inserting and Finding elements takes a object of that type. Here's my design of using the SkipList:
  • To reduce unnecessary digest computation, the comparator function should first compare "getName()". If "getName()" appear to be the same on both side, compare "getFullName()".
  • Since inserting and finding in SkipList requires a object of the type of element in the list, we need to construct a new CS entry once Cs::insert is called (same for Cs::find). This is because the SkipList cannot search object by index. I don't know whether this is tolerable overhead.

When insert to CS:

1. A new CS entry with new data will be created.
2. Call SkipList::find to see whether there is an entry with the same name (including digest if needed) already there in SkipList.
3. If yes:
   1. check unsolicited. If old entry is not unsolicited and new entry is, discard the new entry and return.
   2. Update stale time then return.
4. If no:
   1. Evict one entry if Cs is full.
   2. Insert the new entry to CleanupIndex
   3. Insert the new entry into SkipList then return.

When lookup (This is basically the steps described in Junxiao's slides. Moving forward in SkipList is done by using iterator provided by SkipList in 2nd step):

1. A new CS entry with new data will be created.
2. Use "lower_bound()" to locate starting point. And set nameLength to the number of components in the Interest, set lastMatch to nil.
3. If last component in Interest Name may be an implicit digest, compute the digest of current CS entry.
4. If Interest Name is not a prefix of current CS entry's Name plus implicit digest if computed, goto step 9.
5. if current CS entry violates MinSuffixComponents, MaxSuffixComponents, PublisherPublicKeyLocator, Exclude, MustBeFresh selectors, go to step 8.
6. If ChildSelector prefers leftmost child, return current CS entry.
7. If ChildSelector prefers rightmost child, and ((lastMatch is nil) or (current CS entry and lastMatch have different nameLength-th component)), set lastMatch to current CS entry.
8. Move to next CS entry in the ordered sequence, and goto step 3.
9. Return lastMatch.

When evict entry:

1. Unsolicited entries are evicted first.
2. Stale entries are evicted next.
3. If there is no unsolicited or stale entry, other entries are evicted by the order they are created.
4. This can be maintained by boost::multi_index_container.

For periodically cleanup:

• We decided not to do this during our last meeting with Beichuan.

Additional questions:

• Since now we are using SkipList from repo-ng, I think we need to make NFD depends on it. I am not very familiar with waf. How do I do that?
• Like I mentioned above. Is creating new CS entry just for finding existing entry in SkipList a tolerable overhead?

I am actually not sure whether our skiplist is going to out perform multi-index container. I did a quick look up on multi-index container's performance. It says the implementation is either matching or better than performance of STL containers.

http://www.boost.org/doc/libs/1_56_0/libs/multi_index/doc/performance.html

Neither STL nor Boost has a SkipList.
The SkipList is implemented by repo-ng author, and is not STL container.

Please do some analysis or benchmark to compare which one of the following is faster:

• SkipList for name ordering, Multi-Index Container for cleanup
• Multi-Index Container for both name ordering and cleanup

A possible starting point of this Task is http://gerrit.named-data.net/447 patchset 4.

Although the commit is called "stub", it's a much cleaner ContentStore.

Does the merged CS implementation implements the delayed digest calculation or not yet?

I can think of one potential issue with multiple data packets with the same name (different digests). What is the intended behavior for CS? Keep just one copy?

At API level, ContentStore is not obligated to store or keep any packet.

In current design, the ContentStore will store all Data packets with same Name but different digests.
This behavior is tested in DigestOrder and DigestExclude test cases.

The computation cost is bounded:
When second Data packet with same Name arrives, implicit digests are computed for both Data packets.
When third or more Data packet with same Name arrives, implicit digest is computed for the incoming Data packets, while cached Data packets already have their implicit digests computed.

At most two implicit digest computations can occur per insertion.