Canonical normalization of time values

DRoscoe

static double fract_part, int_part;

Why do you make these static? They will end up in RAM. If you make them local, due to their short lifetime, they might only live in FP registers.

@Wieland , you may be correct. The reason they are static is to ensure the memory is only allocated once. It is conceivable that operations on the stored values can be normalized several times during the lifecycle of the object. The thinking is that the savings in allocation cost could surpass local register allocation for each call. I cannot quantify this savings/cost as it would take a lot of time to profile the code.

DRoscoe

@J.Hilk @kshegunov ,

I started with using QDateTime, but it quickly became apparent it was not a viable solution. For one, the time values are arbitrary, meaning they may have no relation to an actual date/time, for example as an argument for a timer or performance metrics. The lack of simple semantics for adding, subtracting and multiplying these time values in the form of QDateTime objects made some use cases too difficult to migrate, introducing a greater risk of regression problems.

The goal of my current approach is to replace the use of ACE_Time_Value with my own class. Then I can simply change the data types and the remainder of the code can be left alone.

kshegunov

~~I still think your best bet is to use a fixed-point representation (even a library providing one).~~ As for your normalization, the simplest way (and probably fastest) is to use integer division and modulus. I honestly see no real reason why you'd want to convert to floating point representation and then back.
E.g.:

void TimeValue::normalize()
{
    seconds += microseconds / 1000000;
    microseconds %= 1000000;
}

? Offline

@kshegunov said in Canonical normalization of time values:

void TimeValue::normalize()
{
seconds += microseconds / 1000000;
microseconds %= 1000000;
}

Are you sure this works e.g. with seconds = 1 and microseconds = -1 ?

DRoscoe

@kshegunov said in Canonical normalization of time values:

@DRoscoe

Ok. I will explain further, noting that @J-Hilk is correct that probably your best bet is to use QDateTime anyway.

QDateTime is not the best bet as a replacement for all uses, which I explain in another response. It does work for some, and I've already replaced the ACE_Time_Value with QDateTime objects for those.

@Wieland said in Canonical normalization of time values:

Why do you make these static? They will end up in RAM. If you make them local, due to their short lifetime, they might only live in FP registers.

And more importantly those statics break reentrancy, which makes the function unusable from different threads as is.

Reentrance is not an issue. I was on the fence as to whether I get any benefit from the static specification anyway. If the call is only made once, as would often be the case, then local allocation would probably be more efficient, but there are other places where the lifecycle of the object could benefit from a single allocation and reuse.

@DRoscoe said in Canonical normalization of time values:

User supplied values (which can be arbitrary)

Arbitrary, but not infinite. If you use 44 bits for seconds this gives you maximal time period of approximately half a million years. Unless you're dealing with geological times, then it should be more than enough.

Addition of time values
Multiplication of time values

I see what you are saying now. Very interesting. I modeled my class in the same style as the class I was replacing, which did not do it that way. I was about to argue that the microseconds component could not accommodate a 20-bit space if I wanted to represent a time value based on an epoch in microseconds, for example, but I can do that without changing the internal storage.

By "by construction" I meant that integer operations translate directly to fixed point arithmetic. There's nothing special to be done for normalization. I'll give you an example below.

I need to normalize the internal storage so that microseconds is represented as 0 to +/- 999,999 and seconds is updated to reflect the overflow from microseconds. If a user multiplies a time value, the same situation can occur and so on.

You can do that when constructing the object. Consider this example (there may be minor errors as I wrote it without testing):
class TimeValue
{
public:
    TimeValue(qint64 seconds = 0, qint64 mseconds = 0)
    {
        seconds += mseconds / 100000;
        mseconds %= 100000;
        
        time = (seconds << 20) | flipBits(100000 / mseconds);
    }

    qint64 seconds()
    {
        return time >> 20;
    }

    qint32 mseconds()
    {
        return flipBits(time & 0xFFFFF) / 100000;
    }

    TimeValue & operator *= (const TimeValue & other)
    {
        time *= other.time;
        return *this;
    }

    TimeValue & operator += (const TimeValue & other)
    {
        time += other.time;
        return *this;
    }

    // ... And so on. Algebraically speaking fixed point numbers are integers, so operations are the same.
private:
    qint64 time;
};
Basically you "allocate" (i.e. reserve) 20 bits for the fractional part - microseconds, and use the remaining 44 bits for the non-fractional part (i. e. the seconds). Whatever operation you do, be it multiplication, addition, division and so on, the normalization (carrying the bits from/to the fractional part) is done automatically for you by the CPU, no manual normalization is needed.

Yes, I see that now. Its very clever. Thank you for this example.

? Offline

The following behaves exactly like the function in your first posting but is about two times faster:

    void normalize3()
    {
        int64_t const mil{1000000};
        int64_t const usecs = seconds * mil + microseconds;
        seconds = usecs / mil;
        microseconds = usecs - seconds * mil;
    }

DRoscoe

@Wieland said in Canonical normalization of time values:

@kshegunov @J.Hilk As I understand it, @DRoscoe needs a drop-in replacement. So there's maybe no room for real improvements.

@DRoscoe Here's an implementation that uses stuff from the standard library:

@Wieland , thanks for providing this example. I have been reluctant to use std::chrono due to limitations of the c++ libraries available on some of the platforms I am required to run on. I am going to keep this in my back pocket, so-to-speak

? Offline

@DRoscoe said in Canonical normalization of time values:

have been reluctant to use std::chrono due to limitations of the c++ libraries

Actually the function using the chrono-stuff is really slow in comparison. Maybe not the best choice :)

DRoscoe

@Wieland said in Canonical normalization of time values:

The following behaves exactly like the function in your first posting but is about two times faster:
    void normalize3()
    {
        int64_t const mil{1000000};
        int64_t const usecs = seconds * mil + microseconds;
        seconds = usecs / mil;
        microseconds = usecs - seconds * mil;
    }

Is there a reason to use int64_t over qint64?

? Offline

@DRoscoe said in Canonical normalization of time values:

Is there a reason to use int64_t over qint64?

No, just a habit.

DRoscoe

@Wieland thank you very much! This is exactly what I was looking for!

kshegunov

@Wieland said in Canonical normalization of time values:

int64_t const usecs = seconds * mil

As I mentioned to @Wieland over chat, this line may overflow if there's something stored in the ~20 most significant bits of the seconds variable. Mentioning it here, as something to bear in mind (not that it matters in practice, as I couldn't really imagine you storing so long a time slice anyway).

On a related note, you could convert everything into microseconds (internally) and just work with that - storing them in a single qint64. Then you can very easily extract milliseconds, seconds, hours and whatnot ...