Hi all,
When calling gr::block::get_tags_in_range() or
gr::block::get_tags_in_window(), does the GNU Radio API guarantee that
the
returned vector will be sorted based upon the tag offsets (from
“earliest”
to “latest”)?
Since the API docs [1] do not explicitly state this to be the case, I
would
assume the answer is “No.”
Additionally, I see the wiki [2] seems to confirm this:
“Any tag that is connected to the first 100 items will be placed into
this
vector, although not in any specific order.”
However, after a cursory review of the underlying
buffer_reader::get_tags_in_range() and related functions, I see that the
tags are stored in a std::multimap with the offset as the key (thereby
sorting entries via the offset).
This map appears to be iterated over from start offset to end offset
while
inserting tags into the std::vectorgr::tags_t. Therefore, this should
return them ordered, as I desire in this case.
Just curious if anyone could comment on/correct the above observations,
as
well as elaborate on exactly what the API shall (not) guarantee,
regardless
of the current implementation.
Thank you,
Jon
[1]
https://gnuradio.org/doc/doxygen/classgr_1_1block.html#aa0272555827fe26a1878e53ce4be092c
[2]
http://gnuradio.org/redmine/projects/gnuradio/wiki/Guided_Tutorial_Programming_Topics#522-Tag-offsets-and-noutput_items
I don’t know that I can completely answer your question, but I can tell
you
that the change to using a std::multimap occurred during the last day of
GrCon’14 (i.e. the hackfest day) after profiling measurements were
showing
that the tagged stream blocks were spending a great deal of time in the
tag
processing (primarily because at the time the tags were stored in a
std::deque). The switch to using a multimap as the backing store
provided a
significant performance boost. As a side effect this may result in the
tags
being presented in order (I don’t recall off the top of my head if
std::multimap guarantees that, although I can imagine many/most
implementations may store them in-order).
I don’t know if GNURadio wishes to guarantee the order in the future,
if,
for example, we decided to change the backing store again at some point
in
the future. I’ll let others comment on that.
On Wed, Jun 24, 2015 at 1:06 PM, Jon S. [email protected]
Quick follow up: Tim O’Shea provided a nice write-up of the performance
delta with the change in the backing store for tags (for those who may
care
about such things):
http://oshearesearch.com/2014/09/22/five-orders-of-magnitude-improvement-in-gnu-radio-stream-tag-propagation-performance/
Doug
On Wed, Jun 24, 2015 at 4:42 PM, Douglas G. <
On Wed, Jun 24, 2015 at 4:46 PM, Douglas G. <
[email protected]> wrote:
Quick follow up: Tim O’Shea provided a nice write-up of the performance
delta with the change in the backing store for tags (for those who may care
about such things):
http://oshearesearch.com/2014/09/22/five-orders-of-magnitude-improvement-in-gnu-radio-stream-tag-propagation-performance/
Doug
Thanks, Doug. And yes, one of the benefits of using the multimap is that
tags are now stored in order. That’s what helped make such a big
improvement in speed. When getting or deleting tags in an unsorted
vector,
we needed to walk through all tags to find the right ones. When they are
in-order, we know the upper and lower limits of the location of any tags
in
a range for faster access.
Tom
On Wed, Jun 24, 2015 at 6:09 PM, Tom R. [email protected] wrote:
Thank you very much for the additional clarification and details, Doug
and
Tom!
So from what you’ve said, the ordering is an implementation-specific
detail
that an API user shall not assume. To ensure compatibility with past,
present, and future GNU Radio versions, the API user is responsible for
sorting the returned vector, if that’s required. Do you agree?
On 25.06.2015 07:57, Jon S. wrote:
Thank you very much for the additional clarification and details, Doug
and Tom!
So from what you’ve said, the ordering is an implementation-specific
detail that an API user shall not assume. To ensure compatibility with
past, present, and future GNU Radio versions, the API user is
responsible for sorting the returned vector, if that’s required. Do you
agree?
Jon,
Tom did say that tags are sorted since the multimap change. To be both
forward- and mostly backward-compatible, what you’re saying is true.
I’m wondering if we might add a #define for the multimap change… that
way, one could conditionally compile in a std::sort if required.
Cheers,
Martin
I’m wondering if we might add a #define for the multimap change… that
way, one could conditionally compile in a std::sort if required.
Hi Martin,
For what it’s worth, I like that idea. It feels a little icky to be
doing
an unnecessary sort just to ensure the code won’t break.
Cheers,
Jon
Hi Martin,
you can, kind of, already do that:
If buffer->get_tags_begin returns a random_access_iterator, you’re
dealing with the old deque, if it’s just a bidirectional iterator,
you’re dealing with the map implementation.
Checking that is um… C++ish and thus very beautiful. If my
understanding of what C++ compilers does is strong enough then the
following will be resolved at compile time:
#include
#include
…
typedef
std::iterator_traits<detail()->input(0)->buffer()->get_tags_begin()>
traits; //input 0 exists, because where should tags come from if it
didn’t?
bool is_sorted =
!(typeid(traits::iterator_category)==typeid(std::random_access_iterator_tag));
So looking at this…
Yeah. A #define would probably be extremely handy. But since we can’t
retroactively change history, people will want to check the GR version,
so it’s also kind of redundant to our version numbers.
Cheers,
Marcus