tmf/org.eclipse.tracecompass.tmf.core/src/org/eclipse/tracecompass/internal/tmf/core/synchronization/TmfTimestampTransformLinearFast.java

   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 }