diff options
author | antirez <antirez@gmail.com> | 2015-02-05 10:58:28 +0100 |
---|---|---|
committer | antirez <antirez@gmail.com> | 2015-02-11 10:52:26 +0100 |
commit | 88cd9ebc0964c9daf32d97631b5eeba5fd0e8b09 (patch) | |
tree | ba38c9f7a28231551ac616ca5235d7bd02ae7fc0 | |
parent | cd0fcf11e7704c72b68a19f92e093bc5976fe7fc (diff) | |
download | redis-88cd9ebc0964c9daf32d97631b5eeba5fd0e8b09.tar.gz |
dict.c: dictGetRandomKeys() visit pattern optimization.
We use the invariant that the original table ht[0] is never populated up
to the index before the current rehashing index.
Related to issue #2306.
-rw-r--r-- | src/dict.c | 4 |
1 files changed, 4 insertions, 0 deletions
diff --git a/src/dict.c b/src/dict.c index ad74d222a..fbcdd35f8 100644 --- a/src/dict.c +++ b/src/dict.c @@ -701,6 +701,10 @@ unsigned int dictGetRandomKeys(dict *d, dictEntry **des, unsigned int count) { unsigned int i = random() & maxsizemask; while(stored < count) { for (j = 0; j < tables; j++) { + /* Invariant of the dict.c rehashing: up to the indexes already + * visited in ht[0] during the rehashing, there are no populated + * buckets, so we can skip ht[0] for indexes between 0 and idx-1. */ + if (j == 0 && i < d->rehashidx) continue; if (i >= d->ht[j].size) continue; /* Out of range for this table. */ dictEntry *he = d->ht[j].table[i]; while (he) { |