As Data Grows
Also known as: scaling big data large dataset cache memory latency size scalability million billion
● Advanced4 minBefore this: How Kavach Is Fast
Speed at one size can mislead. The same reads and sorts at four sizes, from data that fits in the fastest cache to data that only fits in memory.
A thousand numbers fit in the processor's smallest, fastest cache. A hundred million fit in no cache, so every read that jumps somewhere new waits for main memory. The same programs run at each size, in Kavach, C++ and Python.
- index: 50 million reads at random places in a list. The work is the same at every size; only the list's size changes.
- sort: sorting the whole list, more work as it grows.
- Billions aren't measured: a billion whole numbers is 8 GB per language, more than the test machine holds with two running side by side.
index: 50 million reads from a list of N items
Thousands
index — 50M random reads from a list of 1,000 items · WSL Ubuntu 24.04 · i7-13700HX · kavach build (LLVM) · g++ 13 -O2 · Python 3.12 · best of 9 (Python best of 3)
Millions
index — 50M random reads from a list of 1,000,000 items · WSL Ubuntu 24.04 · i7-13700HX · kavach build (LLVM) · g++ 13 -O2 · Python 3.12 · best of 9 (Python best of 3)
Tens of millions
index — 50M random reads from a list of 10,000,000 items · WSL Ubuntu 24.04 · i7-13700HX · kavach build (LLVM) · g++ 13 -O2 · Python 3.12 · best of 9 (Python best of 3)
Hundreds of millions
index — 50M random reads from a list of 100,000,000 items · WSL Ubuntu 24.04 · i7-13700HX · kavach build (LLVM) · g++ 13 -O2 · Python 3.12 · best of 9 (Python best of 3)
sort: N whole numbers
Thousands
sort — 1,000 integers · WSL Ubuntu 24.04 · i7-13700HX · kavach build (LLVM) · g++ 13 -O2 · Python 3.12 · best of 9 (Python best of 3)
Millions
sort — 1,000,000 integers · WSL Ubuntu 24.04 · i7-13700HX · kavach build (LLVM) · g++ 13 -O2 · Python 3.12 · best of 9 (Python best of 3)
Tens of millions
sort — 10,000,000 integers · WSL Ubuntu 24.04 · i7-13700HX · kavach build (LLVM) · g++ 13 -O2 · Python 3.12 · best of 9 (Python best of 3)
Hundreds of millions
sort — 100,000,000 integers · WSL Ubuntu 24.04 · i7-13700HX · kavach build (LLVM) · g++ 13 -O2 · Python 3.12 · best of 9 (Python best of 3)
Each program takes its size as --items N, so one command reproduces every size:
git clone https://github.com/Mithlesh04/kavach && cd kavach
sh scripts/run-benchmarks.sh "" benchmarks/sizesWhat Kavach does for you
Random reads are fetched ahead
In a loop reading a big list or map at computed places, the next reads are requested from memory early.