Mercurial > hg > openjdk > jdk9 > nashorn
changeset 906:72493c5057dd
8046201: Avoid repeated flattening of nested ConsStrings
Reviewed-by: lagergren, attila
author | hannesw |
---|---|
date | Mon, 23 Jun 2014 18:32:11 +0200 |
parents | 3edd4da9386f |
children | 4f3468f46d20 |
files | src/jdk/nashorn/internal/runtime/ConsString.java test/src/jdk/nashorn/internal/runtime/ConsStringTest.java |
diffstat | 2 files changed, 166 insertions(+), 12 deletions(-) [+] |
line wrap: on
line diff
--- a/src/jdk/nashorn/internal/runtime/ConsString.java Mon Jun 23 21:23:53 2014 +0530 +++ b/src/jdk/nashorn/internal/runtime/ConsString.java Mon Jun 23 18:32:11 2014 +0200 @@ -36,8 +36,12 @@ public final class ConsString implements CharSequence { private CharSequence left, right; - final private int length; - private boolean flat = false; + private final int length; + private volatile int state = STATE_NEW; + + private final static int STATE_NEW = 0; + private final static int STATE_THRESHOLD = 2; + private final static int STATE_FLATTENED = -1; /** * Constructor @@ -57,7 +61,7 @@ @Override public String toString() { - return (String) flattened(); + return (String) flattened(true); } @Override @@ -67,22 +71,31 @@ @Override public char charAt(final int index) { - return flattened().charAt(index); + return flattened(true).charAt(index); } @Override public CharSequence subSequence(final int start, final int end) { - return flattened().subSequence(start, end); + return flattened(true).subSequence(start, end); } - private CharSequence flattened() { - if (!flat) { - flatten(); + /** + * Returns the components of this ConsString as a {@code CharSequence} array with two elements. + * The elements will be either {@code Strings} or other {@code ConsStrings}. + * @return CharSequence array of length 2 + */ + public synchronized CharSequence[] getComponents() { + return new CharSequence[] { left, right }; + } + + private CharSequence flattened(boolean flattenNested) { + if (state != STATE_FLATTENED) { + flatten(flattenNested); } return left; } - private void flatten() { + private synchronized void flatten(boolean flattenNested) { // We use iterative traversal as recursion may exceed the stack size limit. final char[] chars = new char[length]; int pos = length; @@ -97,8 +110,14 @@ do { if (cs instanceof ConsString) { final ConsString cons = (ConsString) cs; - stack.addFirst(cons.left); - cs = cons.right; + // Count the times a cons-string is traversed as part of other cons-strings being flattened. + // If it crosses a threshold we flatten the nested cons-string internally. + if (cons.state == STATE_FLATTENED || (flattenNested && ++cons.state >= STATE_THRESHOLD)) { + cs = cons.flattened(false); + } else { + stack.addFirst(cons.left); + cs = cons.right; + } } else { final String str = (String) cs; pos -= str.length(); @@ -109,7 +128,7 @@ left = new String(chars); right = ""; - flat = true; + state = STATE_FLATTENED; } }
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/test/src/jdk/nashorn/internal/runtime/ConsStringTest.java Mon Jun 23 18:32:11 2014 +0200 @@ -0,0 +1,135 @@ +/* + * Copyright (c) 2010, 2014, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. Oracle designates this + * particular file as subject to the "Classpath" exception as provided + * by Oracle in the LICENSE file that accompanied this code. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ + +package jdk.nashorn.internal.runtime; + +import static org.testng.Assert.assertEquals; +import static org.testng.Assert.assertFalse; +import static org.testng.Assert.assertTrue; + +import jdk.nashorn.internal.runtime.JSType; +import jdk.nashorn.internal.runtime.ScriptRuntime; +import org.testng.annotations.Test; + +/** + * Tests for JSType methods. + * + * @test + * @run testng jdk.nashorn.internal.runtime.ConsStringTest + */ +public class ConsStringTest { + + /** + * Test toString conversion + */ + @Test + public void testConsStringToString() { + final ConsString cs1 = new ConsString("b", "c"); + final ConsString cs2 = new ConsString("d", "e"); + final ConsString cs3 = new ConsString(cs1, cs2); + final ConsString cs4 = new ConsString(cs3, "f"); + final ConsString cs5 = new ConsString("a", cs4); + assertEquals(cs5.toString(), "abcdef"); + assertEquals(cs4.toString(), "bcdef"); + assertEquals(cs3.toString(), "bcde"); + assertEquals(cs2.toString(), "de"); + assertEquals(cs1.toString(), "bc"); + // ConsStrings should be flattened now + assertEquals(cs1.getComponents()[0], "bc"); + assertEquals(cs1.getComponents()[1], ""); + assertEquals(cs2.getComponents()[0], "de"); + assertEquals(cs2.getComponents()[1], ""); + assertEquals(cs3.getComponents()[0], "bcde"); + assertEquals(cs3.getComponents()[1], ""); + assertEquals(cs4.getComponents()[0], "bcdef"); + assertEquals(cs4.getComponents()[1], ""); + assertEquals(cs5.getComponents()[0], "abcdef"); + assertEquals(cs5.getComponents()[1], ""); + } + + /** + * Test charAt + */ + @Test + public void testConsStringCharAt() { + final ConsString cs1 = new ConsString("b", "c"); + final ConsString cs2 = new ConsString("d", "e"); + final ConsString cs3 = new ConsString(cs1, cs2); + final ConsString cs4 = new ConsString(cs3, "f"); + final ConsString cs5 = new ConsString("a", cs4); + assertEquals(cs1.charAt(1), 'c'); + assertEquals(cs2.charAt(0), 'd'); + assertEquals(cs3.charAt(3), 'e'); + assertEquals(cs4.charAt(1), 'c'); + assertEquals(cs5.charAt(2), 'c'); + // ConsStrings should be flattened now + assertEquals(cs1.getComponents()[0], "bc"); + assertEquals(cs1.getComponents()[1], ""); + assertEquals(cs2.getComponents()[0], "de"); + assertEquals(cs2.getComponents()[1], ""); + assertEquals(cs3.getComponents()[0], "bcde"); + assertEquals(cs3.getComponents()[1], ""); + assertEquals(cs4.getComponents()[0], "bcdef"); + assertEquals(cs4.getComponents()[1], ""); + assertEquals(cs5.getComponents()[0], "abcdef"); + assertEquals(cs5.getComponents()[1], ""); + } + + + /** + * Test flattening of top-level and internal ConsStrings + */ + @Test + public void testConsStringFlattening() { + final ConsString cs1 = new ConsString("b", "c"); + final ConsString cs2 = new ConsString("d", "e"); + final ConsString cs3 = new ConsString(cs1, cs2); + final ConsString cs4 = new ConsString(cs3, "f"); + + final ConsString cs5 = new ConsString("a", cs4); + // top-level ConsString should not yet be flattened + assert(cs5.getComponents()[0] == "a"); + assert(cs5.getComponents()[1] == cs4); + assertEquals(cs5.toString(), "abcdef"); + // top-level ConsString should be flattened + assertEquals(cs5.getComponents()[0], "abcdef"); + assertEquals(cs5.getComponents()[1], ""); + // internal ConsString should not yet be flattened after first traversal + assertEquals(cs4.getComponents()[0], cs3); + assertEquals(cs4.getComponents()[1], "f"); + + final ConsString cs6 = new ConsString("a", cs4); + // top-level ConsString should not yet be flattened + assertEquals(cs6.getComponents()[0], "a"); + assertEquals(cs6.getComponents()[1], cs4); + assertEquals(cs6.toString(), "abcdef"); + // top-level ConsString should be flattened + assertEquals(cs6.getComponents()[0], "abcdef"); + assertEquals(cs6.getComponents()[1], ""); + // internal ConsString should have been flattened after second traversal + assertEquals(cs4.getComponents()[0], "bcdef"); + assertEquals(cs4.getComponents()[1], ""); + } +}