Rust: Dropping heavy things in another thread can make your code 10000x faster (opens in new tab)

>As an aside, compilers have used the trick of not free-ing data structures before, because it provides a significant performance boost. Instead of calling free on all those billions of tiny data structures a compiler would generate during its lifetime, they just let them leak. Since a compiler is short lived its not a problem, they get a free lunch (pun unintended), and the OS takes care of cleaning up after all is said and done. My point is that this post isn't theoretical, we do deallocation trickery in the real world.

This reminds me of the exploding ultimate GC technique [1]:

> on-board software for a missile...chief software engineer said "Of course it leaks". ... They added this much additional memory to the hardware to "support" the leaks. Since the missile will explode when it hits its target or at the end of its flight, the ultimate in garbage collection is performed without programmer intervention.

[1]: https://devblogs.microsoft.com/oldnewthing/20180228-00/?p=98...

>As an aside, compilers have used the trick of not free-ing data structures before, because it provides a significant performance boost. Instead of calling free on all those billions of tiny data structures a compiler would generate during its lifetime, they just let them leak. Since a compiler is short lived its not a problem, they get a free lunch (pun unintended), and the OS takes care of cleaning up after all is said and done. My point is that this post isn't theoretical, we do deallocation trickery in the real world.

And then someone tries to use your compiler as a service (code analysis, change triggered compiler) and it's a dead end

One of my “favorite” snags in perf analysis is that periodicity in allocations can misattribute the cost of allocations to the wrong function.

If I allocate just enough memory, but not too much, then pauses for defragmentation of free space may be costed to the code that calls me.

A solution to this that I’ve seen in soft real time systems is to amortize cleanups across all allocations. Every allocation performs n steps of a cleanup process prior to receiving a block of memory. In which case most of the bad actors have to pay part of the cost of memory overhead.

Might be good for Rust to try something in that general realm, or in the cleanup side may be easier to tack on. On free, set a ceiling for operations and queue what is left. That would at least peak shave.

This deallocation trick is neat but in C and C++ you could use a memory pool to do this.

In theory, you could also use a memory pool in Rust but I think the standard library uses malloc without some way of overriding this behaviour.

Isn’t a Rust “move” implemented as a bit wise copy (e.g. memcpy call)? I see people claiming move has no cost but I’m not sure that is true.

> As an aside, compilers have used the trick of not free-ing data structures before

In Clang, this flag is `-Xclang -disable-free`. Not from a Jedi...

I don't know if Rust can do it (unsafe?) but in C and C++, I sometimes end up writing a custom allocator. It is often one of the most significant optimizations.

For example, I had the "million strings" problem once, literally millions. The solution was to put every string into a single large buffer and the pointers in another buffer. Not only I could deallocate everything at once but I also saved a bit of RAM by not aligning (not needed for strings).

> That very thing can easily happen in the real world.

Only if badly designed. That is why it is contrived!

> While that may seem contrived, consider a vector of 1 million strings, something that's not too uncommon

A program dealing with a million elements of any kind should not be performing naive allocations to begin with.

> we do deallocation trickery in the real world

Skipping deallocations is an optimization, not a design pattern.

In other words, the code needs to keep the ability to perform the deallocation for debugging, testing, usage as a library, etc.

One of my favorite papers by Bacon et al expands on this intuition that garbage collection and reference counting are opposite tradeoffs in many respects, and gives a formal theory for it. My views on gc/rc haven't been the same since.

http://researcher.watson.ibm.com/researcher/files/us-bacon/B...

"Generational/compacting GC has the opposite problem. Garbage collection takes time proportional to the live set, and the amount of memory collected is unimportant."

Takes time proportional the live set times the number of GC runs that happen while the objects are alive. In other words, the longer the objects live, the more GC runs have to scan that object (assuming there is enough activity to trigger the GC), and the worse GC looks.

> the ownership system lets you transfer freeing responsibility off-thread safely and cheaply in order to not have it block the critical path

This can also trivially be done in other languages. Atomically append your pointer to a queue of "large things that need to be freed" and move on as though you had actually called free.

Within a particularly time sensitive loop you can even opt to place pointers into a preallocated array locally. Then once per loop iteration swap that array with the thread handling the deallocations for you. It eats up a bit of CPU time but can significantly reduce latency.

I've not worked with any language thus far without automatic garbage collecting, so this was definitely a neat read for me. It sounds rather elegant.

> This is the standard problem with tracing data structures to free them. You frequently run into it with systems based on malloc/free or reference counting. The underlying problem is that freeing the structure takes time proportional to the number of pointers in the structure it has to chase.

That doesn't seem to make intuitive sense. A GC has the same problem.

A garbage collector has to traverse the data structure in a similar way to determine whether it (and it's embedded keys and values) are part of the live set or not, and to invoke finalizers. You're beginning your comparison after the mark step, which isn't a fair assessment since what Rust is doing is akin both both the mark and sweep phases.

The only way to drop an extensively nested structure like this any faster than traversing it would be an arena allocator, and forgetting about the entire arena.

The difference between a GC and this kind of memory management is that the GC does the traversal later, at some point, non-deterministically. Rust allows you to decide between deallocating it in place, immediately, or deferring it to a different thread.

I think the contrived use case is just for illustrative purposes? If I'm understanding correctly, the combination of cleanup code and deallocation can sometimes consume enough time that it's worth dispatching it on another thread. That's hardly specific to Rust though.

As you note that will certainly add some overhead, although that could be minimized by not spawning a fresh thread each time. It could easily reduce latency for a thread the UI is waiting on in many cases.

I believe this is contrived to prove a point.

And this isn't just a help in these contrived examples. I believe process cleanup (an extreme case of cleaning up objects) is one of cases where garbage collection performs better because it doesn't have to unwind the stack, call cleanup functions that are not in the cache, and make a lot of `free` calls to the allocator.

I vaguely remember reading about Google killing processes rather than having them clean up correctly, relying on the OS to properly clean up any resources of significance.

Now this doesn't mean you should do this in all cases. Profile first, see if you can avoid the large objects, and then look into deferred de-allocations ... if the timing of resource cleanup meets your application's guarantees.

Not at all, Herb Sutter has a CppCon talk about this kind of optimisations.

It is also the approach taken by C++/WinRT, COM and UWP components get moved into a background cleaning thread, to avoid application pauses on complex data structures reaching zero count.

I took this to be a contrived example to illustrate the point. I could imagine a process that creates a big data structure (e.g. parse an xml file), pulls some data out, and then drops the data structure. If you want to use that data sooner, you can push the cleanup off your thread.

It’s a contrived example to demonstrate the technique.

Right there is no reason to pass ownership to a function like this.

> Is Rust basically based on unique_ptr?

Rust is based on ownership and statically checked move semantics (by default though can be opted out). So each item has a single owner (which is why Rust deals very badly with graphs, and more generally any situation where ownership is unclear) and the compiler will prevent you from using a moved object (unlike C++).

Separately it has a smart pointer which is the dual of unique_ptr (Box), with the guarantee noted above:

    let b = Box::new(1);
    drop(b);
    println!("{}", b);

will not compile because the second line moves the box, after which it can't be used because it's been removed entirely from this scope.

Rust basically gives the compiler understanding of unique_ptr and prevents you from using it after you’ve moved it.

> One problem with this approach was that you still had to wait for these threads when the application would shut down.

If you know that an object will live for the rest of the program and not need any finalization logic, Rust allows you to "leak" it and save that overhead on shutdown.

You could have just one thread and to kill it at exit. Do not start new threads for each closure that drops object, send closures into one special thread instead.

Out of curiosity, how did you do that in C++?

I only know a very little rust, but since it's generally a good practice to never defer writing (or other side effects) to an ambiguous future point in time - with memory allocations as the only plausible exception - is there any way in rust to make sure one doesn't accidentally move complex objects with drop side-effects into other threads?

Granted the way the type system work you usually know the type of a variable quite well, but could this happen with opaque types?

I'm very much out of my depth, but it felt like one of those things that could really bite you if you are unaware, as happened with finalizers in Java decades ago.

Considering that writing files can also block the process you probably don't want to have that in your latency-sensitive parts either, so you'll have to optimize that one way or another anyway.

For the more general problem you have can also dedicate more threads to the task or apply backpressure.

A while ago I stumbled over a proposal to move a shared pointer (this was C++ code) to a thread in order to trigger the freeing of a legacy data structure there (the multi-thousand delete calls caused the watchdog of the main thread to fail). However, keeping the shared pointer reference in the main thread for too long resulted in the possibility that the "clean-up" thread ran while the main thread still had a hold on the shared pointer... Resulting in a low chance of the "clean-up" thread doing nothing and the main thread still locking up. People here got taught to use shared pointers to prevent memory management errors, but it can really cause a lot of unexpected non-determinism when used blindly.

It seems like the caller should ensure that the buffer is written before giving away ownership. Also, what happens if there is an error writing during finalization/destruction/etc? Seems like you'd want to find out about such errors earlier if at all possible.

This code doesn't duplicate it. In Rust when a variable is sent as an argument to a function it's "ownership" moves to be in the scope of that function.

https://doc.rust-lang.org/book/ch04-01-what-is-ownership.htm...

I’m actually very curious why it takes this long; is Rust memseting the buffer when dropping it?

Edit: it seems like turning on optimizations seems to improve the situation quite a bit. Not sure why they were profiling the debug build.

Rust will automatically clean up data that’s left scope, but you can also manually accomplish this by the “drop” function, which is only necessary if you want to cleanup explicitly, such as in a different thread.

Interestingly, the drop function is actually user-creatable. It’s actually an empty function with a very permissive Non-reference argument. The semantics of ownership in Rust makes that sufficient to trigger memory cleanup.

In C, if you forget to clean up, you have a memory leak which is hard to track down. In Rust, if you don't do this, you're not sacrificing memory leaks, only performance. A profiler can tell you when you should drop asynchronously.

As I understand it, rust is automatically cleaning up, and that can cause glitchy timing. The clever hack is that rust lets you shunt that cleanup process off to another thread when you're the sole owner of that object. You can do the same thing in C, but unlike rust, the cost of cleanup is not hidden by the syntax.

Because it's impossible to do this automatically in the general case.

In particular, types may not be sendable to other threads, or may have side effects on dropping, and in those cases you would need to rearchitect the code before you can apply this technique.

Also this technique adds overhead, so it should never be used (including not doing it conditionally) if you don't care about latency or if the objects are always small, and the compiler cannot know whether that is the case.

If you never drop it, you have a memory leak. If the caller drops it, it's still the same as the `get_size` dropping it in terms of performance impact.

Generally you'd only pass ownership when that's needed for some reason. So this toy example might not be realistic but it does demonstrate the performance impact.

For these contrived cases, yes, you would just pass a reference to the function but I think the point is to simplify the case down to demonstrate a point.

So the caller of the function still needs to free HeavyThing in the same thread.

You’re spot on: this is simply a bad example that you would never see in a real application.

It's not a feature of Rust; it's a "feature" of the way we design operating systems and processors. This is the same in C.

The same could happen in C++, I think. Destructors are supposed to be called recursively.

1) he should pass by reference to avoid the extra copy. So in his example yes it’s dev naivety

2) but somewhere somehow this object will deallocate, so his trick of putting it to another thread would work if the deal location takes awhile. Same for cpp if you have a massive object in a unique ptr. So it’s not a rust issue

That's not really the same issue that is mentionned in the article though, is it ?

The issue from the article would be solved by just passing a reference to the variable.

In your case, cleanup is an action that needs to be done before writing new files. So you have to wait for cleanup anyway, don't you ?

Why can't it cleanup right after the work?

No the zero-cost refers to the abstraction (and runtime cost), which still is zero-cost. Deallocating is part of the normal work load not the abstraction.

Also this isn't rust specific. Most (all?) RAII languages are affected and many GC approaches have this effect, too. Some do add additional abstraction to magically always or sometimes put the de-allocation into another thread.

But de-allocating in another thread is not generally good or bad. There are a lot of use-cases where doing so is rather bad or can't be done (in case TLS is involved). Rust and other similar RAII languages at least let you decide what you want to do.

Now it's (I think) generally known that certain kinds (not all) of GC do make some thinks simpler for GUI-like usage. Through they also tend to have less control.

Note that it's a common pattern for small user CLI facing tools (which are not GC'ed) to leak resources instead of cleaning them up properly. You can do so in rust too if you want but it's a potential problem for longer running applications.

Also here is a faster get `get_len` then both which is also more idiomatic rust then both:

``` fn get_len1(things: &HeavyThings) -> usize { things.len() } ```

If you have a certain thread (e.g. UI thread) in which you never want to do any cleanup work you can consider using a container like:

``` struct DropElsewhere<T: Send>(pub Option<T>); impl<T: Send> Drop for DropElsewhere<T> { fn drop(&mut self) { if let Some(value) = self.take() { thread::spawn(move || drop(value)); } } } ```

You can optimize this with `ManualDrop` to have close to zero-runtime overhead (removes the `take` and `if let` part).

Nothing about how Rust handles deallocation is magical in any way.

It's also definitely a zero-cost abstraction as I can see because the manual solution that's equivalent to get_len1() would be to essentially call free() on things. That would ultimately suffer from the same problem.

As already mentioned, Rust wasn't copying anything; the `HashMap` is not a `Copy`-able type, so it was just moved around (it's also not very large: all its items are behind a pointer to the heap).

All you did was move the drop from the `fn_that_drops_heavy_things` to the end of `main`, where it is outside the timing function.

> but it's simple enough to realize that if this function, as claimed, must drop all the sub-objects within the `HeavyObject` type, then those objects must have been copied from the original object.

Untrue. Rust uses move semantics (or shallow copys for types that implement the Copy trait via e.g. memcpy - no you can't customize this!) Deep copies require explicitly calling methods like ".clone()". So HashMap's pointers and sizes do get memcpyed... 56 bytes on the 64-bit playground currently.

This is similar to how std::move(...)ing a std::unordered_map in C++ nulls out the old object and just copies the pointers of the container - not a deep copy of the subobjects - which in similar C++ code would turn the main thread's destructor into a noop.

The main difference from C++ is: Rust handles this at the language level instead, and doesn't call the dtor at all on the main thread at all if the value was moved. No need for manual movement logic - it is the default, for everything. Also unlike C++, it also prohibits you from using the old moved-from object at compile time, preventing bugs.

Rust isn't copying anything; everything in the original code would be a move.

If your function takes a reference to the object, something still needs to free it.

Yes it’ll reduce latency, but doesn’t it also increase parallelism? A single-threaded program ought to improve overall, unless the extra overhead you mentioned dominates. A parallel program might improve or not.

I think if you wanted to do deferred destruction right, ideally you’d mod an allocator to have functions like (alloc_local, alloc_global, free_now, free_deferred) to avoid exhausting memory. Traits could make this ergonomic.

Also I admit I don’t understand why “you won’t have any backpressure on your allocations,” shouldn’t deferred destruction give you more backpressure if anything? I am probably confused.

this could make your code faster by providing more consistent control flow: the main thread is always doing Work and your gc threads are always cleaning up dead objects. this provides fewer, better-predicted branches and code that's more likely to stay in the icache.

most gc based environments use dedicated threads for gc and finalizers, this is one reason to do so

edit: to be more specific:

your normal flow is to alloc at the top of your function, and at the bottom you dealloc. so in basically every case you are paying the cost of deallocs, but if the alloc is conditional the dealloc is now also conditional which is more branches to predict. the dealloc is probably also handled by functions so you have jumps/calls eating up branch prediction table space

in the gc/offloaded dealloc scenario, your deallocs on the work thread are no longer conditional because you're just handing addresses off to the gc. if your gc is STW you've added 'if (stop_requested) stop()' branches throughout your workload, but those are effectively 0-cost because stop_requested is always false (when it's true, the cost of the mispredict has no significance because your thread is about to suspend). the gc thread is always doing the same thing or waiting, and again when it's about to wait a branch mispredict cost has no significance.

There is no such thing as a free lunch here, so it would reduce the unloaded response time but should have no effect (or a negative impact) on a highly loaded server's response time. I'm finding this out when benchmarking a message passing/queue management system. Anything I do to defer work onto a separate threadpool improves latency up to a point, then reduces throughput.

Lots to be learned at https://blog.golang.org/ismmkeynote

I have no idea, but my guess is that it doesn't matter, as the deallocation is being done by the garbage collection.

Yes. There's also a number of pool/arena allocators in rust which could be used here instead to drop All entries at once.

> C++ supports it in the Standard Library, for all the standard containers.

I don't know what the situation is today, but in the past, the GCC standard library containers had non-trivial destructors when running in debug mode. Ensuring their proper invocation was required to avoid dangling pointers in their book keeping. Non-obvious and painful to debug.

Someone is working on this as a direct response to this blog:

https://www.reddit.com/r/rust/comments/go4xcp/new_crate_defe...

And yes, spawning a thread for every drop is horrible. It's just to prove the concept. The defer_drop crate uses a global worker thread.

It would have to be a non-desktop system.

I'm pretty sure Linux will always free process-private memory, and threads, and file descriptors when a process exits.

The only things that can leak in typical cases are some kinds of shared memory and maybe child processes?

The java equivalent to the Go case would simply be adjusting the -Xms flag. The Go approach is a needlessly convoluted because the runtime doesn't offer any tuning knobs.

As for the rust case, if you squint then it's similar to a concurrent collector.

Something is better than nothing.

If you pass by reference the heavy object won't be dropped. If your goal is to drop a heavy object, this is a cool way to do it.