Optimize NACK list creation.
- No longer looping through all frame buffers.
- Keeping track of the current nack list index when building the list.
- Don't look for changes in the NACK list if the size has increased.
Review URL: https://webrtc-codereview.appspot.com/1076005
git-svn-id: http://webrtc.googlecode.com/svn/trunk@3420 4adac7df-926f-26a2-2b94-8c16560cd09d
diff --git a/webrtc/modules/video_coding/main/source/frame_buffer.cc b/webrtc/modules/video_coding/main/source/frame_buffer.cc
index fe30bea..fe10240 100644
--- a/webrtc/modules/video_coding/main/source/frame_buffer.cc
+++ b/webrtc/modules/video_coding/main/source/frame_buffer.cc
@@ -206,17 +206,16 @@
// Build hard NACK list:Zero out all entries in list up to and including the
// (first) entry equal to _lowSeqNum.
-int VCMFrameBuffer::BuildHardNackList(int* list, int num) {
- if (_sessionInfo.BuildHardNackList(list, num) != 0) {
- return -1;
- }
- return 0;
+int VCMFrameBuffer::BuildHardNackList(int* list, int num,
+ int nack_seq_nums_index) {
+ return _sessionInfo.BuildHardNackList(list, num, nack_seq_nums_index);
}
// Build selective NACK list: Create a soft (selective) list of entries to zero
// out up to and including the (first) entry equal to _lowSeqNum.
-int VCMFrameBuffer::BuildSoftNackList(int* list, int num, int rttMs) {
- return _sessionInfo.BuildSoftNackList(list, num, rttMs);
+int VCMFrameBuffer::BuildSoftNackList(int* list, int num,
+ int nack_seq_nums_index, int rttMs) {
+ return _sessionInfo.BuildSoftNackList(list, num, nack_seq_nums_index, rttMs);
}
void
diff --git a/webrtc/modules/video_coding/main/source/frame_buffer.h b/webrtc/modules/video_coding/main/source/frame_buffer.h
index eeacfad..ef4d154 100644
--- a/webrtc/modules/video_coding/main/source/frame_buffer.h
+++ b/webrtc/modules/video_coding/main/source/frame_buffer.h
@@ -67,10 +67,11 @@
// NACK - Building the NACK lists.
// Build hard NACK list: Zero out all entries in list up to and including
// _lowSeqNum.
- int BuildHardNackList(int* list, int num);
+ int BuildHardNackList(int* list, int num, int nack_seq_nums_index);
// Build soft NACK list: Zero out only a subset of the packets, discard
// empty packets.
- int BuildSoftNackList(int* list, int num, int rttMs);
+ int BuildSoftNackList(int* list, int num, int nack_seq_nums_index,
+ int rttMs);
void IncrementNackCount();
WebRtc_Word16 GetNackCount() const;
diff --git a/webrtc/modules/video_coding/main/source/jitter_buffer.cc b/webrtc/modules/video_coding/main/source/jitter_buffer.cc
index 8121497..b77a95a 100644
--- a/webrtc/modules/video_coding/main/source/jitter_buffer.cc
+++ b/webrtc/modules/video_coding/main/source/jitter_buffer.cc
@@ -926,24 +926,25 @@
nack_seq_nums_internal_[i] = seq_number_iterator;
seq_number_iterator++;
}
- // Now we have a list of all sequence numbers that could have been sent.
- // Zero out the ones we have received.
- for (i = 0; i < max_number_of_frames_; i++) {
- // We don't need to check if frame is decoding since low_seq_num is based
- // on the last decoded sequence number.
- VCMFrameBufferStateEnum state = frame_buffers_[i]->GetState();
- if (kStateFree != state) {
+ if (number_of_seq_num > 0) {
+ // Now we have a list of all sequence numbers that could have been sent.
+ // Zero out the ones we have received.
+ int nack_seq_nums_index = 0;
+ for (FrameList::iterator it = frame_list_.begin(); it != frame_list_.end();
+ ++it) {
// Reaching thus far means we are going to update the NACK list
// When in hybrid mode, we use the soft NACKing feature.
if (nack_mode_ == kNackHybrid) {
- frame_buffers_[i]->BuildSoftNackList(nack_seq_nums_internal_,
- number_of_seq_num,
- rtt_ms_);
+ nack_seq_nums_index = (*it)->BuildSoftNackList(nack_seq_nums_internal_,
+ number_of_seq_num,
+ nack_seq_nums_index,
+ rtt_ms_);
} else {
// Used when the frame is being processed by the decoding thread
// don't need to use that info in this loop.
- frame_buffers_[i]->BuildHardNackList(nack_seq_nums_internal_,
- number_of_seq_num);
+ nack_seq_nums_index = (*it)->BuildHardNackList(nack_seq_nums_internal_,
+ number_of_seq_num,
+ nack_seq_nums_index);
}
}
}
@@ -980,7 +981,6 @@
// Larger list: NACK list was extended since the last call.
*list_extended = true;
}
-
for (unsigned int j = 0; j < *nack_list_size; j++) {
// Check if the list has been extended since it was last created, i.e,
// new items have been added.
diff --git a/webrtc/modules/video_coding/main/source/session_info.cc b/webrtc/modules/video_coding/main/source/session_info.cc
index e40ffea..6c5448b 100644
--- a/webrtc/modules/video_coding/main/source/session_info.cc
+++ b/webrtc/modules/video_coding/main/source/session_info.cc
@@ -353,23 +353,22 @@
}
int VCMSessionInfo::BuildHardNackList(int* seq_num_list,
- int seq_num_list_length) {
- if (NULL == seq_num_list || seq_num_list_length < 1) {
- return -1;
- }
+ int seq_num_list_length,
+ int nack_seq_nums_index) {
+ assert(seq_num_list && seq_num_list_length > 0);
+
if (packets_.empty() && empty_seq_num_low_ == -1) {
- return 0;
+ return nack_seq_nums_index;
}
// Find end point (index of entry equals the sequence number of the first
// packet).
- int index = 0;
int low_seq_num = (packets_.empty()) ? empty_seq_num_low_:
packets_.front().seqNum;
- for (; index < seq_num_list_length; ++index) {
- if (seq_num_list[index] == low_seq_num) {
- seq_num_list[index] = -1;
- ++index;
+ for (; nack_seq_nums_index < seq_num_list_length; ++nack_seq_nums_index) {
+ if (seq_num_list[nack_seq_nums_index] == low_seq_num) {
+ seq_num_list[nack_seq_nums_index] = -1;
+ ++nack_seq_nums_index;
break;
}
}
@@ -379,43 +378,43 @@
PacketIterator it = packets_.begin();
PacketIterator prev_it = it;
++it;
- while (it != packets_.end() && index < seq_num_list_length) {
+ while (it != packets_.end() && nack_seq_nums_index < seq_num_list_length) {
if (!InSequence(it, prev_it)) {
// Found a sequence number gap due to packet loss.
- index += PacketsMissing(it, prev_it);
+ nack_seq_nums_index += PacketsMissing(it, prev_it);
session_nack_ = true;
}
- seq_num_list[index] = -1;
- ++index;
+ seq_num_list[nack_seq_nums_index] = -1;
+ ++nack_seq_nums_index;
prev_it = it;
++it;
}
if (!packets_.front().isFirstPacket)
session_nack_ = true;
}
- index = ClearOutEmptyPacketSequenceNumbers(seq_num_list, seq_num_list_length,
- index);
- return 0;
+ nack_seq_nums_index = ClearOutEmptyPacketSequenceNumbers(seq_num_list,
+ seq_num_list_length,
+ nack_seq_nums_index);
+ return nack_seq_nums_index;
}
int VCMSessionInfo::BuildSoftNackList(int* seq_num_list,
int seq_num_list_length,
+ int nack_seq_nums_index,
int rtt_ms) {
- if (NULL == seq_num_list || seq_num_list_length < 1) {
- return -1;
- }
+ assert(seq_num_list && seq_num_list_length > 0);
+
if (packets_.empty() && empty_seq_num_low_ == -1) {
- return 0;
+ return nack_seq_nums_index;
}
- int index = 0;
int low_seq_num = (packets_.empty()) ? empty_seq_num_low_:
packets_.front().seqNum;
- // Find entrance point (index of entry equals the sequence number of the
- // first packet).
- for (; index < seq_num_list_length; ++index) {
- if (seq_num_list[index] == low_seq_num) {
- seq_num_list[index] = -1;
+ // Find entrance point (nack_seq_nums_index of entry equals the sequence
+ // number of the first packet).
+ for (; nack_seq_nums_index < seq_num_list_length; ++nack_seq_nums_index) {
+ if (seq_num_list[nack_seq_nums_index] == low_seq_num) {
+ seq_num_list[nack_seq_nums_index] = -1;
break;
}
}
@@ -423,9 +422,10 @@
// TODO(mikhal): 1. Update score based on RTT value 2. Add partition data.
// Use the previous available.
bool base_available = false;
- if ((index > 0) && (seq_num_list[index] == -1)) {
+ if ((nack_seq_nums_index > 0) && (seq_num_list[nack_seq_nums_index] == -1)) {
// Found first packet, for now let's go only one back.
- if ((seq_num_list[index - 1] == -1) || (seq_num_list[index - 1] == -2)) {
+ if ((seq_num_list[nack_seq_nums_index - 1] == -1) ||
+ (seq_num_list[nack_seq_nums_index - 1] == -2)) {
// This is indeed the first packet, as previous packet was populated.
base_available = true;
}
@@ -460,10 +460,10 @@
if (!packets_.empty()) {
PacketIterator it = packets_.begin();
PacketIterator prev_it = it;
- ++index;
+ ++nack_seq_nums_index;
++it;
// TODO(holmer): Rewrite this in a way which better makes use of the list.
- while (it != packets_.end() && index < seq_num_list_length) {
+ while (it != packets_.end() && nack_seq_nums_index < seq_num_list_length) {
// Only process media packet sequence numbers.
if (LatestSequenceNumber((*it).seqNum, media_high_seq_num, NULL) ==
(*it).seqNum && (*it).seqNum != media_high_seq_num)
@@ -479,23 +479,24 @@
if (score > nack_score_threshold) {
allow_nack = true;
} else {
- seq_num_list[index] = -1;
+ seq_num_list[nack_seq_nums_index] = -1;
}
- ++index;
+ ++nack_seq_nums_index;
}
}
- seq_num_list[index] = -1;
- ++index;
+ seq_num_list[nack_seq_nums_index] = -1;
+ ++nack_seq_nums_index;
prev_it = it;
++it;
}
}
- index = ClearOutEmptyPacketSequenceNumbers(seq_num_list, seq_num_list_length,
- index);
+ nack_seq_nums_index = ClearOutEmptyPacketSequenceNumbers(seq_num_list,
+ seq_num_list_length,
+ nack_seq_nums_index);
session_nack_ = allow_nack;
- return 0;
+ return nack_seq_nums_index;
}
int VCMSessionInfo::ClearOutEmptyPacketSequenceNumbers(
@@ -527,12 +528,8 @@
const PacketIterator& prev_packet_it) {
if (packet_it == prev_packet_it)
return 0;
- if ((*prev_packet_it).seqNum > (*packet_it).seqNum) // Wrap.
- return static_cast<WebRtc_UWord16>(
- static_cast<WebRtc_UWord32>((*packet_it).seqNum + 0x10000) -
- (*prev_packet_it).seqNum) - 1;
- else
- return (*packet_it).seqNum - (*prev_packet_it).seqNum - 1;
+ return static_cast<uint16_t>((*packet_it).seqNum -
+ (*prev_packet_it).seqNum - 1);
}
bool
diff --git a/webrtc/modules/video_coding/main/source/session_info.h b/webrtc/modules/video_coding/main/source/session_info.h
index bf7e543..0135ee9 100644
--- a/webrtc/modules/video_coding/main/source/session_info.h
+++ b/webrtc/modules/video_coding/main/source/session_info.h
@@ -29,12 +29,14 @@
// Build hard NACK list: Zero out all entries in list up to and including
// _lowSeqNum.
int BuildHardNackList(int* seq_num_list,
- int seq_num_list_length);
+ int seq_num_list_length,
+ int nack_seq_nums_index);
// Build soft NACK list: Zero out only a subset of the packets, discard
// empty packets.
int BuildSoftNackList(int* seq_num_list,
int seq_num_list_length,
+ int nack_seq_nums_index,
int rtt_ms);
void Reset();
int InsertPacket(const VCMPacket& packet,
diff --git a/webrtc/modules/video_coding/main/source/session_info_unittest.cc b/webrtc/modules/video_coding/main/source/session_info_unittest.cc
index e017735..2a78813 100644
--- a/webrtc/modules/video_coding/main/source/session_info_unittest.cc
+++ b/webrtc/modules/video_coding/main/source/session_info_unittest.cc
@@ -817,14 +817,15 @@
EXPECT_EQ(10 * kPacketBufferSize, session_.SessionLength());
BuildSeqNumList(low, packet_.seqNum);
- EXPECT_EQ(0, session_.BuildHardNackList(seq_num_list_, seq_num_list_length_));
+ EXPECT_EQ(seq_num_list_length_, session_.BuildHardNackList(
+ seq_num_list_, seq_num_list_length_, 0));
EXPECT_FALSE(session_.session_nack());
SCOPED_TRACE("Calling VerifyAll");
VerifyAll(-1);
BuildSeqNumList(low, packet_.seqNum);
- EXPECT_EQ(0, session_.BuildSoftNackList(seq_num_list_, seq_num_list_length_,
- 60));
+ EXPECT_EQ(seq_num_list_length_, session_.BuildSoftNackList(
+ seq_num_list_, seq_num_list_length_, 0, 60));
SCOPED_TRACE("Calling VerifyAll");
VerifyAll(-1);
}
@@ -853,7 +854,9 @@
EXPECT_EQ(5 * kPacketBufferSize, session_.SessionLength());
BuildSeqNumList(low, packet_.seqNum);
- EXPECT_EQ(0, session_.BuildHardNackList(seq_num_list_, seq_num_list_length_));
+ // Will be at |seq_num_list_length - 1| since the last packet is missing.
+ EXPECT_EQ(seq_num_list_length_ - 1, session_.BuildHardNackList(
+ seq_num_list_, seq_num_list_length_, 0));
for (int i = 0; i < seq_num_list_length_; ++i) {
if (i % 2)
EXPECT_EQ(static_cast<uint16_t>(low + i), seq_num_list_[i]);
@@ -862,8 +865,9 @@
}
BuildSeqNumList(low, packet_.seqNum);
- EXPECT_EQ(0, session_.BuildSoftNackList(seq_num_list_, seq_num_list_length_,
- 60));
+ // Will be at |seq_num_list_length - 1| since the last packet is missing.
+ EXPECT_EQ(seq_num_list_length_ - 1, session_.BuildSoftNackList(
+ seq_num_list_, seq_num_list_length_, 0, 60));
EXPECT_EQ(true, session_.session_nack());
for (int i = 0; i < seq_num_list_length_; ++i) {
if (i % 2)
@@ -885,14 +889,17 @@
EXPECT_EQ(kPacketBufferSize, session_.SessionLength());
BuildSeqNumList(low, packet_.seqNum + 1);
- EXPECT_EQ(0, session_.BuildHardNackList(seq_num_list_, seq_num_list_length_));
+ // Will be at |seq_num_list_length - 1| since the last packet is missing.
+ EXPECT_EQ(seq_num_list_length_ - 1, session_.BuildHardNackList(
+ seq_num_list_, seq_num_list_length_, 0));
EXPECT_EQ(0xFFFF, seq_num_list_[0]);
EXPECT_EQ(-1, seq_num_list_[1]);
EXPECT_EQ(1, seq_num_list_[2]);
BuildSeqNumList(low, packet_.seqNum + 1);
- EXPECT_EQ(0, session_.BuildSoftNackList(seq_num_list_,seq_num_list_length_,
- 60));
+ // Will be at |seq_num_list_length - 1| since the last packet is missing.
+ EXPECT_EQ(seq_num_list_length_ - 1, session_.BuildSoftNackList(
+ seq_num_list_, seq_num_list_length_, 0, 60));
EXPECT_EQ(true, session_.session_nack());
EXPECT_EQ(0xFFFF, seq_num_list_[0]);
EXPECT_EQ(-1, seq_num_list_[1]);
@@ -917,10 +924,24 @@
FillPacket(0);
ASSERT_EQ(session_.InsertPacket(packet_, frame_buffer_, false, 0), 0);
+ // Test soft NACKing.
EXPECT_EQ(0, session_.SessionLength());
BuildSeqNumList(low, packet_.seqNum + 1);
- EXPECT_EQ(0, session_.BuildSoftNackList(seq_num_list_, seq_num_list_length_,
- 60));
+ // Will be at |seq_num_list_length - 1| since the last packet is missing.
+ EXPECT_EQ(seq_num_list_length_ - 1, session_.BuildSoftNackList(
+ seq_num_list_, seq_num_list_length_, 0, 60));
+ EXPECT_EQ(true, session_.session_nack());
+ EXPECT_EQ(0, seq_num_list_[0]);
+ EXPECT_EQ(-1, seq_num_list_[1]);
+ EXPECT_EQ(-2, seq_num_list_[2]);
+ EXPECT_EQ(-2, seq_num_list_[3]);
+ EXPECT_EQ(4, seq_num_list_[4]);
+
+ // Test hard NACKing.
+ BuildSeqNumList(low, packet_.seqNum + 1);
+ // Will be at |seq_num_list_length - 1| since the last packet is missing.
+ EXPECT_EQ(seq_num_list_length_ - 1, session_.BuildHardNackList(
+ seq_num_list_, seq_num_list_length_, 0));
EXPECT_EQ(true, session_.session_nack());
EXPECT_EQ(0, seq_num_list_[0]);
EXPECT_EQ(-1, seq_num_list_[1]);
