Rust: Dropping heavy things in another thread can make your code 10000x faster • Hacker News Board

Re: Rust: Dropping heavy things in another thread can make your code 10000x faster

#31

Post by chowells » Sat, May 30, 2020, 5:33 PM UTC

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.

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

It's actually a lot to be said for rust that the ownership system lets you transfer freeing responsibility off-thread safely and cheaply in order to not have it block the critical path.

But overall, there's nothing really unexpected here, if you're familiar with memory management.

Re: Rust: Dropping heavy things in another thread can make your code 10000x faster

#32

Post by rhacker » Sat, May 30, 2020, 5:33 PM UTC

Pass by reference?

Re: Rust: Dropping heavy things in another thread can make your code 10000x faster

#33

Post by bszupnick » Sat, May 30, 2020, 5:34 PM UTC

cperciva wrote: post #9

If freeing the data structure in question takes this long, how much time are you wasting duplicating the data structure?

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...

Re: Rust: Dropping heavy things in another thread can make your code 10000x faster

#34

Post by Ididntdothis » Sat, May 30, 2020, 5:35 PM UTC

saagarjha wrote: post #27

Ididntdothis wrote: post #24

I used to do this sometimes with C++ when I realized that clearing out a vector with lots of objects was slow. Is Rust basically based on unique_ptr? One problem with this approach was that you still had to wait for these threads when the application would shut down.

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

Would you have to keep track of these threads in Rust? I have done a lot of desktop development where you have to be aware of what happens during shutdown. Seems a lot of server guys write their code under the assumption that it will never shut down.

Re: Rust: Dropping heavy things in another thread can make your code 10000x faster

#35

Post by bszupnick » Sat, May 30, 2020, 5:35 PM UTC

rhacker wrote: post #32

Pass by reference?

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.

Re: Rust: Dropping heavy things in another thread can make your code 10000x faster

#36

Post by [deleted] » Sat, May 30, 2020, 5:37 PM UTC

[deleted]

Re: Rust: Dropping heavy things in another thread can make your code 10000x faster

#37

Post by loufe » Sat, May 30, 2020, 5:37 PM UTC

chowells wrote: post #31

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. Generational/compacting GC has the opposite problem. Garbage collection takes time proportional to the live set, and the amount…

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.

Re: Rust: Dropping heavy things in another thread can make your code 10000x faster

#38

Post by seventh-chord » Sat, May 30, 2020, 5:38 PM UTC

epage wrote: post #20

saagarjha wrote: post #2

Why would you ever write a get_size function that drops the object you call it on? Surely in an actual, non-contrived usecase spawning another thread and letting the drop occur there would just be plain worse?

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 pr…

Killing a process without freeing all allocations is, as far as I can tell, routine in C. Especially for memory it makes no sense "freeing" allocations, the whole memory space is getting scrapped anyways. Of course, once you add RAAI the compiler cant reason about which destructors it can skip on program exit, and if programmers are negligent of this you get programs that are slow to close.

Re: Rust: Dropping heavy things in another thread can make your code 10000x faster

#39

Post by Reelin » Sat, May 30, 2020, 5:42 PM UTC

chowells wrote: post #31

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. Generational/compacting GC has the opposite problem. Garbage collection takes time proportional to the live set, and the amount…

> 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.

Re: Rust: Dropping heavy things in another thread can make your code 10000x faster

#40

Post by arcticbull » Sat, May 30, 2020, 5:43 PM UTC

chowells wrote: post #31

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. Generational/compacting GC has the opposite problem. Garbage collection takes time proportional to the live set, and the amount…

> 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.