[2/5] libipa: histogram: Fix quantile() calculation for fractional results
diff mbox series

Message ID 20250324170803.103296-3-stefan.klug@ideasonboard.com
State New
Headers show
Series
  • Fix histogram for some (corner) cases
Related show

Commit Message

Stefan Klug March 24, 2025, 5:07 p.m. UTC
The calculation of the frac variable is based solely on integers and
therefore results in the fractional part being either 0 or 1.

In the original code from RaspberryPi this is mitigated by casting the
nominator to a double. This works for most cases, but fails when q is
very small because of the quantization introduced by item being an
integer.

Fix both issues by doing the full calculation in double.

Signed-off-by: Stefan Klug <stefan.klug@ideasonboard.com>
---
 src/ipa/libipa/histogram.cpp | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

Comments

Kieran Bingham March 31, 2025, 6:07 p.m. UTC | #1
Quoting Stefan Klug (2025-03-24 17:07:37)
> The calculation of the frac variable is based solely on integers and
> therefore results in the fractional part being either 0 or 1.
> 
> In the original code from RaspberryPi this is mitigated by casting the
> nominator to a double. This works for most cases, but fails when q is
> very small because of the quantization introduced by item being an
> integer.
> 
> Fix both issues by doing the full calculation in double.
> 
> Signed-off-by: Stefan Klug <stefan.klug@ideasonboard.com>

as far as I can tell this seems reasonable...

Proof is in the pudding-test.... which I see was added later...

Reviewed-by: Kieran Bingham <kieran.bingham@ideasonboard.com>

> ---
>  src/ipa/libipa/histogram.cpp | 3 ++-
>  1 file changed, 2 insertions(+), 1 deletion(-)
> 
> diff --git a/src/ipa/libipa/histogram.cpp b/src/ipa/libipa/histogram.cpp
> index 10e44b54a0cf..c19a4cbbf3cd 100644
> --- a/src/ipa/libipa/histogram.cpp
> +++ b/src/ipa/libipa/histogram.cpp
> @@ -130,7 +130,8 @@ double Histogram::quantile(double q, uint32_t first, uint32_t last) const
>         if (cumulative_[first + 1] == cumulative_[first])
>                 frac = 0;
>         else
> -               frac = (item - cumulative_[first]) / (cumulative_[first + 1] - cumulative_[first]);
> +               frac = (q * total() - cumulative_[first]) /
> +                      (cumulative_[first + 1] - cumulative_[first]);
>         return first + frac;
>  }
>  
> -- 
> 2.43.0
>
Laurent Pinchart March 31, 2025, 10:07 p.m. UTC | #2
Hi Stefan,

Thank you for the patch.

On Mon, Mar 24, 2025 at 06:07:37PM +0100, Stefan Klug wrote:
> The calculation of the frac variable is based solely on integers and
> therefore results in the fractional part being either 0 or 1.

Oops.

> In the original code from RaspberryPi this is mitigated by casting the
> nominator to a double. This works for most cases, but fails when q is
> very small because of the quantization introduced by item being an
> integer.
> 
> Fix both issues by doing the full calculation in double.
> 
> Signed-off-by: Stefan Klug <stefan.klug@ideasonboard.com>
> ---
>  src/ipa/libipa/histogram.cpp | 3 ++-
>  1 file changed, 2 insertions(+), 1 deletion(-)
> 
> diff --git a/src/ipa/libipa/histogram.cpp b/src/ipa/libipa/histogram.cpp
> index 10e44b54a0cf..c19a4cbbf3cd 100644
> --- a/src/ipa/libipa/histogram.cpp
> +++ b/src/ipa/libipa/histogram.cpp
> @@ -130,7 +130,8 @@ double Histogram::quantile(double q, uint32_t first, uint32_t last) const
>  	if (cumulative_[first + 1] == cumulative_[first])
>  		frac = 0;
>  	else
> -		frac = (item - cumulative_[first]) / (cumulative_[first + 1] - cumulative_[first]);
> +		frac = (q * total() - cumulative_[first]) /
> +		       (cumulative_[first + 1] - cumulative_[first]);

Maybe

		frac = (q * total() - cumulative_[first])
		     / (cumulative_[first + 1] - cumulative_[first]);

Reviewed-by: Laurent Pinchart <laurent.pinchart@ideasonboard.com>

>  	return first + frac;
>  }
>

Patch
diff mbox series

diff --git a/src/ipa/libipa/histogram.cpp b/src/ipa/libipa/histogram.cpp
index 10e44b54a0cf..c19a4cbbf3cd 100644
--- a/src/ipa/libipa/histogram.cpp
+++ b/src/ipa/libipa/histogram.cpp
@@ -130,7 +130,8 @@  double Histogram::quantile(double q, uint32_t first, uint32_t last) const
 	if (cumulative_[first + 1] == cumulative_[first])
 		frac = 0;
 	else
-		frac = (item - cumulative_[first]) / (cumulative_[first + 1] - cumulative_[first]);
+		frac = (q * total() - cumulative_[first]) /
+		       (cumulative_[first + 1] - cumulative_[first]);
 	return first + frac;
 }