Re: [Discuss-gnuradio] Serious bug in tag propagation with non-integer relative rate

[Andy Walls]

>1. The gnuradio-runtime propagated tags with double arithmetic; the
>fractional resampler block used mixed float & double arithmetic to
>propagate tags.
>

Oops:

mixed float & double arithmetic to generate output sample intervals.

-Andy

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

Re: [Discuss-gnuradio] Serious bug in tag propagation with non-integer relative rate

[Andy Walls]

On Wed, 2017-12-27 at 16:18 -0500, Andy Walls wrote:
> Hi Eugene
> 
> > From:   Eugene Grayver
> > Date:   Thu, 9 Nov 2017 19:52:35 +
> > 
> > There is a major problem with the way tags are propagated in blocks
> > with non-integer relative rate. If the ratio is not a power of two,
> > the numerical accuracy of the floating point will cause the output
> > tags to diverge from the input tags.  Consider the fractional
> > resampler. It accumulates the timing offset in the range of 0 to 1.
> > However tag propagation multiplies the ratio by the sample number.
> > As
> > the sample number grows the LSB accuracy of the ratio gets scaled
> > by
> > the ever larger value. For a ratio of 1.001 we saw divergence of
> > 1000s of samples over a few minutes at 10msps.

OK, I've got a working fix for this:

https://github.com/gnuradio/gnuradio/pull/1543
or
https://github.com/awalls-cx18/gnuradio.git  branch tag_fix4

You will need to install the mpir and mpir-devel packages for your
distro, as this change adds a dependency on the MPIR library
(libmpirxx.so and libmpir.so).

With the attached GRC flowgraph, the fixed code shows no slips after 8
hours of continuous running on a modest laptop.  Compare that with the
baseline of gnuradio master, where after 8 hours, the tags have slipped
5 output samples to the right.

You were right about it being a floating point precision problem, but
the problem with the fractional resampler over short runs was (moslty)
not in the gnuradio runtime, but the fractional resampler block itself:

1. The gnuradio-runtime propagated tags with double arithmetic; the
fractional resampler block used mixed float & double arithmetic to
propagate tags.

2. Floating point reciprocals aren't exact in the lsb's, so specifying
set_relative_rate(1.0/resamp_ratio) was also introducing errors.  I.e.:

[andy@pinto sw]$ ./rational3 1.001
Resample ratio: 1.0009
Resample ratio: 2254051613498933/2251799813685248
Numerator: 2254051613498933
Denominator: 2251799813685248

Relative rate: 0.99900099900099915
Relative rate: 4499100526843653/4503599627370496
Numerator: 4499100526843653
Denominator: 4503599627370496

Notice how the relative rate's numerator and denominator are not the
same as the resample ratio's denominator and numerator.

Geof:

Could you please take a look at the newly added cmake module
FindMPIR.cmake to see if it need changes for the Windows build?


Jeff and Marcus:

I'll address possible solutions for your observations (non-fixed
relative rate and fraction tag offsets) in a separate post.
I have a concept on how to address both, I think, but they can't be on
master branch due to API changes.

Regards,
Andy


tag_prop_test.grc
Description: XML document
#include 
#include 
#include 
#include 
#include 
#include 

int main(int argc, char *argv[])
{
double resamp_ratio = strtod(argv[1], NULL);
double relative_rate = 1/resamp_ratio;

std::cout.precision(std::numeric_limits::max_digits10);
//-
// Using MPIR's C++ interface
static const mpq_class one_half(1,2);
mpq_class resamp_ratio_q(resamp_ratio);
mpq_class relative_rate_q(relative_rate);
//ratio.canonicalize();
std::cout << "Resample ratio: " << resamp_ratio << std::endl;
std::cout << "Resample ratio: " << resamp_ratio_q << std::endl;
std::cout << "Numerator: " << resamp_ratio_q.get_num().get_ui() << std::endl;
std::cout << "Denominator: " << resamp_ratio_q.get_den().get_ui() << std::endl;
std::cout << std::endl;
std::cout << "Relative rate: " << relative_rate << std::endl;
std::cout << "Relative rate: " << relative_rate_q << std::endl;
std::cout << "Numerator: " << relative_rate_q.get_num().get_ui() << std::endl;
std::cout << "Denominator: " << relative_rate_q.get_den().get_ui() << std::endl;
std::cout << std::endl;
#if 0
//mpz_class offset(0x0803);
uint64_t offset = 0x0803;
mpq_class scaled = offset*ratio;
mpz_class rscaled(scaled + one_half);
mpz_class rscaled2;
rscaled2 = offset * ratio + one_half;
rscaled2 = offset * ratio + one_half + 2;
std::cout << "Offset:" << offset << std::endl;
std::cout << "Scaled offset: " << scaled << std::endl;
std::cout << "Rounded scaled offset: " << rscaled << std::endl;
std::cout << "Rounded scaled offset2: " << rscaled2 << std::endl;
uint64_t rscaledint = rscaled.get_ui();
std::cout << "Native rounded scaled offset: " << rscaledint << std::endl;
#endif
exit(0);
}
___
Discuss-gnuradio mailing list
Discuss-gnuradio@gnu.org
https://lists.gnu.org/mailman/listinfo/discuss-gnuradio

Re: [Discuss-gnuradio] Serious bug in tag propagation with non-integer relative rate

[Jeff Long]

(and if I'd actually read Andy's last post carefully ...)

On 01/01/2018 01:32 PM, Jeff Long wrote:
As Eugene suggests, the fractional resampler can be handled by doing a 
linear mapping from the input to the output of a single work call. 
Wouldn't this work with most or all blocks? There would also need to be 
an offset in order to handle history. Then, there wouldn't be a need to 
use higher precision counters.


On 01/01/2018 11:24 AM, Jeff Long wrote:
I think the reason rate changes are difficult for tags is that the 
block executor tries to guess what a block is doing based on its 
long-term or static rate change. The block itself knows exactly how 
input items relate to output items, and maybe certain blocks need to 
provide more feedback than just a rate. In those cases, the executor 
could use the exact translation provided by the block, and in tamer 
cases the rate can still be used.


On 01/01/2018 10:53 AM, Andy Walls wrote:

Hi Marcus:

On Sun, 2017-12-31 at 15:09 +, Müller, Marcus (CEL) wrote:

Hi Andy, hi Eugene

Hm, coming back to an idea I had not so long ago:

tag offset should not be 64bit unsihned integers only, but also have
a
64 bit fractional part.

That would not immediately solve the computational inaccurracy during
resampling, but would at least for multi (as in >2) rate systems (eg.
rational resampling for sample rate reduction, arbitrary resampling
for
clock recovery) at least give the option of having consistent
tagging.


IMO, adding a fractional part does not solve the problem at hand -
correct tag propagation through 1 block - but it probably is required
for precise propagation through multiple rate changing blocks.

I'm keeping it in mind, but I want to avoid changing existing
interfaces right now.  I.e. get_tags_in_[range|window]() runs into a
backward compatability issue for a tag that comes < 0.5 samples before
the beginning of the requested range: should the tag offset -0.49
samples realtive to the start of the window be returned or not?



Personally, my gut feeling is that for this kind of divisional math,
floating point is not the number format of choice


Agreed.


  (for multiple (as in

2) reasons).


This actually doesn't apply to the arbitrary resampling case as much,
but the d_relative_rate property of a block shouldn't be a floating
point,


Internal to the gnuradio-runtime there are a number of places where,
for estimating, using a floating point d_relative_rate is just fine.
It is expedient and avoids the problem of interger overflow for cases
where one has large integer interpolation and decimation factors.


but a ratio of two integers, one of them being signed. Maybe I
should be adding a set_relative_rate(int64_t numerator, uint_64_t
denominator) to block, and make set_relative_rate(double) a wrapper
for
that (and of course change the block_executor to do fractional rather
than floating point math);


So that's what my change does. :)  I also changed all the blocks, that
could easily easily call the integer version of
set_relataive_rate(interpolation, decimation), to do so.

To avoid integer overflow, I picked an algoritm in the new
set_relative_rate(double) wrapper, to convert the relative rate to a
ratio of two integers that got within 1 ppm of the passed in relative
rate.  Because sane users only use relative rates of 1/25 or 1001/1000
or 255/256 or 2/3 or something like that, and whacky relative rates
using large (>16 bit) integers in the ratio are just a product of
rounding, right?  Well I was wrong. :(

Unfortunately, the fractional resampler is a corner case that actually
uses the rounded (in binary) version of the resampling rate, that the
user specifies, in its actual operation. Computing exact integer ratios
to represent the double can lead to 53 bit numbers (IIRC), which can
lead to integer overflows when multiplying uint64_t's together. :(

So what I'm left with are two broad options to deal with handling a
double relative rate (like the fractional resampler uses):

1. Implement an method like Eugene suggests: do a double multiply, get
a rounded result, do a double division to get back to an initial
offset, subtract off that initial offset, do a double multiply again,
and then a final add.

or

2. Allow and compute large, exact integer ratios of
interpolation/decimation rate and use multiple precision (128 bit)
arithmetic when overflow out of 64 bits is possible.
Maybe using boost::multiprescision with the MIPR library on the
backend.
http://www.boost.org/doc/libs/1_66_0/libs/multiprecision/doc/html/index
.html
http://mpir.org/
(MPIR is supposedly better for Windows compatability than GMP.)


I'm leaning towards option 2.


I find that I never calculate a rate other
than by calculating the floating point approximation of a fraction of
integers, and that there's always been subtle problems when running
odd
ratios for prolonged times.


Technically a finite precision double can always be represented by a
ratio of integers, but those 

Re: [Discuss-gnuradio] Serious bug in tag propagation with non-integer relative rate

[Jeff Long]

As Eugene suggests, the fractional resampler can be handled by doing a 
linear mapping from the input to the output of a single work call. 
Wouldn't this work with most or all blocks? There would also need to be 
an offset in order to handle history. Then, there wouldn't be a need to 
use higher precision counters.


On 01/01/2018 11:24 AM, Jeff Long wrote:
I think the reason rate changes are difficult for tags is that the block 
executor tries to guess what a block is doing based on its long-term or 
static rate change. The block itself knows exactly how input items 
relate to output items, and maybe certain blocks need to provide more 
feedback than just a rate. In those cases, the executor could use the 
exact translation provided by the block, and in tamer cases the rate can 
still be used.


On 01/01/2018 10:53 AM, Andy Walls wrote:

Hi Marcus:

On Sun, 2017-12-31 at 15:09 +, Müller, Marcus (CEL) wrote:

Hi Andy, hi Eugene

Hm, coming back to an idea I had not so long ago:

tag offset should not be 64bit unsihned integers only, but also have
a
64 bit fractional part.

That would not immediately solve the computational inaccurracy during
resampling, but would at least for multi (as in >2) rate systems (eg.
rational resampling for sample rate reduction, arbitrary resampling
for
clock recovery) at least give the option of having consistent
tagging.


IMO, adding a fractional part does not solve the problem at hand -
correct tag propagation through 1 block - but it probably is required
for precise propagation through multiple rate changing blocks.

I'm keeping it in mind, but I want to avoid changing existing
interfaces right now.  I.e. get_tags_in_[range|window]() runs into a
backward compatability issue for a tag that comes < 0.5 samples before
the beginning of the requested range: should the tag offset -0.49
samples realtive to the start of the window be returned or not?



Personally, my gut feeling is that for this kind of divisional math,
floating point is not the number format of choice


Agreed.


  (for multiple (as in

2) reasons).


This actually doesn't apply to the arbitrary resampling case as much,
but the d_relative_rate property of a block shouldn't be a floating
point,


Internal to the gnuradio-runtime there are a number of places where,
for estimating, using a floating point d_relative_rate is just fine.
It is expedient and avoids the problem of interger overflow for cases
where one has large integer interpolation and decimation factors.


but a ratio of two integers, one of them being signed. Maybe I
should be adding a set_relative_rate(int64_t numerator, uint_64_t
denominator) to block, and make set_relative_rate(double) a wrapper
for
that (and of course change the block_executor to do fractional rather
than floating point math);


So that's what my change does. :)  I also changed all the blocks, that
could easily easily call the integer version of
set_relataive_rate(interpolation, decimation), to do so.

To avoid integer overflow, I picked an algoritm in the new
set_relative_rate(double) wrapper, to convert the relative rate to a
ratio of two integers that got within 1 ppm of the passed in relative
rate.  Because sane users only use relative rates of 1/25 or 1001/1000
or 255/256 or 2/3 or something like that, and whacky relative rates
using large (>16 bit) integers in the ratio are just a product of
rounding, right?  Well I was wrong. :(

Unfortunately, the fractional resampler is a corner case that actually
uses the rounded (in binary) version of the resampling rate, that the
user specifies, in its actual operation. Computing exact integer ratios
to represent the double can lead to 53 bit numbers (IIRC), which can
lead to integer overflows when multiplying uint64_t's together. :(

So what I'm left with are two broad options to deal with handling a
double relative rate (like the fractional resampler uses):

1. Implement an method like Eugene suggests: do a double multiply, get
a rounded result, do a double division to get back to an initial
offset, subtract off that initial offset, do a double multiply again,
and then a final add.

or

2. Allow and compute large, exact integer ratios of
interpolation/decimation rate and use multiple precision (128 bit)
arithmetic when overflow out of 64 bits is possible.
Maybe using boost::multiprescision with the MIPR library on the
backend.
http://www.boost.org/doc/libs/1_66_0/libs/multiprecision/doc/html/index
.html
http://mpir.org/
(MPIR is supposedly better for Windows compatability than GMP.)


I'm leaning towards option 2.


I find that I never calculate a rate other
than by calculating the floating point approximation of a fraction of
integers, and that there's always been subtle problems when running
odd
ratios for prolonged times.


Technically a finite precision double can always be represented by a
ratio of integers, but those integers can be very (2^53-ish) large.

Thanks for the feedback.

Regards,
Andy


Best regards,
Marcus

On 

Re: [Discuss-gnuradio] Serious bug in tag propagation with non-integer relative rate

[Jeff Long]

I think the reason rate changes are difficult for tags is that the block 
executor tries to guess what a block is doing based on its long-term or 
static rate change. The block itself knows exactly how input items 
relate to output items, and maybe certain blocks need to provide more 
feedback than just a rate. In those cases, the executor could use the 
exact translation provided by the block, and in tamer cases the rate can 
still be used.


On 01/01/2018 10:53 AM, Andy Walls wrote:

Hi Marcus:

On Sun, 2017-12-31 at 15:09 +, Müller, Marcus (CEL) wrote:

Hi Andy, hi Eugene

Hm, coming back to an idea I had not so long ago:

tag offset should not be 64bit unsihned integers only, but also have
a
64 bit fractional part.

That would not immediately solve the computational inaccurracy during
resampling, but would at least for multi (as in >2) rate systems (eg.
rational resampling for sample rate reduction, arbitrary resampling
for
clock recovery) at least give the option of having consistent
tagging.


IMO, adding a fractional part does not solve the problem at hand -
correct tag propagation through 1 block - but it probably is required
for precise propagation through multiple rate changing blocks.

I'm keeping it in mind, but I want to avoid changing existing
interfaces right now.  I.e. get_tags_in_[range|window]() runs into a
backward compatability issue for a tag that comes < 0.5 samples before
the beginning of the requested range: should the tag offset -0.49
samples realtive to the start of the window be returned or not?



Personally, my gut feeling is that for this kind of divisional math,
floating point is not the number format of choice


Agreed.


  (for multiple (as in

2) reasons).


This actually doesn't apply to the arbitrary resampling case as much,
but the d_relative_rate property of a block shouldn't be a floating
point,


Internal to the gnuradio-runtime there are a number of places where,
for estimating, using a floating point d_relative_rate is just fine.
It is expedient and avoids the problem of interger overflow for cases
where one has large integer interpolation and decimation factors.


but a ratio of two integers, one of them being signed. Maybe I
should be adding a set_relative_rate(int64_t numerator, uint_64_t
denominator) to block, and make set_relative_rate(double) a wrapper
for
that (and of course change the block_executor to do fractional rather
than floating point math);


So that's what my change does. :)  I also changed all the blocks, that
could easily easily call the integer version of
set_relataive_rate(interpolation, decimation), to do so.

To avoid integer overflow, I picked an algoritm in the new
set_relative_rate(double) wrapper, to convert the relative rate to a
ratio of two integers that got within 1 ppm of the passed in relative
rate.  Because sane users only use relative rates of 1/25 or 1001/1000
or 255/256 or 2/3 or something like that, and whacky relative rates
using large (>16 bit) integers in the ratio are just a product of
rounding, right?  Well I was wrong. :(

Unfortunately, the fractional resampler is a corner case that actually
uses the rounded (in binary) version of the resampling rate, that the
user specifies, in its actual operation. Computing exact integer ratios
to represent the double can lead to 53 bit numbers (IIRC), which can
lead to integer overflows when multiplying uint64_t's together. :(

So what I'm left with are two broad options to deal with handling a
double relative rate (like the fractional resampler uses):

1. Implement an method like Eugene suggests: do a double multiply, get
a rounded result, do a double division to get back to an initial
offset, subtract off that initial offset, do a double multiply again,
and then a final add.

or

2. Allow and compute large, exact integer ratios of
interpolation/decimation rate and use multiple precision (128 bit)
arithmetic when overflow out of 64 bits is possible.
Maybe using boost::multiprescision with the MIPR library on the
backend.
http://www.boost.org/doc/libs/1_66_0/libs/multiprecision/doc/html/index
.html
http://mpir.org/
(MPIR is supposedly better for Windows compatability than GMP.)


I'm leaning towards option 2.


I find that I never calculate a rate other
than by calculating the floating point approximation of a fraction of
integers, and that there's always been subtle problems when running
odd
ratios for prolonged times.


Technically a finite precision double can always be represented by a
ratio of integers, but those integers can be very (2^53-ish) large.

Thanks for the feedback.

Regards,
Andy


Best regards,
Marcus

On Sat, 2017-12-30 at 18:24 -0500, Andy Walls wrote:

Hi Eugene:

On Wed, 2017-12-27 at 16:18 -0500, Andy Walls wrote:

Hi Eugene


From:   Eugene Grayver
Date:   Thu, 9 Nov 2017 19:52:35 +

There is a major problem with the way tags are propagated in
blocks
with non-integer relative rate. If the ratio is not a power of
two,
the numerical accuracy of the 

Re: [Discuss-gnuradio] Serious bug in tag propagation with non-integer relative rate

[Andy Walls]

Hi Marcus:

On Sun, 2017-12-31 at 15:09 +, Müller, Marcus (CEL) wrote:
> Hi Andy, hi Eugene
> 
> Hm, coming back to an idea I had not so long ago:
> 
> tag offset should not be 64bit unsihned integers only, but also have
> a
> 64 bit fractional part.
> 
> That would not immediately solve the computational inaccurracy during
> resampling, but would at least for multi (as in >2) rate systems (eg.
> rational resampling for sample rate reduction, arbitrary resampling
> for
> clock recovery) at least give the option of having consistent
> tagging.

IMO, adding a fractional part does not solve the problem at hand -
correct tag propagation through 1 block - but it probably is required
for precise propagation through multiple rate changing blocks.

I'm keeping it in mind, but I want to avoid changing existing
interfaces right now.  I.e. get_tags_in_[range|window]() runs into a
backward compatability issue for a tag that comes < 0.5 samples before
the beginning of the requested range: should the tag offset -0.49
samples realtive to the start of the window be returned or not?


> Personally, my gut feeling is that for this kind of divisional math,
> floating point is not the number format of choice

Agreed.

>  (for multiple (as in
> > 2) reasons).
> 
> This actually doesn't apply to the arbitrary resampling case as much,
> but the d_relative_rate property of a block shouldn't be a floating
> point,

Internal to the gnuradio-runtime there are a number of places where,
for estimating, using a floating point d_relative_rate is just fine. 
It is expedient and avoids the problem of interger overflow for cases
where one has large integer interpolation and decimation factors.

> but a ratio of two integers, one of them being signed. Maybe I
> should be adding a set_relative_rate(int64_t numerator, uint_64_t
> denominator) to block, and make set_relative_rate(double) a wrapper
> for
> that (and of course change the block_executor to do fractional rather
> than floating point math);

So that's what my change does. :)  I also changed all the blocks, that
could easily easily call the integer version of
set_relataive_rate(interpolation, decimation), to do so.

To avoid integer overflow, I picked an algoritm in the new
set_relative_rate(double) wrapper, to convert the relative rate to a
ratio of two integers that got within 1 ppm of the passed in relative
rate.  Because sane users only use relative rates of 1/25 or 1001/1000
or 255/256 or 2/3 or something like that, and whacky relative rates
using large (>16 bit) integers in the ratio are just a product of
rounding, right?  Well I was wrong. :(

Unfortunately, the fractional resampler is a corner case that actually
uses the rounded (in binary) version of the resampling rate, that the
user specifies, in its actual operation. Computing exact integer ratios
to represent the double can lead to 53 bit numbers (IIRC), which can
lead to integer overflows when multiplying uint64_t's together. :(

So what I'm left with are two broad options to deal with handling a
double relative rate (like the fractional resampler uses):

1. Implement an method like Eugene suggests: do a double multiply, get
a rounded result, do a double division to get back to an initial
offset, subtract off that initial offset, do a double multiply again,
and then a final add.

or

2. Allow and compute large, exact integer ratios of
interpolation/decimation rate and use multiple precision (128 bit)
arithmetic when overflow out of 64 bits is possible.
Maybe using boost::multiprescision with the MIPR library on the
backend.
http://www.boost.org/doc/libs/1_66_0/libs/multiprecision/doc/html/index
.html
http://mpir.org/
(MPIR is supposedly better for Windows compatability than GMP.)


I'm leaning towards option 2.

> I find that I never calculate a rate other
> than by calculating the floating point approximation of a fraction of
> integers, and that there's always been subtle problems when running
> odd
> ratios for prolonged times. 

Technically a finite precision double can always be represented by a
ratio of integers, but those integers can be very (2^53-ish) large. 

Thanks for the feedback.

Regards,
Andy

> Best regards,
> Marcus
> 
> On Sat, 2017-12-30 at 18:24 -0500, Andy Walls wrote:
> > Hi Eugene:
> > 
> > On Wed, 2017-12-27 at 16:18 -0500, Andy Walls wrote:
> > > Hi Eugene
> > > 
> > > > From:   Eugene Grayver
> > > > Date:   Thu, 9 Nov 2017 19:52:35 +
> > > > 
> > > > There is a major problem with the way tags are propagated in
> > > > blocks
> > > > with non-integer relative rate. If the ratio is not a power of
> > > > two,
> > > > the numerical accuracy of the floating point will cause the
> > > > output
> > > > tags to diverge from the input tags.  Consider the fractional
> > > > resampler. It accumulates the timing offset in the range of 0
> > > > to
> > > > 1.
> > > > However tag propagation multiplies the ratio by the sample
> > > > number.
> > > > As
> > > > the sample number grows the LSB 

Re: [Discuss-gnuradio] Serious bug in tag propagation with non-integer relative rate

[Andy Walls]

Hi Eugene:

On Wed, 2017-12-27 at 16:18 -0500, Andy Walls wrote:
> Hi Eugene
> 
> > From:   Eugene Grayver
> > Date:   Thu, 9 Nov 2017 19:52:35 +
> > 
> > There is a major problem with the way tags are propagated in blocks
> > with non-integer relative rate. If the ratio is not a power of two,
> > the numerical accuracy of the floating point will cause the output
> > tags to diverge from the input tags.  Consider the fractional
> > resampler. It accumulates the timing offset in the range of 0 to 1.
> > However tag propagation multiplies the ratio by the sample number.
> > As
> > the sample number grows the LSB accuracy of the ratio gets scaled
> > by
> > the ever larger value. For a ratio of 1.001 we saw divergence of
> > 1000s of samples over a few minutes at 10msps.
> 
> Could you please test the following branch to see if it fixes the
> problem?  Maybe test something simple first, like an FIR filter
> decimating by 5 or 3?
> 
> https://github.com/awalls-cx18/gnuradio.git branch: tag_fix3

Don't bother testing.  See below.

> Or if you have a GRC or python script I can use myself for testing,
> that would be great.
> 
> >  I rewrote tag propagation for the resampler but did not rework the
> > generic logic. I think the key point is to use the delta between
> > read
> > and written items to take out the large integer difference and then
> > apply the scaling to a local delta within the current window.
> > 
> 
> The fix that I have made stores the relative_rate as an integer
> numerator and an integer denominator, and it uses integer arithmetic
> to
> propagate tags. (Except if enable_update_rate() is True, in which
> case,
> precision tag placement was abandonded by the block author anyway.)

So this fix makes the fraction resampler tag propagation actually
perform worse.  The reason appears to be that, at least for
resamp_ratios very close to 1.0, the fractional resampler isn't really
running at the requested rate, but some rounded (in binary) rate.

So I have a test flowgraph with a single fractional respampler in it,
with a resample ratio of 1.001 specified.  Here are the parameters
reported by my patched GNURadio:

[andy@pinto grcs]$ ./tag_prop_test.py 
Fractional Resampler resamp ratio:  1.0014673
Block relative rate:  0.999000952364
Block relative rate i:  1000
Block relative rate d:  1001

So we can see that the block is really running with a resampling ratio
of 1.0014673.  The relative rate of 0.999000952364 does appear to
be the correct reciprocal of 1.0014673.  My patch's back-figuring
of a relative rate of 1000/1001 (= 0.999000999 = 1/1.001) is in fact
what the user wanted.  But when propagating tags using those integers,
tags start sliding very soon, since 0.999000999 is not the
0.999000952364 that the block is actually operating at.

I'll have to think about how to deal with this sort of situation.

Regards,
Andy

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

Re: [Discuss-gnuradio] Serious bug in tag propagation with non-integer relative rate

[Dan CaJacob]

I suppose if you don't have 64 bit, you can just shift it to be 32-bit and
sacrifice the lost precision. There's probably other possibilities, but I
think the newer ARM stuff is going 64-bit anyhow.

On Mon, Nov 13, 2017 at 2:01 PM Marcus Müller  wrote:

> Ok, see your point. I was a bit hesitant at first because that will end
> up needing 64bit division (which might really not be much fun on many
> ARMs), but meh, it's not like someone should be pushing tags around as
> if they're samples.
>
> Cheers,
> Marcus
>
> On Sun, 2017-11-12 at 23:33 +, Dan CaJacob wrote:
> > Why not make the sub-second offset a uint64. That way you can express
> time to the atto second (I think). The precision is overkill, but uint32,
> which barely breaks a picosecond is underkill.
> >
> > On Sun, Nov 12, 2017 at 6:19 PM Marcus Müller 
> wrote:
> > > Hi Eugene,
> > > yup, fully agree, the whole concept is slightly broken.
> > > So, first of all, I really think the key problem we're constantly
> working around is that tags have an integer offset – which leads to
> rounding errors, even in relatively benign scenarios.
> > > I'd propose we add a fractional part: that would only extend tag_t by
> another integer field, so existing blocks wouldn't break, and would allow
> non-1:1-sync blocks to properly rewrite tag positions.
> > > As you say, floating point is a bad idea when dealing with times (it
> always has been – see uhd::time_spec_t, where we're constantly paying off
> the technical debt of having floating point as "suggested" default
> representation of time, albeit underneath things should (and to some
> degree, are) counted in ticks). Thus, I'd imagine a tag_t like
> > > struct tag_t {
> > > uint64_t offset; //integer offset, as had
> > > uint32_t fractional_offset; //interpret as fractional part, i.e.
> ·2^{-32}
> > > pmt::pmt_t key;
> > > pmt::pmt_t tag;
> > > pmt::pmt_t srcid; // might as well drop this; maybe someone is
> using this, but I haven't met them
> > > std::vector marked_deleted;
> > > }
> > > Would the fractional offset solve the issues you're seeing, assuming
> that we add proper handling to all the existing resamplers?
> > > Best regards,
> > > Marcus
> > >
> > >
> > > On 09.11.2017 20:52, Eugene Grayver wrote:
> > > > There is a major problem with the way tags are propagated in blocks
> with non-integer relative rate. If the ratio is not a power of two, the
> numerical accuracy of the floating point will cause the output tags to
> diverge from the input tags.  Consider the fractional resampler. It
> accumulates the timing offset in the range of 0 to 1. However tag
> propagation multiplies the ratio by the sample number. As the sample number
> grows the LSB accuracy of the ratio gets scaled by the ever larger value.
> For a ratio of 1.001 we saw divergence of 1000s of samples over a few
> minutes at 10msps. I rewrote tag propagation for the resampler but did not
> rework the generic logic. I think the key point is to use the delta between
> read and written items to take out the large integer difference and then
> apply the scaling to a local delta within the current window.
> > > >
> > > > ___
> > > > Eugene Grayver, Ph.D.
> > > > Aerospace Corp., Sr. Eng. Spec.
> > > > Tel: 310.336.1274 <(310)%20336-1274>
> > > > 
> > > >
> > > >
> > > >
> > > > ___
> > > > Discuss-gnuradio mailing list
> > > > Discuss-gnuradio@gnu.org
> > > > https://lists.gnu.org/mailman/listinfo/discuss-gnuradio
> > >
> > > ___
> > > Discuss-gnuradio mailing list
> > > Discuss-gnuradio@gnu.org
> > > https://lists.gnu.org/mailman/listinfo/discuss-gnuradio
> >
> > --
> > Very Respectfully,
> >
> > Dan CaJacob
> > ___
> > Discuss-gnuradio mailing list
> > Discuss-gnuradio@gnu.org
> > https://lists.gnu.org/mailman/listinfo/discuss-gnuradio

-- 
Very Respectfully,

Dan CaJacob
___
Discuss-gnuradio mailing list
Discuss-gnuradio@gnu.org
https://lists.gnu.org/mailman/listinfo/discuss-gnuradio

Re: [Discuss-gnuradio] Serious bug in tag propagation with non-integer relative rate

[Marcus Müller]

Ok, see your point. I was a bit hesitant at first because that will end
up needing 64bit division (which might really not be much fun on many
ARMs), but meh, it's not like someone should be pushing tags around as
if they're samples.

Cheers,
Marcus

On Sun, 2017-11-12 at 23:33 +, Dan CaJacob wrote:
> Why not make the sub-second offset a uint64. That way you can express time to 
> the atto second (I think). The precision is overkill, but uint32, which 
> barely breaks a picosecond is underkill.
> 
> On Sun, Nov 12, 2017 at 6:19 PM Marcus Müller  
> wrote:
> > Hi Eugene,
> > yup, fully agree, the whole concept is slightly broken. 
> > So, first of all, I really think the key problem we're constantly working 
> > around is that tags have an integer offset – which leads to rounding 
> > errors, even in relatively benign scenarios.
> > I'd propose we add a fractional part: that would only extend tag_t by 
> > another integer field, so existing blocks wouldn't break, and would allow 
> > non-1:1-sync blocks to properly rewrite tag positions.
> > As you say, floating point is a bad idea when dealing with times (it always 
> > has been – see uhd::time_spec_t, where we're constantly paying off the 
> > technical debt of having floating point as "suggested" default 
> > representation of time, albeit underneath things should (and to some 
> > degree, are) counted in ticks). Thus, I'd imagine a tag_t like
> > struct tag_t {
> > uint64_t offset; //integer offset, as had
> > uint32_t fractional_offset; //interpret as fractional part, i.e. 
> > ·2^{-32}
> > pmt::pmt_t key;
> > pmt::pmt_t tag;
> > pmt::pmt_t srcid; // might as well drop this; maybe someone is using 
> > this, but I haven't met them
> > std::vector marked_deleted; 
> > }
> > Would the fractional offset solve the issues you're seeing, assuming that 
> > we add proper handling to all the existing resamplers?
> > Best regards,
> > Marcus
> > 
> > 
> > On 09.11.2017 20:52, Eugene Grayver wrote:
> > > There is a major problem with the way tags are propagated in blocks with 
> > > non-integer relative rate. If the ratio is not a power of two, the 
> > > numerical accuracy of the floating point will cause the output tags to 
> > > diverge from the input tags.  Consider the fractional resampler. It 
> > > accumulates the timing offset in the range of 0 to 1. However tag 
> > > propagation multiplies the ratio by the sample number. As the sample 
> > > number grows the LSB accuracy of the ratio gets scaled by the ever larger 
> > > value. For a ratio of 1.001 we saw divergence of 1000s of samples over a 
> > > few minutes at 10msps. I rewrote tag propagation for the resampler but 
> > > did not rework the generic logic. I think the key point is to use the 
> > > delta between read and written items to take out the large integer 
> > > difference and then apply the scaling to a local delta within the current 
> > > window.
> > >  
> > > ___
> > > Eugene Grayver, Ph.D.
> > > Aerospace Corp., Sr. Eng. Spec.
> > > Tel: 310.336.1274
> > > 
> > >  
> > > 
> > > 
> > > ___
> > > Discuss-gnuradio mailing list
> > > Discuss-gnuradio@gnu.org
> > > https://lists.gnu.org/mailman/listinfo/discuss-gnuradio
> >  
> > ___
> > Discuss-gnuradio mailing list
> > Discuss-gnuradio@gnu.org
> > https://lists.gnu.org/mailman/listinfo/discuss-gnuradio
> 
> -- 
> Very Respectfully,
> 
> Dan CaJacob
> ___
> Discuss-gnuradio mailing list
> Discuss-gnuradio@gnu.org
> https://lists.gnu.org/mailman/listinfo/discuss-gnuradio

smime.p7s
Description: S/MIME cryptographic signature
___
Discuss-gnuradio mailing list
Discuss-gnuradio@gnu.org
https://lists.gnu.org/mailman/listinfo/discuss-gnuradio

Re: [Discuss-gnuradio] Serious bug in tag propagation with non-integer relative rate

[Dan CaJacob]

Why not make the sub-second offset a uint64. That way you can express time
to the atto second (I think). The precision is overkill, but uint32, which
barely breaks a picosecond is underkill.

On Sun, Nov 12, 2017 at 6:19 PM Marcus Müller 
wrote:

> Hi Eugene,
>
> yup, fully agree, the whole concept is slightly broken.
>
> So, first of all, I really think the key problem we're constantly working
> around is that tags have an integer offset – which leads to rounding
> errors, even in relatively benign scenarios.
>
> I'd propose we add a fractional part: that would only extend tag_t by
> another integer field, so existing blocks wouldn't break, and would allow
> non-1:1-sync blocks to properly rewrite tag positions.
>
> As you say, floating point is a bad idea when dealing with times (it
> always has been – see uhd::time_spec_t, where we're constantly paying off
> the technical debt of having floating point as "suggested" default
> representation of time, albeit underneath things should (and to some
> degree, are) counted in ticks). Thus, I'd imagine a tag_t like
>
> struct tag_t {
> uint64_t offset; //integer offset, as had
> uint32_t fractional_offset; //interpret as fractional part, i.e. ·2^{-32}
> pmt::pmt_t key;
> pmt::pmt_t tag;
> pmt::pmt_t srcid; // might as well drop this; maybe someone is using 
> this, but I haven't met them
> std::vector marked_deleted;
> }
>
> Would the fractional offset solve the issues you're seeing, assuming that
> we add proper handling to all the existing resamplers?
> Best regards,
> Marcus
>
>
> On 09.11.2017 20:52, Eugene Grayver wrote:
>
> There is a major problem with the way tags are propagated in blocks with
> non-integer relative rate. If the ratio is not a power of two, the
> numerical accuracy of the floating point will cause the output tags to
> diverge from the input tags.  Consider the fractional resampler. It
> accumulates the timing offset in the range of 0 to 1. However tag
> propagation multiplies the ratio by the sample number. As the sample number
> grows the LSB accuracy of the ratio gets scaled by the ever larger value.
> For a ratio of 1.001 we saw divergence of 1000s of samples over a few
> minutes at 10msps. I rewrote tag propagation for the resampler but did not
> rework the generic logic. I think the key point is to use the delta between
> read and written items to take out the large integer difference and then
> apply the scaling to a local delta within the current window.
>
>
>
> ___
> Eugene Grayver, Ph.D.
> Aerospace Corp., Sr. Eng. Spec.
> Tel: 310.336.1274 <(310)%20336-1274>
> 
>
>
>
>
> ___
> Discuss-gnuradio mailing 
> listDiscuss-gnuradio@gnu.orghttps://lists.gnu.org/mailman/listinfo/discuss-gnuradio
>
>
> ___
> Discuss-gnuradio mailing list
> Discuss-gnuradio@gnu.org
> https://lists.gnu.org/mailman/listinfo/discuss-gnuradio
>
-- 
Very Respectfully,

Dan CaJacob
___
Discuss-gnuradio mailing list
Discuss-gnuradio@gnu.org
https://lists.gnu.org/mailman/listinfo/discuss-gnuradio

Re: [Discuss-gnuradio] Serious bug in tag propagation with non-integer relative rate

[Marcus Müller]

Hi Eugene,

yup, fully agree, the whole concept is slightly broken.

So, first of all, I really think the key problem we're constantly
working around is that tags have an integer offset – which leads to
rounding errors, even in relatively benign scenarios.

I'd propose we add a fractional part: that would only extend tag_t by
another integer field, so existing blocks wouldn't break, and would
allow non-1:1-sync blocks to properly rewrite tag positions.

As you say, floating point is a bad idea when dealing with times (it
always has been – see uhd::time_spec_t, where we're constantly paying
off the technical debt of having floating point as "suggested" default
representation of time, albeit underneath things should (and to some
degree, are) counted in ticks). Thus, I'd imagine a tag_t like

struct tag_t {
uint64_t offset; //integer offset, as had
uint32_t fractional_offset; //interpret as fractional part, i.e. ·2^{-32}
pmt::pmt_t key;
pmt::pmt_t tag;
pmt::pmt_t srcid; // might as well drop this; maybe someone is using this, 
but I haven't met them
std::vector marked_deleted; 
}

Would the fractional offset solve the issues you're seeing, assuming
that we add proper handling to all the existing resamplers?
Best regards,
Marcus

On 09.11.2017 20:52, Eugene Grayver wrote:
>
> There is a major problem with the way tags are propagated in blocks
> with non-integer relative rate. If the ratio is not a power of two,
> the numerical accuracy of the floating point will cause the output
> tags to diverge from the input tags.  Consider the fractional
> resampler. It accumulates the timing offset in the range of 0 to 1.
> However tag propagation multiplies the ratio by the sample number. As
> the sample number grows the LSB accuracy of the ratio gets scaled by
> the ever larger value. For a ratio of 1.001 we saw divergence of 1000s
> of samples over a few minutes at 10msps. I rewrote tag propagation for
> the resampler but did not rework the generic logic. I think the key
> point is to use the delta between read and written items to take out
> the large integer difference and then apply the scaling to a local
> delta within the current window.
>
>  
>
> ___
> Eugene Grayver, Ph.D.
> Aerospace Corp., Sr. Eng. Spec.
> Tel: 310.336.1274
> 
>
>  
>
>
>
> ___
> Discuss-gnuradio mailing list
> Discuss-gnuradio@gnu.org
> https://lists.gnu.org/mailman/listinfo/discuss-gnuradio

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