This is an automated email from the ASF dual-hosted git repository. tballison pushed a commit to branch TIKA-4868-performance-improvements in repository https://gitbox.apache.org/repos/asf/tika.git
commit 39d5e7f44384d69501b5f8481fcbc5266102b81c Author: tallison <[email protected]> AuthorDate: Wed Sep 2 08:41:36 2026 -0400 TIKA-4868: incremental HTML probe stripping; BMP table for block lookup --- CHANGES.txt | 10 ++ .../apache/tika/ml/chardetect/AdaptiveProbe.java | 12 ++- .../tika/ml/chardetect/HtmlByteStripper.java | 115 ++++++++++++++++---- .../ml/chardetect/HtmlByteStripperResumeTest.java | 117 +++++++++++++++++++++ .../tika/ml/junkdetect/UnicodeBlockRanges.java | 20 ++++ .../tika/ml/junkdetect/UnicodeBlockRangesTest.java | 14 +++ 6 files changed, 263 insertions(+), 25 deletions(-) diff --git a/CHANGES.txt b/CHANGES.txt index c2b46bd0ac..f125119319 100644 --- a/CHANGES.txt +++ b/CHANGES.txt @@ -1,5 +1,15 @@ Release 4.1.0 - unreleased + * Mojibuster's adaptive probe strips incrementally instead of + re-stripping the whole buffer on every read (quadratic in read count + on tag-heavy pages; a 293KB page's probe drops 4.5ms -> 0.8ms). + Byte-identical: the resumable scanner holds back at a chunk-final + "<!" so chunked == single-shot at every boundary (exhaustive + boundary tests), and detection output was unchanged across a + 3,034-file differential. JunkDetector's Unicode block lookup also + uses a precomputed BMP table (exhaustive equivalence test) + (TIKA-4868). + * Markdown rendering is another ~8x faster on large documents: a custom Text-node renderer emits unescaped spans in bulk instead of commonmark's per-character escape-check-and-append (9MB render diff --git a/tika-encoding-detectors/tika-encoding-detector-mojibuster/src/main/java/org/apache/tika/ml/chardetect/AdaptiveProbe.java b/tika-encoding-detectors/tika-encoding-detector-mojibuster/src/main/java/org/apache/tika/ml/chardetect/AdaptiveProbe.java index e2100b0533..f9aa049890 100644 --- a/tika-encoding-detectors/tika-encoding-detector-mojibuster/src/main/java/org/apache/tika/ml/chardetect/AdaptiveProbe.java +++ b/tika-encoding-detectors/tika-encoding-detector-mojibuster/src/main/java/org/apache/tika/ml/chardetect/AdaptiveProbe.java @@ -61,6 +61,10 @@ public final class AdaptiveProbe { int cap = Math.min(rawCap, contentTarget); byte[] buf = new byte[cap]; byte[] stripDst = new byte[cap]; + // Resumable strip: each byte is scanned once. Re-stripping from offset 0 + // per read made this loop quadratic in read count on tag-heavy pages. + // Absolute cursor positions stay valid across the copyOf growth below. + HtmlByteStripper.Cursor cursor = new HtmlByteStripper.Cursor(); int total = 0; while (total < rawCap) { int want = Math.min(rawCap - total, contentTarget); @@ -71,10 +75,10 @@ public final class AdaptiveProbe { } int n = IOUtils.read(tis, buf, total, want); total += n; - HtmlByteStripper.Result r = - HtmlByteStripper.stripTags(buf, 0, total, stripDst, 0); - int content = r.tagCount > 0 ? r.length : total; - if (content >= contentTarget || n < want) { + boolean eof = n < want; + HtmlByteStripper.stripTags(buf, total, stripDst, cursor, eof); + int content = cursor.tagCount() > 0 ? cursor.contentLength() : total; + if (content >= contentTarget || eof) { break; // enough body text, or EOF } } diff --git a/tika-encoding-detectors/tika-encoding-detector-mojibuster/src/main/java/org/apache/tika/ml/chardetect/HtmlByteStripper.java b/tika-encoding-detectors/tika-encoding-detector-mojibuster/src/main/java/org/apache/tika/ml/chardetect/HtmlByteStripper.java index 37ae5ad26b..9b2aa44937 100644 --- a/tika-encoding-detectors/tika-encoding-detector-mojibuster/src/main/java/org/apache/tika/ml/chardetect/HtmlByteStripper.java +++ b/tika-encoding-detectors/tika-encoding-detector-mojibuster/src/main/java/org/apache/tika/ml/chardetect/HtmlByteStripper.java @@ -184,27 +184,93 @@ public final class HtmlByteStripper { return strip(src, srcOffset, srcLen, dst, dstOffset, false); } + /** + * Scan state carried across chunked {@link #stripTags(byte[], int, byte[], Cursor, + * boolean)} calls. All positions are absolute indices into the caller's (growing) + * source buffer, so the buffer must retain its prefix across calls (e.g. grow with + * {@code Arrays.copyOf}). Tags-only: the resumable path never drops entities. + */ + static final class Cursor { + private int state = TEXT; + private int nameStart; + private byte[] rawEnd; + private int rawMatch; + private int tagCount; + private int entityCount; + private int entityStart; + private int attrNameStart; + private boolean emitAttrValue; + private int written; + private int next; + // where the very first scan started; guards the comment lookbehind + private int origin; + + int contentLength() { + return written; + } + + int tagCount() { + return tagCount; + } + } + + /** + * Resumable {@link #stripTags(byte[], int, int, byte[], int)}: scans + * {@code src[cursor.next .. end)}, appending stripped output at + * {@code dst[cursor.written]}. Byte-identical to a single-shot strip of the final + * buffer: on a non-final call the scan holds back at a {@code <!} too close to + * {@code end} for the comment lookahead, so the next call re-examines it with more + * bytes; everything else in the machine is strictly left-to-right. + * + * @param isFinal true on the last call (no more input will arrive) + */ + static void stripTags(byte[] src, int end, byte[] dst, Cursor cursor, boolean isFinal) { + scan(src, end, dst, cursor, false, isFinal); + } + private static Result strip(byte[] src, int srcOffset, int srcLen, byte[] dst, int dstOffset, boolean dropEntities) { - int w = dstOffset; - int state = TEXT; - int nameStart = 0; - byte[] rawEnd = null; - int rawMatch = 0; + Cursor c = new Cursor(); + c.next = srcOffset; + c.origin = srcOffset; + c.written = dstOffset; int end = srcOffset + srcLen; - int tagCount = 0; - int entityCount = 0; + scan(src, end, dst, c, dropEntities, true); + int w = c.written; + + // Unterminated entity at EOF: emit consumed prefix as literal text. + if (c.state == ENTITY || c.state == ENTITY_NAME || c.state == ENTITY_NUM + || c.state == ENTITY_DEC || c.state == ENTITY_HEX) { + for (int k = c.entityStart; k < end; k++) { + dst[w++] = src[k]; + } + } + + return new Result(w - dstOffset, c.tagCount, c.entityCount); + } + + private static void scan(byte[] src, int end, byte[] dst, Cursor c, + boolean dropEntities, boolean isFinal) { + int w = c.written; + int state = c.state; + int nameStart = c.nameStart; + byte[] rawEnd = c.rawEnd; + int rawMatch = c.rawMatch; + int tagCount = c.tagCount; + int entityCount = c.entityCount; // Position of the leading '&' for the in-progress entity. // Tracked so the bailout path can emit the consumed prefix // as literal text when the parse fails (e.g. "AT&T"). - int entityStart = 0; - int attrNameStart = 0; + int entityStart = c.entityStart; + int attrNameStart = c.attrNameStart; // When true, the current quoted attribute value's bytes are // emitted to dst (attribute name matched TEXT_ATTRS). Reset // to false when the quote closes or the tag ends. - boolean emitAttrValue = false; + boolean emitAttrValue = c.emitAttrValue; - for (int i = srcOffset; i < end; i++) { + int i = c.next; + outer: + for (; i < end; i++) { byte b = src[i]; switch (state) { case TEXT: @@ -219,6 +285,11 @@ public final class HtmlByteStripper { break; case LT: + if (b == '!' && i + 2 >= end && !isFinal) { + // comment lookahead needs 2 more bytes: hold back so the next + // call re-examines '!' -- keeps chunked == single-shot + break outer; + } if (b == '!' && i + 2 < end && src[i + 1] == '-' && src[i + 2] == '-') { state = COMMENT; @@ -474,7 +545,7 @@ public final class HtmlByteStripper { break; case COMMENT: - if (b == '>' && i >= srcOffset + 2 + if (b == '>' && i >= c.origin + 2 && src[i - 1] == '-' && src[i - 2] == '-') { state = TEXT; } @@ -508,15 +579,17 @@ public final class HtmlByteStripper { } } - // Unterminated entity at EOF: emit consumed prefix as literal text. - if (state == ENTITY || state == ENTITY_NAME || state == ENTITY_NUM - || state == ENTITY_DEC || state == ENTITY_HEX) { - for (int k = entityStart; k < end; k++) { - dst[w++] = src[k]; - } - } - - return new Result(w - dstOffset, tagCount, entityCount); + c.state = state; + c.nameStart = nameStart; + c.rawEnd = rawEnd; + c.rawMatch = rawMatch; + c.tagCount = tagCount; + c.entityCount = entityCount; + c.entityStart = entityStart; + c.attrNameStart = attrNameStart; + c.emitAttrValue = emitAttrValue; + c.written = w; + c.next = i; } /** diff --git a/tika-encoding-detectors/tika-encoding-detector-mojibuster/src/test/java/org/apache/tika/ml/chardetect/HtmlByteStripperResumeTest.java b/tika-encoding-detectors/tika-encoding-detector-mojibuster/src/test/java/org/apache/tika/ml/chardetect/HtmlByteStripperResumeTest.java new file mode 100644 index 0000000000..77a2508a21 --- /dev/null +++ b/tika-encoding-detectors/tika-encoding-detector-mojibuster/src/test/java/org/apache/tika/ml/chardetect/HtmlByteStripperResumeTest.java @@ -0,0 +1,117 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You 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 org.apache.tika.ml.chardetect; + +import static org.junit.jupiter.api.Assertions.assertArrayEquals; +import static org.junit.jupiter.api.Assertions.assertEquals; + +import java.nio.charset.StandardCharsets; +import java.util.Arrays; +import java.util.Random; + +import org.junit.jupiter.api.Test; + +/** + * Chunked stripTags with a carried Cursor must be byte-identical to the single-shot + * strip of the final buffer, for every chunking -- including boundaries inside tags, + * comments (the {@code <!} lookahead hold-back), raw script/style bodies, quoted + * attribute values, and multibyte UTF-8 sequences. + */ +public class HtmlByteStripperResumeTest { + + private static final String[] SAMPLES = { + "plain text, no markup at all — even multibyte: čšž 中文 🚀", + "<html><head><title>t</title></head><body>Hello <b>world</b></body></html>", + "before<!-- a comment with <tags> inside -->after", + "x<!-- unterminated comment...", + "a<!DOCTYPE html>b<?xml version=\"1.0\"?>c", + "<script>var a = '<div>'; // not a tag </script>text<style>.x{}</style>tail", + "<img alt=\"seen text\" src=\"nope.png\" title='also seen'>body", + "AT&T & friends A B ¬anentity; &unterminated", + "stray < less-than and << double and <3 hearts", + "<a href=\"x\">link</a><ul><li>item</li></ul>", + "<div class='q' aria-label=\"read me\">deep</div>", + "čšž<em>中文</em>🚀<!--中-->done", + "text</scripted>more<script>raw</script>end", + "<!", + "<!-", + "<!--", + "<!-->", + "<!---->tail", + }; + + @Test + public void testEveryBoundaryEqualsSingleShot() { + for (String sample : SAMPLES) { + byte[] src = sample.getBytes(StandardCharsets.UTF_8); + Expected want = singleShot(src); + // every single split point, and every pair of split points + for (int cut = 0; cut <= src.length; cut++) { + check(src, new int[]{cut}, want, sample); + } + for (int c1 = 0; c1 <= src.length; c1 += 3) { + for (int c2 = c1; c2 <= src.length; c2 += 3) { + check(src, new int[]{c1, c2}, want, sample); + } + } + } + } + + @Test + public void testRandomChunkingsOnConcatenatedSamples() { + StringBuilder sb = new StringBuilder(); + for (int i = 0; i < 50; i++) { + sb.append(SAMPLES[i % SAMPLES.length]); + } + byte[] src = sb.toString().getBytes(StandardCharsets.UTF_8); + Expected want = singleShot(src); + Random random = new Random(42); + for (int trial = 0; trial < 200; trial++) { + int nCuts = 1 + random.nextInt(8); + int[] cuts = new int[nCuts]; + for (int i = 0; i < nCuts; i++) { + cuts[i] = random.nextInt(src.length + 1); + } + Arrays.sort(cuts); + check(src, cuts, want, "concat trial " + trial); + } + } + + private record Expected(byte[] out, int tagCount) { + } + + private static Expected singleShot(byte[] src) { + byte[] dst = new byte[src.length + 16]; + HtmlByteStripper.Result r = HtmlByteStripper.stripTags(src, 0, src.length, dst, 0); + return new Expected(Arrays.copyOf(dst, r.length), r.tagCount); + } + + private static void check(byte[] src, int[] cuts, Expected want, String label) { + byte[] dst = new byte[src.length + 16]; + HtmlByteStripper.Cursor cursor = new HtmlByteStripper.Cursor(); + int prev = 0; + for (int cut : cuts) { + int end = Math.max(prev, cut); + HtmlByteStripper.stripTags(src, end, dst, cursor, false); + prev = end; + } + HtmlByteStripper.stripTags(src, src.length, dst, cursor, true); + assertEquals(want.tagCount(), cursor.tagCount(), label + " cuts=" + Arrays.toString(cuts)); + assertArrayEquals(want.out(), Arrays.copyOf(dst, cursor.contentLength()), + label + " cuts=" + Arrays.toString(cuts)); + } +} diff --git a/tika-ml/tika-ml-junkdetect/src/main/java/org/apache/tika/ml/junkdetect/UnicodeBlockRanges.java b/tika-ml/tika-ml-junkdetect/src/main/java/org/apache/tika/ml/junkdetect/UnicodeBlockRanges.java index ab7e1b00b7..6eb0dc32c3 100644 --- a/tika-ml/tika-ml-junkdetect/src/main/java/org/apache/tika/ml/junkdetect/UnicodeBlockRanges.java +++ b/tika-ml/tika-ml-junkdetect/src/main/java/org/apache/tika/ml/junkdetect/UnicodeBlockRanges.java @@ -399,11 +399,24 @@ public final class UnicodeBlockRanges { /** Cached start_cp array for binary search. */ private static final int[] STARTS; + + /** + * Precomputed bucket per BMP codepoint (128KB): bucketOf runs per character of + * every scored text, and the binary search was a visible share of junk-detection + * time. Filled from {@link #searchBucketOf(int)}, so the answers are identical + * by construction; supplementary planes stay on the search path. + */ + private static final short[] BMP_BUCKETS; + static { STARTS = new int[RANGES.length]; for (int i = 0; i < RANGES.length; i++) { STARTS[i] = RANGES[i][0]; } + BMP_BUCKETS = new short[0x10000]; + for (int cp = 0; cp < 0x10000; cp++) { + BMP_BUCKETS[cp] = (short) searchBucketOf(cp); + } } private UnicodeBlockRanges() { @@ -423,6 +436,13 @@ public final class UnicodeBlockRanges { * O(log N) where N = {@value #UNASSIGNED} (the number of named blocks). */ public static int bucketOf(int cp) { + if (cp >= 0 && cp < 0x10000) { + return BMP_BUCKETS[cp]; + } + return searchBucketOf(cp); + } + + private static int searchBucketOf(int cp) { // Binary search: find largest STARTS[i] <= cp int lo = 0; int hi = STARTS.length - 1; diff --git a/tika-ml/tika-ml-junkdetect/src/test/java/org/apache/tika/ml/junkdetect/UnicodeBlockRangesTest.java b/tika-ml/tika-ml-junkdetect/src/test/java/org/apache/tika/ml/junkdetect/UnicodeBlockRangesTest.java index e25cff9204..22576a1a77 100644 --- a/tika-ml/tika-ml-junkdetect/src/test/java/org/apache/tika/ml/junkdetect/UnicodeBlockRangesTest.java +++ b/tika-ml/tika-ml-junkdetect/src/test/java/org/apache/tika/ml/junkdetect/UnicodeBlockRangesTest.java @@ -111,4 +111,18 @@ public class UnicodeBlockRangesTest { assertTrue(seen[b], "Bucket id " + b + " is never produced by any codepoint"); } } + + @org.junit.jupiter.api.Test + public void testBmpTableMatchesSearchEverywhere() throws Exception { + // the BMP fast table must agree with the binary search for every codepoint, + // including plane boundaries and a sweep of the supplementary planes + java.lang.reflect.Method search = + UnicodeBlockRanges.class.getDeclaredMethod("searchBucketOf", int.class); + search.setAccessible(true); + for (int cp = 0; cp <= 0x10FFFF; cp += (cp < 0x10000 ? 1 : 17)) { + org.junit.jupiter.api.Assertions.assertEquals( + (int) (Integer) search.invoke(null, cp), + UnicodeBlockRanges.bucketOf(cp), "cp=" + Integer.toHexString(cp)); + } + } }
