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

#261

Post by pdimitar » Sun, May 31, 2020, 12:20 PM UTC

michaelcampbell wrote: post #259

pdimitar wrote: post #166

Earlier quoted context omitted.

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.

Well, I have been taught to take good manual care of all used resources. It is kind of a cognitive shock when you see all your training hand-waved away with "let the OS handle my mess of allocated objects that I'll never call `free` on". It's kind of disappointing on some level. :)

As I acknowledged in other comments of mine downthread, I understand that different situations require different tradeoffs. It's just that forgoing memory deallocation wasn't one of them in my head.

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

#262

Post by pdimitar » Sun, May 31, 2020, 12:23 PM UTC

smabie wrote: post #219

pdimitar wrote: post #184

Earlier quoted context omitted.

I realise that, but nowadays language servers are a pretty normal practice in no small amount of areas.

You mean like LSP? Why would a compiler and a language server be integrated in the first place? Clearly a LSP server wouldn't use a no-freeing strategy, but there's no reason why it would cause issue with a compiler. A compiler must terminate, assuming parsing isn't turing complete (like Perl) and that the source code is finite. This is why it's okay for it to leak memory.

Yep, I guess I conflated compilers and LSP. I imagined compilers would have daemon modes. Seems like I was wrong.

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

#263

Post by pron » Sun, May 31, 2020, 12:39 PM UTC

tsimionescu wrote: post #254

pron wrote: post #113

Earlier quoted context omitted.

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

Not every GC pass. Some modern GCs (like OpenJDK's default GC, G1) track mutation and maintain "remembered sets." They only need to scan objects that have changed since the last scan (they're actually even more efficient than that, but this is a simplification). In addition, when this scanning is required, it is performed concurrently to the application, so the technique of moving the work to a separate thread is done automatically.

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

#264

Post by steveklabnik » Sun, May 31, 2020, 1:07 PM UTC

smabie wrote: post #219

pdimitar wrote: post #184

Earlier quoted context omitted.

I realise that, but nowadays language servers are a pretty normal practice in no small amount of areas.

You mean like LSP? Why would a compiler and a language server be integrated in the first place? Clearly a LSP server wouldn't use a no-freeing strategy, but there's no reason why it would cause issue with a compiler. A compiler must terminate, assuming parsing isn't turing complete (like Perl) and that the source code is finite. This is why it's okay for it to leak memory.

> Why would a compiler and a language server be integrated in the first place?

Because a language server needs to do a lot of the same work as a compiler.

This is an eventual hope for rustc. For now, the latest language server and it share a bunch of libraries, but language servers are effectively compiler frontends.

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

#265

Post by steveklabnik » Sun, May 31, 2020, 1:08 PM UTC

afiori wrote: post #251

josephg wrote: post #194

Earlier quoted context omitted.

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…

It is not an allocator wrapper, but https://docs.rs/defer-drop/1.0.1/defer_drop/index.html

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

#266

Post by littlestymaar » Sun, May 31, 2020, 2:00 PM UTC

tsimionescu wrote: post #260

pshc wrote: post #244

Earlier quoted context omitted.

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

Yes, that's a great summary!

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

#267

Post by setr » Sun, May 31, 2020, 2:31 PM UTC

pdimitar wrote: post #202

setr wrote: post #196

Earlier quoted context omitted.

I don't understand; a lambda function executes and closes, and any leak gets handled by lambda runtime (by freeing the whole lambda function)-- exactly the same as running a cli tool. It seems to me that the server-less context is actually exactly where you'd employ this strategy: the programs by definition cannot be long-lived, so unless they generate so much garbage as to oom in that timeline, there is no need to d…

Yeah, this is what I was saying -- that it could produce too much garbage if no manual free-ing of memory is done. I suppose, judging by the downvotes, that some find that perspective naive so I'll just cut it here because no productive discussion is happening. :(

the purpose/pattern is to ignore deallocation when the program finishes -- not during runtime. If you have 30MB of space, and your program will only ever use 20MB, why bother?

You only need to care when you're at risk of OOM'ing during runtime. If you're generating too much garbage, you either need to start cleaning up after yourself, or you need to generate less of it -- but it doesn't matter which choice you take from the perspective of the OS or the server-less function.

The only reason I can think of for server-less to impact the validity of this pattern is from it's lower memory capacity -- but otherwise it's the same constraints. And anyways, it's probably not nice to generate a few GB of garbage even if the user has the space

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

#268

Post by jeffdavis » Sun, May 31, 2020, 3:00 PM UTC

titzer wrote: post #248

jeffdavis wrote: post #164

Earlier quoted context omitted.

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

This is most decidedly not true for generational GCs, and for concurrent GCs, the tracing work happens asynchronously and in parallel, on other cores, not taking time on the main thread.

You still have to scan the oldest generation at some point; otherwise (assuming some activity) you'll be leaking memory there over time.

Moving the work to another core doesn't really change my statement.

Aside: I wonder if it's feasible to switch to reference counting for the oldest generation? That would move the problem back to deallocation. I'm not sure if that's a good trade-off, but it would be interesting.

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

#269

Post by ablu » Sun, May 31, 2020, 3:03 PM UTC

dirtydroog wrote: post #243

ablu wrote: post #240

Earlier quoted context omitted.

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

shared_ptr all the things? If so, they may as well write in Java.

Even ignoring the shared_ptr abuse, at least for allocating and freeing many small objects Java would most probably be (a lot?) faster than non-optimized allocations and frees in native binaries. But in my case it was legacy code running on an embedded device.

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

#270

Post by zucker42 » Sun, May 31, 2020, 4:10 PM UTC

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, C++ destructors are used for finalizers, not memory management.

In the original comment I may have overstated this. I was ignoring the other uses of destructors because the context of the discussion was memory management. But memory management is a huge portion of what destructors do in C++. Consider a vector of strings (`vector`). The destructor deallocates the memory for all the strings, then deallocates the memory for the vector.

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

How do you deallocate all of the nodes in a binary tree? As far as I can tell, you either have to pointer chase or use a custom allocation strategy. At some point with the second option, you're basically creating an ad-hoc garbage collector.

But I think we may be in vigorous agreement here, since my comment was about the general tradeoff between garbage collection and tracing data structures. I was trying to defend the original assertion that with tracing, "freeing the structure takes time proportional to the number of pointers in the structure it has to chase" while "garbage collection [or at least copy collection] takes time proportional to the live set".