Canonical normalization of time values



  • I am in the process of migrating our code from ACE to Qt. One of the ACE structures we use quite heavily is the ACE_Time_Value class which is a platform-independent method of dealing with arbitrary time values. It has an interface to do all of the usual operations upon it, such as addition, subtraction, multiplication, etc... Internally, the time value is stored as two 64-bit signed integers representing seconds and microseconds respectively. Because operations on the class can result in non-canonical values for each, there is a normalize() method which will adjust the values to canonical form.

    I am writing a class to replace this in our code, to avoid having to rewrite a lot of existing code which uses it. The ACE version of the normalize() method uses some complex if/else and do/while operations to deal with the integer seconds and microseconds without having to resort to floating point arithmetic. The version I wrote is much simpler, but does involve floating-point arithmetic:

    void TimeValue::normalize()
    {
      static double fract_part, int_part;
      double secs = seconds + microseconds * 1e-6;
    
      fract_part = modf(secs, &int_part);
      seconds = int_part;
      microseconds = qRound64(fract_part * 1e6);
    }
    

    "seconds" and "microseconds" are qint64 values. My questions are:

    • Can the above code be optimized a any further? Ideally, any optimizations should be platform-independent
    • Is there a better way to do this in Qt?

    Thanks!


  • Qt Champions 2016

    @DRoscoe said in Canonical normalization of time values:
    Why use a qint64 as seconds? And more importantly, why use qint64 as microseconds?

    A million microseconds is a single second, so if you are representing microseconds I don't see any reason to use so wide of a type ... 20 bits are more than enough. You could in principle use one single 64bit integer to represent 44bits for the seconds and 20 bits for the microseconds (i.e. a 44.20 fixed point) and stick to ordinary integer arithmetic. Normalization will be taken care for you by construction.



  • I use qint64 because the ACE_Time_Value uses 64-bit integers. While storing seconds and microseconds does not require that range, other things like:

    User supplied values (which can be arbitrary)
    Addition of time values
    Multiplication of time values
    Conversion of time values to various formats. For example you can construct one of these from a UTC time value. Since the epoch is 1/1/1970, providing a method which produces microseconds since that epoch can require more room in the data structure.

    I didn't add all of that detail, because it's not relevant to my question and doesn't change the solution.

    As for normalizing in construction, I don't know what you are referring to? Construction of what? If a user constructs a time value with 5 seconds and 8.95476e6 microseconds, 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.



  • @DRoscoe HI,
    have you considered using QDateTime? Internaly it stored as qint64 as a serial msecs value encoding the date and time. This restricts the date range to about +/- 292 million years. Using QDate only makes that a range of +/- 2 billion years.

    QDateTame gives you + functions:

    • addDays(qint64 ndays)
    • addMSecs(qint64 msecs)
    • addMonths(int nmonths)
    • addSecs(qint64 s)
    • addYears(int nyears)

    other usfull things, msecsTo(const QDateTime &other) or secsTo(const QDateTime &other) const If you port old code to Qt, use all of Qt for it :-)

    To your question, I don't see how you could make your code more efficient.


  • Moderators

    @DRoscoe said in Canonical normalization of time values:

    Can the above code be optimized a any further?

    In case you mean run-time optimization: Have you already benchmarked your code against the original implementation? If the other code has a lot of branches like you say, maybe your code is already faster. But predicting that is almost impossible so you have to measure.

    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.


  • Qt Champions 2016

    @DRoscoe

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

    @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.

    @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

    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.


  • Moderators

    @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:

        struct TimeValue
        {
            int64_t seconds{0};
            int64_t microseconds{0};
            
            void normalize() {
                namespace c = std::chrono;
                using ss = c::seconds;
                using us = c::microseconds;
                
                ss const tmp_s{seconds};
                us const tmp_us{microseconds};
                us const tmp_result{tmp_s + tmp_us};
                ss const result_s{c::duration_cast<ss>(tmp_result)};
                us const result_ms{tmp_result - us(result_s)};
                
                seconds = result_s.count();
                microseconds = result_ms.count();
            }
        };
    

  • Qt Champions 2016

    @Wieland said in Canonical normalization of time values:

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

    Okay, but how that prevents you from changing the implementation while keeping the interface the same? That's what I was suggesting, not changing the methods, but rather changing the internal structure.



  • 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.



  • @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.


  • Qt Champions 2016

    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;
    }
    

  • Moderators

    @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 ?



  • @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.


  • Moderators

    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;
        }
    


  • @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


  • Moderators

    @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 :)



  • @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?


  • Moderators

    @DRoscoe said in Canonical normalization of time values:

    Is there a reason to use int64_t over qint64?

    No, just a habit.



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


  • Qt Champions 2016

    @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 ...


Log in to reply
 

Looks like your connection to Qt Forum was lost, please wait while we try to reconnect.