diff options
Diffstat (limited to 'native/jni/src')
8 files changed, 98 insertions, 68 deletions
diff --git a/native/jni/src/defines.h b/native/jni/src/defines.h index 34a646f80..4605890c7 100644 --- a/native/jni/src/defines.h +++ b/native/jni/src/defines.h @@ -322,13 +322,6 @@ static inline void prof_out(void) { #define MAX_POINTER_COUNT 1 #define MAX_POINTER_COUNT_G 2 -// Queue IDs and size for DicNodesCache -#define DIC_NODES_CACHE_INITIAL_QUEUE_ID_ACTIVE 0 -#define DIC_NODES_CACHE_INITIAL_QUEUE_ID_NEXT_ACTIVE 1 -#define DIC_NODES_CACHE_INITIAL_QUEUE_ID_TERMINAL 2 -#define DIC_NODES_CACHE_INITIAL_QUEUE_ID_CACHE_FOR_CONTINUOUS_SUGGESTION 3 -#define DIC_NODES_CACHE_PRIORITY_QUEUES_SIZE 4 - template<typename T> AK_FORCE_INLINE const T &min(const T &a, const T &b) { return a < b ? a : b; } template<typename T> AK_FORCE_INLINE const T &max(const T &a, const T &b) { return a > b ? a : b; } diff --git a/native/jni/src/suggest/core/dicnode/dic_node_priority_queue.h b/native/jni/src/suggest/core/dicnode/dic_node_priority_queue.h index 2a486b804..7461f0cc6 100644 --- a/native/jni/src/suggest/core/dicnode/dic_node_priority_queue.h +++ b/native/jni/src/suggest/core/dicnode/dic_node_priority_queue.h @@ -24,20 +24,16 @@ #include "suggest/core/dicnode/dic_node.h" #include "suggest/core/dicnode/dic_node_release_listener.h" -// The biggest value among MAX_CACHE_DIC_NODE_SIZE, MAX_CACHE_DIC_NODE_SIZE_FOR_SINGLE_POINT, ... -#define MAX_DIC_NODE_PRIORITY_QUEUE_CAPACITY 310 - namespace latinime { class DicNodePriorityQueue : public DicNodeReleaseListener { public: - AK_FORCE_INLINE DicNodePriorityQueue() - : MAX_CAPACITY(MAX_DIC_NODE_PRIORITY_QUEUE_CAPACITY), - mMaxSize(MAX_DIC_NODE_PRIORITY_QUEUE_CAPACITY), mDicNodesBuf(), mUnusedNodeIndices(), - mNextUnusedNodeId(0), mDicNodesQueue() { - mDicNodesBuf.resize(MAX_CAPACITY + 1); - mUnusedNodeIndices.resize(MAX_CAPACITY + 1); - reset(); + AK_FORCE_INLINE explicit DicNodePriorityQueue(const int capacity) + : mCapacity(capacity), mMaxSize(capacity), mDicNodesBuf(), + mUnusedNodeIndices(), mNextUnusedNodeId(0), mDicNodesQueue() { + mDicNodesBuf.resize(mCapacity + 1); + mUnusedNodeIndices.resize(mCapacity + 1); + clearAndResizeToCapacity(); } // Non virtual inline destructor -- never inherit this class @@ -52,11 +48,12 @@ class DicNodePriorityQueue : public DicNodeReleaseListener { } AK_FORCE_INLINE void setMaxSize(const int maxSize) { - mMaxSize = min(maxSize, MAX_CAPACITY); + ASSERT(maxSize <= mCapacity); + mMaxSize = min(maxSize, mCapacity); } - AK_FORCE_INLINE void reset() { - clearAndResize(MAX_CAPACITY); + AK_FORCE_INLINE void clearAndResizeToCapacity() { + clearAndResize(mCapacity); } AK_FORCE_INLINE void clear() { @@ -64,27 +61,19 @@ class DicNodePriorityQueue : public DicNodeReleaseListener { } AK_FORCE_INLINE void clearAndResize(const int maxSize) { + ASSERT(maxSize <= mCapacity); while (!mDicNodesQueue.empty()) { mDicNodesQueue.pop(); } setMaxSize(maxSize); - for (int i = 0; i < MAX_CAPACITY + 1; ++i) { + for (int i = 0; i < mCapacity + 1; ++i) { mDicNodesBuf[i].remove(); mDicNodesBuf[i].setReleaseListener(this); - mUnusedNodeIndices[i] = i == MAX_CAPACITY ? NOT_A_NODE_ID : static_cast<int>(i) + 1; + mUnusedNodeIndices[i] = i == mCapacity ? NOT_A_NODE_ID : static_cast<int>(i) + 1; } mNextUnusedNodeId = 0; } - AK_FORCE_INLINE DicNode *newDicNode(DicNode *dicNode) { - DicNode *newNode = searchEmptyDicNode(); - if (newNode) { - DicNodeUtils::initByCopy(dicNode, newNode); - return newNode; - } - return 0; - } - // Copy AK_FORCE_INLINE DicNode *copyPush(DicNode *dicNode) { return copyPush(dicNode, mMaxSize); @@ -111,12 +100,12 @@ class DicNodePriorityQueue : public DicNodeReleaseListener { } mUnusedNodeIndices[index] = mNextUnusedNodeId; mNextUnusedNodeId = index; - ASSERT(index >= 0 && index < (MAX_CAPACITY + 1)); + ASSERT(index >= 0 && index < (mCapacity + 1)); } AK_FORCE_INLINE void dump() const { AKLOGI("\n\n\n\n\n==========================="); - for (int i = 0; i < MAX_CAPACITY + 1; ++i) { + for (int i = 0; i < mCapacity + 1; ++i) { if (mDicNodesBuf[i].isUsed()) { mDicNodesBuf[i].dump("QUEUE: "); } @@ -125,7 +114,7 @@ class DicNodePriorityQueue : public DicNodeReleaseListener { } private: - DISALLOW_COPY_AND_ASSIGN(DicNodePriorityQueue); + DISALLOW_IMPLICIT_CONSTRUCTORS(DicNodePriorityQueue); static const int NOT_A_NODE_ID = -1; AK_FORCE_INLINE static bool compareDicNode(DicNode *left, DicNode *right) { @@ -139,7 +128,7 @@ class DicNodePriorityQueue : public DicNodeReleaseListener { }; typedef std::priority_queue<DicNode *, std::vector<DicNode *>, DicNodeComparator> DicNodesQueue; - const int MAX_CAPACITY; + const int mCapacity; int mMaxSize; std::vector<DicNode> mDicNodesBuf; // of each element of mDicNodesBuf respectively std::vector<int> mUnusedNodeIndices; @@ -163,13 +152,12 @@ class DicNodePriorityQueue : public DicNodeReleaseListener { } AK_FORCE_INLINE DicNode *searchEmptyDicNode() { - // TODO: Currently O(n) but should be improved to O(1) - if (MAX_CAPACITY == 0) { + if (mCapacity == 0) { return 0; } if (mNextUnusedNodeId == NOT_A_NODE_ID) { AKLOGI("No unused node found."); - for (int i = 0; i < MAX_CAPACITY + 1; ++i) { + for (int i = 0; i < mCapacity + 1; ++i) { AKLOGI("Dump node availability, %d, %d, %d", i, mDicNodesBuf[i].isUsed(), mUnusedNodeIndices[i]); } @@ -185,7 +173,7 @@ class DicNodePriorityQueue : public DicNodeReleaseListener { const int index = static_cast<int>(dicNode - &mDicNodesBuf[0]); mNextUnusedNodeId = mUnusedNodeIndices[index]; mUnusedNodeIndices[index] = NOT_A_NODE_ID; - ASSERT(index >= 0 && index < (MAX_CAPACITY + 1)); + ASSERT(index >= 0 && index < (mCapacity + 1)); } AK_FORCE_INLINE DicNode *pushPoolNodeWithMaxSize(DicNode *dicNode, const int maxSize) { @@ -209,6 +197,15 @@ class DicNodePriorityQueue : public DicNodeReleaseListener { AK_FORCE_INLINE DicNode *copyPush(DicNode *dicNode, const int maxSize) { return pushPoolNodeWithMaxSize(newDicNode(dicNode), maxSize); } + + AK_FORCE_INLINE DicNode *newDicNode(DicNode *dicNode) { + DicNode *newNode = searchEmptyDicNode(); + if (newNode) { + DicNodeUtils::initByCopy(dicNode, newNode); + } + return newNode; + } + }; } // namespace latinime #endif // LATINIME_DIC_NODE_PRIORITY_QUEUE_H diff --git a/native/jni/src/suggest/core/dicnode/dic_nodes_cache.cpp b/native/jni/src/suggest/core/dicnode/dic_nodes_cache.cpp index c3d2a2e74..b6be47e90 100644 --- a/native/jni/src/suggest/core/dicnode/dic_nodes_cache.cpp +++ b/native/jni/src/suggest/core/dicnode/dic_nodes_cache.cpp @@ -23,6 +23,11 @@ namespace latinime { +// The biggest value among MAX_CACHE_DIC_NODE_SIZE, MAX_CACHE_DIC_NODE_SIZE_FOR_SINGLE_POINT, ... +const int DicNodesCache::LARGE_PRIORITY_QUEUE_CAPACITY = 310; +// Capacity for reducing memory footprint. +const int DicNodesCache::SMALL_PRIORITY_QUEUE_CAPACITY = 100; + /** * Truncates all of the dicNodes so that they start at the given commit point. * Only called for multi-word typing input. diff --git a/native/jni/src/suggest/core/dicnode/dic_nodes_cache.h b/native/jni/src/suggest/core/dicnode/dic_nodes_cache.h index 7aab0906e..8493b6a8b 100644 --- a/native/jni/src/suggest/core/dicnode/dic_nodes_cache.h +++ b/native/jni/src/suggest/core/dicnode/dic_nodes_cache.h @@ -31,25 +31,32 @@ class DicNode; */ class DicNodesCache { public: - AK_FORCE_INLINE DicNodesCache() - : mActiveDicNodes(&mDicNodePriorityQueues[DIC_NODES_CACHE_INITIAL_QUEUE_ID_ACTIVE]), - mNextActiveDicNodes(&mDicNodePriorityQueues[ - DIC_NODES_CACHE_INITIAL_QUEUE_ID_NEXT_ACTIVE]), - mTerminalDicNodes(&mDicNodePriorityQueues[DIC_NODES_CACHE_INITIAL_QUEUE_ID_TERMINAL]), - mCachedDicNodesForContinuousSuggestion(&mDicNodePriorityQueues[ - DIC_NODES_CACHE_INITIAL_QUEUE_ID_CACHE_FOR_CONTINUOUS_SUGGESTION]), - mInputIndex(0), mLastCachedInputIndex(0) { - } + AK_FORCE_INLINE explicit DicNodesCache(const bool usesLargeCapacityCache) + : mUsesLargeCapacityCache(usesLargeCapacityCache), + mDicNodePriorityQueue0(getCacheCapacity()), + mDicNodePriorityQueue1(getCacheCapacity()), + mDicNodePriorityQueue2(getCacheCapacity()), + mDicNodePriorityQueueForTerminal(MAX_RESULTS), + mActiveDicNodes(&mDicNodePriorityQueue0), + mNextActiveDicNodes(&mDicNodePriorityQueue1), + mCachedDicNodesForContinuousSuggestion(&mDicNodePriorityQueue2), + mTerminalDicNodes(&mDicNodePriorityQueueForTerminal), + mInputIndex(0), mLastCachedInputIndex(0) {} AK_FORCE_INLINE virtual ~DicNodesCache() {} AK_FORCE_INLINE void reset(const int nextActiveSize, const int terminalSize) { mInputIndex = 0; mLastCachedInputIndex = 0; - mActiveDicNodes->reset(); - mNextActiveDicNodes->clearAndResize(nextActiveSize); + // We want to use the max capacity for the current active dic node queue. + mActiveDicNodes->clearAndResizeToCapacity(); + // nextActiveSize is used to limit the next iteration's active dic node size. + const int nextActiveSizeFittingToTheCapacity = min(nextActiveSize, getCacheCapacity()); + mNextActiveDicNodes->clearAndResize(nextActiveSizeFittingToTheCapacity); mTerminalDicNodes->clearAndResize(terminalSize); - mCachedDicNodesForContinuousSuggestion->reset(); + // We want to use the max capacity for the cached dic nodes that will be used for the + // continuous suggestion. + mCachedDicNodesForContinuousSuggestion->clearAndResizeToCapacity(); } AK_FORCE_INLINE void continueSearch() { @@ -157,21 +164,35 @@ class DicNodesCache { return tmp; } + AK_FORCE_INLINE int getCacheCapacity() const { + return mUsesLargeCapacityCache ? + LARGE_PRIORITY_QUEUE_CAPACITY : SMALL_PRIORITY_QUEUE_CAPACITY; + } + AK_FORCE_INLINE void resetTemporaryCaches() { mActiveDicNodes->clear(); mNextActiveDicNodes->clear(); mTerminalDicNodes->clear(); } - DicNodePriorityQueue mDicNodePriorityQueues[DIC_NODES_CACHE_PRIORITY_QUEUES_SIZE]; + static const int LARGE_PRIORITY_QUEUE_CAPACITY; + static const int SMALL_PRIORITY_QUEUE_CAPACITY; + + const bool mUsesLargeCapacityCache; + // Instances + DicNodePriorityQueue mDicNodePriorityQueue0; + DicNodePriorityQueue mDicNodePriorityQueue1; + DicNodePriorityQueue mDicNodePriorityQueue2; + DicNodePriorityQueue mDicNodePriorityQueueForTerminal; + // Active dicNodes currently being expanded. DicNodePriorityQueue *mActiveDicNodes; // Next dicNodes to be expanded. DicNodePriorityQueue *mNextActiveDicNodes; - // Current top terminal dicNodes. - DicNodePriorityQueue *mTerminalDicNodes; // Cached dicNodes used for continuous suggestion. DicNodePriorityQueue *mCachedDicNodesForContinuousSuggestion; + // Current top terminal dicNodes. + DicNodePriorityQueue *mTerminalDicNodes; int mInputIndex; int mLastCachedInputIndex; }; diff --git a/native/jni/src/suggest/core/layout/proximity_info_state.cpp b/native/jni/src/suggest/core/layout/proximity_info_state.cpp index 7780efdfd..fbabd92f2 100644 --- a/native/jni/src/suggest/core/layout/proximity_info_state.cpp +++ b/native/jni/src/suggest/core/layout/proximity_info_state.cpp @@ -36,8 +36,8 @@ void ProximityInfoState::initInputParams(const int pointerId, const float maxPoi const int *const xCoordinates, const int *const yCoordinates, const int *const times, const int *const pointerIds, const bool isGeometric) { ASSERT(isGeometric || (inputSize < MAX_WORD_LENGTH)); - mIsContinuousSuggestionPossible = - ProximityInfoStateUtils::checkAndReturnIsContinuousSuggestionPossible( + mIsContinuousSuggestionPossible = (mHasBeenUpdatedByGeometricInput != isGeometric) ? + false : ProximityInfoStateUtils::checkAndReturnIsContinuousSuggestionPossible( inputSize, xCoordinates, yCoordinates, times, mSampledInputSize, &mSampledInputXs, &mSampledInputYs, &mSampledTimes, &mSampledInputIndice); if (DEBUG_DICT) { @@ -155,6 +155,7 @@ void ProximityInfoState::initInputParams(const int pointerId, const float maxPoi if (DEBUG_GEO_FULL) { AKLOGI("ProximityState init finished: %d points out of %d", mSampledInputSize, inputSize); } + mHasBeenUpdatedByGeometricInput = isGeometric; } // This function basically converts from a length to an edit distance. Accordingly, it's obviously diff --git a/native/jni/src/suggest/core/layout/proximity_info_state.h b/native/jni/src/suggest/core/layout/proximity_info_state.h index dbcd54488..01bf81864 100644 --- a/native/jni/src/suggest/core/layout/proximity_info_state.h +++ b/native/jni/src/suggest/core/layout/proximity_info_state.h @@ -46,10 +46,11 @@ class ProximityInfoState { : mProximityInfo(0), mMaxPointToKeyLength(0.0f), mAverageSpeed(0.0f), mHasTouchPositionCorrectionData(false), mMostCommonKeyWidthSquare(0), mKeyCount(0), mCellHeight(0), mCellWidth(0), mGridHeight(0), mGridWidth(0), - mIsContinuousSuggestionPossible(false), mSampledInputXs(), mSampledInputYs(), - mSampledTimes(), mSampledInputIndice(), mSampledLengthCache(), - mBeelineSpeedPercentiles(), mSampledNormalizedSquaredLengthCache(), mSpeedRates(), - mDirections(), mCharProbabilities(), mSampledNearKeySets(), mSampledSearchKeySets(), + mIsContinuousSuggestionPossible(false), mHasBeenUpdatedByGeometricInput(false), + mSampledInputXs(), mSampledInputYs(), mSampledTimes(), mSampledInputIndice(), + mSampledLengthCache(), mBeelineSpeedPercentiles(), + mSampledNormalizedSquaredLengthCache(), mSpeedRates(), mDirections(), + mCharProbabilities(), mSampledNearKeySets(), mSampledSearchKeySets(), mSampledSearchKeyVectors(), mTouchPositionCorrectionEnabled(false), mSampledInputSize(0), mMostProbableStringProbability(0.0f) { memset(mInputProximities, 0, sizeof(mInputProximities)); @@ -204,6 +205,7 @@ class ProximityInfoState { int mGridHeight; int mGridWidth; bool mIsContinuousSuggestionPossible; + bool mHasBeenUpdatedByGeometricInput; std::vector<int> mSampledInputXs; std::vector<int> mSampledInputYs; diff --git a/native/jni/src/suggest/core/session/dic_traverse_session.cpp b/native/jni/src/suggest/core/session/dic_traverse_session.cpp index 0ca583f90..2c2259214 100644 --- a/native/jni/src/suggest/core/session/dic_traverse_session.cpp +++ b/native/jni/src/suggest/core/session/dic_traverse_session.cpp @@ -23,6 +23,11 @@ namespace latinime { +// 256K bytes threshold is heuristically used to distinguish dictionaries containing many unigrams +// (e.g. main dictionary) from small dictionaries (e.g. contacts...) +const int DicTraverseSession::DICTIONARY_SIZE_THRESHOLD_TO_USE_LARGE_CACHE_FOR_SUGGESTION = + 256 * 1024; + void DicTraverseSession::init(const Dictionary *const dictionary, const int *prevWord, int prevWordLength, const SuggestOptions *const suggestOptions) { mDictionary = dictionary; @@ -59,8 +64,9 @@ const DictionaryStructureWithBufferPolicy *DicTraverseSession::getDictionaryStru return mDictionary->getDictionaryStructurePolicy(); } -void DicTraverseSession::resetCache(const int nextActiveCacheSize, const int maxWords) { - mDicNodesCache.reset(nextActiveCacheSize, maxWords); +void DicTraverseSession::resetCache(const int thresholdForNextActiveDicNodes, const int maxWords) { + mDicNodesCache.reset(thresholdForNextActiveDicNodes /* nextActiveSize */, + maxWords /* terminalSize */); mMultiBigramMap.clear(); mPartiallyCommited = false; } diff --git a/native/jni/src/suggest/core/session/dic_traverse_session.h b/native/jni/src/suggest/core/session/dic_traverse_session.h index 23de5cc65..fe8893590 100644 --- a/native/jni/src/suggest/core/session/dic_traverse_session.h +++ b/native/jni/src/suggest/core/session/dic_traverse_session.h @@ -37,8 +37,12 @@ class DicTraverseSession { public: // A factory method for DicTraverseSession - static AK_FORCE_INLINE void *getSessionInstance(JNIEnv *env, jstring localeStr) { - return new DicTraverseSession(env, localeStr); + static AK_FORCE_INLINE void *getSessionInstance(JNIEnv *env, jstring localeStr, + jlong dictSize) { + // To deal with the trade-off between accuracy and memory space, large cache is used for + // dictionaries larger that the threshold + return new DicTraverseSession(env, localeStr, + dictSize >= DICTIONARY_SIZE_THRESHOLD_TO_USE_LARGE_CACHE_FOR_SUGGESTION); } static AK_FORCE_INLINE void initSessionInstance(DicTraverseSession *traverseSession, @@ -54,10 +58,10 @@ class DicTraverseSession { delete traverseSession; } - AK_FORCE_INLINE DicTraverseSession(JNIEnv *env, jstring localeStr) + AK_FORCE_INLINE DicTraverseSession(JNIEnv *env, jstring localeStr, bool usesLargeCache) : mPrevWordPos(NOT_A_VALID_WORD_POS), mProximityInfo(0), - mDictionary(0), mSuggestOptions(0), mDicNodesCache(), mMultiBigramMap(), - mInputSize(0), mPartiallyCommited(false), mMaxPointerCount(1), + mDictionary(0), mSuggestOptions(0), mDicNodesCache(usesLargeCache), + mMultiBigramMap(), mInputSize(0), mPartiallyCommited(false), mMaxPointerCount(1), mMultiWordCostMultiplier(1.0f) { // NOTE: mProximityInfoStates is an array of instances. // No need to initialize it explicitly here. @@ -73,7 +77,7 @@ class DicTraverseSession { const int inputSize, const int *const inputXs, const int *const inputYs, const int *const times, const int *const pointerIds, const float maxSpatialDistance, const int maxPointerCount); - void resetCache(const int nextActiveCacheSize, const int maxWords); + void resetCache(const int thresholdForNextActiveDicNodes, const int maxWords); const DictionaryStructureWithBufferPolicy *getDictionaryStructurePolicy() const; @@ -181,6 +185,7 @@ class DicTraverseSession { DISALLOW_IMPLICIT_CONSTRUCTORS(DicTraverseSession); // threshold to start caching static const int CACHE_START_INPUT_LENGTH_THRESHOLD; + static const int DICTIONARY_SIZE_THRESHOLD_TO_USE_LARGE_CACHE_FOR_SUGGESTION; void initializeProximityInfoStates(const int *const inputCodePoints, const int *const inputXs, const int *const inputYs, const int *const times, const int *const pointerIds, const int inputSize, const float maxSpatialDistance, const int maxPointerCount); |