On 21.04.23 13:13, Johannes Berg wrote:
On Fri, 2023-04-21 at 12:34 +0200, Benjamin Beichler wrote:
> >
> > So then let's say we want to fix the existing code. I can think of these
> > possible ways:
> >
> > * splitting off a bit for initialized from the unsigned long
> > (which at least for 64-bit should be OK since presumably most code
> > using this will run on 32-bit systems too)
> > * adding another value for it, e.g. making it u32 and adding a bool
> > for
> > "first value"
> > * biasing the value, like Felix proposes, could be by 1 or -1 for
> > example
You forgot the possibility to introduce a separate init function, which
boils down to a shift with an assignment statement for code, and no
further data memory cost. Even simply extending the current init
function (which simply always set 0) would be enough.
Sort of. Yeah I should've mentioned it, but that means you actually have
to know the first value, and track "first time usage" separately in the
user code.
Or you init to something useful at the first value, e.g. saying for
signal strength "let's assume -45dBm average if we don't know". That
doesn't seem very practical?
The behaviour of "first value inserted will init" seems sensible.
> > As for biasing the value, couldn't that lead to a similar problem? It's
> > clearly less likely that the end of the range is reached rather than
> > zero, but still?
> I don't see how it can reduce the range in any way, since the bias is
> added to the fractional part. A range reduction would seem to imply
> having an average value that's bigger than the maximum allowed shifted
> input (top bits cut off), and I don't think that's possible.
>
It does not reduce the range, but it does not matter whether your
internal state is 0 or 2^(-precision), the non-intuitive behavior stays
the same.
OK I was sort of handwaving ... :-)
To have a problem, basically the +1 has to overflow the value, so that
we think that the next time around we should init, rather than add.
That means the existing average has to be 0xffff'ffff (let's take 32
bits, its easier to type). Clearly that can't happen on the first time
since then the precision bits are all 0.
But I think Felix is right (thought not sure about the reasoning) and
that cannot happen, because the add calculation does a ">>weight_rcp"
shift at the end, so there are always some top bits that are non-zero,
and _weight_rcp has to be a power of two. Now, 1 is a power of two, but
that'd be really stupid, and nobody is using it ... So I think if we
prohibit 1 for that, we're fine?
Btw, Felix, shouldn't your patch have said "bool init = !internal"?
No, 'internal' is the correct value. The name is confusing though - I
intended it to be short for 'initalized', but it should probably be
renamed to 'valid' or something like that.
- Felix
