Capstone 3: measure and speed it up
The last lesson of the course measures the project it built. The index and the queries are correct, and the question is what they cost: the build touches every word of every document, and a query touches only the words it names.
The method is the one of lesson 118: a steady clock, a repeated run and a correctness check next to the timer. A faster version that returns a different answer is not an improvement, and the last section compares the two indexes before it believes the number.
The benchmark ends the course the way it began: with a program, a command and an output, and a statement about what the numbers mean. The next step is a project of your own, and the method is the one in this lesson.
Time the build
The program builds an index over 500 documents of 50 words each, with a hundred distinct words spread across them. The clock starts before the loops and stops after them, and the print is the number of words and whether the time was positive.
The output is 100 1: the index holds a hundred words, and the build took at least a microsecond. The time itself changes with the machine and the load, which is why the page shows the check and not a claim about speed.
The build is one pass over the documents, and the map insert costs a logarithm of the words in the index. That is the cost model to compare against, not a stopwatch reading from another machine.
#include <chrono>
#include <iostream>
#include <map>
#include <set>
#include <string>
int main()
{
const int documents = 500;
const int words = 50;
auto start = std::chrono::steady_clock::now();
std::map<std::string, std::set<int>> index;
for (int document = 0; document < documents; ++document) {
for (int position = 0; position < words; ++position) {
index["word" + std::to_string((document + position) % 100)].insert(document);
}
}
auto end = std::chrono::steady_clock::now();
auto micros = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
std::cout << index.size() << ' ' << (micros > 0) << '\n';
}
g++ -std=c++23 -Wall -Wextra build.cpp -o index_build_timed
./index_build_timed
100 1
Time a thousand queries
A query is two lookups and a size addition in this program, so a thousand of them measure the lookup and the set access rather than the intersection. The total is printed as a checksum so the optimiser cannot remove the loop.
The program prints the checksum and whether the time was positive. The checksum is deterministic and the time is not, which is the pair a benchmark has to report: the answer and the cost.
A query touches the words it names, so its cost does not grow with the size of the corpus. That is the property of the inverted index that the build pays for, and the reason the structure exists.
#include <chrono>
#include <iostream>
#include <map>
#include <set>
#include <string>
int main()
{
std::map<std::string, std::set<int>> index;
for (int document = 0; document < 500; ++document) {
for (int position = 0; position < 50; ++position) {
index["word" + std::to_string((document + position) % 100)].insert(document);
}
}
auto start = std::chrono::steady_clock::now();
long checksum = 0;
for (int query = 0; query < 1000; ++query) {
auto first = index.find("word" + std::to_string(query % 100));
auto second = index.find("word" + std::to_string((query + 1) % 100));
if (first != index.end() && second != index.end()) {
checksum += static_cast<long>(first->second.size() + second->second.size());
}
}
auto end = std::chrono::steady_clock::now();
auto micros = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
std::cout << checksum << ' ' << (micros > 0) << '\n';
}
g++ -std=c++23 -Wall -Wextra queries.cpp -o index_queries_timed
./index_queries_timed
500000 1
The ordered map and the hash map
std::unordered_map looks a word up by hash instead of by comparison, which is constant time on average and loses the sorted order. The program builds the same index both ways and prints the two times and the two sizes.
The sizes are equal and the times differ from run to run. The hash map is usually faster to build because it does not keep the keys in order, and the price is the order the previous lesson's output relied on.
A real engine picks the map from the operations it needs: ordered output, a range of keys, or the fastest lookup. The benchmark is how that choice is defended, and the sizes are how a wrong choice is caught.
#include <chrono>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <unordered_map>
template <typename Index>
Index build()
{
Index index;
for (int document = 0; document < 500; ++document) {
for (int position = 0; position < 50; ++position) {
index["word" + std::to_string((document + position) % 100)].insert(document);
}
}
return index;
}
int main()
{
auto first_start = std::chrono::steady_clock::now();
auto ordered = build<std::map<std::string, std::set<int>>>();
auto first_end = std::chrono::steady_clock::now();
auto second_start = std::chrono::steady_clock::now();
auto hashed = build<std::unordered_map<std::string, std::set<int>>>();
auto second_end = std::chrono::steady_clock::now();
auto ordered_micros =
std::chrono::duration_cast<std::chrono::microseconds>(first_end - first_start).count();
auto hashed_micros =
std::chrono::duration_cast<std::chrono::microseconds>(second_end - second_start).count();
std::cout << "map " << ordered.size() << ' ' << ordered_micros << "us ";
std::cout << "hash " << hashed.size() << ' ' << hashed_micros << "us\n";
}
g++ -std=c++23 -Wall -Wextra hash.cpp -o index_hash
./index_hash
map 100 66811us hash 100 45686us
The faster one must answer the same
The optimisation is only an improvement if the answers do not change. The program builds both indexes, runs the same query on both and compares the resulting sets.
The output is same answer: the two structures hold the same documents for the word, and the check is a set comparison rather than a printed line. A benchmark without this check measures a program that may be wrong.
That is the rule the capstone ends on. The course started with a hello world and a compiler, and it ends with a measured data structure and a test that says the measurement means something.
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <unordered_map>
int main()
{
std::map<std::string, std::set<int>> ordered;
std::unordered_map<std::string, std::set<int>> hashed;
for (int document = 0; document < 100; ++document) {
for (int position = 0; position < 20; ++position) {
std::string word = "word" + std::to_string((document + position) % 10);
ordered[word].insert(document);
hashed[word].insert(document);
}
}
std::set<int> left = ordered["word3"];
std::set<int> right = hashed["word3"];
std::cout << (left == right ? "same answer" : "different answer") << '\n';
std::cout << left.size() << '\n';
}
g++ -std=c++23 -Wall -Wextra same.cpp -o index_same
./index_same
same answer
100
Exercises
- Reserve the buckets of the unordered_map with the expected word count and measure again.
- Time the build with one document and with a thousand and describe how the time grows.
- Make the benchmark print the median of five runs instead of one.
Questions
A new set of questions in a new order every time. Choose one answer for each, then check.
-
Why does the benchmark print a checksum as well as a time?
Answer
So the optimiser keeps the loop and the answer is visible
Work with no visible result can be removed, and the checksum proves it ran.
-
What does the hash map give up for its speed?
Answer
The sorted order of the keys
The unordered map trades order for an average constant-time lookup.
-
Why does the lesson compare the two indexes' answers?
Answer
A faster program that returns a different answer is not an improvement
Correctness is the first property, and the benchmark is worth nothing without it.
-
What does this program print?
#include <chrono> #include <iostream> #include <map> #include <set> #include <string> int main() { auto start = std::chrono::steady_clock::now(); std::map<std::string, std::set<int>> index; for (int document = 0; document < 500; ++document) for (int position = 0; position < 50; ++position) index["word" + std::to_string((document + position) % 100)].insert(document); auto micros = std::chrono::duration_cast<std::chrono::microseconds>(std::chrono::steady_clock::now() - start).count(); std::cout << index.size() << ' ' << (micros > 0); }Answer
100 1
There are a hundred distinct words, and the build takes at least a microsecond.
-
What does this program print?
#include <chrono> #include <iostream> #include <map> #include <set> #include <string> int main() { std::map<std::string, std::set<int>> index; for (int document = 0; document < 500; ++document) for (int position = 0; position < 50; ++position) index["word" + std::to_string((document + position) % 100)].insert(document); long checksum = 0; for (int query = 0; query < 1000; ++query) { auto a = index.find("word" + std::to_string(query % 100)); auto b = index.find("word" + std::to_string((query + 1) % 100)); checksum += static_cast<long>(a->second.size() + b->second.size()); } std::cout << checksum << ' ' << 1; }Answer
500000 1
Each of the 1000 queries adds 500 ids, and the clock reports a positive time.
-
What does this program print about the two indexes?
#include <iostream> #include <map> #include <set> #include <string> #include <unordered_map> template <typename Index> Index build() { Index index; for (int d = 0; d < 500; ++d) for (int p = 0; p < 50; ++p) index["word" + std::to_string((d + p) % 100)].insert(d); return index; } int main() { auto ordered = build<std::map<std::string, std::set<int>>>(); auto hashed = build<std::unordered_map<std::string, std::set<int>>>(); std::cout << ordered.size() << ' ' << hashed.size() << ' ' << (ordered.size() == hashed.size()); }Answer
100 100 1
Both structures hold the same hundred words, which is the size the benchmark compares.
-
What does this program print?
#include <iostream> #include <map> #include <set> #include <string> #include <unordered_map> int main() { std::map<std::string, std::set<int>> ordered; std::unordered_map<std::string, std::set<int>> hashed; for (int document = 0; document < 100; ++document) for (int position = 0; position < 20; ++position) { std::string word = "word" + std::to_string((document + position) % 10); ordered[word].insert(document); hashed[word].insert(document); } std::set<int> left = ordered["word3"]; std::set<int> right = hashed["word3"]; std::cout << (left == right ? "same answer" : "different answer"); }Answer
same answer
Both structures hold the same documents for the word, and the comparison is true.
-
Which clock does the benchmark use?
Answer
std::chrono::steady_clockThe steady clock is monotonic, so the difference of two readings is a real interval.
-
Why does a query not grow with the size of the corpus?
Answer
It touches only the words it names
The inverted index makes the lookup independent of the number of documents.
-
What is the last check of the course?
Answer
That the optimised version gives the same answer
The measurement means something only if the faster code is still correct.
The code on this page was built with g++ 15.2.0 and run on Alpine Linux 3.24.3 (x86_64) in a Docker container.
Article author: Arthur Isaev