8000 perf: reduce storage requirements for bounded btreemaps by ~25%. by ielashi · Pull Request #130 · dfinity/stable-structures · GitHub
[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to content

perf: reduce storage requirements for bounded btreemaps by ~25%. #130

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Merged
merged 2 commits into from
Sep 15, 2023
Merged

perf: reduce storage requirements for bounded btreemaps by ~25%. #130

merged 2 commits into from
Sep 15, 2023

Conversation

ielashi
Copy link
Contributor
@ielashi ielashi commented Sep 14, 2023

I did an analysis on how big node entries are. A node can have at most 11 entries, but ~70% of nodes contain <= 8 entries. With that information, I was able to reduce the page size in BTreeMap V2 in the case where the keys and values are both bounded, resulting in a storage saving of ~25%.

The report, generated by our new benchmarking framework, clearly shows the gains. V2 benchmarks saw a decline in the number of stable pages needed without compromising performance.

Benchmark: btreemap_insert_10mib_values
  measurements:
    instructions: 278228334 (0.00%) (no change)
    node_load_v2: 10377468 (0.00%) (no change)
    node_save_v2: 245958554 (0.00%) (no change)
    stable_memory_size: 33 (0.00%) (no change)

---------------------------------------------------

Benchmark: btreemap_insert_blob_4_1024
  measurements:
    instructions: 938860652 (0.00%) (no change)
    node_load_v1: 246219371 (0.00%) (no change)
    node_save_v1: 370094431 (0.00%) (no change)
    stable_memory_size: 124 (0.00%) (no change)

---------------------------------------------------

Benchmark: btreemap_insert_blob_4_1024_v2
  measurements:
    instructions: 1284860075 (-0.01%) (change within noise threshold)
    node_load_v2: 302568355 (0.00%) (no change)
    node_save_v2: 661255273 (-0.02%) (change within noise threshold)
    stable_memory_size: 93 (improved by 25.00%)

---------------------------------------------------

Benchmark: btreemap_insert_blob_8_1024
  measurements:
    instructions: 1084934108 (0.00%) (no change)
    node_load_v1: 286595797 (0.00%) (no change)
    node_save_v1: 394314301 (0.00%) (no change)
    stable_memory_size: 184 (0.00%) (no change)

---------------------------------------------------

Benchmark: btreemap_insert_blob_8_1024_v2
  measurements:
    instructions: 1458496280 (-0.01%) (change within noise threshold)
    node_load_v2: 344800342 (0.00%) (change within noise threshold)
    node_save_v2: 711692000 (-0.03%) (change within noise threshold)
    stable_memory_size: 139 (improved by 24.46%)

---------------------------------------------------

Benchmark: btreemap_insert_blob_16_1024
  measurements:
    instructions: 1177421502 (0.00%) (no change)
    node_load_v1: 362914338 (0.00%) (no change)
    node_save_v1: 403464072 (0.00%) (no change)
    stable_memory_size: 216 (0.00%) (no change)

---------------------------------------------------

Benchmark: btreemap_insert_blob_16_1024_v2
  measurements:
    instructions: 1588123192 (-0.02%) (change within noise threshold)
    node_load_v2: 440221819 (0.00%) (change within noise threshold)
    node_save_v2: 739898082 (-0.04%) (change within noise threshold)
    stable_memory_size: 162 (improved by 25.00%)

---------------------------------------------------

Benchmark: btreemap_insert_blob_32_1024
  measurements:
    instructions: 1224612399 (0.00%) (no change)
    node_load_v1: 390780802 (0.00%) (no change)
    node_save_v1: 415826600 (0.00%) (no change)
    stable_memory_size: 231 (0.00%) (no change)

---------------------------------------------------

Benchmark: btreemap_insert_blob_32_1024_v2
  measurements:
    instructions: 1655605924 (-0.02%) (change within noise threshold)
    node_load_v2: 477569310 (0.00%) (no change)
    node_save_v2: 768954087 (-0.03%) (change within noise threshold)
    stable_memory_size: 174 (improved by 24.68%)

---------------------------------------------------

Benchmark: btreemap_insert_blob_64_1024
  measurements:
    instructions: 1464177820 (0.00%) (no change)
    node_load_v1: 595998298 (0.00%) (no change)
    node_save_v1: 418743231 (0.00%) (no change)
    stable_memory_size: 246 (0.00%) (no change)

---------------------------------------------------

Benchmark: btreemap_insert_blob_64_1024_v2
  measurements:
    instructions: 1928636138 (-0.01%) (change within noise threshold)
    node_load_v2: 692235029 (0.00%) (no change)
    node_save_v2: 785237958 (-0.03%) (change within noise threshold)
    stable_memory_size: 184 (improved by 25.20%)

---------------------------------------------------

Benchmark: btreemap_insert_blob_128_1024
  measurements:
    instructions: 1730313092 (0.00%) (no change)
    node_load_v1: 818923030 (0.00%) (no change)
    node_save_v1: 424573804 (0.00%) (no change)
    stable_memory_size: 261 (0.00%) (no change)

---------------------------------------------------

Benchmark: btreemap_insert_blob_128_1024_v2
  measurements:
    instructions: 2230592033 (-0.01%) (change within noise threshold)
    node_load_v2: 916541484 (0.00%) (no change)
    node_save_v2: 814064656 (-0.03%) (change within noise threshold)
    stable_memory_size: 196 (improved by 24.90%)

---------------------------------------------------

Benchmark: btreemap_insert_blob_256_1024
  measurements:
    instructions: 2255818313 (0.00%) (no change)
    node_load_v1: 1272224795 (0.00%) (no change)
    node_save_v1: 430174789 (0.00%) (no change)
    stable_memory_size: 293 (0.00%) (no change)

---------------------------------------------------

Benchmark: btreemap_insert_blob_256_1024_v2
  measurements:
    instructions: 2794429751 (-0.01%) (change within noise threshold)
    node_load_v2: 1368657545 (0.00%) (no change)
    node_save_v2: 851897559 (-0.02%) (change within noise threshold)
    stable_memory_size: 220 (improved by 24.91%)

---------------------------------------------------

Benchmark: btreemap_insert_blob_512_1024
  measurements:
    instructions: 3306816049 (0.00%) (no change)
    node_load_v1: 2162164471 (0.00%) (no change)
    node_save_v1: 447463180 (0.00%) (no change)
    stable_memory_size: 352 (0.00%) (no change)

---------------------------------------------------

Benchmark: btreemap_insert_blob_512_1024_v2
  measurements:
    instructions: 3902055470 (-0.00%) (change within noise threshold)
    node_load_v2: 2249757429 (0.00%) (no change)
    node_save_v2: 953602203 (-0.01%) (change within noise threshold)
    stable_memory_size: 264 (improved by 25.00%)

---------------------------------------------------

Benchmark: btreemap_insert_u64_u64
  measurements:
    instructions: 771845193 (0.00%) (no change)
    node_load_v1: 274520203 (0.00%) (no change)
    node_save_v1: 266527196 (0.00%) (no change)
    stable_memory_size: 8 (0.00%) (no change)

---------------------------------------------------

Benchmark: btreemap_insert_u64_u64_v2
  measurements:
    instructions: 848175865 (0.67%) (change within noise threshold)
    node_load_v2: 324943098 (1.24%) (change within noise threshold)
    node_save_v2: 295936099 (0.23%) (change within noise threshold)
    stable_memory_size: 7 (improved by 12.50%)

---------------------------------------------------

Benchmark: btreemap_insert_u64_blob_8
  measurements:
    instructions: 750190911 (0.00%) (no change)
    node_load_v1: 276866073 (0.00%) (no change)
    node_save_v1: 255664450 (0.00%) (no change)
    stable_memory_size: 8 (0.00%) (no change)

---------------------------------------------------

Benchmark: btreemap_insert_u64_blob_8_v2
  measurements:
    instructions: 806917372 (0.11%) (change within noise threshold)
    node_load_v2: 320660408 (0.10%) (change within noise threshold)
    node_save_v2: 272412341 (0.12%) (change within noise threshold)
    stable_memory_size: 6 (improved by 25.00%)

---------------------------------------------------

Benchmark: btreemap_insert_blob_8_u64
  measurements:
    instructions: 684689096 (0.00%) (no change)
    node_load_v1: 277937358 (0.00%) (no change)
    node_save_v1: 189388784 (0.00%) (no change)
    stable_memory_size: 7 (0.00%) (no change)

---------------------------------------------------

Benchmark: btreemap_insert_blob_8_u64_v2
  measurements:
    instructions: 805533962 (0.84%) (change within noise threshold)
    node_load_v2: 358481378 (1.04%) (change within noise threshold)
    node_save_v2: 230438833 (0.29%) (change within noise threshold)
    stable_memory_size: 5 (improved by 28.57%)

---------------------------------------------------

Benchmark: btreemap_get_blob_4_1024
  measurements:
    instructions: 401718154 (0.00%) (no change)
    node_load_v1: 259275488 (0.00%) (no change)
    stable_memory_size: 124 (0.00%) (no change)

---------------------------------------------------

Benchmark: btreemap_get_blob_4_1024_v2
  measurements:
    instructions: 480241876 (0.00%) (no change)
    node_load_v2: 329436785 (0.00%) (no change)
    stable_memory_size: 93 (improved by 25.00%)

---------------------------------------------------

Benchmark: btreemap_get_blob_8_1024
  measurements:
    instructions: 473964224 (0.00%) (no change)
    node_load_v1: 304258691 (0.00%) (no change)
    stable_memory_size: 184 (0.00%) (no change)

---------------------------------------------------

Benchmark: btreemap_get_blob_8_1024_v2
  measurements:
    instructions: 549627424 (0.00%) (no change)
    node_load_v2: 371386524 (0.00%) (no change)
    stable_memory_size: 139 (improved by 24.46%)

---------------------------------------------------

Benchmark: btreemap_get_blob_16_1024
  measurements:
    instructions: 553966238 (0.00%) (no change)
    node_load_v1: 383794822 (0.00%) (no change)
    stable_memory_size: 216 (0.00%) (no change)

---------------------------------------------------

Benchmark: btreemap_get_blob_16_1024_v2
  measurements:
    instructions: 637391324 (0.00%) (no change)
    node_load_v2: 464133703 (0.00%) (no change)
    stable_memory_size: 162 (improved by 25.00%)

---------------------------------------------------

Benchmark: btreemap_get_blob_32_1024
  measurements:
    instructions: 591716960 (0.00%) (no change)
    node_load_v1: 410436451 (0.00%) (no change)
    stable_memory_size: 231 (0.00%) (no change)

---------------------------------------------------

Benchmark: btreemap_get_blob_32_1024_v2
  measurements:
    instructions: 679662006 (0.00%) (no change)
    node_load_v2: 495574095 (0.00%) (no change)
    stable_memory_size: 174 (improved by 24.68%)

---------------------------------------------------

Benchmark: btreemap_get_blob_64_1024
  measurements:
    instructions: 814621589 (0.00%) (no change)
    node_load_v1: 627796876 (0.00%) (no change)
    stable_memory_size: 246 (0.00%) (no change)

---------------------------------------------------

Benchmark: btreemap_get_blob_64_1024_v2
  measurements:
    instructions: 902934555 (0.00%) (no change)
    node_load_v2: 708745655 (0.00%) (no change)
    stable_memory_size: 184 (improved by 25.20%)

---------------------------------------------------

Benchmark: btreemap_get_blob_128_1024
  measurements:
    instructions: 1036041908 (0.00%) (no change)
    node_load_v1: 839537545 (0.00%) (no change)
    stable_memory_size: 261 (0.00%) (no change)

---------------------------------------------------

Benchmark: btreemap_get_blob_128_1024_v2
  measurements:
    instructions: 1140173768 (0.00%) (no change)
    node_load_v2: 933785784 (0.00%) (no change)
    stable_memory_size: 196 (improved by 24.90%)

---------------------------------------------------

Benchmark: btreemap_get_u64_u64
  measurements:
    instructions: 412643077 (0.00%) (no change)
    node_load_v1: 290922161 (0.00%) (no change)
    stable_memory_size: 8 (0.00%) (no change)

---------------------------------------------------

Benchmark: btreemap_get_u64_u64_v2
  measurements:
    instructions: 477401878 (1.60%) (change within noise threshold)
    node_load_v2: 347289827 (1.76%) (change within noise threshold)
    stable_memory_size: 7 (improved by 12.50%)

---------------------------------------------------

Benchmark: btreemap_get_u64_blob_8
  measurements:
    instructions: 409579480 (0.00%) (no change)
    node_load_v1: 292395667 (0.00%) (no change)
    stable_memory_size: 8 (0.00%) (no change)

---------------------------------------------------

Benchmark: btreemap_get_u64_blob_8_v2
  measurements:
    instructions: 465392548 (0.00%) (no change)
    node_load_v2: 342799065 (0.00%) (no change)
    stable_memory_size: 6 (improved by 25.00%)

---------------------------------------------------

Benchmark: btreemap_get_blob_8_u64
  measurements:
    instructions: 426482546 (0.00%) (no change)
    node_load_v1: 294602061 (0.00%) (no change)
    stable_memory_size: 7 (0.00%) (no change)

---------------------------------------------------

Benchmark: btreemap_get_blob_8_u64_v2
  measurements:
    instructions: 523481237 (regressed by 2.27%)
    node_load_v2: 383093469 (regressed by 2.43%)
    stable_memory_size: 5 (improved by 28.57%)

---------------------------------------------------

Benchmark: btreemap_get_blob_256_1024
  measurements:
    instructions: 1523593515 (0.00%) (no change)
    node_load_v1: 1301924960 (0.00%) (no change)
    stable_memory_size: 293 (0.00%) (no change)

---------------------------------------------------

Benchmark: btreemap_get_blob_256_1024_v2
  measurements:
    instructions: 1628351182 (0.00%) (no change)
    node_load_v2: 1392993062 (0.00%) (no change)
    stable_memory_size: 220 (improved by 24.91%)

---------------------------------------------------

Benchmark: btreemap_get_blob_512_1024
  measurements:
    instructions: 2489215042 (0.00%) (no change)
    node_load_v1: 2219164452 (0.00%) (no change)
    stable_memory_size: 352 (0.00%) (no change)

---------------------------------------------------

Benchmark: btreemap_get_blob_512_1024_v2
  measurements:
    instructions: 2596163236 (0.00%) (no change)
    node_load_v2: 2312346281 (0.00%) (no change)
    stable_memory_size: 264 (improved by 25.00%)

---------------------------------------------------

Benchmark: btreemap_remove_blob_4_1024
  measurements:
    instructions: 1006445824 (0.00%) (no change)
    node_load_v1: 269171795 (0.00%) (no change)
    node_save_v1: 421165272 (0.00%) (no change)
    stable_memory_size: 124 (0.00%) (no change)

---------------------------------------------------

Benchmark: btreemap_remove_blob_4_1024_v2
  measurements:
    instructions: 1417601784 (-0.00%) (change within noise threshold)
    node_load_v2: 334156300 (0.00%) (change within noise threshold)
    node_save_v2: 771175843 (-0.01%) (change within noise threshold)
    stable_memory_size: 93 (improved by 25.00%)

---------------------------------------------------

Benchmark: btreemap_remove_blob_8_1024
  measurements:
    instructions: 1300448303 (0.00%) (no change)
    node_load_v1: 325916114 (0.00%) (no change)
    node_save_v1: 562174712 (0.00%) (no change)
    stable_memory_size: 184 (0.00%) (no change)

---------------------------------------------------

Benchmark: btreemap_remove_blob_8_1024_v2
  measurements:
    instructions: 1841887486 (-0.01%) (change within noise threshold)
    node_load_v2: 391438934 (0.00%) (no change)
    node_save_v2: 1045403922 (-0.01%) (change within noise threshold)
    stable_memory_size: 139 (improved by 24.46%)

---------------------------------------------------

Benchmark: btreemap_remove_blob_16_1024
  measurements:
    instructions: 1544917110 (0.00%) (no change)
    node_load_v1: 420249550 (0.00%) (no change)
    node_save_v1: 654430779 (0.00%) (no change)
    stable_memory_size: 216 (0.00%) (no change)

---------------------------------------------------

Benchmark: btreemap_remove_blob_16_1024_v2
  measurements:
    instructions: 2218448732 (-0.01%) (change within noise threshold)
    node_load_v2: 513947291 (0.00%) (no change)
    node_save_v2: 1243769246 (-0.01%) (change within noise threshold)
    stable_memory_size: 162 (improved by 25.00%)

---------------------------------------------------

Benchmark: btreemap_remove_blob_32_1024
  measurements:
    instructions: 1622774819 (0.00%) (no change)
    node_load_v1: 443614945 (0.00%) (no change)
    node_save_v1: 681136613 (0.00%) (no change)
    stable_memory_size: 231 (0.00%) (no change)

---------------------------------------------------

Benchmark: btreemap_remove_blob_32_1024_v2
  measurements:
    instructions: 2327559094 (-0.01%) (change within noise threshold)
    node_load_v2: 545935373 (-0.00%) (change within noise threshold)
    node_save_v2: 1295876421 (-0.01%) (change within noise threshold)
    stable_memory_size: 174 (improved by 24.68%)

---------------------------------------------------

Benchmark: btreemap_remove_blob_64_1024
  measurements:
    instructions: 1917032351 (0.00%) (no change)
    node_load_v1: 675469604 (0.00%) (no change)
    node_save_v1: 700312977 (0.00%) (no change)
    stable_memory_size: 246 (0.00%) (no change)

---------------------------------------------------

Benchmark: btreemap_remove_blob_64_1024_v2
  measurements:
    instructions: 2663779711 (-0.01%) (change within noise threshold)
    node_load_v2: 783139557 (0.00%) (no change)
    node_save_v2: 1347825662 (-0.01%) (change within noise threshold)
    stable_memory_size: 184 (improved by 25.20%)

---------------------------------------------------

Benchmark: btreemap_remove_blob_128_1024
  measurements:
    instructions: 2236575844 (0.00%) (no change)
    node_load_v1: 922607545 (0.00%) (no change)
    node_save_v1: 716920195 (0.00%) (no change)
    stable_memory_size: 261 (0.00%) (no change)

---------------------------------------------------

Benchmark: btreemap_remove_blob_128_1024_v2
  measurements:
    instructions: 3031279182 (-0.00%) (change within noise threshold)
    node_load_v2: 1029479582 (0.00%) (no change)
    node_save_v2: 1412131798 (-0.01%) (change within noise threshold)
    stable_memory_size: 196 (improved by 24.90%)

---------------------------------------------------

Benchmark: btreemap_remove_blob_256_1024
  measurements:
    instructions: 2839195280 (0.00%) (no change)
    node_load_v1: 1421754484 (0.00%) (no change)
    node_save_v1: 722710062 (0.00%) (no change)
    stable_memory_size: 293 (0.00%) (no change)

---------------------------------------------------

Benchmark: btreemap_remove_blob_256_1024_v2
  measurements:
    instructions: 3696334312 (-0.00%) (change within noise threshold)
    node_load_v2: 1528516744 (0.00%) (no change)
    node_save_v2: 1474999328 (-0.01%) (change within noise threshold)
    stable_memory_size: 220 (improved by 24.91%)

---------------------------------------------------

Benchmark: btreemap_remove_blob_512_1024
  measurements:
    instructions: 4124317339 (0.00%) (no change)
    node_load_v1: 2441544783 (0.00%) (no change)
    node_save_v1: 765030850 (0.00%) (no change)
    stable_memory_size: 352 (0.00%) (no change)

---------------------------------------------------

Benchmark: btreemap_remove_blob_512_1024_v2
  measurements:
    instructions: 5148900105 (-0.00%) (change within noise threshold)
    node_load_v2: 2551454747 (0.00%) (change within noise threshold)
    node_save_v2: 1679737551 (-0.00%) (change within noise threshold)
    stable_memory_size: 264 (improved by 25.00%)

---------------------------------------------------

Benchmark: btreemap_remove_u64_u64
  measurements:
    instructions: 1110124274 (0.00%) (no change)
    node_load_v1: 314148033 (0.00%) (no change)
    node_save_v1: 483110284 (0.00%) (no change)
    stable_memory_size: 8 (0.00%) (no change)

---------------------------------------------------

Benchmark: btreemap_remove_u64_u64_v2
  measurements:
    instructions: 1193726508 (1.02%) (change within noise threshold)
    node_load_v2: 372663005 (regressed by 2.18%)
    node_save_v2: 507231342 (0.68%) (change within noise threshold)
    stable_memory_size: 7 (improved by 12.50%)

---------------------------------------------------

Benchmark: btreemap_remove_u64_blob_8
  measurements:
    instructions: 1072866879 (0.00%) (no change)
    node_load_v1: 313757215 (0.00%) (no change)
    node_save_v1: 457702957 (0.00%) (no change)
    stable_memory_size: 8 (0.00%) (no change)

---------------------------------------------------

Benchmark: btreemap_remove_u64_blob_8_v2
  measurements:
    instructions: 1131312211 (0.25%) (change within noise threshold)
    node_load_v2: 364893854 (0.54%) (change within noise threshold)
    node_save_v2: 464658073 (0.15%) (change within noise threshold)
    stable_memory_size: 6 (improved by 25.00%)

---------------------------------------------------

Benchmark: btreemap_remove_blob_8_u64
  measurements:
    instructions: 903826016 (0.00%) (no change)
    node_load_v1: 318747944 (0.00%) (no change)
    node_save_v1: 302202576 (0.00%) (no change)
    stable_memory_size: 7 (0.00%) (no change)

---------------------------------------------------

Benchmark: btreemap_remove_blob_8_u64_v2
  measurements:
    instructions: 1051368948 (1.19%) (change within noise threshold)
    node_load_v2: 405289279 (regressed by 2.05%)
    node_save_v2: 364434857 (0.84%) (change within noise threshold)
    stable_memory_size: 5 (improved by 28.57%)

---------------------------------------------------

@ielashi ielashi requested review from roman-kashitsyn and a team as code owners September 14, 2023 10:57
@ielashi ielashi merged commit 6a17564 into main Sep 15, 2023
@ielashi ielashi deleted the ielashi/bounded_page_size branch September 15, 2023 07:48
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers

@dsarlis dsarlis dsarlis approved these changes

@roman-kashitsyn roman-kashitsyn Awaiting requested review from roman-kashitsyn

Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.
2 participants
@ielashi @dsarlis
0