{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreia7olsafv2ktgcvbplrq2peabr2m5fa2p2pdeedo3ev6tqleqlt3u",
    "uri": "at://did:plc:25rdn5elo5izoxrmtis34zuk/app.bsky.feed.post/3mop5hpef67o2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiaujoz7h2zc2n6m34hdcdctsarcx5irmtus5hpfrokwmrsiccdkf4"
    },
    "mimeType": "image/webp",
    "size": 329990
  },
  "path": "/amirsefati/the-rust-performance-trap-i-hit-while-sorting-small-network-datasets-2gj5",
  "publishedAt": "2026-06-20T04:58:26.000Z",
  "site": "https://dev.to",
  "tags": [
    "rust",
    "performance",
    "networking"
  ],
  "textContent": "#  The Rust Performance Trap I Hit While Sorting Small Network Datasets\n\nI recently ran into one of those performance problems that looks completely obvious in hindsight, but was surprisingly hard to notice while I was inside the code.\n\nI was working on a deep search and ranking part of a Rust project that processed network-related data.\n\nThe system had to evaluate many small groups of candidates repeatedly. You can think of these candidates as possible network paths, intermediate nodes, route-like records, latency candidates, or weighted decisions inside a search tree.\n\nAt each step, I had a small list of candidates.\n\nNot thousands of items.\n\nUsually something like 10, 20, maybe 40 or 50.\n\nEach candidate needed to be scored and ordered before the search could continue.\n\nThe first version of the code was simple and readable:\n\n\n\n    let mut candidates = Vec::new();\n\n    for item in input {\n        candidates.push(item);\n    }\n\n    candidates.sort_by_key(|item| compute_score(item));\n\n\nIt worked.\n\nIt was clean.\n\nBut after profiling it with a flamegraph, I noticed something uncomfortable: the program was spending too much time around temporary allocations.\n\nAt first, that sounds strange. A small `Vec` does not look expensive.\n\nBut in a deep search algorithm, a \"small allocation\" repeated millions of times is no longer small.\n\nThat was the beginning of the rabbit hole.\n\n##  The First Bottleneck: Heap Allocation\n\nThe first problem was heap allocation.\n\nEvery time the search visited a node, it created temporary vectors to collect, score, and sort candidates. Since the search tree was deep, this happened again and again.\n\nOne allocation does not matter much.\n\nThousands of allocations may still be fine.\n\nBut millions of tiny allocations inside a hot path can become a serious bottleneck.\n\nThe important thing is this:\n\n> Heap allocation is not just \"getting some memory\".\n\nThere is real machinery behind it.\n\nWhen a program allocates memory on the heap, the allocator has to find a suitable block of memory, update internal metadata, sometimes handle alignment, sometimes split or reuse blocks, and later track that memory so it can be freed safely.\n\nEven if the allocator is very optimized, this is still more expensive than using memory that is already available on the stack.\n\nWith stack memory, the cost is usually very small. The program mostly adjusts the stack pointer. It is simple, predictable, and extremely cache-friendly.\n\nHeap memory is more flexible, but that flexibility has a price.\n\nIn my case, I did not need flexibility.\n\nI already knew the candidate lists were small. I did not need an unbounded dynamic vector for every step of the search. I needed a tiny temporary buffer.\n\nBut I was still paying the cost of heap allocation over and over again.\n\n##  Why Heap Allocation Can Be Expensive in a Hot Path\n\nHeap allocation becomes especially problematic when it happens inside a tight loop or a deeply repeated algorithm.\n\nThere are a few reasons for that.\n\n###  1. Allocator Overhead\n\nA heap allocator has to manage memory dynamically.\n\nThat means it needs bookkeeping.\n\nWhen I create a `Vec`, Rust itself is not doing something inefficient. `Vec` is a great data structure. But when it needs capacity, it asks the allocator for heap memory.\n\nThe allocator has to find a free region that fits the requested size. It may reuse an existing block, split a larger block, or request more memory from the system.\n\nEven when this is fast, it is not free.\n\nIn normal application code, this cost may not matter. In a hot path, it can dominate the runtime.\n\n###  2. Memory Locality\n\nStack memory is usually very close to the current execution context.\n\nSmall arrays on the stack tend to be friendly to the CPU cache. The CPU can load nearby memory efficiently, and the access pattern is usually predictable.\n\nHeap memory can be more scattered.\n\nIf temporary vectors are allocated and freed repeatedly, the actual memory locations may not be as local as a compact stack buffer.\n\nThis matters because modern CPUs are extremely fast, but memory is relatively slow. A lot of real-world performance comes down to whether the CPU can keep useful data in cache.\n\nIf the CPU has to wait for memory, the algorithm may look good on paper but still run slower in practice.\n\n###  3. Fragmentation and Metadata\n\nHeap allocators also maintain metadata.\n\nThey need to know which blocks are free, which blocks are used, and how large those blocks are.\n\nOver time, allocation and deallocation patterns can create fragmentation. For small short-lived allocations, modern allocators are usually smart, but they still have to manage the lifecycle of memory.\n\nFor a deep search algorithm, this was unnecessary noise.\n\nThe lifetime of the data was very short. Each temporary list only lived during one search step.\n\nThat is exactly the kind of data that usually fits better on the stack.\n\n###  4. More Pressure on the CPU Cache\n\nThe real issue was not only the cost of allocation itself.\n\nThe bigger problem was the combination of allocation, sorting, scoring, and repeated traversal.\n\nThe algorithm was doing many tiny operations. Each operation looked harmless, but together they created pressure on the CPU cache.\n\nTemporary heap allocations increased the amount of memory traffic. The CPU had to touch more memory, follow more pointers, and deal with less predictable access patterns.\n\nWhen code runs once, this is not a big deal.\n\nWhen code runs inside the hottest part of a search engine, it matters.\n\n##  The First Optimization: Remove Temporary Heap Allocation\n\nSo my first idea was simple:\n\n> Stop creating temporary vectors in the hot path.\n\nInstead of collecting candidates into a heap-allocated `Vec`, I moved toward a fixed-size temporary buffer.\n\nConceptually, something like this:\n\n\n\n    const MAX_CANDIDATES: usize = 64;\n\n    let mut buffer: [MaybeUninit<ScoredCandidate>; MAX_CANDIDATES] = unsafe {\n        MaybeUninit::uninit().assume_init()\n    };\n\n\nThe exact implementation depends on the project, of course. The important part is the idea:\n\n  * the number of candidates was bounded\n  * the temporary data had a very short lifetime\n  * the buffer could live on the stack\n  * no heap allocation was needed for every search node\n\n\n\nAfter this change, I expected the program to become faster.\n\nAnd partially, I was right.\n\nThe allocation cost disappeared from the flamegraph.\n\nBut then I hit the second trap.\n\n##  The Surprising Part: Removing Allocations Made It Slower\n\nAfter removing the temporary heap allocation, I used Rust's standard sorting method:\n\n\n\n    items.sort_unstable_by_key(|item| compute_score(item));\n\n\nAt first glance, this looked like the right choice.\n\nIt is in-place. It avoids extra allocation. It is part of the standard library. It uses a serious optimized sorting algorithm.\n\nBut the program became slower.\n\nThat was confusing.\n\nI had removed heap allocation. I had improved memory usage. I was using a well-optimized standard method.\n\nSo why did performance drop?\n\nThe flamegraph gave me the answer.\n\nThe allocation cost was gone, but now the program was spending too much time recomputing scores.\n\nThe key detail is that `sort_unstable_by_key` does not cache the key for every item.\n\nThe closure can be called multiple times during sorting.\n\nThat is completely fine when the key is cheap, like reading an integer field:\n\n\n\n    items.sort_unstable_by_key(|item| item.priority);\n\n\nBut my key was not cheap.\n\nThe score calculation was based on multiple network-related signals, such as:\n\n  * estimated latency\n  * hop penalty\n  * node priority\n  * route freshness\n  * failure probability\n  * domain-specific weights\n\n\n\nSo every comparison could trigger real computation again.\n\nAnd again.\n\nAnd again.\n\nI had removed heap allocation, but I had accidentally introduced repeated CPU work in the hottest part of the program.\n\nThe code looked clean, but it was doing more work than it appeared.\n\n##  Why the Default Sort Was Not the Best Tool Here\n\nRust's `sort_unstable_by_key` is not bad.\n\nActually, it is very good.\n\nThe problem was not Rust.\n\nThe problem was that I used a general-purpose sorting method for a very specific workload.\n\nModern sorting algorithms are excellent for large arrays and general cases. Rust's unstable sort is designed to perform well across many real-world patterns.\n\nBut my workload had two special properties:\n\n  1. The arrays were very small.\n  2. The key calculation was relatively expensive.\n\n\n\nFor large arrays, an `O(N log N)` sort is usually the obvious choice.\n\nBut for tiny arrays, Big-O can be misleading.\n\nWhen `N` is 10, 20, or 40, constant factors matter a lot.\n\nAt that size, the overhead of the sorting algorithm, the number of comparisons, branch behavior, cache locality, and repeated score calculation can matter more than the theoretical complexity.\n\nIn my case, the theoretical advantage of the sorting algorithm was less important than the practical cost of using it in a tiny hot loop.\n\n##  The Fix: Cache the Scores and Sort a Small Stack Buffer\n\nThe final solution was simple:\n\n  1. Compute the score for each candidate exactly once.\n  2. Store the candidate and its score in a small stack buffer.\n  3. Sort the scored candidates using insertion sort.\n\n\n\nConceptually:\n\n\n\n    struct ScoredCandidate<T> {\n        score: i32,\n        item: T,\n    }\n\n\nInstead of asking the sorting algorithm to repeatedly call `compute_score`, I made the score part of the temporary data.\n\nThe scoring step became linear:\n\n\n\n    for candidate in candidates {\n        let score = compute_score(candidate);\n\n        scored.push(ScoredCandidate {\n            score,\n            item: candidate,\n        });\n    }\n\n\nAfter that, sorting only compared already-computed integers.\n\nThat completely changed the cost profile.\n\nThe expensive part happened once per candidate, not many times per comparison.\n\n##  Why Insertion Sort Worked Better\n\nFor the sorting step, I used insertion sort.\n\nYes, insertion sort.\n\nThe algorithm that is usually introduced early in computer science classes and then quickly ignored because it is `O(N²)`.\n\nBut for small arrays, insertion sort can be extremely fast.\n\nWhy?\n\nBecause it is simple.\n\nIt has very little overhead. It works well with contiguous memory. It does not need extra allocation. It has predictable behavior. And when the array is small, the quadratic complexity does not have enough room to become a problem.\n\nFor example, sorting 20 or 30 items with insertion sort is not scary.\n\nEspecially when the data is already in a small stack buffer and comparisons are cheap integer comparisons.\n\nIn this case, insertion sort matched the workload better than a more advanced general-purpose sorting algorithm.\n\nThis is one of those cases where the \"worse\" algorithm on paper was better for the real machine.\n\n##  The Result\n\nAfter the change, the flamegraph looked completely different.\n\nThe repeated scoring calls disappeared from the hot path.\n\nThe allocation-related noise was gone.\n\nThe middle layers of the search became much faster.\n\nThe biggest improvement did not come from one magical trick. It came from aligning the implementation with the real shape of the workload:\n\n  * small candidate lists\n  * deep repeated search\n  * short-lived temporary data\n  * expensive scoring\n  * no need for heap flexibility\n  * stack-friendly memory layout\n  * simple sorting over cached scores\n\n\n\nThe final version was not more complicated in spirit.\n\nIt was actually more honest about what the program was doing.\n\nThe program did not need a dynamic vector and a general-purpose sort at every search node.\n\nIt needed a tiny local ranking buffer.\n\n##  The Lesson\n\nThe main lesson for me was this:\n\n> The fastest algorithm in theory is not always the fastest algorithm on real hardware.\n\nBig-O matters, but it is not the whole story.\n\nIn performance-sensitive code, especially backend, networking, infrastructure, or systems code, the real questions are often more practical:\n\n  * How large is the data really?\n  * How often does this code run?\n  * Is this allocation inside a hot path?\n  * Is the temporary memory short-lived?\n  * Is the key cheap or expensive?\n  * Are we recomputing something that could be cached?\n  * Is the memory layout friendly to the CPU cache?\n  * Does a general-purpose standard method match this exact workload?\n\n\n\nStandard library methods are great defaults. Most of the time, they are exactly what we should use.\n\nBut \"default\" does not mean \"always optimal\".\n\nIn my case, the better solution was:\n\n  * avoid repeated heap allocations\n  * compute scores once\n  * store small temporary data on the stack\n  * use insertion sort for tiny arrays\n\n\n\nThat was enough to beat the more advanced-looking approach.\n\n##  Final Thought\n\nThis experience reminded me that performance work is not only about knowing algorithms.\n\nIt is about understanding the shape of the data, the lifetime of memory, and how the CPU actually executes the code.\n\nSometimes the bottleneck is not where you expect it to be.\n\nSometimes removing an allocation exposes another hidden cost.\n\nAnd sometimes the \"bad\" `O(N²)` algorithm is exactly what your CPU wanted.",
  "title": "The Rust Performance Trap I Hit While Sorting Small Network Datasets"
}