summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorGaming4JC <g4jc@hyperbola.info>2020-01-18 17:24:00 -0500
committerGaming4JC <g4jc@hyperbola.info>2020-01-26 15:50:38 -0500
commite17a17766ede7e44cbc1050b35268c38af8602ae (patch)
tree9477c8abb87c3943fa8ff345e5c69a2b235a4e8e
parent76a4af34064296177e11a0d3887a5763a6c3a572 (diff)
downloadUXP-e17a17766ede7e44cbc1050b35268c38af8602ae.tar
UXP-e17a17766ede7e44cbc1050b35268c38af8602ae.tar.gz
UXP-e17a17766ede7e44cbc1050b35268c38af8602ae.tar.lz
UXP-e17a17766ede7e44cbc1050b35268c38af8602ae.tar.xz
UXP-e17a17766ede7e44cbc1050b35268c38af8602ae.zip
Bug 1366241 - Change memory layout of element name and attribute name hashes from sorted to level order BST in order to take advantage of cache during lookup.
Tag UXP Issue #1344
-rw-r--r--parser/html/java/htmlparser/src/nu/validator/htmlparser/impl/AttributeName.java59
-rw-r--r--parser/html/java/htmlparser/src/nu/validator/htmlparser/impl/ElementName.java59
2 files changed, 108 insertions, 10 deletions
diff --git a/parser/html/java/htmlparser/src/nu/validator/htmlparser/impl/AttributeName.java b/parser/html/java/htmlparser/src/nu/validator/htmlparser/impl/AttributeName.java
index 667e8eb93..83ff7ec31 100644
--- a/parser/html/java/htmlparser/src/nu/validator/htmlparser/impl/AttributeName.java
+++ b/parser/html/java/htmlparser/src/nu/validator/htmlparser/impl/AttributeName.java
@@ -25,6 +25,9 @@
package nu.validator.htmlparser.impl;
import java.util.Arrays;
+import java.util.Collections;
+import java.util.LinkedList;
+import java.util.List;
import nu.validator.htmlparser.annotation.Inline;
import nu.validator.htmlparser.annotation.Local;
@@ -254,6 +257,24 @@ public final class AttributeName
return arr;
}
+ @Inline static int levelOrderBinarySearch(int[] data, int key) {
+ int n = data.length;
+ int i = 0;
+
+ while (i < n) {
+ int val = data[i];
+ if (val < key) {
+ i = 2 * i + 2;
+ } else if (val > key) {
+ i = 2 * i + 1;
+ } else {
+ return i;
+ }
+ }
+
+ return -1;
+ }
+
/**
* Returns an attribute name by buffer.
*
@@ -277,7 +298,9 @@ public final class AttributeName
, Interner interner) {
// XXX deal with offset
@Unsigned int hash = AttributeName.bufToHash(buf, length);
- int index = Arrays.binarySearch(AttributeName.ATTRIBUTE_HASHES, hash);
+ int[] hashes;
+ hashes = AttributeName.ATTRIBUTE_HASHES;
+ int index = levelOrderBinarySearch(hashes, hash);
if (index < 0) {
return null;
}
@@ -685,6 +708,25 @@ public final class AttributeName
// return bufToHash(name.toCharArray(), name.length());
// }
//
+// private static void fillLevelOrderArray(List<AttributeName> sorted, int depth,
+// int rootIdx, AttributeName[] levelOrder) {
+// if (rootIdx >= levelOrder.length) {
+// return;
+// }
+//
+// if (depth > 0) {
+// fillLevelOrderArray(sorted, depth - 1, rootIdx * 2 + 1, levelOrder);
+// }
+//
+// if (!sorted.isEmpty()) {
+// levelOrder[rootIdx] = sorted.remove(0);
+// }
+//
+// if (depth > 0) {
+// fillLevelOrderArray(sorted, depth - 1, rootIdx * 2 + 2, levelOrder);
+// }
+// }
+//
// /**
// * Regenerate self
// *
@@ -713,15 +755,22 @@ public final class AttributeName
// + att.constName() + " = new AttributeName" + att.toString()
// + ";");
// }
+//
+// LinkedList<AttributeName> sortedNames = new LinkedList<AttributeName>();
+// Collections.addAll(sortedNames, ATTRIBUTE_NAMES);
+// AttributeName[] levelOrder = new AttributeName[ATTRIBUTE_NAMES.length];
+// int bstDepth = (int) Math.ceil(Math.log(ATTRIBUTE_NAMES.length) / Math.log(2));
+// fillLevelOrderArray(sortedNames, bstDepth, 0, levelOrder);
+//
// System.out.println("private final static @NoLength AttributeName[] ATTRIBUTE_NAMES = {");
-// for (int i = 0; i < ATTRIBUTE_NAMES.length; i++) {
-// AttributeName att = ATTRIBUTE_NAMES[i];
+// for (int i = 0; i < levelOrder.length; i++) {
+// AttributeName att = levelOrder[i];
// System.out.println(att.constName() + ",");
// }
// System.out.println("};");
// System.out.println("private final static int[] ATTRIBUTE_HASHES = {");
-// for (int i = 0; i < ATTRIBUTE_NAMES.length; i++) {
-// AttributeName att = ATTRIBUTE_NAMES[i];
+// for (int i = 0; i < levelOrder.length; i++) {
+// AttributeName att = levelOrder[i];
// System.out.println(Integer.toString(att.hash()) + ",");
// }
// System.out.println("};");
diff --git a/parser/html/java/htmlparser/src/nu/validator/htmlparser/impl/ElementName.java b/parser/html/java/htmlparser/src/nu/validator/htmlparser/impl/ElementName.java
index cc363acde..46b7a901e 100644
--- a/parser/html/java/htmlparser/src/nu/validator/htmlparser/impl/ElementName.java
+++ b/parser/html/java/htmlparser/src/nu/validator/htmlparser/impl/ElementName.java
@@ -25,6 +25,9 @@
package nu.validator.htmlparser.impl;
import java.util.Arrays;
+import java.util.Collections;
+import java.util.LinkedList;
+import java.util.List;
import nu.validator.htmlparser.annotation.Inline;
import nu.validator.htmlparser.annotation.Local;
@@ -115,9 +118,29 @@ public final class ElementName
return (flags & ElementName.NOT_INTERNED) == 0;
}
+ @Inline static int levelOrderBinarySearch(int[] data, int key) {
+ int n = data.length;
+ int i = 0;
+
+ while (i < n) {
+ int val = data[i];
+ if (val < key) {
+ i = 2 * i + 2;
+ } else if (val > key) {
+ i = 2 * i + 1;
+ } else {
+ return i;
+ }
+ }
+
+ return -1;
+ }
+
@Inline static ElementName elementNameByBuffer(@NoLength char[] buf, int offset, int length, Interner interner) {
@Unsigned int hash = ElementName.bufToHash(buf, length);
- int index = Arrays.binarySearch(ElementName.ELEMENT_HASHES, hash);
+ int[] hashes;
+ hashes = ElementName.ELEMENT_HASHES;
+ int index = levelOrderBinarySearch(hashes, hash);
if (index < 0) {
return null;
} else {
@@ -406,6 +429,25 @@ public final class ElementName
// return null;
// }
//
+// private static void fillLevelOrderArray(List<ElementName> sorted, int depth,
+// int rootIdx, ElementName[] levelOrder) {
+// if (rootIdx >= levelOrder.length) {
+// return;
+// }
+//
+// if (depth > 0) {
+// fillLevelOrderArray(sorted, depth - 1, rootIdx * 2 + 1, levelOrder);
+// }
+//
+// if (!sorted.isEmpty()) {
+// levelOrder[rootIdx] = sorted.remove(0);
+// }
+//
+// if (depth > 0) {
+// fillLevelOrderArray(sorted, depth - 1, rootIdx * 2 + 2, levelOrder);
+// }
+// }
+//
// /**
// * Regenerate self
// *
@@ -436,15 +478,22 @@ public final class ElementName
// + el.constName() + " = new ElementName" + el.toString()
// + ";");
// }
+//
+// LinkedList<ElementName> sortedNames = new LinkedList<ElementName>();
+// Collections.addAll(sortedNames, ELEMENT_NAMES);
+// ElementName[] levelOrder = new ElementName[ELEMENT_NAMES.length];
+// int bstDepth = (int) Math.ceil(Math.log(ELEMENT_NAMES.length) / Math.log(2));
+// fillLevelOrderArray(sortedNames, bstDepth, 0, levelOrder);
+//
// System.out.println("private final static @NoLength ElementName[] ELEMENT_NAMES = {");
-// for (int i = 0; i < ELEMENT_NAMES.length; i++) {
-// ElementName el = ELEMENT_NAMES[i];
+// for (int i = 0; i < levelOrder.length; i++) {
+// ElementName el = levelOrder[i];
// System.out.println(el.constName() + ",");
// }
// System.out.println("};");
// System.out.println("private final static int[] ELEMENT_HASHES = {");
-// for (int i = 0; i < ELEMENT_NAMES.length; i++) {
-// ElementName el = ELEMENT_NAMES[i];
+// for (int i = 0; i < levelOrder.length; i++) {
+// ElementName el = levelOrder[i];
// System.out.println(Integer.toString(el.hash()) + ",");
// }
// System.out.println("};");