Commit | Line | Data |
---|---|---|
5745c0a3 FG |
1 | /******************************************************************************* |
2 | * Copyright (c) 2015 École Polytechnique de Montréal | |
3 | * | |
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 | |
8 | * | |
9 | * Contributors: | |
10 | * Francis Giraldeau - Initial implementation and API | |
11 | * Geneviève Bastien - Fixes and improvements | |
12 | *******************************************************************************/ | |
13 | ||
14 | package org.eclipse.tracecompass.internal.tmf.core.synchronization; | |
15 | ||
c338f3eb GB |
16 | import java.io.IOException; |
17 | import java.io.ObjectInputStream; | |
5745c0a3 FG |
18 | import java.math.BigDecimal; |
19 | import java.math.MathContext; | |
20 | ||
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; | |
24 | ||
25 | import com.google.common.hash.HashFunction; | |
26 | import com.google.common.hash.Hashing; | |
27 | ||
28 | /** | |
29 | * Fast linear timestamp transform. | |
30 | * | |
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 | |
33 | * | |
34 | * f(t) = fAlpha * t + fBeta | |
35 | * | |
36 | * to | |
37 | * | |
38 | * f(t) = (fAlphaLong * (t - ts)) / m + fBeta + c | |
39 | * | |
40 | * where fAlphaLong = fAlpha * m, and c is the constant part of the slope | |
41 | * product. | |
42 | * | |
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. | |
52 | * | |
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. | |
58 | * | |
59 | * @author Francis Giraldeau <francis.giraldeau@gmail.com> | |
60 | * | |
61 | */ | |
62 | public class TmfTimestampTransformLinearFast implements ITmfTimestampTransformInvertible { | |
63 | ||
64 | private static final long serialVersionUID = 2398540405078949740L; | |
65 | ||
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; | |
70 | ||
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; | |
77 | ||
c338f3eb | 78 | private transient long fOffset; |
5745c0a3 FG |
79 | private transient long fRangeStart; |
80 | private transient long fScaleMiss; | |
81 | private transient long fScaleHit; | |
82 | ||
83 | /** | |
84 | * Default constructor, equivalent to the identity. | |
85 | */ | |
86 | public TmfTimestampTransformLinearFast() { | |
87 | this(BigDecimal.ONE, BigDecimal.ZERO); | |
88 | } | |
89 | ||
90 | /** | |
91 | * Constructor with alpha and beta | |
92 | * | |
93 | * @param alpha | |
94 | * The slope of the linear transform | |
95 | * @param beta | |
96 | * The initial offset of the linear transform | |
97 | */ | |
98 | public TmfTimestampTransformLinearFast(final double alpha, final double beta) { | |
99 | this(BigDecimal.valueOf(alpha), BigDecimal.valueOf(beta)); | |
100 | } | |
101 | ||
102 | /** | |
103 | * Constructor with alpha and beta as BigDecimal | |
104 | * | |
105 | * @param alpha | |
106 | * The slope of the linear transform (must be in the range | |
107 | * [1e-9, 1e9] | |
108 | * @param beta | |
109 | * The initial offset of the linear transform | |
110 | */ | |
111 | public TmfTimestampTransformLinearFast(final BigDecimal alpha, final BigDecimal beta) { | |
112 | /* | |
113 | * Validate the slope range: | |
114 | * | |
115 | * - Negative slope means timestamp goes backward wrt another computer, | |
116 | * and this would violate the basic laws of physics. | |
117 | * | |
118 | * - A slope smaller than 1e-9 means the transform result will always be | |
119 | * truncated to zero nanosecond. | |
120 | * | |
121 | * - A slope larger than Integer.MAX_VALUE is too large for the | |
122 | * nanosecond scale. | |
123 | * | |
124 | * Therefore, a valid slope must be in the range [1e-9, 1e9] | |
125 | */ | |
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$ | |
129 | } | |
130 | fAlpha = alpha; | |
131 | fBeta = beta; | |
132 | ||
133 | /* | |
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. | |
140 | * | |
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 | |
148 | * | |
149 | * bitsof(fDeltaBits) + bitsof(fAlphaLong) = 62 + 2 = 64 | |
150 | */ | |
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(); | |
c338f3eb | 155 | rescale(0); |
5745c0a3 FG |
156 | fScaleMiss = 0; |
157 | fScaleHit = 0; | |
158 | fHashCode = HASHER.newHasher() | |
159 | .putDouble(fAlpha.doubleValue()) | |
160 | .putDouble(fBeta.doubleValue()) | |
161 | .putLong(fAlphaLong) | |
162 | .hash() | |
163 | .asInt(); | |
164 | } | |
165 | ||
166 | //------------------------------------------------------------------------- | |
167 | // Main timestamp computation | |
168 | //------------------------------------------------------------------------- | |
169 | ||
170 | @Override | |
171 | public ITmfTimestamp transform(ITmfTimestamp timestamp) { | |
b2c971ec | 172 | return TmfTimestamp.create(transform(timestamp.getValue()), timestamp.getScale()); |
5745c0a3 FG |
173 | } |
174 | ||
175 | @Override | |
176 | public long transform(long timestamp) { | |
177 | long delta = timestamp - fRangeStart; | |
178 | if (delta >= fDeltaMax || delta < 0) { | |
179 | /* | |
180 | * Rescale if we exceed the safe range. | |
181 | * | |
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. | |
185 | * | |
186 | * TODO: use exact math arithmetic to detect overflow when switching to Java 8 | |
187 | */ | |
c338f3eb | 188 | rescale(timestamp); |
5745c0a3 FG |
189 | delta = Math.abs(timestamp - fRangeStart); |
190 | fScaleMiss++; | |
191 | } else { | |
192 | fScaleHit++; | |
193 | } | |
194 | return ((fAlphaLong * delta) >> fDeltaBits) + fOffset; | |
195 | } | |
196 | ||
c338f3eb GB |
197 | private void rescale(long timestamp) { |
198 | fRangeStart = timestamp - (timestamp % fDeltaMax); | |
199 | fOffset = BigDecimal.valueOf(fRangeStart).multiply(fAlpha, MC).add(fBeta, MC).longValue(); | |
200 | } | |
201 | ||
5745c0a3 FG |
202 | //------------------------------------------------------------------------- |
203 | // Transform composition | |
204 | //------------------------------------------------------------------------- | |
205 | ||
206 | @Override | |
207 | public ITmfTimestampTransform composeWith(ITmfTimestampTransform composeWith) { | |
208 | if (composeWith.equals(TmfTimestampTransform.IDENTITY)) { | |
209 | /* If composing with identity, just return this */ | |
210 | 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); | |
219 | } else { | |
220 | /* | |
221 | * We do not know what to do with this kind of transform, just | |
222 | * return this | |
223 | */ | |
224 | return this; | |
225 | } | |
226 | } | |
227 | ||
228 | @Override | |
229 | public ITmfTimestampTransform inverse() { | |
230 | return new TmfTimestampTransformLinearFast(BigDecimal.ONE.divide(fAlpha, MC), | |
231 | BigDecimal.valueOf(-1).multiply(fBeta).divide(fAlpha, MC)); | |
232 | } | |
233 | ||
234 | //------------------------------------------------------------------------- | |
235 | // Getters and utility methods | |
236 | //------------------------------------------------------------------------- | |
237 | ||
238 | /** | |
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. | |
241 | * | |
242 | * @return number of misses | |
243 | */ | |
244 | public long getCacheMisses() { | |
245 | return fScaleMiss; | |
246 | } | |
247 | ||
248 | /** | |
249 | * A scale hit occurs if the timestamp is in the range for fast transform. | |
250 | * | |
251 | * @return number of hits | |
252 | */ | |
253 | public long getCacheHits() { | |
254 | return fScaleHit; | |
255 | } | |
256 | ||
257 | /** | |
258 | * Reset scale misses to zero | |
259 | */ | |
260 | public void resetScaleStats() { | |
261 | fScaleMiss = 0; | |
262 | fScaleHit = 0; | |
263 | } | |
264 | ||
265 | /** | |
266 | * @return the slope alpha | |
267 | */ | |
268 | public BigDecimal getAlpha() { | |
269 | return fAlpha; | |
270 | } | |
271 | ||
272 | /** | |
273 | * @return the offset beta | |
274 | */ | |
275 | public BigDecimal getBeta() { | |
276 | return fBeta; | |
277 | } | |
278 | ||
279 | /** | |
280 | * The value delta max is the timestamp range where integer arithmetic is | |
281 | * used. | |
282 | * | |
283 | * @return the maximum delta | |
284 | */ | |
285 | public long getDeltaMax() { | |
286 | return fDeltaMax; | |
287 | } | |
288 | ||
289 | @Override | |
290 | public String toString() { | |
291 | return String.format("%s [ slope = %s, offset = %s ]", //$NON-NLS-1$ | |
292 | getClass().getSimpleName(), | |
293 | fAlpha.toString(), | |
294 | fBeta.toString()); | |
295 | } | |
296 | ||
297 | @Override | |
298 | public boolean equals(Object obj) { | |
299 | if (this == obj) { | |
300 | return true; | |
301 | } | |
302 | if (obj instanceof TmfTimestampTransformLinearFast) { | |
303 | TmfTimestampTransformLinearFast other = (TmfTimestampTransformLinearFast) obj; | |
304 | return this.getAlpha().equals(other.getAlpha()) && | |
305 | this.getBeta().equals(other.getBeta()); | |
306 | } | |
307 | return false; | |
308 | } | |
309 | ||
310 | @Override | |
311 | public int hashCode() { | |
312 | return fHashCode; | |
313 | } | |
314 | ||
c338f3eb GB |
315 | // Deserialization method, make sure there is a first scaling |
316 | private void readObject(ObjectInputStream stream) | |
317 | throws IOException, ClassNotFoundException { | |
318 | stream.defaultReadObject(); | |
319 | ||
320 | rescale(0); | |
321 | } | |
322 | ||
5745c0a3 | 323 | } |