Re: [Discuss-gnuradio] Order of tags returned by gr::block::get_tags_in_range()/window()

[Jon Szymaniak]

On Wed, Jun 24, 2015 at 6:09 PM, Tom Rondeau <address@hidden> wrote:

On Wed, Jun 24, 2015 at 4:46 PM, Douglas Geiger <address@hidden> 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

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

 

 

On Wed, Jun 24, 2015 at 4:42 PM, Douglas Geiger <address@hidden> wrote:

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 Szymaniak <address@hidden> wrote:

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::vector<gr::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

_______________________________________________
Discuss-gnuradio mailing list
address@hidden
https://lists.gnu.org/mailman/listinfo/discuss-gnuradio

--

Doug Geiger
address@hidden

--

Doug Geiger
address@hidden

_______________________________________________
Discuss-gnuradio mailing list
address@hidden
https://lists.gnu.org/mailman/listinfo/discuss-gnuradio