Changed queue implementation to the proposed vector-based solution.

webrtc/modules/audio_processing/swapped_nonblocking_queue.h

+/*
+ *  Copyright (c) 2015 The WebRTC project authors. All Rights Reserved.
+ *
+ *  Use of this source code is governed by a BSD-style license
+ *  that can be found in the LICENSE file in the root of the source
+ *  tree. An additional intellectual property rights grant can be found
+ *  in the file PATENTS.  All contributing project authors may
+ *  be found in the AUTHORS file in the root of the source tree.
+ */
+
+#ifndef WEBRTC_MODULES_AUDIO_PROCESSING_SWAPPED_NONBLOCKING_QUEUE_H_
+#define WEBRTC_MODULES_AUDIO_PROCESSING_SWAPPED_NONBLOCKING_QUEUE_H_
+
+#include <vector>
+
+#include "webrtc/base/checks.h"
+#include "webrtc/base/criticalsection.h"
+
+namespace webrtc {
+
+// This class is to be used as a one-way queue where data is

[kwiberg-webrtc, 2015/10/10 10:16:56]

"is to be used as a" -> "is"

[peah-webrtc, 2015/10/12 13:01:06]

Sorry, I don't follow that. Please elaborate further :-)

[kwiberg-webrtc, 2015/10/12 14:05:48]

Just replace the left-hand side string with the right-hand side one.

[peah-webrtc, 2015/10/13 11:56:11]

Ah :-). Of course, I thought it was something more fundamental.

[peah-webrtc, 2015/10/13 11:56:11]

Done.

+// written from one end and read from the other end.
+// The read and write operations are protected by a common lock.

[kwiberg-webrtc, 2015/10/10 10:16:56]

At this level, it's probably better to just say that it's safe to access this
concurrently from multiple threads.

[peah-webrtc, 2015/10/12 13:01:07]

Done.

[hlundin-webrtc, 2015/10/13 06:37:57]

+1. Spare the implementation details.

[peah-webrtc, 2015/10/13 11:56:11]

Done.

+// The queueable objects must all implement a swap() method.

[kwiberg-webrtc, 2015/10/10 10:16:55]

That shouldn't be necessary. As long as the usual swapping idiom
(http://en.cppreference.com/w/cpp/concept/Swappable) works, we should be able to
use T.

But you do require T to have a default constructor.

[peah-webrtc, 2015/10/12 13:01:08]

I changed the comment a bit. Could you please verify that it is correct!

[kwiberg-webrtc, 2015/10/12 14:05:48]

Looks good.

[peah-webrtc, 2015/10/13 11:56:11]

Acknowledged.

+template <typename T>
+class SwappedNonBlockingQueue {

[kwiberg-webrtc, 2015/10/10 10:16:56]

It's a swapping queue, not a swappable one. "NonblockingSwapQueue"?

[The Sun (google.com), 2015/10/10 14:00:54]

SwapQueue is a great term! Nonblocking or not.

[peah-webrtc, 2015/10/12 13:01:07]

Totally agree! I changed it to swap_queue and skipped the nonblocking for now.
Ok?

[kwiberg-webrtc, 2015/10/12 14:05:48]

Acknowledged.

+ public:
+  explicit SwappedNonBlockingQueue<T>(size_t initial_size) {

[kwiberg-webrtc, 2015/10/10 10:16:56]

No need to repeat the <T> here.

[peah-webrtc, 2015/10/12 13:01:08]

Done.

+    queue_.resize(initial_size);

[kwiberg-webrtc, 2015/10/10 10:16:56]

std::vector has a constructor that does this. And the size is fixed, right? So
drop the "initial". (Or better, use "max_size" as Fredrik suggested below.)

[peah-webrtc, 2015/10/12 13:01:08]

Done.

+    Reset();

[kwiberg-webrtc, 2015/10/10 10:16:56]

This takes a lock, and just sets two members to zero. I'd say it makes more
sense to initialize them without this call.

[peah-webrtc, 2015/10/12 13:01:07]

Done.

[hlundin-webrtc, 2015/10/13 06:37:57]

OTOH, calling Reset() here makes it more obvious that the Reset method in fact
resets the object to the same state it had when constructed.

[peah-webrtc, 2015/10/13 11:56:11]

That was partly my initial intention as well, and also I wanted to avoid code
duplication. With the current implementation, and the Clear method, it is a bit
different though. Are you fine with the current implementation?

+  }
+
+  explicit SwappedNonBlockingQueue<T>(size_t initial_size, const T& initializer)

[the sun, 2015/10/09 12:09:54]

Remove "explicit".

"initial_size" -> "max_size" or just "size"? Size isn't dynamic, right?

Add comment on what initializer is.

[peah-webrtc, 2015/10/12 13:01:08]

Done.

+      : SwappedNonBlockingQueue<T>(initial_size) {
+    // Fill the queue with elements identical to initializer
+    for (typename std::vector<T>::iterator it = queue_.begin();

[the sun, 2015/10/09 12:09:55]

for (auto it = ... ?

[peah-webrtc, 2015/10/12 13:01:07]

Done.

+         it != queue_.end(); ++it)

[the sun, 2015/10/09 12:09:54]

Always use braces, please.

[peah-webrtc, 2015/10/12 13:01:08]

Done.

[hlundin-webrtc, 2015/10/13 06:37:57]

I agree, but I know that braces here would get push-back in Chromium. But,
please add them here.

[peah-webrtc, 2015/10/13 11:56:11]

Acknowledged.

+      *it = initializer;
+  }

[kwiberg-webrtc, 2015/10/10 10:16:55]

std::vector has a constructor for this too.

[peah-webrtc, 2015/10/12 13:01:07]

I removed this one and instead added the one below. Is that ok?

[kwiberg-webrtc, 2015/10/12 14:05:48]

No, I count three constructors in the new patch set. See comments there.

[peah-webrtc, 2015/10/13 11:56:11]

Will have a look at that

+

[kwiberg-webrtc, 2015/10/10 10:16:56]

The constructors are the complicated part of this. Specifically, the problem is
that because you have std::vector both in the implementation and as an important
potential value of T, you can't use move construction anywhere, and you can't
trust the default constructor or even a copy constructor to do the right thing.
And you need to give the user control of how those "empty" Ts are constructed.

Perhaps a constructor like this would be the least bad option:

  // TODO(peah): Change to std::vector<T>&& when we have a C++11
  // standard library.
  explicit NonblockingSwapQueue(std::vector<T>* empty_slots) {
    RTC_CHECK_GE(empty_slots.size(), 1u);
    using std::swap;
    swap(queue_, empty_slots);
  }

That way, the caller can prepare the empty slots however she wants (including
choosing how many there are), and we just steal them. It's not ideal, since it
exposes the fact that the queue uses std::vector internally, but it's probably
good enough.

For Ts that have a good enough default constructor, you can keep the constructor
that takes just a size.

[peah-webrtc, 2015/10/12 13:01:07]

Sounds good! I took the implementation of this one as you suggested.

[peah-webrtc, 2015/10/12 13:01:07]

Done.

+  // Resets the queue to have zero content.
+  void Reset() {

[the sun, 2015/10/09 12:09:54]

Really needed?

[kwiberg-webrtc, 2015/10/10 10:16:56]

+1. Also, consider calling it clear() or Clear(); the STL containers call their
corresponding methods clear().

[peah-webrtc, 2015/10/12 13:01:08]

I think it is needed as it provides lower cost resetting of the state. But I
changed it to the more appropriate name Clear().

+    rtc::CritScope cs(&crit_queue_);
+    last_write_index_ = 0;
+    last_read_index_ = 0;
+  }
+
+  // Inserts a chunk of data into the queue in a thread safe manner.
+  // The input is replaced by an undefined chunk of type T.

[the sun, 2015/10/09 12:09:54]

replaced by -> swapped with

[peah-webrtc, 2015/10/12 13:01:08]

Done.

+  // Returns false if the queue is full, and true if not.

[kwiberg-webrtc, 2015/10/10 10:16:55]

It's not an arbitrary value; it's either one which was created at queue
construction, or one which was provided to Remove. This is an important point,
because it allows callers to pass in Ts that e.g. own large enough allocations
and be sure that Ts they get out here also have that property.

It might be a good idea to document how the queue handles "empty" and "full" Ts,
and that the constructors take or create "empty" Ts, Insert takes a "full" T and
gives back an "empty" one, and Remove takes an "empty" T and gives back a "full"
one.

[peah-webrtc, 2015/10/12 13:01:07]

Makes sense! I revised the comments of the class and this method accordingly.
How do you think it turned out?

[peah-webrtc, 2015/10/12 13:01:07]

I added some documentation. Please let me know if I should add more!

[kwiberg-webrtc, 2015/10/12 14:05:48]

Acknowledged.

[hlundin-webrtc, 2015/10/13 06:37:57]

Clarify that false if returned if the queue is full already before trying to
insert; not if it becomes full by this call.

[peah-webrtc, 2015/10/13 11:56:11]

Good point! I added some more documentation regarding that. 

+  bool Insert(T* const input) {

[kwiberg-webrtc, 2015/10/10 10:16:56]

Better drop the const here, or people will confuse it with const T*.

[peah-webrtc, 2015/10/12 13:01:07]

Done.

[peah-webrtc, 2015/10/12 13:01:07]

Done.

+    rtc::CritScope cs(&crit_queue_);
+
+    // Early return if the queue is full.
+    size_t next_write_index_ =

[the sun, 2015/10/09 12:09:54]

No trailing underscore on local variables.

Can you just

size_t next_write_index = (last_write_index_ + 1) % queue.size() ?

which you could also put in an internal

inline bool CheckIfFull() {
...

and use in IsFull() as well.

[peah-webrtc, 2015/10/12 13:01:07]

I removed those functions because with the current counter for number of
elements they become trivial.

[peah-webrtc, 2015/10/12 13:01:07]

Did this, but a bit differently. I also kept the short-circuit instead of the
modulus operation.

+        (last_write_index_ < (queue_.size() - 1) ? last_write_index_ + 1 : 0);
+    if (next_write_index_ == last_read_index_)
+      return false;

[kwiberg-webrtc, 2015/10/10 10:16:56]

Hmm. This means you'll keep at most size() - 1 elements in the queue. I guess
that's unavoidable if you just keep two indices in the range [0..size()-1],
since the number of elements need to be in the range [0..size()].

Perhaps it's better to have e.g. next_read_pos_ and num_elements_ as members?

[peah-webrtc, 2015/10/12 13:01:08]

Good point. I added the num_elements_ idea, but kept the preexisting
last_write_index_ and last_read_index_ even though that 3-index/counter scheme
is redundant (only using the two variables next_read_pos_ and num_elements_ you
proposed is sufficient).
The reason for this is that the index updating becomes simpler, cleaner and
cheaper with the redundant scheme.

Please let me know what you think!

[peah-webrtc, 2015/10/12 13:01:08]

I added the num_elements_ as member which simplifies the code a lot and allows
for full queue usage. I kept the the two write and read indices, however, even
thought they are redundant, as they are slightly less computationally complex to
use and makes the code easier to read.
Please let me know if you still prefer to have them replaced by only using the
next_read_pos_ variable.

+
+    last_write_index_ = next_write_index_;
+    input->swap(queue_[last_write_index_]);

[kwiberg-webrtc, 2015/10/10 10:16:56]

See http://en.cppreference.com/w/cpp/concept/Swappable for the recommended way
to swap objects of an arbitrary type. In brief, you should do

  #include <utility>

  ...

    using std::swap;
    swap(x, y);

That will work if T has added a specialization to std::swap (or if the standard
library has one built in), if there is a method T::swap(T&), or if there is a
non-member swap(T&, T&).

[peah-webrtc, 2015/10/12 13:01:07]

Thanks!!!! Does this look as what you intended?

[kwiberg-webrtc, 2015/10/12 14:05:48]

Yes.

[peah-webrtc, 2015/10/13 11:56:11]

Acknowledged.

+
+    return true;
+  }
+
+  // Removes a chunk of data from the queue in a thread safe manner.
+  // Returns false if the queue is empty, and true if not.

[hlundin-webrtc, 2015/10/13 06:37:57]

Again, clarify that false is returned if the queue was already empty, so that no
data could be fetched.

[peah-webrtc, 2015/10/13 11:56:11]

Good point! I added some more documentation regarding that. 

+  bool Remove(T* const output) {
+    rtc::CritScope cs(&crit_queue_);
+
+    // Early return for empty queue.
+    if (last_read_index_ == last_write_index_)
+      return false;
+
+    last_read_index_ =

[the sun, 2015/10/09 12:09:55]

Use modulo instead of conditional

[kwiberg-webrtc, 2015/10/10 10:16:56]

I'd also have used a conditional, because mod can be expensive. (I'm hoping the
compiler would use a conditional move or something instead of a conditional
branch.)

...

So I tried this. For this program:

  std::size_t f(std::size_t i, std::size_t s) {
    return i + 1 < s ? i + 1 : 0;
  }

clang produced this code:

   0:	48 ff c7            	inc    %rdi
   3:	31 c0               	xor    %eax,%eax
   5:	48 39 f7           	cmp    %rsi,%rdi
   8:	48 0f 42 c7      	cmovb  %rdi,%rax
   c:	c3                   	retq   

(gcc produced essentially the same code.)

We can't expect it to do as well for the mod operation, since that would mean
it'd have to keep track of the global invariant that the index always starts out
in the range [0..size-1].

[peah-webrtc, 2015/10/12 13:01:07]

Great investigation! Cool!!! I'll keep the conditional as it is then.

+        (last_read_index_ < (queue_.size() - 1) ? last_read_index_ + 1 : 0);
+    output->swap(queue_[last_read_index_]);
+
+    return true;
+  }
+
+  size_t EmptyQueue() {

[the sun, 2015/10/09 12:09:55]

1. Is this really needed in the API?

should return a bool

Should be const.

I'd prefer this to be named IsEmpty(). "EmptyQueue" could be an imperative as
well.

[kwiberg-webrtc, 2015/10/10 10:16:56]

+1 to what Fredrik said. The best thing would be if we didn't need it at all.

[peah-webrtc, 2015/10/12 13:01:07]

Agree, I removed the function.

[peah-webrtc, 2015/10/12 13:01:08]

Done.

+    rtc::CritScope cs(&crit_queue_);
+    if (last_read_index_ == last_write_index_)
+      return false;
+  }
+
+  size_t FullQueue() {

[the sun, 2015/10/09 12:09:54]

1. Is this really needed in the API?

bool, const, IsFull()

[kwiberg-webrtc, 2015/10/10 10:16:56]

+1

[peah-webrtc, 2015/10/12 13:01:08]

Agree, I removed the function.

[peah-webrtc, 2015/10/12 13:01:08]

Done.

+    rtc::CritScope cs(&crit_queue_);
+    size_t next_write_index_ =

[the sun, 2015/10/09 12:09:54]

Move to internal CheckIfFull() utility

[peah-webrtc, 2015/10/12 13:01:08]

I removed that functionality, as it with the current element is trivial.

+        (last_write_index_ < (queue_.size() - 1) ? last_write_index_ + 1 : 0);
+    if (next_write_index_ == last_read_index_)
+      return false;
+  }
+
+ private:
+  std::vector<T> queue_;

[kwiberg-webrtc, 2015/10/10 10:16:56]

GUARDED_BY?

[peah-webrtc, 2015/10/12 13:01:08]

Done.

+  size_t last_write_index_ GUARDED_BY(crit_queue_);
+  size_t last_read_index_ GUARDED_BY(crit_queue_);
+  rtc::CriticalSection crit_queue_;

[the sun, 2015/10/09 12:09:54]

Make mutable

[kwiberg-webrtc, 2015/10/10 10:16:55]

This class is unusable if it's const, so I don't see the point.

[The Sun (google.com), 2015/10/10 14:00:54]

That's to make it possible for IsEmpty and IsFull to be const declared.

OTOH, I'd prefer to remove the lock from IsEmpty/IsFull and instead make them
private for now. If we realize there is an actual need for them, we can promote
them to be public.

[kwiberg-webrtc, 2015/10/10 17:48:40]

Yeah, OK. No caller is going to make use of that, but it'll catch mistakes in
the implementations of those two methods.
As I said in an earlier comment, I think it'd be better to use next_read_pos_
and num_elements_ as member variables. One side effect of that is that these two
methods will become trivial and can be eliminated if they're only for private
use.

[peah-webrtc, 2015/10/12 13:01:08]

Agree to both of you! I removed the IsEmpty and IsFull functions. 
And did not add mutable for the critical section

+
+  RTC_DISALLOW_COPY_AND_ASSIGN(SwappedNonBlockingQueue);
+};
+
+}  // namespace webrtc
+
+#endif  // WEBRTC_MODULES_AUDIO_PROCESSING_SWAPPED_NONBLOCKING_QUEUE_H_