TMF: Introduce a fast linear timestamp transform
authorFrancis Giraldeau <francis.giraldeau@gmail.com>
Wed, 24 Dec 2014 18:40:22 +0000 (13:40 -0500)
committerAlexandre Montplaisir <alexmonthy@voxpopuli.im>
Tue, 13 Jan 2015 00:01:42 +0000 (19:01 -0500)
The fast timestamp transform uses standard integer arithmetic to compute the
the transform, instead of BigDecimal, yet producing monotonic timestamp within
3ns of the original function.

Test that the fast transform yields about the same results as the original
function, either forward or backward, and also verify that the cache is
effectively used.

The benchmark results are:

Transform   | time (ms)
-----------------------
original    |     17310
fast        |       256

This benchmark suggests that the fast transform is about 67 times faster than
the original transform.

Change-Id: Ifdf8e23b3e042bf1f2b0454e64a4ab4c47d408d4
Signed-off-by: Francis Giraldeau <francis.giraldeau@gmail.com>
Reviewed-on: https://git.eclipse.org/r/38770
Reviewed-by: Hudson CI
Reviewed-by: Alexandre Montplaisir <alexmonthy@voxpopuli.im>
Tested-by: Alexandre Montplaisir <alexmonthy@voxpopuli.im>
org.eclipse.tracecompass.lttng2.kernel.core.tests/src/org/eclipse/tracecompass/lttng2/kernel/core/tests/event/matchandsync/ExperimentSyncTest.java
org.eclipse.tracecompass.tmf.core.tests/perf/org/eclipse/tracecompass/tmf/core/tests/perf/synchronization/TimestampTransformBenchmark.java
org.eclipse.tracecompass.tmf.core.tests/src/org/eclipse/tracecompass/tmf/core/tests/synchronization/AllTests.java
org.eclipse.tracecompass.tmf.core.tests/src/org/eclipse/tracecompass/tmf/core/tests/synchronization/TsTransformFactoryTest.java
org.eclipse.tracecompass.tmf.core.tests/src/org/eclipse/tracecompass/tmf/core/tests/synchronization/TsTransformFastTest.java [new file with mode: 0644]
org.eclipse.tracecompass.tmf.core.tests/src/org/eclipse/tracecompass/tmf/core/tests/synchronization/TsTransformTest.java
org.eclipse.tracecompass.tmf.core/src/org/eclipse/tracecompass/internal/tmf/core/synchronization/TmfTimestampTransformLinear.java
org.eclipse.tracecompass.tmf.core/src/org/eclipse/tracecompass/internal/tmf/core/synchronization/TmfTimestampTransformLinearFast.java [new file with mode: 0644]
org.eclipse.tracecompass.tmf.core/src/org/eclipse/tracecompass/tmf/core/synchronization/ITmfTimestampTransform.java
org.eclipse.tracecompass.tmf.core/src/org/eclipse/tracecompass/tmf/core/synchronization/TimestampTransformFactory.java

index 823ad6d2c91b854fc620239f6b5fde992468dbbb..8c475e8a12f2b5acd7a2672fe51998be69dedbb0 100644 (file)
@@ -69,7 +69,7 @@ public class ExperimentSyncTest {
             trace1.setTimestampTransform(tt1);
             trace2.setTimestampTransform(tt2);
 
-            assertEquals("TmfTimestampLinear [ slope = 0.9999413783703139011056845831168394, offset = 79796507913179.33347660124688298171 ]", tt1.toString());
+            assertEquals("TmfTimestampTransformLinearFast [ slope = 0.9999413783703139011056845831168394, offset = 79796507913179.33347660124688298171 ]", tt1.toString());
             assertEquals(TimestampTransformFactory.getDefaultTransform(), tt2);
 
             assertEquals(syncAlgo.getTimestampTransform(trace1.getHostId()), trace1.getTimestampTransform());
@@ -104,8 +104,8 @@ public class ExperimentSyncTest {
             trace3.setTimestampTransform(tt3);
 
             assertEquals(TimestampTransformFactory.getDefaultTransform(), tt1);
-            assertEquals("TmfTimestampLinear [ slope = 0.9999996313017589597204633828681240, offset = 498490309972.0038068817738527724192 ]", tt2.toString());
-            assertEquals("TmfTimestampLinear [ slope = 1.000000119014882262265342419815932, offset = -166652893534.6189900382736187431134 ]", tt3.toString());
+            assertEquals("TmfTimestampTransformLinearFast [ slope = 0.9999996313017589597204633828681240, offset = 498490309972.0038068817738527724192 ]", tt2.toString());
+            assertEquals("TmfTimestampTransformLinearFast [ slope = 1.000000119014882262265342419815932, offset = -166652893534.6189900382736187431134 ]", tt3.toString());
 
         }
     }
index 4f81e6447d9bc0fd559b8075b11c35077519e920..a89276c8cc015a4604293845cfd454dd33c6f006 100644 (file)
@@ -15,8 +15,11 @@ package org.eclipse.tracecompass.tmf.core.tests.perf.synchronization;
 import org.eclipse.test.performance.Dimension;
 import org.eclipse.test.performance.Performance;
 import org.eclipse.test.performance.PerformanceMeter;
+import org.eclipse.tracecompass.internal.tmf.core.synchronization.TmfTimestampTransformLinear;
+import org.eclipse.tracecompass.internal.tmf.core.synchronization.TmfTimestampTransformLinearFast;
 import org.eclipse.tracecompass.tmf.core.synchronization.ITmfTimestampTransform;
 import org.eclipse.tracecompass.tmf.core.synchronization.TimestampTransformFactory;
+import org.junit.Ignore;
 import org.junit.Test;
 
 /**
@@ -50,6 +53,24 @@ public class TimestampTransformBenchmark {
         doTimestampTransformRun("Linear transform with larger slope and negative offset", transform, 5);
     }
 
+    /**
+     * Benchmark to compare the classic and fast timestamp transform.
+     *
+     * Ignore when running automatically, just for local benchmarks.
+     */
+    @Ignore
+    @Test
+    public void testCompareTimestampTransformPerformance() {
+        /*
+         * We call constructors directly instead of TimestampTransformFactory to
+         * create properly each transform type.
+         */
+        ITmfTimestampTransform classic = new TmfTimestampTransformLinear(Math.PI, 1234);
+        ITmfTimestampTransform fast = new TmfTimestampTransformLinearFast(Math.PI, 1234);
+        doTimestampTransformRun("Linear transform classic", classic, 5);
+        doTimestampTransformRun("Linear transform fast", fast, 5);
+    }
+
     private static void doTimestampTransformRun(String testName, ITmfTimestampTransform xform, long loopCount) {
         Performance perf = Performance.getDefault();
         PerformanceMeter pm = perf.createPerformanceMeter(TEST_ID + testName);
index 7ae1451d9f6641d91948bb401b31fbf6de6f11b7..36fef562f0ea3656a6398e975f6ae0b1f2eae531 100644 (file)
@@ -22,6 +22,8 @@ import org.junit.runners.Suite;
 @Suite.SuiteClasses({ TsTransformTest.class,
         SyncTest.class,
         TsTransformFactoryTest.class,
+        TsTransformTest.class,
+        TsTransformFastTest.class,
         TimeOffsetTest.class })
 public class AllTests {
 
index 183903461e6a4cd0a07bfed2daf9feaabf6bc741..c613378dc7fbb6ec9e006327162b6e2dc2af6381 100644 (file)
@@ -106,8 +106,8 @@ public class TsTransformFactoryTest {
      */
     @Test
     public void testToString() {
-        final String expectedLinear = "TmfTimestampLinear [ slope = 314.0, offset = 0.0 ]";
-        final String expectedLinearBigDec = "TmfTimestampLinear [ slope = 314, offset = 0 ]";
+        final String expectedLinear = "TmfTimestampTransformLinearFast [ slope = 314.0, offset = 0.0 ]";
+        final String expectedLinearBigDec = "TmfTimestampTransformLinearFast [ slope = 314, offset = 0 ]";
         final String expectedOffset = "TmfConstantTransform [ offset = 314 ]";
         final String expectedIdentity = "TmfTimestampTransform [ IDENTITY ]";
         final String expectedOffset100 = "TmfConstantTransform [ offset = 100 ]";
diff --git a/org.eclipse.tracecompass.tmf.core.tests/src/org/eclipse/tracecompass/tmf/core/tests/synchronization/TsTransformFastTest.java b/org.eclipse.tracecompass.tmf.core.tests/src/org/eclipse/tracecompass/tmf/core/tests/synchronization/TsTransformFastTest.java
new file mode 100644 (file)
index 0000000..8e894e2
--- /dev/null
@@ -0,0 +1,167 @@
+/*******************************************************************************
+ * Copyright (c) 2015 École Polytechnique de Montréal
+ *
+ * All rights reserved. This program and the accompanying materials are made
+ * available under the terms of the Eclipse Public License v1.0 which
+ * accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ *
+ * Contributors:
+ *   Francis Giraldeau - Initial implementation and API
+ *   Geneviève Bastien - Fixes and improvements
+ *******************************************************************************/
+
+package org.eclipse.tracecompass.tmf.core.tests.synchronization;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertNotNull;
+import static org.junit.Assert.assertTrue;
+
+import org.eclipse.tracecompass.internal.tmf.core.synchronization.TmfTimestampTransformLinear;
+import org.eclipse.tracecompass.internal.tmf.core.synchronization.TmfTimestampTransformLinearFast;
+import org.eclipse.tracecompass.tmf.core.synchronization.ITmfTimestampTransform;
+import org.junit.Test;
+
+/**
+ * Tests for {@link TmfTimestampTransformLinearFast}
+ *
+ * @author Geneviève Bastien
+ */
+public class TsTransformFastTest {
+
+    private static final long ts = 1361657893526374091L;
+
+    /**
+     * Test whether the fast linear transform always yields the same value for
+     * the same timestamp
+     */
+    @Test
+    public void testFLTRepeatability() {
+        TmfTimestampTransformLinearFast fast = new TmfTimestampTransformLinearFast(Math.PI, 0);
+        // Access fDeltaMax to compute the cache range boundaries
+        long deltaMax = fast.getDeltaMax();
+        // Initialize the transform
+        long timestamp = ts - (ts % deltaMax);
+        fast.transform(timestamp);
+        long tsMiss = timestamp + deltaMax;
+        long tsNoMiss = timestamp + deltaMax - 1;
+
+        // Get the transformed value to a timestamp without cache miss
+        long tsTNoMiss = fast.transform(tsNoMiss);
+        assertEquals(1, fast.getCacheMisses());
+
+        // Cause a cache miss
+        fast.transform(tsMiss);
+        assertEquals(2, fast.getCacheMisses());
+
+        /*
+         * Get the transformed value of the same previous timestamp after the
+         * miss
+         */
+        long tsTAfterMiss = fast.transform(tsNoMiss);
+        assertEquals(tsTNoMiss, tsTAfterMiss);
+    }
+
+    /**
+     * Test that 2 equal fast transform always give the same results for the
+     * same values
+     */
+    @Test
+    public void testFLTEquivalence() {
+        TmfTimestampTransformLinearFast fast = new TmfTimestampTransformLinearFast(Math.PI, 0);
+        TmfTimestampTransformLinearFast fast2 = new TmfTimestampTransformLinearFast(Math.PI, 0);
+
+        long deltaMax = fast.getDeltaMax();
+
+        long start = (ts - (ts % deltaMax) - 10);
+        checkTime(fast, fast2, 20, start, 1);
+    }
+
+    /**
+     * Test the precision of the fast timestamp transform compared to the
+     * original transform.
+     */
+    @Test
+    public void testFastTransformPrecision() {
+        TmfTimestampTransformLinear precise = new TmfTimestampTransformLinear(Math.PI, 0);
+        TmfTimestampTransformLinearFast fast = new TmfTimestampTransformLinearFast(Math.PI, 0);
+        int samples = 100;
+        long start = (long) Math.pow(10, 18);
+        long end = Long.MAX_VALUE;
+        int step = (int) ((end - start) / (samples * Math.PI));
+        checkTime(precise, fast, samples, start, step);
+        assertEquals(samples, fast.getCacheMisses());
+
+        // check that rescale is done only when required
+        // assumes tsBitWidth == 30
+        // test forward and backward timestamps
+        samples = 1000;
+        int[] directions = new int[] { 1, -1 };
+        for (Integer direction : directions) {
+            for (int i = 0; i <= 30; i++) {
+                fast.resetScaleStats();
+                step = (1 << i) * direction;
+                checkTime(precise, fast, samples, start, step);
+                assertTrue(String.format("samples: %d scale misses: %d",
+                        samples, fast.getCacheMisses()), samples >= fast.getCacheMisses());
+            }
+        }
+
+    }
+
+    /**
+     * Test that fast transform produces the same result for small and large slopes.
+     */
+    @Test
+    public void testFastTransformSlope() {
+        int[] dir = new int[] { 1, -1 };
+        long start = (1 << 30);
+        for (int ex = -9; ex <= 9; ex++) {
+            for (int d = 0; d < dir.length; d++) {
+                double slope = Math.pow(10.0, ex);
+                TmfTimestampTransformLinear precise = new TmfTimestampTransformLinear(slope, 0);
+                TmfTimestampTransformLinearFast fast = new TmfTimestampTransformLinearFast(slope, 0);
+                checkTime(precise, fast, 1000, start, dir[d]);
+            }
+        }
+    }
+
+    /**
+     * Check that the proper exception are raised for illegal slopes
+     */
+    @Test
+    public void testFastTransformArguments() {
+        double[] slopes = new double[] { -1.0, ((double)Integer.MAX_VALUE) + 1, 1e-10 };
+        for (double slope: slopes) {
+            Exception exception = null;
+            try {
+                new TmfTimestampTransformLinearFast(slope, 0.0);
+            } catch (IllegalArgumentException e) {
+                exception = e;
+            }
+            assertNotNull(exception);
+        }
+    }
+
+    private static void checkTime(ITmfTimestampTransform precise, ITmfTimestampTransform fast,
+            int samples, long start, long step) {
+        long prev = 0;
+        for (int i = 0; i < samples; i++) {
+            long time = start + i * step;
+            long exp = precise.transform(time);
+            long act = fast.transform(time);
+            long err = act - exp;
+            // allow only two ns of error
+            assertTrue("[" + err + "]", Math.abs(err) < 3);
+            if (i > 0) {
+                if (step > 0) {
+                    assertTrue("monotonic error" + act + " " + prev, act >= prev);
+                } else if (step < 0) {
+                    assertTrue("monotonic ", act <= prev);
+                }
+            }
+            prev = act;
+        }
+    }
+
+}
index 5bb800112d482267343828de33051845c8cd1ff7..c8e3d193f2599cd3e8f4fb9dd5601e8cf1d1ec06 100644 (file)
@@ -12,7 +12,9 @@
 
 package org.eclipse.tracecompass.tmf.core.tests.synchronization;
 
-import static org.junit.Assert.*;
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertTrue;
 
 import java.math.BigDecimal;
 import java.util.HashMap;
@@ -33,8 +35,8 @@ import org.junit.Test;
 @SuppressWarnings("nls")
 public class TsTransformTest {
 
-    private long ts = 1361657893526374091L;
-    private ITmfTimestamp oTs = new TmfTimestamp(ts);
+    private static final long ts = 1361657893526374091L;
+    private static final ITmfTimestamp oTs = new TmfTimestamp(ts);
 
     /**
      * Test the linear transform
@@ -141,4 +143,5 @@ public class TsTransformTest {
         assertEquals(312, tc1.transform(t));
 
     }
+
 }
index 8c88c29856bee7b597af52f2ee162c96a8cd0641..6618985112ce379223b1b809b8a46e2050a1d591 100644 (file)
@@ -107,7 +107,9 @@ public class TmfTimestampTransformLinear implements ITmfTimestampTransformInvert
             TmfTimestampTransformLinear ttl = (TmfTimestampTransformLinear) composeWith;
             BigDecimal newAlpha = fAlpha.multiply(ttl.fAlpha, fMc);
             BigDecimal newBeta = fAlpha.multiply(ttl.fBeta, fMc).add(fBeta);
-            return TimestampTransformFactory.createLinear(newAlpha, newBeta);
+            /* Don't use the factory to make sure any further composition will
+             * be performed on the same object type */
+            return new TmfTimestampTransformLinear(newAlpha, newBeta);
         } else {
             /*
              * We do not know what to do with this kind of transform, just
@@ -147,4 +149,17 @@ public class TmfTimestampTransformLinear implements ITmfTimestampTransformInvert
         return TimestampTransformFactory.createLinear(BigDecimal.ONE.divide(fAlpha, fMc), BigDecimal.valueOf(-1).multiply(fBeta).divide(fAlpha, fMc));
     }
 
+    /**
+     * @return the slope alpha
+     */
+    public BigDecimal getAlpha() {
+        return fAlpha;
+    }
+
+    /**
+     * @return the offset beta
+     */
+    public BigDecimal getBeta() {
+        return fBeta;
+    }
 }
diff --git a/org.eclipse.tracecompass.tmf.core/src/org/eclipse/tracecompass/internal/tmf/core/synchronization/TmfTimestampTransformLinearFast.java b/org.eclipse.tracecompass.tmf.core/src/org/eclipse/tracecompass/internal/tmf/core/synchronization/TmfTimestampTransformLinearFast.java
new file mode 100644 (file)
index 0000000..cfa4b5d
--- /dev/null
@@ -0,0 +1,311 @@
+/*******************************************************************************
+ * Copyright (c) 2015 École Polytechnique de Montréal
+ *
+ * All rights reserved. This program and the accompanying materials are made
+ * available under the terms of the Eclipse Public License v1.0 which
+ * accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ *
+ * Contributors:
+ *   Francis Giraldeau - Initial implementation and API
+ *   Geneviève Bastien - Fixes and improvements
+ *******************************************************************************/
+
+package org.eclipse.tracecompass.internal.tmf.core.synchronization;
+
+import java.math.BigDecimal;
+import java.math.MathContext;
+
+import org.eclipse.tracecompass.tmf.core.synchronization.ITmfTimestampTransform;
+import org.eclipse.tracecompass.tmf.core.timestamp.ITmfTimestamp;
+import org.eclipse.tracecompass.tmf.core.timestamp.TmfTimestamp;
+
+import com.google.common.hash.HashFunction;
+import com.google.common.hash.Hashing;
+
+/**
+ * Fast linear timestamp transform.
+ *
+ * Reduce the use of BigDecimal for an interval of time where the transform can
+ * be computed only with integer math. By rearranging the linear equation
+ *
+ * f(t) = fAlpha * t + fBeta
+ *
+ * to
+ *
+ * f(t) = (fAlphaLong * (t - ts)) / m + fBeta + c
+ *
+ * where fAlphaLong = fAlpha * m, and c is the constant part of the slope
+ * product.
+ *
+ * The slope applies to a relative time reference instead of absolute timestamp
+ * from epoch. The constant part of the slope for the interval is added to beta.
+ * It reduces the width of slope and timestamp to 32-bit integers, and the
+ * result fits a 64-bit value. Using standard integer arithmetic yield speedup
+ * compared to BigDecimal, while preserving precision. Depending of rounding,
+ * there may be a slight difference of +/- 3ns between the value computed by the
+ * fast transform compared to BigDecimal. The timestamps produced are indepotent
+ * (transforming the same timestamp will always produce the same result), and
+ * the timestamps are monotonic.
+ *
+ * The number of bits available for the cache range is variable. The variable
+ * alphaLong must be a 32-bit value. We reserve 30-bit for the decimal part to
+ * reach the nanosecond precision. If the slope is greater than 1.0, the shift
+ * is reduced to avoid overflow. It reduces the useful cache range, but the
+ * result is correct even for large (1e9) slope.
+ *
+ * @author Francis Giraldeau <francis.giraldeau@gmail.com>
+ *
+ */
+public class TmfTimestampTransformLinearFast implements ITmfTimestampTransformInvertible {
+
+    private static final long serialVersionUID = 2398540405078949740L;
+
+    private static final int INTEGER_BITS = 32;
+    private static final int DECIMAL_BITS = 30;
+    private static final HashFunction HASHER = Hashing.goodFastHash(32);
+    private static final MathContext MC = MathContext.DECIMAL128;
+
+    private final BigDecimal fAlpha;
+    private final BigDecimal fBeta;
+    private final long fAlphaLong;
+    private final long fDeltaMax;
+    private final int fDeltaBits;
+    private final int fHashCode;
+
+    private long fOffset;
+
+    private transient long fRangeStart;
+    private transient long fScaleMiss;
+    private transient long fScaleHit;
+
+    /**
+     * Default constructor, equivalent to the identity.
+     */
+    public TmfTimestampTransformLinearFast() {
+        this(BigDecimal.ONE, BigDecimal.ZERO);
+    }
+
+    /**
+     * Constructor with alpha and beta
+     *
+     * @param alpha
+     *            The slope of the linear transform
+     * @param beta
+     *            The initial offset of the linear transform
+     */
+    public TmfTimestampTransformLinearFast(final double alpha, final double beta) {
+        this(BigDecimal.valueOf(alpha), BigDecimal.valueOf(beta));
+    }
+
+    /**
+     * Constructor with alpha and beta as BigDecimal
+     *
+     * @param alpha
+     *            The slope of the linear transform (must be in the range
+     *            [1e-9, 1e9]
+     * @param beta
+     *            The initial offset of the linear transform
+     */
+    public TmfTimestampTransformLinearFast(final BigDecimal alpha, final BigDecimal beta) {
+        /*
+         * Validate the slope range:
+         *
+         * - Negative slope means timestamp goes backward wrt another computer,
+         *   and this would violate the basic laws of physics.
+         *
+         * - A slope smaller than 1e-9 means the transform result will always be
+         *   truncated to zero nanosecond.
+         *
+         * - A slope larger than Integer.MAX_VALUE is too large for the
+         *   nanosecond scale.
+         *
+         * Therefore, a valid slope must be in the range [1e-9, 1e9]
+         */
+        if (alpha.compareTo(BigDecimal.valueOf(1e-9)) < 0 ||
+                alpha.compareTo(BigDecimal.valueOf(1e9)) > 0) {
+            throw new IllegalArgumentException("The slope alpha must in the range [1e-9, 1e9]"); //$NON-NLS-1$
+        }
+        fAlpha = alpha;
+        fBeta = beta;
+
+        /*
+         * The result of (fAlphaLong * delta) must be at most 64-bit value.
+         * Below, we compute the number of bits usable to represent the delta.
+         * Small fAlpha (close to one) have greater range left for delta (at
+         * most 30-bit). For large fAlpha, we reduce the delta range. If fAlpha
+         * is close to ~1e9, then the delta size will be zero, effectively
+         * recomputing the result using the BigDecimal for each transform.
+         *
+         * Long.numberOfLeadingZeros(fAlpha.longValue()) returns the number of
+         * zero bits of the integer part of the slope. Then, fIntegerBits is
+         * subtracted, which returns the number of bits usable for delta. This
+         * value is bounded in the interval of [0, 30], because the delta can't
+         * be negative, and we handle at most nanosecond precision, or 2^30. One
+         * bit for each operand is reserved for the sign (Java enforce signed
+         * arithmetics), such that
+         *
+         * bitsof(fDeltaBits) + bitsof(fAlphaLong) = 62 + 2 = 64
+         */
+        int width = Long.numberOfLeadingZeros(fAlpha.longValue()) - INTEGER_BITS;
+        fDeltaBits = Math.max(Math.min(width, DECIMAL_BITS), 0);
+        fDeltaMax = 1 << fDeltaBits;
+        fAlphaLong = fAlpha.multiply(BigDecimal.valueOf(fDeltaMax), MC).longValue();
+        fRangeStart = 0L;
+        fOffset = 0L;
+        fScaleMiss = 0;
+        fScaleHit = 0;
+        fHashCode = HASHER.newHasher()
+                .putDouble(fAlpha.doubleValue())
+                .putDouble(fBeta.doubleValue())
+                .putLong(fAlphaLong)
+                .hash()
+                .asInt();
+    }
+
+    //-------------------------------------------------------------------------
+    // Main timestamp computation
+    //-------------------------------------------------------------------------
+
+    @Override
+    public ITmfTimestamp transform(ITmfTimestamp timestamp) {
+        return new TmfTimestamp(timestamp, transform(timestamp.getValue()));
+    }
+
+    @Override
+    public long transform(long timestamp) {
+        long delta = timestamp - fRangeStart;
+        if (delta >= fDeltaMax || delta < 0) {
+            /*
+             * Rescale if we exceed the safe range.
+             *
+             * If the same timestamp is transform with two different fStart
+             * reference, they may not produce the same result. To avoid this
+             * problem, align fStart on a deterministic boundary.
+             *
+             * TODO: use exact math arithmetic to detect overflow when switching to Java 8
+             */
+            fRangeStart = timestamp - (timestamp % fDeltaMax);
+            fOffset = BigDecimal.valueOf(fRangeStart).multiply(fAlpha, MC).add(fBeta, MC).longValue();
+            delta = Math.abs(timestamp - fRangeStart);
+            fScaleMiss++;
+        } else {
+            fScaleHit++;
+        }
+        return ((fAlphaLong * delta) >> fDeltaBits) + fOffset;
+    }
+
+    //-------------------------------------------------------------------------
+    // Transform composition
+    //-------------------------------------------------------------------------
+
+    @Override
+    public ITmfTimestampTransform composeWith(ITmfTimestampTransform composeWith) {
+        if (composeWith.equals(TmfTimestampTransform.IDENTITY)) {
+            /* If composing with identity, just return this */
+            return this;
+        } else if (composeWith instanceof TmfTimestampTransformLinearFast) {
+            /* If composeWith is a linear transform, add the two together */
+            TmfTimestampTransformLinearFast ttl = (TmfTimestampTransformLinearFast) composeWith;
+            BigDecimal newAlpha = fAlpha.multiply(ttl.getAlpha(), MC);
+            BigDecimal newBeta = fAlpha.multiply(ttl.getBeta(), MC).add(fBeta);
+            /* Don't use the factory to make sure any further composition will
+             * be performed on the same object type */
+            return new TmfTimestampTransformLinearFast(newAlpha, newBeta);
+        } else {
+            /*
+             * We do not know what to do with this kind of transform, just
+             * return this
+             */
+            return this;
+        }
+    }
+
+    @Override
+    public ITmfTimestampTransform inverse() {
+        return new TmfTimestampTransformLinearFast(BigDecimal.ONE.divide(fAlpha, MC),
+                BigDecimal.valueOf(-1).multiply(fBeta).divide(fAlpha, MC));
+    }
+
+    //-------------------------------------------------------------------------
+    // Getters and utility methods
+    //-------------------------------------------------------------------------
+
+    /**
+     * A cache miss occurs when the timestamp is out of the range for integer
+     * computation, and therefore requires using BigDecimal for re-scaling.
+     *
+     * @return number of misses
+     */
+    public long getCacheMisses() {
+        return fScaleMiss;
+    }
+
+    /**
+     * A scale hit occurs if the timestamp is in the range for fast transform.
+     *
+     * @return number of hits
+     */
+    public long getCacheHits() {
+        return fScaleHit;
+    }
+
+    /**
+     * Reset scale misses to zero
+     */
+    public void resetScaleStats() {
+        fScaleMiss = 0;
+        fScaleHit = 0;
+    }
+
+    /**
+     * @return the slope alpha
+     */
+    public BigDecimal getAlpha() {
+        return fAlpha;
+    }
+
+    /**
+     * @return the offset beta
+     */
+    public BigDecimal getBeta() {
+        return fBeta;
+    }
+
+    /**
+     * The value delta max is the timestamp range where integer arithmetic is
+     * used.
+     *
+     * @return the maximum delta
+     */
+    public long getDeltaMax() {
+        return fDeltaMax;
+    }
+
+    @Override
+    public String toString() {
+        return String.format("%s [ slope = %s, offset = %s ]",  //$NON-NLS-1$
+                getClass().getSimpleName(),
+                fAlpha.toString(),
+                fBeta.toString());
+    }
+
+    @Override
+    public boolean equals(Object obj) {
+        if (this == obj) {
+            return true;
+        }
+        if (obj instanceof TmfTimestampTransformLinearFast) {
+            TmfTimestampTransformLinearFast other = (TmfTimestampTransformLinearFast) obj;
+            return this.getAlpha().equals(other.getAlpha()) &&
+                    this.getBeta().equals(other.getBeta());
+        }
+        return false;
+    }
+
+    @Override
+    public int hashCode() {
+        return fHashCode;
+    }
+
+}
\ No newline at end of file
index c86149afb1d757d769c500c1e1892fd2e7f5dc37..b959409ee4aa62272855ebb89e674681143c93e9 100644 (file)
@@ -45,12 +45,14 @@ public interface ITmfTimestampTransform extends Serializable {
 
     /**
      * Returns a timestamp transform that is the composition of two timestamp
-     * transforms.
+     * transforms. Composed objects must be the same type.
      *
      * @param composeWith
      *            The transform to first apply on the timestamp before applying
      *            the current object
      * @return A new timestamp transform object with the resulting composition.
+     *
+     * TODO: allow composition of different transform types.
      */
     ITmfTimestampTransform composeWith(ITmfTimestampTransform composeWith);
 
index bb916112ccc3700a650c1267625856afb3f9e290..613018b267fad2d09268da137af1960509bae299 100644 (file)
@@ -24,7 +24,7 @@ import org.eclipse.core.runtime.CoreException;
 import org.eclipse.tracecompass.internal.tmf.core.Activator;
 import org.eclipse.tracecompass.internal.tmf.core.synchronization.TmfConstantTransform;
 import org.eclipse.tracecompass.internal.tmf.core.synchronization.TmfTimestampTransform;
-import org.eclipse.tracecompass.internal.tmf.core.synchronization.TmfTimestampTransformLinear;
+import org.eclipse.tracecompass.internal.tmf.core.synchronization.TmfTimestampTransformLinearFast;
 import org.eclipse.tracecompass.tmf.core.TmfCommonConstants;
 import org.eclipse.tracecompass.tmf.core.timestamp.ITmfTimestamp;
 
@@ -93,7 +93,7 @@ public final class TimestampTransformFactory {
         if (factor == 1.0) {
             return createWithOffset(offset);
         }
-        return new TmfTimestampTransformLinear(factor, offset.normalize(0, ITmfTimestamp.NANOSECOND_SCALE).getValue());
+        return new TmfTimestampTransformLinearFast(factor, offset.normalize(0, ITmfTimestamp.NANOSECOND_SCALE).getValue());
     }
 
     /**
@@ -111,7 +111,7 @@ public final class TimestampTransformFactory {
         if (factor == 1.0) {
             return createWithOffset(offset);
         }
-        return new TmfTimestampTransformLinear(factor, offset);
+        return new TmfTimestampTransformLinearFast(factor, offset);
     }
 
     /**
@@ -130,7 +130,7 @@ public final class TimestampTransformFactory {
         if (factor.equals(BigDecimal.ONE)) {
             return createWithOffset(offset.longValueExact());
         }
-        return new TmfTimestampTransformLinear(factor, offset);
+        return new TmfTimestampTransformLinearFast(factor, offset);
     }
 
     /**
This page took 0.036633 seconds and 5 git commands to generate.