--- title: Meta Garbage Collection: Using OCaml's GC to GC Rust description: Soteria Rust, a symbolic execution tool for Rust programs, encountered quadratic time complexity in its Tree Borrows aliasing model implementation. The root... canonical: https://daily.dev/posts/meta-garbage-collection-using-ocaml-s-gc-to-gc-rust-ayxxkojbd twitter:card: summary_large_image twitter:site: @dailydotdev og:type: website og:site_name: daily.dev og:title: Meta Garbage Collection: Using OCaml's GC to GC Rust | daily.dev og:description: Soteria Rust, a symbolic execution tool for Rust programs, encountered quadratic time complexity in its Tree Borrows aliasing model implementation. The root... og:url: https://daily.dev/posts/meta-garbage-collection-using-ocaml-s-gc-to-gc-rust-ayxxkojbd og:image: https://api.daily.dev/og/posts/AyXXkOjbD.png og:image:alt: Meta Garbage Collection: Using OCaml's GC to GC Rust og:image:width: 1200 og:image:height: 630 og:locale: en --- > ## Documentation Index > Fetch the complete documentation index at: https://daily.dev/llms.txt > Use this file to discover all available pages before exploring further. # Meta Garbage Collection: Using OCaml's GC to GC Rust **[Lobsters](https://daily.dev/sources/lobsters)** · 15 min read · 2 upvotes · 0 comments ## Summary Soteria Rust, a symbolic execution tool for Rust programs, encountered quadratic time complexity in its Tree Borrows aliasing model implementation. The root cause: each loop iteration adds nodes to a Tree Borrows tree that is never pruned, causing O(N²) node accesses. The fix leverages OCaml's built-in garbage collector — since Soteria is written in OCaml — by storing tree nodes as weak references via OCaml's Weak and Ephemeron data structures. When the tree exceeds a threshold T, a major GC cycle is triggered, collecting unreachable nodes. A backoff mechanism doubles T when GC yields no freed nodes. The result is linear time complexity, with up to 10.6x speedup on benchmarks. The approach required only ~40 lines of code, compared to Miri's manually implemented GC for the same problem. ## Full article daily.dev links to this article rather than hosting it. Read it at the original source: ## Questions this post answers ### Why does tracking Rust's Tree Borrows aliasing model become quadratic in the number of loop iterations? Each iteration of a for-loop implicitly reborrows references (e.g. through Range::next calls), adding new nodes to the Tree Borrows tracking tree without ever removing old, unreachable ones. With A nodes added and B accesses per iteration, total node accesses grow as roughly A*B*N²/2, since the tree is only half-grown on average across N iterations, producing quadratic instead of linear time. _Developers debugging unexpected quadratic blowups in interpreters or analysis tools can find related deep dives on daily.dev._ ### Is it safe to garbage collect Tree Borrows tree nodes that are no longer reachable in a Rust aliasing checker? Yes, as long as three conditions hold: protected nodes (held during a function's active scope) must stay strongly referenced so they're never collected, a child node is always at least as close to undefined behavior as its parent so removing an unreachable parent can't hide UB, and references held across symbolic execution branches must be kept live so nodes reachable in another branch aren't erased. _Engineers building sound program analysis tools can track these kinds of soundness proofs on daily.dev._ ### How much speedup did using OCaml's garbage collector for Tree Borrows tracking in Soteria Rust achieve over a naive quadratic implementation? Delegating collection of unreachable Tree Borrows nodes to OCaml's Gc.major(), triggered once the tracking tree exceeds a tunable threshold with a doubling backoff when nothing gets freed, converted quadratic growth into linear time. A synthetic N=2000 loop benchmark saw a 10.6x speedup, and a Tokio-derived initialization benchmark with a 1024-element array dropped from 14.8 seconds to 1.7 seconds, an 8.7x speedup. _Teams weighing performance tradeoffs in verification tooling can follow benchmarking writeups like this on daily.dev._ ## Similar posts on daily.dev - [kyju.org](https://daily.dev/posts/kyju-org-cwlzepurv) · Lobsters · 0 upvotes · 0 comments - [How AST-grep Rewrote Tree-sitter in Rust and Made It 30% Faster](https://daily.dev/posts/how-ast-grep-rewrote-tree-sitter-in-rust-and-made-it-30-faster-a1lxwchoq) · Hacker News · 0 upvotes · 0 comments - [Garbage collection in Rust got a little better](https://daily.dev/posts/garbage-collection-in-rust-got-a-little-better-zximifcs8) · Lobsters · 16 upvotes · 3 comments - [Speeding Up the Plush Garbage Collector](https://daily.dev/posts/speeding-up-the-plush-garbage-collector-94olnbjbh) · Pointers Gone Wild · 13 upvotes · 0 comments --- Tags: [#rust](https://daily.dev/tags/rust), [#ocaml](https://daily.dev/tags/ocaml) [View this post on daily.dev](https://daily.dev/posts/meta-garbage-collection-using-ocaml-s-gc-to-gc-rust-ayxxkojbd) ```json {"@context":"https://schema.org","@graph":[{"@type":"Organization","@id":"https://daily.dev/#organization","name":"daily.dev","url":"https://daily.dev","logo":{"@type":"ImageObject","url":"https://daily.dev/apple-touch-icon.png","width":180,"height":180},"sameAs":["https://twitter.com/dailydotdev","https://github.com/dailydotdev","https://www.linkedin.com/company/daily-dev-ltd"]},{"@type":"WebSite","@id":"https://daily.dev/#website","url":"https://daily.dev","name":"daily.dev","publisher":{"@id":"https://daily.dev/#organization"},"potentialAction":{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https://daily.dev/search?q={search_term_string}"},"query-input":"required name=search_term_string"}}]} {"@context":"https://schema.org","@type":"TechArticle","headline":"Meta Garbage Collection: Using OCaml's GC to GC Rust","url":"https://daily.dev/posts/meta-garbage-collection-using-ocaml-s-gc-to-gc-rust-ayxxkojbd","mainEntityOfPage":{"@type":"WebPage","@id":"https://daily.dev/posts/meta-garbage-collection-using-ocaml-s-gc-to-gc-rust-ayxxkojbd"},"datePublished":"2026-07-20T22:35:12.690Z","dateModified":"2026-09-14T07:03:12.176Z","description":"Soteria Rust, a symbolic execution tool for Rust programs, encountered quadratic time complexity in its Tree Borrows aliasing model implementation. The root...","image":"https://media.daily.dev/image/upload/f_auto,q_auto/v1/posts/b75e968bad97859a5880a630a9693f80?_a=AQAEuop","thumbnailUrl":"https://media.daily.dev/image/upload/f_auto,q_auto/v1/posts/b75e968bad97859a5880a630a9693f80?_a=AQAEuop","isAccessibleForFree":true,"articleSection":"Lobsters","inLanguage":"en","publisher":{"@type":"Organization","name":"daily.dev","url":"https://daily.dev","logo":{"@type":"ImageObject","url":"https://daily.dev/apple-touch-icon.png","width":180,"height":180}},"author":{"@type":"Organization","name":"Lobsters","logo":"https://media.daily.dev/image/upload/s--tl8v_Fku--/f_auto,t_logo/v1698841318/logos/lobste.jpg","url":"https://daily.dev/sources/lobsters"},"commentCount":0,"discussionUrl":"https://daily.dev/posts/meta-garbage-collection-using-ocaml-s-gc-to-gc-rust-ayxxkojbd","interactionStatistic":[{"@type":"InteractionCounter","interactionType":{"@type":"LikeAction"},"userInteractionCount":2},{"@type":"InteractionCounter","interactionType":{"@type":"CommentAction"},"userInteractionCount":0}],"keywords":"rust,ocaml","timeRequired":"PT15M"} {"@context":"https://schema.org","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https://daily.dev"},{"@type":"ListItem","position":2,"name":"Lobsters","item":"https://daily.dev/sources/lobsters"},{"@type":"ListItem","position":3,"name":"Meta Garbage Collection: Using OCaml's GC to GC Rust"}]} {"@context":"https://schema.org","@type":"FAQPage","@id":"https://daily.dev/posts/meta-garbage-collection-using-ocaml-s-gc-to-gc-rust-ayxxkojbd#faq","mainEntity":[{"@type":"Question","name":"Why does tracking Rust's Tree Borrows aliasing model become quadratic in the number of loop iterations?","acceptedAnswer":{"@type":"Answer","text":"Each iteration of a for-loop implicitly reborrows references (e.g. through Range::next calls), adding new nodes to the Tree Borrows tracking tree without ever removing old, unreachable ones. With A nodes added and B accesses per iteration, total node accesses grow as roughly A*B*N²/2, since the tree is only half-grown on average across N iterations, producing quadratic instead of linear time. Developers debugging unexpected quadratic blowups in interpreters or analysis tools can find related deep dives on daily.dev."}},{"@type":"Question","name":"Is it safe to garbage collect Tree Borrows tree nodes that are no longer reachable in a Rust aliasing checker?","acceptedAnswer":{"@type":"Answer","text":"Yes, as long as three conditions hold: protected nodes (held during a function's active scope) must stay strongly referenced so they're never collected, a child node is always at least as close to undefined behavior as its parent so removing an unreachable parent can't hide UB, and references held across symbolic execution branches must be kept live so nodes reachable in another branch aren't erased. Engineers building sound program analysis tools can track these kinds of soundness proofs on daily.dev."}},{"@type":"Question","name":"How much speedup did using OCaml's garbage collector for Tree Borrows tracking in Soteria Rust achieve over a naive quadratic implementation?","acceptedAnswer":{"@type":"Answer","text":"Delegating collection of unreachable Tree Borrows nodes to OCaml's Gc.major(), triggered once the tracking tree exceeds a tunable threshold with a doubling backoff when nothing gets freed, converted quadratic growth into linear time. A synthetic N=2000 loop benchmark saw a 10.6x speedup, and a Tokio-derived initialization benchmark with a 1024-element array dropped from 14.8 seconds to 1.7 seconds, an 8.7x speedup. Teams weighing performance tradeoffs in verification tooling can follow benchmarking writeups like this on daily.dev."}}]} ```