Optimize ZRANK by avoiding string comparisons during skiplist traversal #14636
Conversation
This optimization is based on Valkey PR redis#1389. The key improvements are: 1. Repurpose level[0].span to store node height (since it's always 1 or 0) 2. Add helper functions to manage span and height access 3. Implement zslGetRankByNode() to calculate rank by walking upward from a node 4. Add zsetGetSLNodeByEntry() to get skiplist node directly from dict entry 5. Update zsetRank() to use the optimized path for skiplist encoding Performance improvements (based on Valkey benchmarks with 1M elements): - Throughput: 8-45% improvement (best with fewer unique scores) - Latency: 6-30% reduction (best with fewer unique scores) The optimization avoids expensive string comparisons by using pointer arithmetic to get the skiplist node directly from the dict entry, then walking upward through the skiplist using stored node heights. All existing tests pass. No changes to command syntax, RDB format, AOF format, or replication protocol.
| /* Span is the number of elements between this node and the next node at this level. | ||
| * At level 0, span is always 1 (or 0 for the last node), so we repurpose it to store | ||
| * the node's level. This enables O(1) access to node level for rank calculations. */ | ||
| unsigned long span; |
There was a problem hiding this comment.
This assumes level-0 spans are always 1 or 0, which holds for a standard skiplist (every node connects forward at L0 unless it's the tail). But confirm: Does insertion/deletion ever set non-trivial L0 spans? If so, this could corrupt ranks.
There was a problem hiding this comment.
The suggested code is designed to use level[0].span exclusively for the node’s metadata. Needs to be verified it meets the expected behavior.
| /* Get the skiplist node from a dict entry. The dict value points to &node->score, | ||
| * so we use pointer arithmetic to get the node address. This enables O(1) lookup | ||
| * of the skiplist node from the hash table, used by optimized ZRANK. */ | ||
| static inline zskiplistNode *zsetGetSLNodeByEntry(dictEntry *de) { |
There was a problem hiding this comment.
Unit Tests: New TCL tests for ZRANK on large zsets (e.g., 1M elements, random inserts) verifying ranks match pre-PR. Include tail-node and max-height cases.
There was a problem hiding this comment.
I verified it manually and also got covered by benchmark tests. Not sure if tcl is the right place to maintain such tests. ... The good news is that this kind of corruption is expected to be revealed fairly quickly.
3 participants
This optimization is based on Valkey valkey-io/valkey#1389
Summary
This PR optimizes the ZRANK command by eliminating expensive string comparisons during skiplist traversal.
The issue
The original ZRANK implementation:
String comparisons are expensive as they require accessing multiple memory locations and comparing byte-by-byte. - Performance profiling showed these comparisons can consume up to 20% of the rank calculation time.
The Optimization
Leverages the fact that the hash table value points directly to &node->score in the skiplist node. Using pointer arithmetic, we can:
Get the skiplist node directly from the hash table entry (O(1) lookup)
Key insight: At level 0, the span is always 1 (or 0 for the last node), so we repurpose level[0].span to store the node's height. This enables O(1) access to node height without adding new fields.
This optimization improves ZRANK performance by 2-14% across different data distributions (asissted lua and randomize zrank scores. TPS):