Lies, Damned Lies, and Substrings
summary
Generates all substrings and shows the concrete costs: the average substring ≈ n/3 so naive copying makes the nested loops O(n^3), but MRI uses copy‑on‑write only when the substring includes the final NUL byte, so typical substrings are copied and the benchmark grows ≈8× when input doubles. The talk inspects memory structs with a C debugger, patched string.c macro and rebuilt Ruby to enable middle‑substring sharing, and demonstrates that creating lazy shallow slices yields O(n^2) allocation cost while full output or printing remains cubic.
AI-written summary · about
chapters (4)
related talks
39mWhat lies beneath the beautiful code?
42mThe Mechanics of Ruby
34mBeyond the language. An introduction to algorithms.
24mRuby Performance Secrets and How to Uncover Them
32mWhat Rust can teach us about Ruby
39mPointers for Eliminating Heaps of Memory
19mThe Harvey Dent Dilemma: Ruby's White Knight Rises (or Falls)
42mRopes: An Alternative to Ruby's Strings