You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@lucene.apache.org by "danmuzi (via GitHub)" <gi...@apache.org> on 2026/07/18 18:34:51 UTC
Re: [PR] Optimize transition lookup in CompiledAutomaton.addTail [lucene]
danmuzi commented on code in PR #16361:
URL: https://github.com/apache/lucene/pull/16361#discussion_r3608855498
##########
lucene/benchmark-jmh/src/java/org/apache/lucene/benchmark/jmh/CompiledAutomatonBenchmark.java:
##########
@@ -0,0 +1,64 @@
+package org.apache.lucene.benchmark.jmh;
Review Comment:
Missing header comment
##########
lucene/benchmark-jmh/src/java/org/apache/lucene/benchmark/jmh/CompiledAutomatonBenchmark.java:
##########
@@ -0,0 +1,64 @@
+package org.apache.lucene.benchmark.jmh;
+
+import java.io.IOException;
+import java.util.Random;
+import java.util.concurrent.TimeUnit;
+import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.BytesRefBuilder;
+import org.apache.lucene.util.automaton.Automaton;
+import org.apache.lucene.util.automaton.CompiledAutomaton;
+import org.openjdk.jmh.annotations.Benchmark;
+import org.openjdk.jmh.annotations.BenchmarkMode;
+import org.openjdk.jmh.annotations.Fork;
+import org.openjdk.jmh.annotations.Measurement;
+import org.openjdk.jmh.annotations.Mode;
+import org.openjdk.jmh.annotations.OutputTimeUnit;
+import org.openjdk.jmh.annotations.Scope;
+import org.openjdk.jmh.annotations.Setup;
+import org.openjdk.jmh.annotations.State;
+import org.openjdk.jmh.annotations.Warmup;
+
+@Fork(1)
+@Warmup(iterations = 3, time = 2)
+@Measurement(iterations = 5, time = 2)
+@BenchmarkMode(Mode.Throughput)
+@OutputTimeUnit(TimeUnit.MILLISECONDS)
+@State(Scope.Benchmark)
+public class CompiledAutomatonBenchmark {
+
+ private CompiledAutomaton compiled;
+ private BytesRef[] inputs;
+ private BytesRefBuilder output;
+ private int index;
+
+ @Setup
+ public void setup() throws IOException {
+ Automaton.Builder builder = new Automaton.Builder();
+ int state0 = builder.createState();
+ int destState = builder.createState();
+ builder.setAccept(destState, true);
+ // Add 120 transitions to state 0 with sorted labels
+ for (int i = 0; i < 120; i++) {
+ builder.addTransition(state0, destState, i * 2, i * 2);
+ }
Review Comment:
`CompiledAutomaton` converts this automaton to a UTF-8 byte automaton internally.
As a result, state 0 ends up with 66 transitions rather than 120: the 64 even labels from 0 through 126 remain single-byte transitions, while labels from 128 through 238 are encoded as two-byte UTF-8 sequences sharing the leading bytes `0xC2` or `0xC3`.
Also, inputs matching one of the even labels from 0 through 126 are accepted directly, so `floor()` returns before reaching `addTail()`. That means roughly 27% of the iterations do not exercise the changed code.
Could we use only single-byte labels (e.g., even labels below 128) and inputs that always miss (e.g., odd byte values), so that every iteration measures the intended `addTail()` transition lookup directly?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org