1 /*******************************************************************************
2 * Copyright (c) 2015 École Polytechnique de Montréal
4 * All rights reserved. This program and the accompanying materials are made
5 * available under the terms of the Eclipse Public License v1.0 which
6 * accompanies this distribution, and is available at
7 * http://www.eclipse.org/legal/epl-v10.html
10 * Francis Giraldeau - Initial implementation and API
11 * Geneviève Bastien - Fixes and improvements
12 *******************************************************************************/
14 package org
.eclipse
.tracecompass
.internal
.tmf
.core
.synchronization
;
16 import java
.math
.BigDecimal
;
17 import java
.math
.MathContext
;
19 import org
.eclipse
.tracecompass
.tmf
.core
.synchronization
.ITmfTimestampTransform
;
20 import org
.eclipse
.tracecompass
.tmf
.core
.timestamp
.ITmfTimestamp
;
21 import org
.eclipse
.tracecompass
.tmf
.core
.timestamp
.TmfTimestamp
;
23 import com
.google
.common
.hash
.HashFunction
;
24 import com
.google
.common
.hash
.Hashing
;
27 * Fast linear timestamp transform.
29 * Reduce the use of BigDecimal for an interval of time where the transform can
30 * be computed only with integer math. By rearranging the linear equation
32 * f(t) = fAlpha * t + fBeta
36 * f(t) = (fAlphaLong * (t - ts)) / m + fBeta + c
38 * where fAlphaLong = fAlpha * m, and c is the constant part of the slope
41 * The slope applies to a relative time reference instead of absolute timestamp
42 * from epoch. The constant part of the slope for the interval is added to beta.
43 * It reduces the width of slope and timestamp to 32-bit integers, and the
44 * result fits a 64-bit value. Using standard integer arithmetic yield speedup
45 * compared to BigDecimal, while preserving precision. Depending of rounding,
46 * there may be a slight difference of +/- 3ns between the value computed by the
47 * fast transform compared to BigDecimal. The timestamps produced are indepotent
48 * (transforming the same timestamp will always produce the same result), and
49 * the timestamps are monotonic.
51 * The number of bits available for the cache range is variable. The variable
52 * alphaLong must be a 32-bit value. We reserve 30-bit for the decimal part to
53 * reach the nanosecond precision. If the slope is greater than 1.0, the shift
54 * is reduced to avoid overflow. It reduces the useful cache range, but the
55 * result is correct even for large (1e9) slope.
57 * @author Francis Giraldeau <francis.giraldeau@gmail.com>
60 public class TmfTimestampTransformLinearFast
implements ITmfTimestampTransformInvertible
{
62 private static final long serialVersionUID
= 2398540405078949740L;
64 private static final int INTEGER_BITS
= 32;
65 private static final int DECIMAL_BITS
= 30;
66 private static final HashFunction HASHER
= Hashing
.goodFastHash(32);
67 private static final MathContext MC
= MathContext
.DECIMAL128
;
69 private final BigDecimal fAlpha
;
70 private final BigDecimal fBeta
;
71 private final long fAlphaLong
;
72 private final long fDeltaMax
;
73 private final int fDeltaBits
;
74 private final int fHashCode
;
78 private transient long fRangeStart
;
79 private transient long fScaleMiss
;
80 private transient long fScaleHit
;
83 * Default constructor, equivalent to the identity.
85 public TmfTimestampTransformLinearFast() {
86 this(BigDecimal
.ONE
, BigDecimal
.ZERO
);
90 * Constructor with alpha and beta
93 * The slope of the linear transform
95 * The initial offset of the linear transform
97 public TmfTimestampTransformLinearFast(final double alpha
, final double beta
) {
98 this(BigDecimal
.valueOf(alpha
), BigDecimal
.valueOf(beta
));
102 * Constructor with alpha and beta as BigDecimal
105 * The slope of the linear transform (must be in the range
108 * The initial offset of the linear transform
110 public TmfTimestampTransformLinearFast(final BigDecimal alpha
, final BigDecimal beta
) {
112 * Validate the slope range:
114 * - Negative slope means timestamp goes backward wrt another computer,
115 * and this would violate the basic laws of physics.
117 * - A slope smaller than 1e-9 means the transform result will always be
118 * truncated to zero nanosecond.
120 * - A slope larger than Integer.MAX_VALUE is too large for the
123 * Therefore, a valid slope must be in the range [1e-9, 1e9]
125 if (alpha
.compareTo(BigDecimal
.valueOf(1e-9)) < 0 ||
126 alpha
.compareTo(BigDecimal
.valueOf(1e9
)) > 0) {
127 throw new IllegalArgumentException("The slope alpha must in the range [1e-9, 1e9]"); //$NON-NLS-1$
133 * The result of (fAlphaLong * delta) must be at most 64-bit value.
134 * Below, we compute the number of bits usable to represent the delta.
135 * Small fAlpha (close to one) have greater range left for delta (at
136 * most 30-bit). For large fAlpha, we reduce the delta range. If fAlpha
137 * is close to ~1e9, then the delta size will be zero, effectively
138 * recomputing the result using the BigDecimal for each transform.
140 * Long.numberOfLeadingZeros(fAlpha.longValue()) returns the number of
141 * zero bits of the integer part of the slope. Then, fIntegerBits is
142 * subtracted, which returns the number of bits usable for delta. This
143 * value is bounded in the interval of [0, 30], because the delta can't
144 * be negative, and we handle at most nanosecond precision, or 2^30. One
145 * bit for each operand is reserved for the sign (Java enforce signed
146 * arithmetics), such that
148 * bitsof(fDeltaBits) + bitsof(fAlphaLong) = 62 + 2 = 64
150 int width
= Long
.numberOfLeadingZeros(fAlpha
.longValue()) - INTEGER_BITS
;
151 fDeltaBits
= Math
.max(Math
.min(width
, DECIMAL_BITS
), 0);
152 fDeltaMax
= 1 << fDeltaBits
;
153 fAlphaLong
= fAlpha
.multiply(BigDecimal
.valueOf(fDeltaMax
), MC
).longValue();
158 fHashCode
= HASHER
.newHasher()
159 .putDouble(fAlpha
.doubleValue())
160 .putDouble(fBeta
.doubleValue())
166 //-------------------------------------------------------------------------
167 // Main timestamp computation
168 //-------------------------------------------------------------------------
171 public ITmfTimestamp
transform(ITmfTimestamp timestamp
) {
172 return TmfTimestamp
.create(transform(timestamp
.getValue()), timestamp
.getScale());
176 public long transform(long timestamp
) {
177 long delta
= timestamp
- fRangeStart
;
178 if (delta
>= fDeltaMax
|| delta
< 0) {
180 * Rescale if we exceed the safe range.
182 * If the same timestamp is transform with two different fStart
183 * reference, they may not produce the same result. To avoid this
184 * problem, align fStart on a deterministic boundary.
186 * TODO: use exact math arithmetic to detect overflow when switching to Java 8
188 fRangeStart
= timestamp
- (timestamp
% fDeltaMax
);
189 fOffset
= BigDecimal
.valueOf(fRangeStart
).multiply(fAlpha
, MC
).add(fBeta
, MC
).longValue();
190 delta
= Math
.abs(timestamp
- fRangeStart
);
195 return ((fAlphaLong
* delta
) >> fDeltaBits
) + fOffset
;
198 //-------------------------------------------------------------------------
199 // Transform composition
200 //-------------------------------------------------------------------------
203 public ITmfTimestampTransform
composeWith(ITmfTimestampTransform composeWith
) {
204 if (composeWith
.equals(TmfTimestampTransform
.IDENTITY
)) {
205 /* If composing with identity, just return this */
207 } else if (composeWith
instanceof TmfTimestampTransformLinearFast
) {
208 /* If composeWith is a linear transform, add the two together */
209 TmfTimestampTransformLinearFast ttl
= (TmfTimestampTransformLinearFast
) composeWith
;
210 BigDecimal newAlpha
= fAlpha
.multiply(ttl
.getAlpha(), MC
);
211 BigDecimal newBeta
= fAlpha
.multiply(ttl
.getBeta(), MC
).add(fBeta
);
212 /* Don't use the factory to make sure any further composition will
213 * be performed on the same object type */
214 return new TmfTimestampTransformLinearFast(newAlpha
, newBeta
);
217 * We do not know what to do with this kind of transform, just
225 public ITmfTimestampTransform
inverse() {
226 return new TmfTimestampTransformLinearFast(BigDecimal
.ONE
.divide(fAlpha
, MC
),
227 BigDecimal
.valueOf(-1).multiply(fBeta
).divide(fAlpha
, MC
));
230 //-------------------------------------------------------------------------
231 // Getters and utility methods
232 //-------------------------------------------------------------------------
235 * A cache miss occurs when the timestamp is out of the range for integer
236 * computation, and therefore requires using BigDecimal for re-scaling.
238 * @return number of misses
240 public long getCacheMisses() {
245 * A scale hit occurs if the timestamp is in the range for fast transform.
247 * @return number of hits
249 public long getCacheHits() {
254 * Reset scale misses to zero
256 public void resetScaleStats() {
262 * @return the slope alpha
264 public BigDecimal
getAlpha() {
269 * @return the offset beta
271 public BigDecimal
getBeta() {
276 * The value delta max is the timestamp range where integer arithmetic is
279 * @return the maximum delta
281 public long getDeltaMax() {
286 public String
toString() {
287 return String
.format("%s [ slope = %s, offset = %s ]", //$NON-NLS-1$
288 getClass().getSimpleName(),
294 public boolean equals(Object obj
) {
298 if (obj
instanceof TmfTimestampTransformLinearFast
) {
299 TmfTimestampTransformLinearFast other
= (TmfTimestampTransformLinearFast
) obj
;
300 return this.getAlpha().equals(other
.getAlpha()) &&
301 this.getBeta().equals(other
.getBeta());
307 public int hashCode() {