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
.io
.IOException
;
17 import java
.io
.ObjectInputStream
;
18 import java
.math
.BigDecimal
;
19 import java
.math
.MathContext
;
21 import org
.eclipse
.tracecompass
.tmf
.core
.synchronization
.ITmfTimestampTransform
;
22 import org
.eclipse
.tracecompass
.tmf
.core
.timestamp
.ITmfTimestamp
;
23 import org
.eclipse
.tracecompass
.tmf
.core
.timestamp
.TmfTimestamp
;
25 import com
.google
.common
.hash
.HashFunction
;
26 import com
.google
.common
.hash
.Hashing
;
29 * Fast linear timestamp transform.
31 * Reduce the use of BigDecimal for an interval of time where the transform can
32 * be computed only with integer math. By rearranging the linear equation
34 * f(t) = fAlpha * t + fBeta
38 * f(t) = (fAlphaLong * (t - ts)) / m + fBeta + c
40 * where fAlphaLong = fAlpha * m, and c is the constant part of the slope
43 * The slope applies to a relative time reference instead of absolute timestamp
44 * from epoch. The constant part of the slope for the interval is added to beta.
45 * It reduces the width of slope and timestamp to 32-bit integers, and the
46 * result fits a 64-bit value. Using standard integer arithmetic yield speedup
47 * compared to BigDecimal, while preserving precision. Depending of rounding,
48 * there may be a slight difference of +/- 3ns between the value computed by the
49 * fast transform compared to BigDecimal. The timestamps produced are indepotent
50 * (transforming the same timestamp will always produce the same result), and
51 * the timestamps are monotonic.
53 * The number of bits available for the cache range is variable. The variable
54 * alphaLong must be a 32-bit value. We reserve 30-bit for the decimal part to
55 * reach the nanosecond precision. If the slope is greater than 1.0, the shift
56 * is reduced to avoid overflow. It reduces the useful cache range, but the
57 * result is correct even for large (1e9) slope.
59 * @author Francis Giraldeau <francis.giraldeau@gmail.com>
62 public class TmfTimestampTransformLinearFast
implements ITmfTimestampTransformInvertible
{
64 private static final long serialVersionUID
= 2398540405078949740L;
66 private static final int INTEGER_BITS
= 32;
67 private static final int DECIMAL_BITS
= 30;
68 private static final HashFunction HASHER
= Hashing
.goodFastHash(32);
69 private static final MathContext MC
= MathContext
.DECIMAL128
;
71 private final BigDecimal fAlpha
;
72 private final BigDecimal fBeta
;
73 private final long fAlphaLong
;
74 private final long fDeltaMax
;
75 private final int fDeltaBits
;
76 private final int fHashCode
;
78 private transient long fOffset
;
79 private transient long fRangeStart
;
80 private transient long fScaleMiss
;
81 private transient long fScaleHit
;
84 * Default constructor, equivalent to the identity.
86 public TmfTimestampTransformLinearFast() {
87 this(BigDecimal
.ONE
, BigDecimal
.ZERO
);
91 * Constructor with alpha and beta
94 * The slope of the linear transform
96 * The initial offset of the linear transform
98 public TmfTimestampTransformLinearFast(final double alpha
, final double beta
) {
99 this(BigDecimal
.valueOf(alpha
), BigDecimal
.valueOf(beta
));
103 * Constructor with alpha and beta as BigDecimal
106 * The slope of the linear transform (must be in the range
109 * The initial offset of the linear transform
111 public TmfTimestampTransformLinearFast(final BigDecimal alpha
, final BigDecimal beta
) {
113 * Validate the slope range:
115 * - Negative slope means timestamp goes backward wrt another computer,
116 * and this would violate the basic laws of physics.
118 * - A slope smaller than 1e-9 means the transform result will always be
119 * truncated to zero nanosecond.
121 * - A slope larger than Integer.MAX_VALUE is too large for the
124 * Therefore, a valid slope must be in the range [1e-9, 1e9]
126 if (alpha
.compareTo(BigDecimal
.valueOf(1e-9)) < 0 ||
127 alpha
.compareTo(BigDecimal
.valueOf(1e9
)) > 0) {
128 throw new IllegalArgumentException("The slope alpha must in the range [1e-9, 1e9]"); //$NON-NLS-1$
134 * The result of (fAlphaLong * delta) must be at most 64-bit value.
135 * Below, we compute the number of bits usable to represent the delta.
136 * Small fAlpha (close to one) have greater range left for delta (at
137 * most 30-bit). For large fAlpha, we reduce the delta range. If fAlpha
138 * is close to ~1e9, then the delta size will be zero, effectively
139 * recomputing the result using the BigDecimal for each transform.
141 * Long.numberOfLeadingZeros(fAlpha.longValue()) returns the number of
142 * zero bits of the integer part of the slope. Then, fIntegerBits is
143 * subtracted, which returns the number of bits usable for delta. This
144 * value is bounded in the interval of [0, 30], because the delta can't
145 * be negative, and we handle at most nanosecond precision, or 2^30. One
146 * bit for each operand is reserved for the sign (Java enforce signed
147 * arithmetics), such that
149 * bitsof(fDeltaBits) + bitsof(fAlphaLong) = 62 + 2 = 64
151 int width
= Long
.numberOfLeadingZeros(fAlpha
.longValue()) - INTEGER_BITS
;
152 fDeltaBits
= Math
.max(Math
.min(width
, DECIMAL_BITS
), 0);
153 fDeltaMax
= 1 << fDeltaBits
;
154 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
189 delta
= Math
.abs(timestamp
- fRangeStart
);
194 return ((fAlphaLong
* delta
) >> fDeltaBits
) + fOffset
;
197 private void rescale(long timestamp
) {
198 fRangeStart
= timestamp
- (timestamp
% fDeltaMax
);
199 fOffset
= BigDecimal
.valueOf(fRangeStart
).multiply(fAlpha
, MC
).add(fBeta
, MC
).longValue();
202 //-------------------------------------------------------------------------
203 // Transform composition
204 //-------------------------------------------------------------------------
207 public ITmfTimestampTransform
composeWith(ITmfTimestampTransform composeWith
) {
208 if (composeWith
.equals(TmfTimestampTransform
.IDENTITY
)) {
209 /* If composing with identity, just return this */
211 } else if (composeWith
instanceof TmfTimestampTransformLinearFast
) {
212 /* If composeWith is a linear transform, add the two together */
213 TmfTimestampTransformLinearFast ttl
= (TmfTimestampTransformLinearFast
) composeWith
;
214 BigDecimal newAlpha
= fAlpha
.multiply(ttl
.getAlpha(), MC
);
215 BigDecimal newBeta
= fAlpha
.multiply(ttl
.getBeta(), MC
).add(fBeta
);
216 /* Don't use the factory to make sure any further composition will
217 * be performed on the same object type */
218 return new TmfTimestampTransformLinearFast(newAlpha
, newBeta
);
221 * We do not know what to do with this kind of transform, just
229 public ITmfTimestampTransform
inverse() {
230 return new TmfTimestampTransformLinearFast(BigDecimal
.ONE
.divide(fAlpha
, MC
),
231 BigDecimal
.valueOf(-1).multiply(fBeta
).divide(fAlpha
, MC
));
234 //-------------------------------------------------------------------------
235 // Getters and utility methods
236 //-------------------------------------------------------------------------
239 * A cache miss occurs when the timestamp is out of the range for integer
240 * computation, and therefore requires using BigDecimal for re-scaling.
242 * @return number of misses
244 public long getCacheMisses() {
249 * A scale hit occurs if the timestamp is in the range for fast transform.
251 * @return number of hits
253 public long getCacheHits() {
258 * Reset scale misses to zero
260 public void resetScaleStats() {
266 * @return the slope alpha
268 public BigDecimal
getAlpha() {
273 * @return the offset beta
275 public BigDecimal
getBeta() {
280 * The value delta max is the timestamp range where integer arithmetic is
283 * @return the maximum delta
285 public long getDeltaMax() {
290 public String
toString() {
291 return String
.format("%s [ slope = %s, offset = %s ]", //$NON-NLS-1$
292 getClass().getSimpleName(),
298 public boolean equals(Object obj
) {
302 if (obj
instanceof TmfTimestampTransformLinearFast
) {
303 TmfTimestampTransformLinearFast other
= (TmfTimestampTransformLinearFast
) obj
;
304 return this.getAlpha().equals(other
.getAlpha()) &&
305 this.getBeta().equals(other
.getBeta());
311 public int hashCode() {
315 // Deserialization method, make sure there is a first scaling
316 private void readObject(ObjectInputStream stream
)
317 throws IOException
, ClassNotFoundException
{
318 stream
.defaultReadObject();