Conversation
rafie
previously approved these changes
Aug 1, 2021
Codecov Report
@@ Coverage Diff @@
## master #2153 +/- ##
=======================================
Coverage 80.42% 80.42%
=======================================
Files 150 150
Lines 21997 21997
=======================================
Hits 17691 17691
Misses 4306 4306 Continue to review full report at Codecov.
|
MeirShpilraien
left a comment
There was a problem hiding this comment.
Small comments, looks very good 👍
ashtul
pushed a commit
that referenced
this pull request
Aug 2, 2021
* Improve FT.INFO complexity to O(1) * split cardinality and size for MemUsage * Per meir's review * per review (cherry picked from commit e1a8af5)
ashtul
pushed a commit
that referenced
this pull request
Aug 23, 2021
* Improve FT.INFO complexity to O(1) * split cardinality and size for MemUsage * Per meir's review * per review (cherry picked from commit e1a8af5)
ashtul
pushed a commit
that referenced
this pull request
Aug 24, 2021
…xity to O(1) (#2153) (#2201) * Add UNF flag for SORTABLE fields (#2188) * Add UNF flag for SORTABLE fields * add test (cherry picked from commit aa9808d) * Document SORTABLE UNF * Improve FT.INFO complexity to O(1) (#2153) * Improve FT.INFO complexity to O(1) * split cardinality and size for MemUsage * Per meir's review * per review (cherry picked from commit e1a8af5) * remove json test Co-authored-by: Emmanuel Keller <emmanuel.keller@redislabs.com>
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
3 participants
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Fixes #2116
The previous function iterated recursively over the whole trie and collected the size of each node including the string which defines the node ID. This operation has the complexity of O(n) and presents the lower bound of memory allocation since the memory allocated for the struct would be padded to 8 bytes (since the struct contains
void *ptr).The calculation in this PR is based on the cardinality of the trie. It multiplies it by the size of the struct, the point and char held by its parent, and a constant of 8 bytes, to compensate for the memory which is padded out.