Fix O(n^2) algorithm in the GC cleanup logic #429
Conversation
|
|
||
| auto itr = std::find(m_vecepochs.begin(), m_vecepochs.end(), m_epochNext+1); | ||
| if (itr == m_vecepochs.end()) | ||
| auto itr = std::find(m_listepochs.begin(), m_listepochs.end(), m_epochNext+1); |
There was a problem hiding this comment.
Would it be possible to use an unordered set? You could still iterate in O(N) and insert/delete in O(1), but this find operation would be O(1) instead of O(N)?
There was a problem hiding this comment.
We rely on sorted order though
There was a problem hiding this comment.
What about an ordered set? insertion/deletion would be logarithmic instead of constant, but so would this find.
There was a problem hiding this comment.
Deletion is O(log n) though, this would regress us to O(n log n) performance instead of the O(n) that we are currently so its not a net benefit.
|
I verified this fix on my cloud environment. It is now much better, The '0 qps' issue cannot be reproduced during the fullsync replication cycle. Thanks John. btw. the following changes will also help on minimizing the CPU usage during the GC cycle, i suggest we add the change to KEYDB core as well: (gc.h) class GarbageCollector |
Because deletion from a vector is a linear operation the loop inside endEpoch() is O(n^2). It was written this way to be safe while deleting the vector but can cause serious consequences during large GC epochs where large numbers of epochs need to be cleared.
The fix is to move to a list datastructure with O(1) deletion. This is the more appropriate datastructure for this operation.