Project

General

Profile

Actions

Task #1447

open

Replace std::list with std::unordered_map for similar Interests in NameTree entry

Added by Alex Afanasyev about 10 years ago. Updated over 4 years ago.

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

0%

Estimated time:
2.00 h

Description

PIT entries with same Name and different selectors should be looked up in a hash table using hash(selectors.wireEncode()) as a hash index.

The procedure should also include a provision for special case when no selectors are present in interests (there is interest.hasSelectors() method).

Actions #1

Updated by Junxiao Shi almost 10 years ago

20140515 conference call decides that this task should be worked on only if performance profiling proves hashtable would be faster.

Which approach is faster is related to traffic pattern: how many Interests are using same prefix but different selectors?

Actions #2

Updated by Junxiao Shi almost 10 years ago

  • Subject changed from Replace std::list with boost::unordered_set for similar Interests in PIT entry to Replace std::list with boost::unordered_map for similar Interests in NameTree entry
  • Description updated (diff)
  • Target version deleted (v0.2)
Actions #3

Updated by Junxiao Shi almost 10 years ago

  • Estimated time set to 2.00 h

I asked @Wentao Shang for Selector usage in BMS application.
He mentions a use case:

  • Producer names Data with a timestamp NameComponent
  • Consumer expresses Interests to request Data sequentially. Every Interest has the same Name but different Selectors. To request Data in time period (T1,T2), the consumer would:
    1. request with Exclude=Any,T1
    2. when this request is answered, suppose the timestamp in Data is T3, the next Interest would be sent immediately with Exclude=Any,T3
    3. repeat until the timestamp in Data >= T2
  • Consumer sends the next Interest as soon as the previous one is answered. If network latency is low, Interest rate can be very high.

In this use case, it shall be beneficial to organize PIT entries in the same NameTree entry into a hashtable, instead of the current doubly linked list.

Actions #4

Updated by Junxiao Shi almost 10 years ago

20140704 conference call decides not to put this Task for 0.3.

@Wentao Shang should perform performance profiling on a node with extensive Selector usage, and find out what's the bottleneck.

Actions #5

Updated by Junxiao Shi over 9 years ago

A chat with Lixia after NDNcomm2014 points out that application designers have a tendency of abusing selectors. Selectors should be used only for Name discovery, so the use case in note-3 represents a suboptimal application design.

Actions #6

Updated by Wentao Shang over 9 years ago

Junxiao Shi wrote:

@Wentao Shang should perform performance profiling on a node with extensive Selector usage, and find out what's the bottleneck.

NFD profiling has been selected to be one of the course projects for CS217A in Fall'14 at UCLA. If no student picks this project eventually, @Wentao Shang will do the performance profiling.

Actions #7

Updated by Junxiao Shi over 9 years ago

  • Subject changed from Replace std::list with boost::unordered_map for similar Interests in NameTree entry to Replace std::list with std::unordered_map for similar Interests in NameTree entry

I want to clarify the needed profiling as mentioned in note-4:

  • INPUT: Interests with same Name, but many different Selectors
  • find out whether std::list m_pitEntries in NameTree entry is a bottleneck, and whether changing it to std::unordered_map would improve performance

The performance of evaluating each individual Selector is irrelevant to this Task.

Actions #8

Updated by Junxiao Shi over 9 years ago

During 20141215 conference call, Lixia reveals that the course project is NFD stress test (benchmark) on NDN testbed, which is different from what's specified in note-4 and note-7.

Actions #9

Updated by Junxiao Shi over 9 years ago

  • Assignee set to Wentao Shang

I have seen the course project report. It doesn't have the benchmark required by note-4 and note-7.

@Wentao Shang, please do the profiling as you promised in note-6.

Actions #10

Updated by Junxiao Shi over 8 years ago

  • Assignee deleted (Wentao Shang)

At 20151110 conference call, Wentao claims that he will never have time to do the benchmark promised in note-6.

Lixia suggests that we can reject this issue, because there's no evidence it's needed.

Actions #11

Updated by Junxiao Shi over 8 years ago

  • Target version set to Unsupported

20151117 conference call decides that we won't need this for now.

Actions #12

Updated by Davide Pesavento over 4 years ago

  • Target version deleted (Unsupported)
Actions

Also available in: Atom PDF