Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

abramov.io

Post reply on HN
Print view View original

251–260 of 285 posts

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

#251

Post by afiori »

josephg wrote: post #194
orf wrote: post #86

Earlier quoted context omitted.

You can change the global allocator in any rust project. You can write your own easy enough, or use one like jemalloc

Sure; but when you’re using arenas and things like that you usually you will want different objects allocated into different pools (or with different lifetime properties). Rust only lets you pick one allocator for the entire process, so you can’t specify “all the children of this data structure go in arena A, and this other allocation goes into a traditional heap”. It’s more awkward, but I much prefer Zig’s approach…

As someone that is interested in the topic and in Zig's "provide your own allocator" approach I have a question: would it be possible to make an allocator wrapper that moves values to be deallocated to a different thread?

As far as I know it would require both Rust's borrowing semantics and Zig's architectural choice.

From purely my own fan-boy perspective Zig approach is something that I would have really liked for Rust to adopt (I have no idea of which one came first chronologically).

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

#252

Post by tsimionescu »

burpsnard wrote: post #197
loufe wrote: post #37

Earlier quoted context omitted.

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.

It's worth popping the hood and getting your fingers dirty. C was written in an era where memory was a scarce and precious resource to be grudgingly used if absolutely necessary

Please note that C is quite a few years older than the first GC languages. LISP1.5, ALGOL-68 and APL all had garbage collectors before C even existed.

Not to say that it's not worth it to learn manual memory management as well, but it is important not to think that GCs are a fancy modern tool, and that greybeards would never touch one. There were greybeards using punch cards and programming in a GC language, with output printed out on paper.

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

#253

Post by tsimionescu »

chowells wrote: post #62
arcticbull wrote: post #40

Earlier quoted context omitted.

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

I said generational/compacting collector. You're talking about a mark and sweep collector. A generational/compacting collector traverses pointers from the live roots, and copies everything it finds to the start of its memory space, and then declares the rest unused. If there is 1GB of unused memory, it's irrelevant. Only the things that can be reached are even examined. As I said, this has the opposite problem. When…

Even mark-and-sweep collectors only mark starting from GC roots, they don't mark through unreachable objects.

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

#254

Post by tsimionescu »

pron wrote: post #113
arcticbull wrote: post #40

Earlier quoted context omitted.

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

> 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 Yes, but in practice tracing in a tracing GC is done concurrently and with the help of GC barriers that don't require synchronization and so are generally cheaper than the common mechanisms for reference-counting GC. > and to invoke finalizers As others…

No, they are actually fundamentally wrong. GCs never scan garbage - they only scan objects that are referenced from a GC root.

Note that the problem appears in a different place: if your large structure is actually not garbage, then every GC pass will have to scan it to see what other objects it is keeping alive.

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

#255

Post by cesarb »

tsimionescu wrote: post #249
dathinab wrote: post #138

Earlier quoted context omitted.

What is bit-wise copied is the pointer to the memory. I.e. a `HashMap` struct, or `Vec` struct don't directly contain the data. For example the `Vec` is defined internally as something similar to: `struct Vec { data: *mut [T], capacity: usize, len: usize, marker: PhantomData }` (Slightly simplified, not actual Vec type). So a move of a Vec copies at most 3 usize (24 bytes on 64bit systems), similar thinks apply for a…

So the Vec type is not storing data on the stack, like C++'s std::vector can?

Exactly, neither Rust's Vec nor Rust's String (which is actually a Vec in disguise) store data within the struct itself, it's always stored in an external allocation. This is intentional, to avoid extra branches on whether the data is inline or not. If you have a lot of small vectors, and using less memory is more important for your use case than avoiding the extra branches, there are alternatives like https://crates.io/crates/smallvec that you can use.

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

#256

Post by tsimionescu »

arcticbull wrote: post #40
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…

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

All garbage collectors start from live objects and only scan those. Then, whatever objects they have not scanned get collected. In copying collectors (like most generational ones), this means that garbage is never touched.

In the mark-and-sweep algorithms, the mark phase still never touches the unreachable objects. However, the sweep phase does need to return those objects to the free list, so it will have to walk them. It will still not do it the same way as malloc/free, as it can walk the heap in order and free unmarked objects as it encounters them, no need to follow pointers, so it may still have better cache performance.

Finalizers introduce extra difficulty, but still the behavior is fundamentally different. What usually happens is that objects which have finalizers are usually remembered in a special list which acts as a GC root itself. When they are only reachable from that list, they get marked so that the finalize will run (usually on a special Finalizer thread). When the Finalizer is finished, and assuming the object was not resurrected, they get removed from the Finalizer list, and now they are not reachable from anywhere at all, so the next GC will finally clean them up. Usually, there is also some API for user code to mark a Finalizable object as 'finalized', which essentially removed it from the Finalizer list early and allows it to be collected as normal, without going through the above process.

And yes, having a large number of finalizable objects in your memory is usually considered a very bad idea. Generally, they are only recommended as a fail-safe measure: you are supposed to do explicit cleaning, but as a fail-safe, to avoid your program crashing in production if a connection or file leak was missed, you also have the Finalizer to throw buckets of water out of your boat (but you should really notice that it is happening and plug that leak, rather then relying on the bucketeer).

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

#257

Post by tsimionescu »

jfkebwjsbx wrote: post #229
zucker42 wrote: post #94

Earlier quoted context omitted.

Java is an example of a language with a generational copy collector by default. Most objects in Java don't have a finalizer, since after all the main point of, for example, destructors in C++ is to make sure you don't leak memory, which the GC solves. But when the `finalize` method is used is causes significant overhead. > Objects with finalizers (those that have a non-trivial finalize() method) have significant over…

> after all the main point of, for example, destructors in C++ is to make sure you don't leak memory, which the GC solves No, C++ destructors are used for finalizers, not memory management. Memory deallocation is a particular use case for finalizers which is avoided when performance is a concern. > Another point is the C++/Rust pattern of each object recursively freeing the objects it owns presumably leads to slower…

> No, a program that does pointer chasing and has to deallocate many small allocations is badly designed. If you are going to do that, using a GC language would be much better.

It is debatable whether using it is good or bad design, but at least the C++ std lib does offer a data structure which requires exactly this kind of deallocation: std::list and std::forward_list. And, given the cache characteristics of array VS linked list implementations, I would guess that most uses of std::list occur for huge lists that get written to often, as that seems to be the only case where the big-O advantage of list inster/delete would actually materialize into any performance benefit over a std::vector.

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

#258

Post by tsimionescu »

Reelin wrote: post #88
arcticbull wrote: post #65

Earlier quoted context omitted.

How are finalizers invoked if the structure isn't traversed? Would it just be optimized away none of the objects have finalizers? Hence my suggestion about the area allocators being a better point of comparison.

My understanding is that finalizers are special cased for a generational GC, have a tendency to introduce significant overhead, and (as with any GC scheme) generally run at unpredictable times. My impression is that RAII idioms are strongly discouraged in conjunction with most GC ecosystems.

Actually, RAII idioms are generally encouraged, but finalizers are not. For the rare few classes that hold resources in GC languages, the Resource is usually Acquired at Initialization as well, and released in a special method (IDisposable.Dispose() in C#, AutoCloseable.Close() in Java). There is also usually some special syntax for automatically calling this syntax when the object exits some scope, though that scope usually has to be declared by the user (using(), try-with-resources, with() in Python etc.).

The biggest difference I know of is that the 'holds-resources' property does not propagate automatically like it does in C++. It's not that hard to always remember to call using(file = new File()) [...]. However, it's much easier to forget that you have a File field in your class which you initialize in the constructor, and so your class must itself be declared IDisposable/AutoCloseable etc.

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

#259

Post by michaelcampbell »

pdimitar wrote: post #166
qzw wrote: post #132

Earlier quoted context omitted.

Well, then that’s not the original use case anymore, and it’ll have to be re-engineered. In the meantime it may have been used for years and the perf difference may have saved many developer-years collectively across its user base. Surely you’re not suggesting that the compiler developers should be prematurely optimizing for future use cases that they may not even have envisioned.

I am suggesting they apply good practices. I'd never imagine that compilers were actually doing what was stated -- sounds awful. I understand it's tradeoffs and we all have real-world limitations to contend with -- but again, of all the corners that could be cut that's exactly the one I didn't imagine they would. Nasty.

> I'd never imagine that compilers were actually doing what was stated -- sounds awful.

And how many millions of iterations have been done successfully in that "awful" system?

The very fact that you never imagined it I think says a lot.

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

#260

Post by tsimionescu »

pshc wrote: post #244
littlestymaar wrote: post #149

The title is slightly wrong: it's not going to make your code faster , it's going to reduce latency on the given thread. It maybe a net win if this is the UI thread of a desktop app, but overall, it will come at a performance cost: because modern allocators have thread-local memory pools, and now you're moving away from it. And if you're running you code on a NUMA system (most server nowadays), when moving from one t…

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…

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

I think the point is that, if the same thread is doing both allocation and de-allocation, the thread is naturally prevented from allocating too much by the work it must do to de-allocate. If you move the de-allocation to another thread, your first thread may now be allocating like crazy, and the de-allocation thread may not be able to keep up.

In a real GC system, this is not that much of a problem, as the allocator and de-allocator can work with each other (if the allocator can't allocate any more memory, it will generally pause until the de-allocator can provide more memory before failing). But in this naive implementation, the allocator thread can exhaust all available memory and fail, even though there are a lot of objects waiting in the de-allocation queue.

Post reply on HN