Optimize GraphemeClusterSegmentFinder performance
This CL utilized minikin:isGraphemeBreak to compute all grapheme break indices when creating GraphemeClusterSegmentFinder. This makes all methods (such as #nextStartBoundary) of GraphemeClusterSegmentFinder O(1) instead of O(n).
Bug: 271004887
Test: atest TextViewHandwritingGestureTest
Change-Id: I61c1f2c45123a584456b4860b72cd4fdc84c5f1c
diff --git a/core/java/android/text/GraphemeClusterSegmentFinder.java b/core/java/android/text/GraphemeClusterSegmentFinder.java
index 656774f..0f6fdaf 100644
--- a/core/java/android/text/GraphemeClusterSegmentFinder.java
+++ b/core/java/android/text/GraphemeClusterSegmentFinder.java
@@ -18,7 +18,8 @@
import android.annotation.IntRange;
import android.annotation.NonNull;
-import android.graphics.Paint;
+import android.graphics.TemporaryBuffer;
+import android.graphics.text.GraphemeBreak;
/**
* Implementation of {@code SegmentFinder} using grapheme clusters as the text segment. Whitespace
@@ -31,8 +32,8 @@
* Segmentation - Grapheme Cluster Boundaries</a>
*/
public class GraphemeClusterSegmentFinder extends SegmentFinder {
- private final CharSequence mText;
- private final TextPaint mTextPaint;
+ private static AutoGrowArray.FloatArray sTempAdvances = null;
+ private final boolean[] mIsGraphemeBreak;
/**
* Constructs a GraphemeClusterSegmentFinder instance for the specified text which uses the
@@ -43,51 +44,73 @@
*/
public GraphemeClusterSegmentFinder(
@NonNull CharSequence text, @NonNull TextPaint textPaint) {
- mText = text;
- mTextPaint = textPaint;
+
+ if (sTempAdvances == null) {
+ sTempAdvances = new AutoGrowArray.FloatArray(text.length());
+ } else if (sTempAdvances.size() < text.length()) {
+ sTempAdvances.resize(text.length());
+ }
+
+ mIsGraphemeBreak = new boolean[text.length()];
+ float[] advances = sTempAdvances.getRawArray();
+ char[] chars = TemporaryBuffer.obtain(text.length());
+
+ TextUtils.getChars(text, 0, text.length(), chars, 0);
+
+ textPaint.getTextWidths(chars, 0, text.length(), advances);
+
+ GraphemeBreak.isGraphemeBreak(advances, chars, /* start= */ 0, /* end= */ text.length(),
+ mIsGraphemeBreak);
+ TemporaryBuffer.recycle(chars);
+ }
+
+ private int previousBoundary(@IntRange(from = 0) int offset) {
+ if (offset <= 0) return DONE;
+ do {
+ --offset;
+ } while (offset > 0 && !mIsGraphemeBreak[offset]);
+ return offset;
+ }
+
+ private int nextBoundary(@IntRange(from = 0) int offset) {
+ if (offset >= mIsGraphemeBreak.length) return DONE;
+ do {
+ ++offset;
+ } while (offset < mIsGraphemeBreak.length && !mIsGraphemeBreak[offset]);
+ return offset;
}
@Override
public int previousStartBoundary(@IntRange(from = 0) int offset) {
- if (offset == 0) return DONE;
- int boundary = mTextPaint.getTextRunCursor(
- mText, 0, mText.length(), false, offset, Paint.CURSOR_BEFORE);
- return boundary == -1 ? DONE : boundary;
+ return previousBoundary(offset);
}
@Override
public int previousEndBoundary(@IntRange(from = 0) int offset) {
if (offset == 0) return DONE;
- int boundary = mTextPaint.getTextRunCursor(
- mText, 0, mText.length(), false, offset, Paint.CURSOR_BEFORE);
+ int boundary = previousBoundary(offset);
// Check that there is another cursor position before, otherwise this is not a valid
// end boundary.
- if (mTextPaint.getTextRunCursor(
- mText, 0, mText.length(), false, boundary, Paint.CURSOR_BEFORE) == -1) {
+ if (boundary == DONE || previousBoundary(boundary) == DONE) {
return DONE;
}
- return boundary == -1 ? DONE : boundary;
+ return boundary;
}
@Override
public int nextStartBoundary(@IntRange(from = 0) int offset) {
- if (offset == mText.length()) return DONE;
- int boundary = mTextPaint.getTextRunCursor(
- mText, 0, mText.length(), false, offset, Paint.CURSOR_AFTER);
+ if (offset == mIsGraphemeBreak.length) return DONE;
+ int boundary = nextBoundary(offset);
// Check that there is another cursor position after, otherwise this is not a valid
// start boundary.
- if (mTextPaint.getTextRunCursor(
- mText, 0, mText.length(), false, boundary, Paint.CURSOR_AFTER) == -1) {
+ if (boundary == DONE || nextBoundary(boundary) == DONE) {
return DONE;
}
- return boundary == -1 ? DONE : boundary;
+ return boundary;
}
@Override
public int nextEndBoundary(@IntRange(from = 0) int offset) {
- if (offset == mText.length()) return DONE;
- int boundary = mTextPaint.getTextRunCursor(
- mText, 0, mText.length(), false, offset, Paint.CURSOR_AFTER);
- return boundary == -1 ? DONE : boundary;
+ return nextBoundary(offset);
}
}
diff --git a/graphics/java/android/graphics/text/GraphemeBreak.java b/graphics/java/android/graphics/text/GraphemeBreak.java
new file mode 100644
index 0000000..f82b2fd
--- /dev/null
+++ b/graphics/java/android/graphics/text/GraphemeBreak.java
@@ -0,0 +1,59 @@
+/*
+ * Copyright (C) 2023 The Android Open Source Project
+ *
+ * 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 android.graphics.text;
+
+/** @hide */
+public class GraphemeBreak {
+ private GraphemeBreak() { }
+
+ /**
+ * Util method that checks if the offsets in given range are grapheme break.
+ *
+ * @param advances the advances of characters in the given text. It contains the font
+ * information used by the algorithm to determine the grapheme break. It's useful
+ * when some character is missing in the font. For example, if the smile emoji
+ * "0xD83D 0xDE0A" is not found in the font and is displayed as 2 characters.
+ * We can't treat it as a single grapheme cluster.
+ * @param text the text to be processed.
+ * @param start the start offset of the queried range, inclusive.
+ * @param end the end offset of the queried range, exclusive.
+ * @param isGraphemeBreak the array to receive the result. The i-th element of the
+ * array will be set to true if the offset (start + i) is a grapheme
+ * break; otherwise, it will be set to false.
+ */
+ public static void isGraphemeBreak(float[] advances, char[] text, int start, int end,
+ boolean[] isGraphemeBreak) {
+ if (start > end) {
+ throw new IllegalArgumentException("start is greater than end: start = " + start
+ + " end = " + end);
+ }
+ if (advances.length < end) {
+ throw new IllegalArgumentException("the length of advances is less than end"
+ + "advances.length = " + advances.length
+ + " end = " + end);
+ }
+ if (isGraphemeBreak.length < end - start) {
+ throw new IndexOutOfBoundsException("isGraphemeBreak doesn't have enough space to "
+ + "receive the result, isGraphemeBreak.length: " + isGraphemeBreak.length
+ + " needed space: " + (end - start));
+ }
+ nIsGraphemeBreak(advances, text, start, end, isGraphemeBreak);
+ }
+
+ private static native void nIsGraphemeBreak(float[] advances, char[] text, int start, int end,
+ boolean[] isGraphemeBreak);
+}
diff --git a/libs/hwui/Android.bp b/libs/hwui/Android.bp
index bcbe706..baf2d8d 100644
--- a/libs/hwui/Android.bp
+++ b/libs/hwui/Android.bp
@@ -374,6 +374,7 @@
"jni/text/LineBreaker.cpp",
"jni/text/MeasuredText.cpp",
"jni/text/TextShaper.cpp",
+ "jni/text/GraphemeBreak.cpp",
],
header_libs: [
diff --git a/libs/hwui/apex/LayoutlibLoader.cpp b/libs/hwui/apex/LayoutlibLoader.cpp
index b7a1563..770822a 100644
--- a/libs/hwui/apex/LayoutlibLoader.cpp
+++ b/libs/hwui/apex/LayoutlibLoader.cpp
@@ -66,6 +66,7 @@
extern int register_android_graphics_text_LineBreaker(JNIEnv* env);
extern int register_android_graphics_text_MeasuredText(JNIEnv* env);
extern int register_android_graphics_text_TextShaper(JNIEnv* env);
+extern int register_android_graphics_text_GraphemeBreak(JNIEnv* env);
extern int register_android_util_PathParser(JNIEnv* env);
extern int register_android_view_DisplayListCanvas(JNIEnv* env);
@@ -125,6 +126,8 @@
{"android.graphics.text.MeasuredText",
REG_JNI(register_android_graphics_text_MeasuredText)},
{"android.graphics.text.TextRunShaper", REG_JNI(register_android_graphics_text_TextShaper)},
+ {"android.graphics.text.GraphemeBreak",
+ REG_JNI(register_android_graphics_text_GraphemeBreak)},
{"android.util.PathParser", REG_JNI(register_android_util_PathParser)},
};
diff --git a/libs/hwui/apex/jni_runtime.cpp b/libs/hwui/apex/jni_runtime.cpp
index c509ed4..09ae7e7 100644
--- a/libs/hwui/apex/jni_runtime.cpp
+++ b/libs/hwui/apex/jni_runtime.cpp
@@ -77,6 +77,7 @@
extern int register_android_graphics_text_MeasuredText(JNIEnv* env);
extern int register_android_graphics_text_LineBreaker(JNIEnv *env);
extern int register_android_graphics_text_TextShaper(JNIEnv *env);
+extern int register_android_graphics_text_GraphemeBreak(JNIEnv* env);
extern int register_android_graphics_MeshSpecification(JNIEnv* env);
extern int register_android_graphics_Mesh(JNIEnv* env);
@@ -148,6 +149,7 @@
REG_JNI(register_android_graphics_text_MeasuredText),
REG_JNI(register_android_graphics_text_LineBreaker),
REG_JNI(register_android_graphics_text_TextShaper),
+ REG_JNI(register_android_graphics_text_GraphemeBreak),
REG_JNI(register_android_graphics_MeshSpecification),
REG_JNI(register_android_graphics_Mesh),
diff --git a/libs/hwui/jni/text/GraphemeBreak.cpp b/libs/hwui/jni/text/GraphemeBreak.cpp
new file mode 100644
index 0000000..55f03bd
--- /dev/null
+++ b/libs/hwui/jni/text/GraphemeBreak.cpp
@@ -0,0 +1,67 @@
+/*
+ * Copyright (C) 2023 The Android Open Source Project
+ *
+ * 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.
+ */
+
+#undef LOG_TAG
+#define LOG_TAG "GraphemeBreaker"
+
+#include <minikin/GraphemeBreak.h>
+#include <nativehelper/ScopedPrimitiveArray.h>
+
+#include "GraphicsJNI.h"
+
+namespace android {
+
+static void nIsGraphemeBreak(JNIEnv* env, jclass, jfloatArray advances, jcharArray text, jint start,
+ jint end, jbooleanArray isGraphemeBreak) {
+ if (start > end || env->GetArrayLength(advances) < end ||
+ env->GetArrayLength(isGraphemeBreak) < end - start) {
+ doThrowAIOOBE(env);
+ }
+
+ if (start == end) {
+ return;
+ }
+
+ ScopedFloatArrayRO advancesArray(env, advances);
+ ScopedCharArrayRO textArray(env, text);
+ ScopedBooleanArrayRW isGraphemeBreakArray(env, isGraphemeBreak);
+
+ size_t count = end - start;
+ for (size_t offset = 0; offset < count; ++offset) {
+ bool isBreak = minikin::GraphemeBreak::isGraphemeBreak(advancesArray.get(), textArray.get(),
+ start, end, start + offset);
+ isGraphemeBreakArray[offset] = isBreak ? JNI_TRUE : JNI_FALSE;
+ }
+}
+
+static const JNINativeMethod gMethods[] = {
+ {"nIsGraphemeBreak",
+ "("
+ "[F" // advances
+ "[C" // text
+ "I" // start
+ "I" // end
+ "[Z" // isGraphemeBreak
+ ")V",
+ (void*)nIsGraphemeBreak},
+};
+
+int register_android_graphics_text_GraphemeBreak(JNIEnv* env) {
+ return RegisterMethodsOrDie(env, "android/graphics/text/GraphemeBreak", gMethods,
+ NELEM(gMethods));
+}
+
+} // namespace android