Re: [Discuss-gnuradio] Serious bug in tag propagation with non-integer relative rate
>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
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
(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
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
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
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
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
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üllerwrote: > 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
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
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üllerwrote: > 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
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