Skip to content
This repository was archived by the owner on Dec 1, 2024. It is now read-only.
/ leveldown Public archive

Commit 112906b

Browse files
vweeversvweevers
committed
Optimize db.iterator()
By using `emplace_back()`, reusing the `std::vector` cache between `iterator.next()` calls, and not advancing the iterator prematurely. That last one only matters for single reads (i.e. the first `next()` call or one made after seeking) and it doesn't improve performance compared to the previous release, just undoes a mistake in b815bea.
1 parent 7356ba4 commit 112906b

File tree

1 file changed

+67
-69
lines changed

1 file changed

+67
-69
lines changed

‎binding.cc‎

Lines changed: 67 additions & 69 deletions
Original file line numberDiff line numberDiff line change
@@ -467,7 +467,7 @@ struct Database {
467467
}
468468
}
469469

470-
bool HasPriorityWork () {
470+
bool HasPriorityWork () const {
471471
return priorityWork_ > 0;
472472
}
473473

@@ -521,8 +521,7 @@ struct BaseIterator {
521521
gt_(gt),
522522
gte_(gte),
523523
limit_(limit),
524-
count_(0),
525-
eof_(false) {
524+
count_(0) {
526525
options_ = new leveldb::ReadOptions();
527526
options_->fill_cache = fillCache;
528527
options_->snapshot = database->NewSnapshot();
@@ -588,40 +587,22 @@ struct BaseIterator {
588587
didSeek_ = true;
589588

590589
if (OutOfRange(target)) {
591-
if (reverse_) {
592-
dbIterator_->SeekToFirst();
593-
dbIterator_->Prev();
594-
} else {
595-
dbIterator_->SeekToLast();
596-
dbIterator_->Next();
597-
}
598-
599-
return;
590+
return SeekToEnd();
600591
}
601592

602593
dbIterator_->Seek(target);
603594

604595
if (dbIterator_->Valid()) {
605596
int cmp = dbIterator_->key().compare(target);
606-
if (cmp > 0 && reverse_) {
607-
dbIterator_->Prev();
608-
} else if (cmp < 0 && !reverse_) {
609-
dbIterator_->Next();
597+
if (reverse_ ? cmp > 0 : cmp < 0) {
598+
Next();
610599
}
611600
} else {
612-
if (reverse_) {
613-
dbIterator_->SeekToLast();
614-
} else {
615-
dbIterator_->SeekToFirst();
616-
}
601+
SeekToFirst();
617602
if (dbIterator_->Valid()) {
618603
int cmp = dbIterator_->key().compare(target);
619-
if (cmp > 0 && reverse_) {
620-
dbIterator_->SeekToFirst();
621-
dbIterator_->Prev();
622-
} else if (cmp < 0 && !reverse_) {
623-
dbIterator_->SeekToLast();
624-
dbIterator_->Next();
604+
if (reverse_ ? cmp > 0 : cmp < 0) {
605+
SeekToEnd();
625606
}
626607
}
627608
}
@@ -636,24 +617,34 @@ struct BaseIterator {
636617
}
637618
}
638619

639-
bool ReadOne () {
640-
if (eof_ || !dbIterator_->Valid()) {
641-
return false;
642-
}
643-
644-
if ((limit_ >= 0 && ++count_ > limit_) || OutOfRange(dbIterator_->key())) {
645-
eof_ = true;
646-
return false;
647-
}
620+
bool Valid () const {
621+
return dbIterator_->Valid() && !OutOfRange(dbIterator_->key());
622+
}
648623

649-
return true;
624+
bool Increment () {
625+
return limit_ < 0 || ++count_ <= limit_;
650626
}
651627

652-
void Advance () {
628+
void Next () {
653629
if (reverse_) dbIterator_->Prev();
654630
else dbIterator_->Next();
655631
}
656632

633+
void SeekToFirst () {
634+
if (reverse_) dbIterator_->SeekToLast();
635+
else dbIterator_->SeekToFirst();
636+
}
637+
638+
void SeekToLast () {
639+
if (reverse_) dbIterator_->SeekToFirst();
640+
else dbIterator_->SeekToLast();
641+
}
642+
643+
void SeekToEnd () {
644+
SeekToLast();
645+
Next();
646+
}
647+
657648
leveldb::Slice CurrentKey () const {
658649
return dbIterator_->key();
659650
}
@@ -666,7 +657,13 @@ struct BaseIterator {
666657
return dbIterator_->status();
667658
}
668659

669-
bool OutOfRange (const leveldb::Slice& target) {
660+
bool OutOfRange (const leveldb::Slice& target) const {
661+
// TODO: benchmark to see if this is worth it
662+
// if (upperBoundOnly && !reverse_) {
663+
// return ((lt_ != NULL && target.compare(*lt_) >= 0) ||
664+
// (lte_ != NULL && target.compare(*lte_) > 0));
665+
// }
666+
670667
return ((lt_ != NULL && target.compare(*lt_) >= 0) ||
671668
(lte_ != NULL && target.compare(*lte_) > 0) ||
672669
(gt_ != NULL && target.compare(*gt_) <= 0) ||
@@ -686,7 +683,6 @@ struct BaseIterator {
686683
std::string* gte_;
687684
int limit_;
688685
int count_;
689-
bool eof_;
690686
leveldb::ReadOptions* options_;
691687
};
692688

@@ -734,33 +730,36 @@ struct Iterator final : public BaseIterator {
734730
if (ref_ != NULL) napi_delete_reference(env, ref_);
735731
}
736732

737-
bool ReadMany (uint32_t size, std::vector<std::pair<std::string, std::string>>& result) {
733+
bool ReadMany (uint32_t size) {
734+
cache_.clear();
738735
size_t bytesRead = 0;
739736

740-
while (ReadOne()) {
741-
std::string key, value;
737+
while (true) {
738+
if (landed_) Next();
739+
if (!Valid() || !Increment()) break;
742740

743741
if (keys_) {
744742
leveldb::Slice slice = CurrentKey();
745-
key.assign(slice.data(), slice.size());
746-
bytesRead += key.size();
743+
cache_.emplace_back(slice.data(), slice.size());
744+
bytesRead += slice.size();
745+
} else {
746+
cache_.emplace_back("");
747747
}
748748

749749
if (values_) {
750750
leveldb::Slice slice = CurrentValue();
751-
value.assign(slice.data(), slice.size());
752-
bytesRead += value.size();
751+
cache_.emplace_back(slice.data(), slice.size());
752+
bytesRead += slice.size();
753+
} else {
754+
cache_.emplace_back("");
753755
}
754756

755-
Advance();
756-
result.push_back(std::make_pair(key, value));
757-
758757
if (!landed_) {
759758
landed_ = true;
760759
return true;
761760
}
762761

763-
if (bytesRead > highWaterMark_ || result.size() >= size) {
762+
if (bytesRead > highWaterMark_ || cache_.size() >= size * 2) {
764763
return true;
765764
}
766765
}
@@ -778,6 +777,7 @@ struct Iterator final : public BaseIterator {
778777
bool nexting_;
779778
bool isEnding_;
780779
BaseWorker* endWorker_;
780+
std::vector<std::string> cache_;
781781

782782
private:
783783
napi_ref ref_;
@@ -1136,18 +1136,18 @@ struct ClearWorker final : public PriorityWorker {
11361136
std::string* gt,
11371137
std::string* gte)
11381138
: PriorityWorker(env, database, callback, "leveldown.db.clear") {
1139-
baseIterator_ = new BaseIterator(database, reverse, lt, lte, gt, gte, limit, false);
1139+
iterator_ = new BaseIterator(database, reverse, lt, lte, gt, gte, limit, false);
11401140
writeOptions_ = new leveldb::WriteOptions();
11411141
writeOptions_->sync = false;
11421142
}
11431143

11441144
~ClearWorker () {
1145-
delete baseIterator_;
1145+
delete iterator_;
11461146
delete writeOptions_;
11471147
}
11481148

11491149
void DoExecute () override {
1150-
baseIterator_->SeekToRange();
1150+
iterator_->SeekToRange();
11511151

11521152
// TODO: add option
11531153
uint32_t hwm = 16 * 1024;
@@ -1156,14 +1156,14 @@ struct ClearWorker final : public PriorityWorker {
11561156
while (true) {
11571157
size_t bytesRead = 0;
11581158

1159-
while (bytesRead < hwm && baseIterator_->ReadOne()) {
1160-
leveldb::Slice key = baseIterator_->CurrentKey();
1159+
while (bytesRead <= hwm && iterator_->Valid() && iterator_->Increment()) {
1160+
leveldb::Slice key = iterator_->CurrentKey();
11611161
batch.Delete(key);
11621162
bytesRead += key.size();
1163-
baseIterator_->Advance();
1163+
iterator_->Next();
11641164
}
11651165

1166-
if (!SetStatus(baseIterator_->Status()) || bytesRead == 0) {
1166+
if (!SetStatus(iterator_->Status()) || bytesRead == 0) {
11671167
break;
11681168
}
11691169

@@ -1174,11 +1174,11 @@ struct ClearWorker final : public PriorityWorker {
11741174
batch.Clear();
11751175
}
11761176

1177-
baseIterator_->End();
1177+
iterator_->End();
11781178
}
11791179

11801180
private:
1181-
BaseIterator* baseIterator_;
1181+
BaseIterator* iterator_;
11821182
leveldb::WriteOptions* writeOptions_;
11831183
};
11841184

@@ -1536,22 +1536,21 @@ struct NextWorker final : public BaseWorker {
15361536

15371537
// Limit the size of the cache to prevent starving the event loop
15381538
// in JS-land while we're recursively calling process.nextTick().
1539-
ok_ = iterator_->ReadMany(1000, result_);
1539+
ok_ = iterator_->ReadMany(1000);
15401540

15411541
if (!ok_) {
15421542
SetStatus(iterator_->Status());
15431543
}
15441544
}
15451545

15461546
void HandleOKCallback (napi_env env, napi_value callback) override {
1547-
size_t arraySize = result_.size() * 2;
1547+
size_t arraySize = iterator_->cache_.size();
15481548
napi_value jsArray;
15491549
napi_create_array_with_length(env, arraySize, &jsArray);
15501550

1551-
for (size_t idx = 0; idx < result_.size(); ++idx) {
1552-
std::pair<std::string, std::string> row = result_[idx];
1553-
std::string key = row.first;
1554-
std::string value = row.second;
1551+
for (size_t idx = 0; idx < iterator_->cache_.size(); idx += 2) {
1552+
std::string key = iterator_->cache_[idx];
1553+
std::string value = iterator_->cache_[idx + 1];
15551554

15561555
napi_value returnKey;
15571556
if (iterator_->keyAsBuffer_) {
@@ -1568,8 +1567,8 @@ struct NextWorker final : public BaseWorker {
15681567
}
15691568

15701569
// put the key & value in a descending order, so that they can be .pop:ed in javascript-land
1571-
napi_set_element(env, jsArray, static_cast<int>(arraySize - idx * 2 - 1), returnKey);
1572-
napi_set_element(env, jsArray, static_cast<int>(arraySize - idx * 2 - 2), returnValue);
1570+
napi_set_element(env, jsArray, static_cast<int>(arraySize - idx - 1), returnKey);
1571+
napi_set_element(env, jsArray, static_cast<int>(arraySize - idx - 2), returnValue);
15731572
}
15741573

15751574
napi_value argv[3];
@@ -1592,7 +1591,6 @@ struct NextWorker final : public BaseWorker {
15921591
}
15931592

15941593
Iterator* iterator_;
1595-
std::vector<std::pair<std::string, std::string> > result_;
15961594
bool ok_;
15971595
};
15981596

0 commit comments

Comments
 (0)