On Wed, 11 Dec 2019 at 01:24, Laurenz Albe <laurenz.albe@cybertec.at> wrote:
>
> On Tue, 2019-12-10 at 15:50 -0700, Jim Finnerty wrote:
> > As a proof of concept, I hacked around a bit today to re-purpose one of the
> > bits of the Cost structure to mean "is_disabled" so that we can distinguish
> > 'disabled' from 'non-disabled' paths without making the Cost structure any
> > bigger. In fact, it's still a valid double. The obvious choice would have
> > been to re-purpose the sign bit, but I've had occasion to exploit negative
> > costs before so for this POC I used the high-order bit of the fractional
> > bits of the double. (see Wikipedia for double precision floating point for
> > the layout).
> >
> > The idea is to set a special bit when disable_cost is added to a cost.
> > Dedicating multiple bits instead of just 1 would be easily done, but as it
> > is we can accumulate many disable_costs without overflowing, so just
> > comparing the cost suffices.
>
> Doesn't that rely on a specific implementation of double precision (IEEE)?
> I thought that we don't want to limit ourselves to platforms with IEEE floats.
We could always implement it again in another format....
However, I wouldn't have expected to be bit twiddling. I would have
expected to use standard functions like ldexp to do this. In fact I
think if you use the high bit of the exponent you could do it entirely
using ldexp and regular double comparisons (with fabs).
Ie, to set the bit you set cost = ldexp(cost, __DBL_MAX_EXP__/2). And
to check for the bit being set you compare ilogb(cost,
__DBL_MAX_EXP__/2). Hm. that doesn't handle if the cost is already < 1
in which case I guess you would have to set it to 1 first. Or reserve
the two high bits of the cost so you can represent disabled values
that had negative exponents before being disabled.
I wonder if it wouldn't be a lot cleaner and more flexible to just go
with a plain float for Cost and use the other 32 bits for counters and
bitmasks and still be ahead of the game. A double can store 2^1024 but
a float 2^128 which still feels like it should be more than enough to
store the kinds of costs plans have without the disabled costs. 2^128
milliseconds is still 10^28 years which is an awfully expensive
query....
--
greg