Merge "Added splay octane benchmark."
diff --git a/benchmarks/src/main/java/com/google/gwt/benchmark/benchmarks/octane/SplayBenchmarkGWT.gwt.xml b/benchmarks/src/main/java/com/google/gwt/benchmark/benchmarks/octane/SplayBenchmarkGWT.gwt.xml
new file mode 100644
index 0000000..2965146
--- /dev/null
+++ b/benchmarks/src/main/java/com/google/gwt/benchmark/benchmarks/octane/SplayBenchmarkGWT.gwt.xml
@@ -0,0 +1,19 @@
+<!--                                                                        -->
+<!-- Copyright 2014 Google Inc.                                             -->
+<!-- Licensed under the Apache License, Version 2.0 (the "License"); you    -->
+<!-- may not use this file except in compliance with the License. You may   -->
+<!-- may obtain a copy of the License at                                    -->
+<!--                                                                        -->
+<!-- http://www.apache.org/licenses/LICENSE-2.0                             -->
+<!--                                                                        -->
+<!-- Unless required by applicable law or agreed to in writing, software    -->
+<!-- distributed under the License is distributed on an "AS IS" BASIS,      -->
+<!-- WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or        -->
+<!-- implied. License for the specific language governing permissions and   -->
+<!-- limitations under the License.                                         -->
+
+<module>
+  <inherits name="com.google.gwt.benchmark.benchmarks.octane.Octane"/>
+  <entry-point class="com.google.gwt.benchmark.benchmarks.octane.client.splay.gwt.SplayBenchmarkGWT.EntryPoint"/>
+  <source path="client" includes="splay/gwt/*.java"/>
+</module>
\ No newline at end of file
diff --git a/benchmarks/src/main/java/com/google/gwt/benchmark/benchmarks/octane/SplayBenchmarkGWTD8.gwt.xml b/benchmarks/src/main/java/com/google/gwt/benchmark/benchmarks/octane/SplayBenchmarkGWTD8.gwt.xml
new file mode 100644
index 0000000..4a07c45
--- /dev/null
+++ b/benchmarks/src/main/java/com/google/gwt/benchmark/benchmarks/octane/SplayBenchmarkGWTD8.gwt.xml
@@ -0,0 +1,18 @@
+<!--                                                                        -->
+<!-- Copyright 2014 Google Inc.                                             -->
+<!-- Licensed under the Apache License, Version 2.0 (the "License"); you    -->
+<!-- may not use this file except in compliance with the License. You may   -->
+<!-- may obtain a copy of the License at                                    -->
+<!--                                                                        -->
+<!-- http://www.apache.org/licenses/LICENSE-2.0                             -->
+<!--                                                                        -->
+<!-- Unless required by applicable law or agreed to in writing, software    -->
+<!-- distributed under the License is distributed on an "AS IS" BASIS,      -->
+<!-- WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or        -->
+<!-- implied. License for the specific language governing permissions and   -->
+<!-- limitations under the License.                                         -->
+
+<module>
+  <inherits name="com.google.gwt.benchmark.benchmarks.octane.SplayBenchmarkGWT"/>
+  <inherits name="com.google.gwt.benchmark.d8.D8"/>
+</module>
\ No newline at end of file
diff --git a/benchmarks/src/main/java/com/google/gwt/benchmark/benchmarks/octane/SplayBenchmarkJS.gwt.xml b/benchmarks/src/main/java/com/google/gwt/benchmark/benchmarks/octane/SplayBenchmarkJS.gwt.xml
new file mode 100644
index 0000000..0272e9d
--- /dev/null
+++ b/benchmarks/src/main/java/com/google/gwt/benchmark/benchmarks/octane/SplayBenchmarkJS.gwt.xml
@@ -0,0 +1,19 @@
+<!--                                                                        -->
+<!-- Copyright 2014 Google Inc.                                             -->
+<!-- Licensed under the Apache License, Version 2.0 (the "License"); you    -->
+<!-- may not use this file except in compliance with the License. You may   -->
+<!-- may obtain a copy of the License at                                    -->
+<!--                                                                        -->
+<!-- http://www.apache.org/licenses/LICENSE-2.0                             -->
+<!--                                                                        -->
+<!-- Unless required by applicable law or agreed to in writing, software    -->
+<!-- distributed under the License is distributed on an "AS IS" BASIS,      -->
+<!-- WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or        -->
+<!-- implied. License for the specific language governing permissions and   -->
+<!-- limitations under the License.                                         -->
+
+<module>
+  <inherits name="com.google.gwt.benchmark.benchmarks.octane.Octane"/>
+  <entry-point class="com.google.gwt.benchmark.benchmarks.octane.client.splay.js.SplayJSBenchmark.EntryPoint"/>
+  <source path="client" includes="splay/js/*.java,splay/js/*.js"/>
+</module>
\ No newline at end of file
diff --git a/benchmarks/src/main/java/com/google/gwt/benchmark/benchmarks/octane/SplayBenchmarkJSD8.gwt.xml b/benchmarks/src/main/java/com/google/gwt/benchmark/benchmarks/octane/SplayBenchmarkJSD8.gwt.xml
new file mode 100644
index 0000000..267afe1
--- /dev/null
+++ b/benchmarks/src/main/java/com/google/gwt/benchmark/benchmarks/octane/SplayBenchmarkJSD8.gwt.xml
@@ -0,0 +1,18 @@
+<!--                                                                        -->
+<!-- Copyright 2014 Google Inc.                                             -->
+<!-- Licensed under the Apache License, Version 2.0 (the "License"); you    -->
+<!-- may not use this file except in compliance with the License. You may   -->
+<!-- may obtain a copy of the License at                                    -->
+<!--                                                                        -->
+<!-- http://www.apache.org/licenses/LICENSE-2.0                             -->
+<!--                                                                        -->
+<!-- Unless required by applicable law or agreed to in writing, software    -->
+<!-- distributed under the License is distributed on an "AS IS" BASIS,      -->
+<!-- WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or        -->
+<!-- implied. License for the specific language governing permissions and   -->
+<!-- limitations under the License.                                         -->
+
+<module>
+  <inherits name="com.google.gwt.benchmark.benchmarks.octane.SplayBenchmarkJS"/>
+  <inherits name="com.google.gwt.benchmark.d8.D8"/>
+</module>
\ No newline at end of file
diff --git a/benchmarks/src/main/java/com/google/gwt/benchmark/benchmarks/octane/client/splay/gwt/BenchmarkMath.java b/benchmarks/src/main/java/com/google/gwt/benchmark/benchmarks/octane/client/splay/gwt/BenchmarkMath.java
new file mode 100644
index 0000000..cad92de
--- /dev/null
+++ b/benchmarks/src/main/java/com/google/gwt/benchmark/benchmarks/octane/client/splay/gwt/BenchmarkMath.java
@@ -0,0 +1,36 @@
+/*
+ * Copyright 2014 Google Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License"); you may not
+ * use this file except in compliance with the License. You may obtain a copy of
+ * the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+ * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+ * License for the specific language governing permissions and limitations under
+ * the License.
+ */
+package com.google.gwt.benchmark.benchmarks.octane.client.splay.gwt;
+
+
+/**
+ * BenchmarkMath is a special implementation of Math.random that returns the same
+ * number sequence every time.
+ */
+public class BenchmarkMath {
+
+  private static int seed = 49734321;
+
+  public static double random() {
+    seed = ((seed + 0x7ed55d16) + (seed << 12))  & 0xffffffff;
+    seed = ((seed ^ 0xc761c23c) ^ (seed >>> 19)) & 0xffffffff;
+    seed = ((seed + 0x165667b1) + (seed << 5))   & 0xffffffff;
+    seed = ((seed + 0xd3a2646c) ^ (seed << 9))   & 0xffffffff;
+    seed = ((seed + 0xfd7046c5) + (seed << 3))   & 0xffffffff;
+    seed = ((seed ^ 0xb55a4f09) ^ (seed >>> 16)) & 0xffffffff;
+    return ((double)(seed & 0xfffffff)) / 0x10000000;
+  }
+}
diff --git a/benchmarks/src/main/java/com/google/gwt/benchmark/benchmarks/octane/client/splay/gwt/Splay.java b/benchmarks/src/main/java/com/google/gwt/benchmark/benchmarks/octane/client/splay/gwt/Splay.java
new file mode 100644
index 0000000..5081fa1
--- /dev/null
+++ b/benchmarks/src/main/java/com/google/gwt/benchmark/benchmarks/octane/client/splay/gwt/Splay.java
@@ -0,0 +1,186 @@
+/*
+ * Copyright 2014 Google Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License"); you may not
+ * use this file except in compliance with the License. You may obtain a copy of
+ * the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+ * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+ * License for the specific language governing permissions and limitations under
+ * the License.
+ */
+package com.google.gwt.benchmark.benchmarks.octane.client.splay.gwt;
+
+import com.google.gwt.benchmark.collection.shared.CollectionFactory;
+import com.google.gwt.benchmark.collection.shared.JavaScriptArrayNumber;
+import com.google.gwt.core.client.GWT;
+
+public class Splay {
+  // Configuration.
+  private final int kSplayTreeSize = 8000;
+  private final int kSplayTreeModifications = 80;
+  private final int kSplayTreePayloadDepth = 5;
+
+  private SplayTree splayTree = null;
+  private double splaySampleTimeStart = 0.0;
+
+  private static class Payload {
+
+    @SuppressWarnings("unused")
+    private JavaScriptArrayNumber array;
+    @SuppressWarnings("unused")
+    private String string;
+    @SuppressWarnings("unused")
+    private Payload left;
+    @SuppressWarnings("unused")
+    private Payload right;
+
+    public Payload(String tag) {
+      JavaScriptArrayNumber numbers = CollectionFactory.createNumber(10);
+      numbers.push(0);
+      numbers.push(1);
+      numbers.push(2);
+      numbers.push(3);
+      numbers.push(4);
+      numbers.push(5);
+      numbers.push(6);
+      numbers.push(7);
+      numbers.push(8);
+      numbers.push(9);
+      this.array = numbers;
+      this.string = "String for key " + tag + " in leaf node";
+    }
+
+    public Payload(Payload left, Payload right) {
+      this.left = left;
+      this.right = right;
+    }
+  }
+
+  private Payload GeneratePayloadTree(int depth, String tag) {
+    if (depth == 0) {
+      return new Payload(tag);
+    } else {
+      return new Payload(GeneratePayloadTree(depth - 1, tag), GeneratePayloadTree(depth - 1, tag));
+    }
+  }
+
+  private double GenerateKey() {
+    // original code:
+    // // The benchmark framework guarantees that Math.random is
+    // // deterministic; see base.js.
+    // return Math.random();
+
+    // making sure we do not introduce randomness
+    return BenchmarkMath.random();
+  }
+
+  private int splaySamples = 0;
+  private int splaySumOfSquaredPauses = 0;
+
+  private int SplayRMS() {
+    return (int) Math.round(Math.sqrt(splaySumOfSquaredPauses / splaySamples) * 10000);
+  }
+
+  private void SplayUpdateStats(double time) {
+    double pause = time - splaySampleTimeStart;
+    splaySampleTimeStart = time;
+    splaySamples++;
+    splaySumOfSquaredPauses += pause * pause;
+  }
+
+  private double InsertNewNode() {
+    // Insert new node with a unique key.
+    double key;
+    do {
+      key = GenerateKey();
+    } while (splayTree.find(key) != null);
+
+    Payload payload = GeneratePayloadTree(kSplayTreePayloadDepth, key + "");
+    splayTree.insert(key, payload);
+    return key;
+  }
+
+  private boolean hasPerformanceNow() {
+    if (GWT.isScript()) {
+      return hasPerformanceNow0();
+    } else {
+      return true;
+    }
+
+  }
+
+  private native boolean hasPerformanceNow0() /*-{
+    return !!$wnd.performance && $wnd.performance.now;
+  }-*/;
+
+  private double now() {
+    if (GWT.isScript()) {
+      return now0();
+    } else {
+      return System.currentTimeMillis();
+    }
+  }
+
+  private native double now0() /*-{
+                               return $wnd.performance.now()
+                               }-*/;
+
+  void SplaySetup() {
+    // Check if the platform has the performance.now high resolution timer.
+    // If not, throw exception and quit.
+    if (!hasPerformanceNow()) {
+      throw new RuntimeException("PerformanceNowUnsupported");
+    }
+
+    splayTree = new SplayTree();
+    splaySampleTimeStart = now();
+    for (int i = 0; i < kSplayTreeSize; i++) {
+      InsertNewNode();
+      if ((i + 1) % 20 == 19) {
+        SplayUpdateStats(now());
+      }
+    }
+  }
+
+  void SplayTearDown() {
+    // Allow the garbage collector to reclaim the memory
+    // used by the splay tree no matter how we exit the
+    // tear down function.
+    JavaScriptArrayNumber keys = splayTree.exportKeys();
+    splayTree = null;
+
+    splaySamples = 0;
+    splaySumOfSquaredPauses = 0;
+
+    // Verify that the splay tree has the right size.
+    int length = keys.length();
+    if (length != kSplayTreeSize) {
+      throw new RuntimeException("Splay tree has wrong size");
+    }
+
+    // Verify that the splay tree has sorted, unique keys.
+    for (int i = 0; i < length - 1; i++) {
+      if (keys.get(i) >= keys.get(i + 1)) {
+        throw new RuntimeException("Splay tree not sorted");
+      }
+    }
+  }
+
+  void SplayRun() {
+    // Replace a few nodes in the splay tree.
+    for (int i = 0; i < kSplayTreeModifications; i++) {
+      double key = InsertNewNode();
+      SplayTree.Node greatest = splayTree.findGreatestLessThan(key);
+      if (greatest == null)
+        splayTree.remove(key);
+      else
+        splayTree.remove(greatest.key);
+    }
+    SplayUpdateStats(now());
+  }
+}
diff --git a/benchmarks/src/main/java/com/google/gwt/benchmark/benchmarks/octane/client/splay/gwt/SplayBenchmarkGWT.java b/benchmarks/src/main/java/com/google/gwt/benchmark/benchmarks/octane/client/splay/gwt/SplayBenchmarkGWT.java
new file mode 100644
index 0000000..18e9fb0
--- /dev/null
+++ b/benchmarks/src/main/java/com/google/gwt/benchmark/benchmarks/octane/client/splay/gwt/SplayBenchmarkGWT.java
@@ -0,0 +1,58 @@
+/*
+ * Copyright 2014 Google Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License"); you may not
+ * use this file except in compliance with the License. You may obtain a copy of
+ * the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+ * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+ * License for the specific language governing permissions and limitations under
+ * the License.
+ */
+package com.google.gwt.benchmark.benchmarks.octane.client.splay.gwt;
+
+import com.google.gwt.benchmark.benchmarks.octane.client.splay.js.SplayJSBenchmark;
+import com.google.gwt.benchmark.framework.client.AbstractBenchmarkEntryPoint;
+import com.google.gwt.benchmark.framework.shared.AbstractBenchmark;
+
+public class SplayBenchmarkGWT extends AbstractBenchmark {
+
+  /**
+   * EntryPoint for SplayGWT benchmark.
+   */
+  public static class EntryPoint extends AbstractBenchmarkEntryPoint {
+
+    @Override
+    protected AbstractBenchmark getBenchmark() {
+      return new SplayJSBenchmark();
+    }
+  }
+
+  private Splay splay;
+
+  public SplayBenchmarkGWT() {
+    super("SplayBenchmarkGWT");
+  }
+
+  @Override
+  public Object run() {
+    splay.SplayRun();
+    return null;
+  }
+
+  @Override
+  public void setupOneTime() {
+    splay = new Splay();
+    splay.SplaySetup();
+  }
+
+  @Override
+  public void tearDownOneTime() {
+    splay.SplayTearDown();
+    splay = null;
+  }
+}
diff --git a/benchmarks/src/main/java/com/google/gwt/benchmark/benchmarks/octane/client/splay/gwt/SplayTree.java b/benchmarks/src/main/java/com/google/gwt/benchmark/benchmarks/octane/client/splay/gwt/SplayTree.java
new file mode 100644
index 0000000..80ab4f7
--- /dev/null
+++ b/benchmarks/src/main/java/com/google/gwt/benchmark/benchmarks/octane/client/splay/gwt/SplayTree.java
@@ -0,0 +1,283 @@
+/*
+ * Copyright 2014 Google Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License"); you may not
+ * use this file except in compliance with the License. You may obtain a copy of
+ * the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+ * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+ * License for the specific language governing permissions and limitations under
+ * the License.
+ */
+package com.google.gwt.benchmark.benchmarks.octane.client.splay.gwt;
+
+import com.google.gwt.benchmark.benchmarks.octane.client.splay.gwt.SplayTree.Node.Visitor;
+import com.google.gwt.benchmark.collection.shared.CollectionFactory;
+import com.google.gwt.benchmark.collection.shared.JavaScriptArrayNumber;
+
+public class SplayTree {
+
+  public static class Node {
+
+    public double key;
+    public Object value;
+    public Node left;
+    public Node right;
+
+    /**
+     * @param key
+     * @param value
+     */
+    public Node(double key, Object value) {
+      this.key = key;
+      this.value = value;
+    }
+
+    /**
+     * Performs an ordered traversal of the subtree starting at this SplayTree.Node.
+     *
+     * @param {function(SplayTree.Node)} f Visitor function.
+     * @private
+     */
+    @SuppressWarnings("javadoc")
+    public void traverse_(Visitor f) {
+      Node current = this;
+      while (current != null) {
+        Node left = current.left;
+        if (left != null)
+          left.traverse_(f);
+        f.call(current);
+        current = current.right;
+      }
+    }
+
+    public interface Visitor {
+      void call(Node n);
+    }
+
+  }
+
+  /**
+   * Pointer to the root node of the tree.
+   *
+   * @type {SplayTree.Node}
+   * @private
+   */
+  private SplayTree.Node root_ = null;
+
+  public SplayTree() {
+  }
+
+  /**
+   * @return {boolean} Whether the tree is empty.
+   */
+  public boolean isEmpty() {
+    return root_ == null;
+  }
+
+  /**
+   * Inserts a node into the tree with the specified key and value if the tree does not already
+   * contain a node with the specified key. If the value is inserted, it becomes the root of the
+   * tree.
+   *
+   * @param {number} key Key to insert into the tree.
+   * @param {*} value Value to insert into the tree.
+   */
+  @SuppressWarnings("javadoc")
+  public void insert(double key, Object value) {
+    if (this.isEmpty()) {
+      this.root_ = new SplayTree.Node(key, value);
+      return;
+    }
+    // Splay on the key to move the last node on the search path for
+    // the key to the root of the tree.
+    this.splay_(key);
+    if (this.root_.key == key) {
+      return;
+    }
+    SplayTree.Node node = new SplayTree.Node(key, value);
+    if (key > this.root_.key) {
+      node.left = this.root_;
+      node.right = this.root_.right;
+      this.root_.right = null;
+    } else {
+      node.right = this.root_;
+      node.left = this.root_.left;
+      this.root_.left = null;
+    }
+    this.root_ = node;
+  }
+
+  /**
+   * Removes a node with the specified key from the tree if the tree contains a node with this key.
+   * The removed node is returned. If the key is not found, an exception is thrown.
+   *
+   * @param {number} key Key to find and remove from the tree.
+   * @return {SplayTree.Node} The removed node.
+   */
+  @SuppressWarnings("javadoc")
+  public SplayTree.Node remove(double key) {
+    if (this.isEmpty()) {
+      throw new RuntimeException("Key not found: " + key);
+    }
+    this.splay_(key);
+    if (this.root_.key != key) {
+      throw new RuntimeException("Key not found: " + key);
+    }
+    SplayTree.Node removed = this.root_;
+    if (this.root_.left == null) {
+      this.root_ = this.root_.right;
+    } else {
+      SplayTree.Node right = this.root_.right;
+      this.root_ = this.root_.left;
+      // Splay to make sure that the new root has an empty right child.
+      this.splay_(key);
+      // Insert the original right child as the right child of the new
+      // root.
+      this.root_.right = right;
+    }
+    return removed;
+  }
+
+  /**
+   * Returns the node having the specified key or null if the tree doesn't contain a node with the
+   * specified key.
+   *
+   * @param {number} key Key to find in the tree.
+   * @return {SplayTree.Node} Node having the specified key.
+   */
+  @SuppressWarnings("javadoc")
+  public SplayTree.Node find(double key) {
+    if (this.isEmpty()) {
+      return null;
+    }
+    this.splay_(key);
+    return this.root_.key == key ? this.root_ : null;
+  }
+
+  /**
+   * @return {SplayTree.Node} Node having the maximum key value.
+   */
+  public SplayTree.Node findMax(SplayTree.Node opt_startNode) {
+    if (this.isEmpty()) {
+      return null;
+    }
+    SplayTree.Node current = opt_startNode != null ? opt_startNode : this.root_;
+    while (current.right != null) {
+      current = current.right;
+    }
+    return current;
+  }
+
+  /**
+   * @return {SplayTree.Node} Node having the maximum key value that is less than the specified key
+   *         value.
+   */
+  public SplayTree.Node findGreatestLessThan(double key) {
+    if (this.isEmpty()) {
+      return null;
+    }
+    // Splay on the key to move the node with the given key or the last
+    // node on the search path to the top of the tree.
+    this.splay_(key);
+    // Now the result is either the root node or the greatest node in
+    // the left subtree.
+    if (this.root_.key < key) {
+      return this.root_;
+    } else if (this.root_.left != null) {
+      return this.findMax(this.root_.left);
+    } else {
+      return null;
+    }
+  }
+
+  /**
+   * @return {Array<*>} An array containing all the keys of tree's nodes.
+   */
+  public JavaScriptArrayNumber exportKeys() {
+    final JavaScriptArrayNumber result = CollectionFactory.createNumber();
+    if (!this.isEmpty()) {
+      this.root_.traverse_(new Visitor() {
+        public void call(Node n) {
+          result.push(n.key);
+        }
+      });
+    }
+    return result;
+  }
+
+  /**
+   * Perform the splay operation for the given key. Moves the node with the given key to the top of
+   * the tree. If no node has the given key, the last node on the search path is moved to the top of
+   * the tree. This is the simplified top-down splaying algorithm from: "Self-adjusting Binary
+   * Search Trees" by Sleator and Tarjan
+   *
+   * @param {number} key Key to splay the tree on.
+   * @private
+   */
+  @SuppressWarnings("javadoc")
+  private void splay_(double key) {
+    if (this.isEmpty()) {
+      return;
+    }
+    // Create a dummy node. The use of the dummy node is a bit
+    // counter-intuitive: The right child of the dummy node will hold
+    // the L tree of the algorithm. The left child of the dummy node
+    // will hold the R tree of the algorithm. Using a dummy node, left
+    // and right will always be nodes and we avoid special cases.
+    SplayTree.Node dummy, left, right;
+    dummy = left = right = new SplayTree.Node(-1, null);
+    SplayTree.Node current = this.root_;
+    while (true) {
+      if (key < current.key) {
+        if (current.left == null) {
+          break;
+        }
+        if (key < current.left.key) {
+          // Rotate right.
+          SplayTree.Node tmp = current.left;
+          current.left = tmp.right;
+          tmp.right = current;
+          current = tmp;
+          if (current.left == null) {
+            break;
+          }
+        }
+        // Link right.
+        right.left = current;
+        right = current;
+        current = current.left;
+      } else if (key > current.key) {
+        if (current.right == null) {
+          break;
+        }
+        if (key > current.right.key) {
+          // Rotate left.
+          SplayTree.Node tmp = current.right;
+          current.right = tmp.left;
+          tmp.left = current;
+          current = tmp;
+          if (current.right == null) {
+            break;
+          }
+        }
+        // Link left.
+        left.right = current;
+        left = current;
+        current = current.right;
+      } else {
+        break;
+      }
+    }
+    // Assemble.
+    left.right = current.left;
+    right.left = current.right;
+    current.left = dummy.right;
+    current.right = dummy.left;
+    this.root_ = current;
+  }
+}
diff --git a/benchmarks/src/main/java/com/google/gwt/benchmark/benchmarks/octane/client/splay/js/SplayJSBenchmark.java b/benchmarks/src/main/java/com/google/gwt/benchmark/benchmarks/octane/client/splay/js/SplayJSBenchmark.java
new file mode 100644
index 0000000..9bfdf4d
--- /dev/null
+++ b/benchmarks/src/main/java/com/google/gwt/benchmark/benchmarks/octane/client/splay/js/SplayJSBenchmark.java
@@ -0,0 +1,72 @@
+/*
+ * Copyright 2014 Google Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License"); you may not
+ * use this file except in compliance with the License. You may obtain a copy of
+ * the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+ * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+ * License for the specific language governing permissions and limitations under
+ * the License.
+ */
+package com.google.gwt.benchmark.benchmarks.octane.client.splay.js;
+
+import com.google.gwt.benchmark.benchmarks.octane.client.OctaneJS;
+import com.google.gwt.benchmark.framework.client.AbstractBenchmarkEntryPoint;
+import com.google.gwt.benchmark.framework.client.Injector;
+import com.google.gwt.benchmark.framework.client.Injector.GlobalMapping;
+import com.google.gwt.benchmark.framework.shared.AbstractBenchmark;
+import com.google.gwt.core.client.GWT;
+import com.google.gwt.resources.client.ClientBundle;
+import com.google.gwt.resources.client.TextResource;
+
+public class SplayJSBenchmark extends AbstractBenchmark {
+
+  /**
+   * EntryPoint for Splay JavaScript benchmark.
+   */
+  public static class EntryPoint extends AbstractBenchmarkEntryPoint {
+
+    @Override
+    protected AbstractBenchmark getBenchmark() {
+      return new SplayJSBenchmark();
+    }
+  }
+
+  interface Resource extends ClientBundle {
+    @Source("splay.js")
+    TextResource navierStokesJavaScript();
+  }
+
+  public SplayJSBenchmark() {
+    super("SplayBenchmarkJS");
+  }
+
+  @Override
+  public native Object run() /*-{
+    return $wnd.__octane__splay_js_run();
+  }-*/;
+
+  @Override
+  public void setupOneTime() {
+    Resource r = GWT.create(Resource.class);
+    new Injector().injectJavaScript(OctaneJS.PREAMBLE + "performance = $wnd.performance;" + r.navierStokesJavaScript().getText(),
+        new GlobalMapping("__octane__splay_js_run", "SplayRun"),
+        new GlobalMapping("__octane__splay_js_setup", "SplaySetup"),
+        new GlobalMapping("__octane__splay_js_teardown", "SplayTearDown"));
+    callSetup();
+  }
+
+  @Override
+  public native void tearDownOneTime() /*-{
+    $wnd.__octane__splay_js_teardown();
+  }-*/;
+
+  private native void callSetup() /*-{
+    $wnd.__octane__splay_js_setup();
+  }-*/;
+}
diff --git a/benchmarks/src/main/java/com/google/gwt/benchmark/benchmarks/octane/client/splay/js/splay.js b/benchmarks/src/main/java/com/google/gwt/benchmark/benchmarks/octane/client/splay/js/splay.js
new file mode 100644
index 0000000..88525d7
--- /dev/null
+++ b/benchmarks/src/main/java/com/google/gwt/benchmark/benchmarks/octane/client/splay/js/splay.js
@@ -0,0 +1,442 @@
+// Copyright 2009 the V8 project authors. All rights reserved.
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are
+// met:
+//
+//     * Redistributions of source code must retain the above copyright
+//       notice, this list of conditions and the following disclaimer.
+//     * Redistributions in binary form must reproduce the above
+//       copyright notice, this list of conditions and the following
+//       disclaimer in the documentation and/or other materials provided
+//       with the distribution.
+//     * Neither the name of Google Inc. nor the names of its
+//       contributors may be used to endorse or promote products derived
+//       from this software without specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+// This benchmark is based on a JavaScript log processing module used
+// by the V8 profiler to generate execution time profiles for runs of
+// JavaScript applications, and it effectively measures how fast the
+// JavaScript engine is at allocating nodes and reclaiming the memory
+// used for old nodes. Because of the way splay trees work, the engine
+// also has to deal with a lot of changes to the large tree object
+// graph.
+
+var Splay = new BenchmarkSuite('Splay', [81491, 2739514], [
+  new Benchmark("Splay", true, false, 1400,
+    SplayRun, SplaySetup, SplayTearDown, SplayRMS)
+]);
+
+
+// Configuration.
+
+// added to remove random
+Math1 = {};
+Math1.random = (function() {
+  var seed = 49734321;
+  return function() {
+    // Robert Jenkins' 32 bit integer hash function.
+    seed = ((seed + 0x7ed55d16) + (seed << 12))  & 0xffffffff;
+    seed = ((seed ^ 0xc761c23c) ^ (seed >>> 19)) & 0xffffffff;
+    seed = ((seed + 0x165667b1) + (seed << 5))   & 0xffffffff;
+    seed = ((seed + 0xd3a2646c) ^ (seed << 9))   & 0xffffffff;
+    seed = ((seed + 0xfd7046c5) + (seed << 3))   & 0xffffffff;
+    seed = ((seed ^ 0xb55a4f09) ^ (seed >>> 16)) & 0xffffffff;
+    return (seed & 0xfffffff) / 0x10000000;
+  };
+})();
+
+var kSplayTreeSize = 8000;
+var kSplayTreeModifications = 80;
+var kSplayTreePayloadDepth = 5;
+
+var splayTree = null;
+var splaySampleTimeStart = 0.0;
+
+function GeneratePayloadTree(depth, tag) {
+  if (depth == 0) {
+    return {
+      array  : [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ],
+      string : 'String for key ' + tag + ' in leaf node'
+    };
+  } else {
+    return {
+      left:  GeneratePayloadTree(depth - 1, tag),
+      right: GeneratePayloadTree(depth - 1, tag)
+    };
+  }
+}
+
+
+function GenerateKey() {
+  // The benchmark framework guarantees that Math.random is
+  // deterministic; see base.js.
+  return Math1.random();
+}
+
+
+
+var splaySamples = 0;
+var splaySumOfSquaredPauses = 0;
+
+function SplayRMS() {
+  return Math.round(Math.sqrt(splaySumOfSquaredPauses / splaySamples) * 10000);
+}
+
+function SplayUpdateStats(time) {
+  var pause = time - splaySampleTimeStart;
+  splaySampleTimeStart = time;
+  splaySamples++;
+  splaySumOfSquaredPauses += pause * pause;
+}
+
+function InsertNewNode() {
+  // Insert new node with a unique key.
+  var key;
+  do {
+    key = GenerateKey();
+  } while (splayTree.find(key) != null);
+  var payload = GeneratePayloadTree(kSplayTreePayloadDepth, String(key));
+  splayTree.insert(key, payload);
+  return key;
+}
+
+
+function SplaySetup() {
+  // Check if the platform has the performance.now high resolution timer.
+  // If not, throw exception and quit.
+  if (!performance.now) {
+    throw "PerformanceNowUnsupported";
+  }
+
+  splayTree = new SplayTree();
+  splaySampleTimeStart = performance.now()
+  for (var i = 0; i < kSplayTreeSize; i++) {
+    InsertNewNode();
+    if ((i+1) % 20 == 19) {
+      SplayUpdateStats(performance.now());
+    }
+  }
+}
+
+
+function SplayTearDown() {
+  // Allow the garbage collector to reclaim the memory
+  // used by the splay tree no matter how we exit the
+  // tear down function.
+  var keys = splayTree.exportKeys();
+  splayTree = null;
+
+  splaySamples = 0;
+  splaySumOfSquaredPauses = 0;
+
+  // Verify that the splay tree has the right size.
+  var length = keys.length;
+  if (length != kSplayTreeSize) {
+    throw new Error("Splay tree has wrong size");
+  }
+
+  // Verify that the splay tree has sorted, unique keys.
+  for (var i = 0; i < length - 1; i++) {
+    if (keys[i] >= keys[i + 1]) {
+      throw new Error("Splay tree not sorted");
+    }
+  }
+}
+
+
+function SplayRun() {
+  // Replace a few nodes in the splay tree.
+  for (var i = 0; i < kSplayTreeModifications; i++) {
+    var key = InsertNewNode();
+    var greatest = splayTree.findGreatestLessThan(key);
+    if (greatest == null) splayTree.remove(key);
+    else splayTree.remove(greatest.key);
+  }
+  SplayUpdateStats(performance.now());
+}
+
+
+/**
+ * Constructs a Splay tree.  A splay tree is a self-balancing binary
+ * search tree with the additional property that recently accessed
+ * elements are quick to access again. It performs basic operations
+ * such as insertion, look-up and removal in O(log(n)) amortized time.
+ *
+ * @constructor
+ */
+function SplayTree() {
+};
+
+
+/**
+ * Pointer to the root node of the tree.
+ *
+ * @type {SplayTree.Node}
+ * @private
+ */
+SplayTree.prototype.root_ = null;
+
+
+/**
+ * @return {boolean} Whether the tree is empty.
+ */
+SplayTree.prototype.isEmpty = function() {
+  return !this.root_;
+};
+
+
+/**
+ * Inserts a node into the tree with the specified key and value if
+ * the tree does not already contain a node with the specified key. If
+ * the value is inserted, it becomes the root of the tree.
+ *
+ * @param {number} key Key to insert into the tree.
+ * @param {*} value Value to insert into the tree.
+ */
+SplayTree.prototype.insert = function(key, value) {
+  if (this.isEmpty()) {
+    this.root_ = new SplayTree.Node(key, value);
+    return;
+  }
+  // Splay on the key to move the last node on the search path for
+  // the key to the root of the tree.
+  this.splay_(key);
+  if (this.root_.key == key) {
+    return;
+  }
+  var node = new SplayTree.Node(key, value);
+  if (key > this.root_.key) {
+    node.left = this.root_;
+    node.right = this.root_.right;
+    this.root_.right = null;
+  } else {
+    node.right = this.root_;
+    node.left = this.root_.left;
+    this.root_.left = null;
+  }
+  this.root_ = node;
+};
+
+
+/**
+ * Removes a node with the specified key from the tree if the tree
+ * contains a node with this key. The removed node is returned. If the
+ * key is not found, an exception is thrown.
+ *
+ * @param {number} key Key to find and remove from the tree.
+ * @return {SplayTree.Node} The removed node.
+ */
+SplayTree.prototype.remove = function(key) {
+  if (this.isEmpty()) {
+    throw Error('Key not found: ' + key);
+  }
+  this.splay_(key);
+  if (this.root_.key != key) {
+    throw Error('Key not found: ' + key);
+  }
+  var removed = this.root_;
+  if (!this.root_.left) {
+    this.root_ = this.root_.right;
+  } else {
+    var right = this.root_.right;
+    this.root_ = this.root_.left;
+    // Splay to make sure that the new root has an empty right child.
+    this.splay_(key);
+    // Insert the original right child as the right child of the new
+    // root.
+    this.root_.right = right;
+  }
+  return removed;
+};
+
+
+/**
+ * Returns the node having the specified key or null if the tree doesn't contain
+ * a node with the specified key.
+ *
+ * @param {number} key Key to find in the tree.
+ * @return {SplayTree.Node} Node having the specified key.
+ */
+SplayTree.prototype.find = function(key) {
+  if (this.isEmpty()) {
+    return null;
+  }
+  this.splay_(key);
+  return this.root_.key == key ? this.root_ : null;
+};
+
+
+/**
+ * @return {SplayTree.Node} Node having the maximum key value.
+ */
+SplayTree.prototype.findMax = function(opt_startNode) {
+  if (this.isEmpty()) {
+    return null;
+  }
+  var current = opt_startNode || this.root_;
+  while (current.right) {
+    current = current.right;
+  }
+  return current;
+};
+
+
+/**
+ * @return {SplayTree.Node} Node having the maximum key value that
+ *     is less than the specified key value.
+ */
+SplayTree.prototype.findGreatestLessThan = function(key) {
+  if (this.isEmpty()) {
+    return null;
+  }
+  // Splay on the key to move the node with the given key or the last
+  // node on the search path to the top of the tree.
+  this.splay_(key);
+  // Now the result is either the root node or the greatest node in
+  // the left subtree.
+  if (this.root_.key < key) {
+    return this.root_;
+  } else if (this.root_.left) {
+    return this.findMax(this.root_.left);
+  } else {
+    return null;
+  }
+};
+
+
+/**
+ * @return {Array<*>} An array containing all the keys of tree's nodes.
+ */
+SplayTree.prototype.exportKeys = function() {
+  var result = [];
+  if (!this.isEmpty()) {
+    this.root_.traverse_(function(node) { result.push(node.key); });
+  }
+  return result;
+};
+
+
+/**
+ * Perform the splay operation for the given key. Moves the node with
+ * the given key to the top of the tree.  If no node has the given
+ * key, the last node on the search path is moved to the top of the
+ * tree. This is the simplified top-down splaying algorithm from:
+ * "Self-adjusting Binary Search Trees" by Sleator and Tarjan
+ *
+ * @param {number} key Key to splay the tree on.
+ * @private
+ */
+SplayTree.prototype.splay_ = function(key) {
+  if (this.isEmpty()) {
+    return;
+  }
+  // Create a dummy node.  The use of the dummy node is a bit
+  // counter-intuitive: The right child of the dummy node will hold
+  // the L tree of the algorithm.  The left child of the dummy node
+  // will hold the R tree of the algorithm.  Using a dummy node, left
+  // and right will always be nodes and we avoid special cases.
+  var dummy, left, right;
+  dummy = left = right = new SplayTree.Node(null, null);
+  var current = this.root_;
+  while (true) {
+    if (key < current.key) {
+      if (!current.left) {
+        break;
+      }
+      if (key < current.left.key) {
+        // Rotate right.
+        var tmp = current.left;
+        current.left = tmp.right;
+        tmp.right = current;
+        current = tmp;
+        if (!current.left) {
+          break;
+        }
+      }
+      // Link right.
+      right.left = current;
+      right = current;
+      current = current.left;
+    } else if (key > current.key) {
+      if (!current.right) {
+        break;
+      }
+      if (key > current.right.key) {
+        // Rotate left.
+        var tmp = current.right;
+        current.right = tmp.left;
+        tmp.left = current;
+        current = tmp;
+        if (!current.right) {
+          break;
+        }
+      }
+      // Link left.
+      left.right = current;
+      left = current;
+      current = current.right;
+    } else {
+      break;
+    }
+  }
+  // Assemble.
+  left.right = current.left;
+  right.left = current.right;
+  current.left = dummy.right;
+  current.right = dummy.left;
+  this.root_ = current;
+};
+
+
+/**
+ * Constructs a Splay tree node.
+ *
+ * @param {number} key Key.
+ * @param {*} value Value.
+ */
+SplayTree.Node = function(key, value) {
+  this.key = key;
+  this.value = value;
+};
+
+
+/**
+ * @type {SplayTree.Node}
+ */
+SplayTree.Node.prototype.left = null;
+
+
+/**
+ * @type {SplayTree.Node}
+ */
+SplayTree.Node.prototype.right = null;
+
+
+/**
+ * Performs an ordered traversal of the subtree starting at
+ * this SplayTree.Node.
+ *
+ * @param {function(SplayTree.Node)} f Visitor function.
+ * @private
+ */
+SplayTree.Node.prototype.traverse_ = function(f) {
+  var current = this;
+  while (current) {
+    var left = current.left;
+    if (left) left.traverse_(f);
+    f(current);
+    current = current.right;
+  }
+};