Canonical normalization of time values
-
@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.
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 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)orsecsTo(const QDateTime &other) constIf 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.
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.
-
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.
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; } -
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; }@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 ?
-
Ok. I will explain further, noting that @J-Hilk is correct that probably your best bet is to use
QDateTimeanyway.@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 valuesBy "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.
@kshegunov said in Canonical normalization of time values:
Ok. I will explain further, noting that @J-Hilk is correct that probably your best bet is to use
QDateTimeanyway.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 valuesI 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.
-
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; } -
@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(); } };@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
-
@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
@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 :)
-
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:
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?
-
@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?
@DRoscoe said in Canonical normalization of time values:
Is there a reason to use int64_t over qint64?
No, just a habit.
-
@DRoscoe said in Canonical normalization of time values:
Is there a reason to use int64_t over qint64?
No, just a habit.
-
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:
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 ...
