Fix the performance issue on suggesting aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
Bug: 6576793
Change-Id: I46f56654cd25dc28668ad75ac71e0e3beb8cdcf3
diff --git a/native/jni/src/correction.cpp b/native/jni/src/correction.cpp
index fe3f292..d56938d 100644
--- a/native/jni/src/correction.cpp
+++ b/native/jni/src/correction.cpp
@@ -109,6 +109,10 @@
initEditDistance(mEditDistanceTable);
}
+void Correction::resetCorrection() {
+ mTotalTraverseCount = 0;
+}
+
void Correction::initCorrection(const ProximityInfo *pi, const int inputLength,
const int maxDepth) {
mProximityInfo = pi;
diff --git a/native/jni/src/correction.h b/native/jni/src/correction.h
index 1ac4b87..3300a84 100644
--- a/native/jni/src/correction.h
+++ b/native/jni/src/correction.h
@@ -94,6 +94,7 @@
}
Correction(const int typedLetterMultiplier, const int fullWordMultiplier);
+ void resetCorrection();
void initCorrection(
const ProximityInfo *pi, const int inputLength, const int maxWordLength);
void initCorrectionState(const int rootPos, const int childCount, const bool traverseAll);
@@ -129,6 +130,10 @@
bool needsToPrune() const;
+ int pushAndGetTotalTraverseCount() {
+ return ++mTotalTraverseCount;
+ }
+
int getFreqForSplitMultipleWords(
const int *freqArray, const int *wordLengthArray, const int wordCount,
const bool isSpaceProximity, const unsigned short *word);
@@ -200,6 +205,8 @@
int mTerminalOutputIndex;
int mMaxErrors;
+ uint8_t mTotalTraverseCount;
+
// The following arrays are state buffer.
unsigned short mWord[MAX_WORD_LENGTH_INTERNAL];
int mDistances[MAX_WORD_LENGTH_INTERNAL];
diff --git a/native/jni/src/defines.h b/native/jni/src/defines.h
index 19f8434..b61ebd2 100644
--- a/native/jni/src/defines.h
+++ b/native/jni/src/defines.h
@@ -24,6 +24,7 @@
#define AKLOGI ALOGI
#define DUMP_WORD(word, length) do { dumpWord(word, length); } while(0)
+#define DUMP_WORD_INT(word, length) do { dumpWordInt(word, length); } while(0)
static inline void dumpWord(const unsigned short* word, const int length) {
static char charBuf[50];
@@ -35,10 +36,21 @@
AKLOGI("[ %s ]", charBuf);
}
+static inline void dumpWordInt(const int* word, const int length) {
+ static char charBuf[50];
+
+ for (int i = 0; i < length; ++i) {
+ charBuf[i] = word[i];
+ }
+ charBuf[length] = 0;
+ AKLOGI("i[ %s ]", charBuf);
+}
+
#else
#define AKLOGE(fmt, ...)
#define AKLOGI(fmt, ...)
#define DUMP_WORD(word, length)
+#define DUMP_WORD_INT(word, length)
#endif
#ifdef FLAG_DO_PROFILE
@@ -223,6 +235,10 @@
#define SUB_QUEUE_MAX_COUNT 10
#define SUB_QUEUE_MIN_WORD_LENGTH 4
#define MULTIPLE_WORDS_SUGGESTION_MAX_WORDS 10
+// TODO: Remove this limitation
+#define MULTIPLE_WORDS_SUGGESTION_MAX_WORD_LENGTH 12
+// TODO: Remove this limitation
+#define MULTIPLE_WORDS_SUGGESTION_MAX_TOTAL_TRAVERSE_COUNT 110
#define MULTIPLE_WORDS_DEMOTION_RATE 80
#define MIN_INPUT_LENGTH_FOR_THREE_OR_MORE_WORDS_CORRECTION 6
diff --git a/native/jni/src/unigram_dictionary.cpp b/native/jni/src/unigram_dictionary.cpp
index efe9c4f..690d8dc 100644
--- a/native/jni/src/unigram_dictionary.cpp
+++ b/native/jni/src/unigram_dictionary.cpp
@@ -177,6 +177,7 @@
queuePool->clearAll();
Correction* masterCorrection = correction;
+ correction->resetCorrection();
if (BinaryFormat::REQUIRES_GERMAN_UMLAUT_PROCESSING & FLAGS)
{ // Incrementally tune the word and try all possibilities
int codesBuffer[getCodesBufferSize(codes, codesSize)];
@@ -301,6 +302,7 @@
const int *yCoordinates, const int *codes, const int inputLength, Correction *correction) {
if (DEBUG_DICT) {
AKLOGI("initSuggest");
+ DUMP_WORD_INT(codes, inputLength);
}
proximityInfo->setInputParams(codes, inputLength, xCoordinates, yCoordinates);
const int maxDepth = min(inputLength * MAX_DEPTH_MULTIPLIER, MAX_WORD_LENGTH);
@@ -324,6 +326,16 @@
const int inputLength, const std::map<int, int> *bigramMap, const uint8_t *bigramFilter,
Correction *correction, WordsPriorityQueuePool *queuePool,
const bool doAutoCompletion, const int maxErrors, const int currentWordIndex) {
+ uint8_t totalTraverseCount = correction->pushAndGetTotalTraverseCount();
+ if (DEBUG_DICT) {
+ AKLOGI("Traverse count %d", totalTraverseCount);
+ }
+ if (totalTraverseCount > MULTIPLE_WORDS_SUGGESTION_MAX_TOTAL_TRAVERSE_COUNT) {
+ if (DEBUG_DICT) {
+ AKLOGI("Abort traversing %d", totalTraverseCount);
+ }
+ return;
+ }
// TODO: Remove setCorrectionParams
correction->setCorrectionParams(0, 0, 0,
-1 /* spaceProximityPos */, -1 /* missingSpacePos */, useFullEditDistance,
@@ -410,7 +422,7 @@
}
}
-bool UnigramDictionary::getSubStringSuggestion(
+int UnigramDictionary::getSubStringSuggestion(
ProximityInfo *proximityInfo, const int *xcoordinates, const int *ycoordinates,
const int *codes, const bool useFullEditDistance, Correction *correction,
WordsPriorityQueuePool* queuePool, const int inputLength,
@@ -449,8 +461,9 @@
}
}
WordsPriorityQueue* queue = queuePool->getSubQueue(currentWordIndex, inputWordLength);
- if (!queue || queue->size() < 1) {
- return false;
+ // TODO: Return the correct value depending on doAutoCompletion
+ if (!queue || queue->size() <= 0) {
+ return FLAG_MULTIPLE_SUGGEST_ABORT;
}
int score = 0;
const float ns = queue->getHighestNormalizedScore(
@@ -463,7 +476,7 @@
// threshold.
if (ns < TWO_WORDS_CORRECTION_WITH_OTHER_ERROR_THRESHOLD
|| nextWordLength < SUB_QUEUE_MIN_WORD_LENGTH) {
- return false;
+ return FLAG_MULTIPLE_SUGGEST_SKIP;
}
freq = score >> (nextWordLength + TWO_WORDS_PLUS_OTHER_ERROR_CORRECTION_DEMOTION_DIVIDER);
}
@@ -474,7 +487,7 @@
}
if (freq <= 0 || nextWordLength <= 0
|| MAX_WORD_LENGTH <= (outputWordStartPos + nextWordLength)) {
- return false;
+ return FLAG_MULTIPLE_SUGGEST_SKIP;
}
for (int i = 0; i < nextWordLength; ++i) {
outputWord[outputWordStartPos + i] = tempOutputWord[i];
@@ -491,7 +504,7 @@
if ((inputWordStartPos + inputWordLength) < inputLength) {
if (outputWordStartPos + nextWordLength >= MAX_WORD_LENGTH) {
- return false;
+ return FLAG_MULTIPLE_SUGGEST_SKIP;
}
outputWord[tempOutputWordLength] = SPACE;
if (outputWordLength) {
@@ -512,7 +525,7 @@
}
addWord(outputWord, tempOutputWordLength, pairFreq, queuePool->getMasterQueue());
}
- return true;
+ return FLAG_MULTIPLE_SUGGEST_CONTINUE;
}
void UnigramDictionary::getMultiWordsSuggestionRec(ProximityInfo *proximityInfo,
@@ -542,11 +555,18 @@
// Current word
int inputWordStartPos = startInputPos;
int inputWordLength = i - startInputPos;
- if (!getSubStringSuggestion(proximityInfo, xcoordinates, ycoordinates, codes,
- useFullEditDistance, correction, queuePool, inputLength, hasAutoCorrectionCandidate,
- startWordIndex, inputWordStartPos, inputWordLength, outputWordLength,
- true /* not used */, freqArray, wordLengthArray, outputWord,
- &tempOutputWordLength)) {
+ if (inputWordLength > MULTIPLE_WORDS_SUGGESTION_MAX_WORD_LENGTH) {
+ break;
+ }
+ const int suggestionFlag = getSubStringSuggestion(proximityInfo, xcoordinates, ycoordinates,
+ codes, useFullEditDistance, correction, queuePool, inputLength,
+ hasAutoCorrectionCandidate, startWordIndex, inputWordStartPos, inputWordLength,
+ outputWordLength, true /* not used */, freqArray, wordLengthArray, outputWord,
+ &tempOutputWordLength);
+ if (suggestionFlag == FLAG_MULTIPLE_SUGGEST_ABORT) {
+ // TODO: break here
+ continue;
+ } else if (suggestionFlag == FLAG_MULTIPLE_SUGGEST_SKIP) {
continue;
}
@@ -557,10 +577,11 @@
// Missing space
inputWordStartPos = i;
inputWordLength = inputLength - i;
- if(!getSubStringSuggestion(proximityInfo, xcoordinates, ycoordinates, codes,
+ if(getSubStringSuggestion(proximityInfo, xcoordinates, ycoordinates, codes,
useFullEditDistance, correction, queuePool, inputLength, hasAutoCorrectionCandidate,
startWordIndex + 1, inputWordStartPos, inputWordLength, tempOutputWordLength,
- false /* missing space */, freqArray, wordLengthArray, outputWord, 0)) {
+ false /* missing space */, freqArray, wordLengthArray, outputWord, 0)
+ != FLAG_MULTIPLE_SUGGEST_CONTINUE) {
getMultiWordsSuggestionRec(proximityInfo, xcoordinates, ycoordinates, codes,
useFullEditDistance, inputLength, correction, queuePool,
hasAutoCorrectionCandidate, inputWordStartPos, startWordIndex + 1,
diff --git a/native/jni/src/unigram_dictionary.h b/native/jni/src/unigram_dictionary.h
index b708940..a1a8299 100644
--- a/native/jni/src/unigram_dictionary.h
+++ b/native/jni/src/unigram_dictionary.h
@@ -70,6 +70,9 @@
static const int DEFAULT_MAX_ERRORS = 2;
static const int MAX_ERRORS_FOR_TWO_WORDS = 1;
+ static const int FLAG_MULTIPLE_SUGGEST_ABORT = 0;
+ static const int FLAG_MULTIPLE_SUGGEST_SKIP = 1;
+ static const int FLAG_MULTIPLE_SUGGEST_CONTINUE = 2;
UnigramDictionary(const uint8_t* const streamStart, int typedLetterMultipler,
int fullWordMultiplier, int maxWordLength, int maxWords, const unsigned int flags);
int getFrequency(const int32_t* const inWord, const int length) const;
@@ -127,7 +130,7 @@
ProximityInfo *proximityInfo, unsigned short *word);
int getMostFrequentWordLikeInner(const uint16_t* const inWord, const int length,
short unsigned int *outWord);
- bool getSubStringSuggestion(
+ int getSubStringSuggestion(
ProximityInfo *proximityInfo, const int *xcoordinates, const int *ycoordinates,
const int *codes, const bool useFullEditDistance, Correction *correction,
WordsPriorityQueuePool* queuePool, const int inputLength,