| 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 | |
| 16 | import java.math.BigDecimal; |
| 17 | import java.math.MathContext; |
| 18 | |
| 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; |
| 22 | |
| 23 | import com.google.common.hash.HashFunction; |
| 24 | import com.google.common.hash.Hashing; |
| 25 | |
| 26 | /** |
| 27 | * Fast linear timestamp transform. |
| 28 | * |
| 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 |
| 31 | * |
| 32 | * f(t) = fAlpha * t + fBeta |
| 33 | * |
| 34 | * to |
| 35 | * |
| 36 | * f(t) = (fAlphaLong * (t - ts)) / m + fBeta + c |
| 37 | * |
| 38 | * where fAlphaLong = fAlpha * m, and c is the constant part of the slope |
| 39 | * product. |
| 40 | * |
| 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. |
| 50 | * |
| 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. |
| 56 | * |
| 57 | * @author Francis Giraldeau <francis.giraldeau@gmail.com> |
| 58 | * |
| 59 | */ |
| 60 | public class TmfTimestampTransformLinearFast implements ITmfTimestampTransformInvertible { |
| 61 | |
| 62 | private static final long serialVersionUID = 2398540405078949740L; |
| 63 | |
| 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; |
| 68 | |
| 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; |
| 75 | |
| 76 | private long fOffset; |
| 77 | |
| 78 | private transient long fRangeStart; |
| 79 | private transient long fScaleMiss; |
| 80 | private transient long fScaleHit; |
| 81 | |
| 82 | /** |
| 83 | * Default constructor, equivalent to the identity. |
| 84 | */ |
| 85 | public TmfTimestampTransformLinearFast() { |
| 86 | this(BigDecimal.ONE, BigDecimal.ZERO); |
| 87 | } |
| 88 | |
| 89 | /** |
| 90 | * Constructor with alpha and beta |
| 91 | * |
| 92 | * @param alpha |
| 93 | * The slope of the linear transform |
| 94 | * @param beta |
| 95 | * The initial offset of the linear transform |
| 96 | */ |
| 97 | public TmfTimestampTransformLinearFast(final double alpha, final double beta) { |
| 98 | this(BigDecimal.valueOf(alpha), BigDecimal.valueOf(beta)); |
| 99 | } |
| 100 | |
| 101 | /** |
| 102 | * Constructor with alpha and beta as BigDecimal |
| 103 | * |
| 104 | * @param alpha |
| 105 | * The slope of the linear transform (must be in the range |
| 106 | * [1e-9, 1e9] |
| 107 | * @param beta |
| 108 | * The initial offset of the linear transform |
| 109 | */ |
| 110 | public TmfTimestampTransformLinearFast(final BigDecimal alpha, final BigDecimal beta) { |
| 111 | /* |
| 112 | * Validate the slope range: |
| 113 | * |
| 114 | * - Negative slope means timestamp goes backward wrt another computer, |
| 115 | * and this would violate the basic laws of physics. |
| 116 | * |
| 117 | * - A slope smaller than 1e-9 means the transform result will always be |
| 118 | * truncated to zero nanosecond. |
| 119 | * |
| 120 | * - A slope larger than Integer.MAX_VALUE is too large for the |
| 121 | * nanosecond scale. |
| 122 | * |
| 123 | * Therefore, a valid slope must be in the range [1e-9, 1e9] |
| 124 | */ |
| 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$ |
| 128 | } |
| 129 | fAlpha = alpha; |
| 130 | fBeta = beta; |
| 131 | |
| 132 | /* |
| 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. |
| 139 | * |
| 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 |
| 147 | * |
| 148 | * bitsof(fDeltaBits) + bitsof(fAlphaLong) = 62 + 2 = 64 |
| 149 | */ |
| 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(); |
| 154 | fRangeStart = 0L; |
| 155 | fOffset = 0L; |
| 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) { |
| 172 | return TmfTimestamp.create(transform(timestamp.getValue()), timestamp.getScale()); |
| 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 | */ |
| 188 | fRangeStart = timestamp - (timestamp % fDeltaMax); |
| 189 | fOffset = BigDecimal.valueOf(fRangeStart).multiply(fAlpha, MC).add(fBeta, MC).longValue(); |
| 190 | delta = Math.abs(timestamp - fRangeStart); |
| 191 | fScaleMiss++; |
| 192 | } else { |
| 193 | fScaleHit++; |
| 194 | } |
| 195 | return ((fAlphaLong * delta) >> fDeltaBits) + fOffset; |
| 196 | } |
| 197 | |
| 198 | //------------------------------------------------------------------------- |
| 199 | // Transform composition |
| 200 | //------------------------------------------------------------------------- |
| 201 | |
| 202 | @Override |
| 203 | public ITmfTimestampTransform composeWith(ITmfTimestampTransform composeWith) { |
| 204 | if (composeWith.equals(TmfTimestampTransform.IDENTITY)) { |
| 205 | /* If composing with identity, just return this */ |
| 206 | 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); |
| 215 | } else { |
| 216 | /* |
| 217 | * We do not know what to do with this kind of transform, just |
| 218 | * return this |
| 219 | */ |
| 220 | return this; |
| 221 | } |
| 222 | } |
| 223 | |
| 224 | @Override |
| 225 | public ITmfTimestampTransform inverse() { |
| 226 | return new TmfTimestampTransformLinearFast(BigDecimal.ONE.divide(fAlpha, MC), |
| 227 | BigDecimal.valueOf(-1).multiply(fBeta).divide(fAlpha, MC)); |
| 228 | } |
| 229 | |
| 230 | //------------------------------------------------------------------------- |
| 231 | // Getters and utility methods |
| 232 | //------------------------------------------------------------------------- |
| 233 | |
| 234 | /** |
| 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. |
| 237 | * |
| 238 | * @return number of misses |
| 239 | */ |
| 240 | public long getCacheMisses() { |
| 241 | return fScaleMiss; |
| 242 | } |
| 243 | |
| 244 | /** |
| 245 | * A scale hit occurs if the timestamp is in the range for fast transform. |
| 246 | * |
| 247 | * @return number of hits |
| 248 | */ |
| 249 | public long getCacheHits() { |
| 250 | return fScaleHit; |
| 251 | } |
| 252 | |
| 253 | /** |
| 254 | * Reset scale misses to zero |
| 255 | */ |
| 256 | public void resetScaleStats() { |
| 257 | fScaleMiss = 0; |
| 258 | fScaleHit = 0; |
| 259 | } |
| 260 | |
| 261 | /** |
| 262 | * @return the slope alpha |
| 263 | */ |
| 264 | public BigDecimal getAlpha() { |
| 265 | return fAlpha; |
| 266 | } |
| 267 | |
| 268 | /** |
| 269 | * @return the offset beta |
| 270 | */ |
| 271 | public BigDecimal getBeta() { |
| 272 | return fBeta; |
| 273 | } |
| 274 | |
| 275 | /** |
| 276 | * The value delta max is the timestamp range where integer arithmetic is |
| 277 | * used. |
| 278 | * |
| 279 | * @return the maximum delta |
| 280 | */ |
| 281 | public long getDeltaMax() { |
| 282 | return fDeltaMax; |
| 283 | } |
| 284 | |
| 285 | @Override |
| 286 | public String toString() { |
| 287 | return String.format("%s [ slope = %s, offset = %s ]", //$NON-NLS-1$ |
| 288 | getClass().getSimpleName(), |
| 289 | fAlpha.toString(), |
| 290 | fBeta.toString()); |
| 291 | } |
| 292 | |
| 293 | @Override |
| 294 | public boolean equals(Object obj) { |
| 295 | if (this == obj) { |
| 296 | return true; |
| 297 | } |
| 298 | if (obj instanceof TmfTimestampTransformLinearFast) { |
| 299 | TmfTimestampTransformLinearFast other = (TmfTimestampTransformLinearFast) obj; |
| 300 | return this.getAlpha().equals(other.getAlpha()) && |
| 301 | this.getBeta().equals(other.getBeta()); |
| 302 | } |
| 303 | return false; |
| 304 | } |
| 305 | |
| 306 | @Override |
| 307 | public int hashCode() { |
| 308 | return fHashCode; |
| 309 | } |
| 310 | |
| 311 | } |