Hacker News Reader

Comment by carllerche | Hacker News Reader

Author here. I'll be watching the comments and can answer any questions!

I do want to make clear that most of the optimizations discussed are implemented in the Go scheduler, which is where I discovered them. I wrote the article to call them out as they were not easy to discover.

View on HN

It looks like the number of threads in the threadpool is fixed. If have 1 one thread in the thread pool, is it possible to dead lock it by queuing a Task A the blocks waiting for Task B to do something, where A starts executing before B?

Do you think it would make sense to dynamically adjust the number of threads in the pool? An example of a thread pool that dynamically adjusts the number of threads is .NET. The algorithm is described by Matt Warren[1] and a paper[2]. In addition to the C++ version Matt links to, there is a C#[3] implementation.

[1]: https://mattwarren.org/2017/04/13/The-CLR-Thread-Pool-Thread... [2]: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.487... [3]: https://github.com/dotnet/corert/blob/master/src/System.Priv...

The expectation is that all code running on the Tokio scheduler does not block and does not do anything CPU intensive.

There is follow up work planned to allow annotating blocking / CPU intensive bits of code so that the scheduler can do something smarter (things like you linked).

The old scheduler already had such an annotation, but in the interest of shipping, this has punted in the new scheduler.

Is that expectation wrt. responsiveness guarantees? In other words, if I'm just interested in throughput are CPU intensive tasks a problem? For example, my expectation is that it would be appropriate to use the new Tokio scheduler to parallelize a compute intensive simulation workload (where inside a "frame" responsiveness is not a problem).

The Tokio scheduler uses cooperative multitasking (non-preemptive). So, if your task runs without yielding it can prevent other runnable tasks from executing.

So, if that is acceptable, then it is fine.

Is there a recommended approach to dealing with the occassional cpu intensive task?

Supposing you were running an http server and most responses were very quick - but occassionally a request came along that required calculating pi to the n billionth digit.. (for example).. Would you need to farm that request to a separate process - or could you keep it in process but in a separate thread outside of Tokio?

I believe tokio-threadpool is designes for this scebario.

Right now, CPU intensive code blocks or code blocks that block need to be annotated. This way, the scheduler can respond accordingly (cooperative).

The Go team is working on an update of its scheduler to make it preemptive. Will Tokio follow suit?

https://github.com/golang/go/issues/24543

My understanding of that PR is it relates to how the Go compiler does code generation. Rust takes a different approach and is about to ship `async / await` which is a different strategy.

Preemption is out of scope for Tokio as we are focusing on a runtime to power Rust async functions. So, for the foreseeable, Tokio will using "cooperative preemption" via `await` points.

IIRC: one of the issues with the original Rust stdlib greenthread implementation was that it's extremely difficult to preempt execution in a systems language. It's also quite difficult to add userland execution preemption without incurring significant performance penalties.

How do you preempt syscalls or FFI calls? (Go will almost certainly also have this issue with cgo modules)

I would be very surprised if preemptible Futures are something Tokio can or would implement.

What does systems mean here? There is a dirty trick with a NOP and self rewriting code that's quite cheap when not triggered. I think java does it that way.

Elaborate?

So you put in a NOP before each backward jump. To preempt you overwrite it with a jump to a handler that saves the state of the thread.

How multitasking used to work on Atari :)

But this requires code pages to be writable. Which, from a security perspective is awful.

How does that resolve syscall question?

Syscall you have to do with a signal

This presumes writable code segments, which many OSes shun.

It's java. Dynamic code generated by a jit.

Which NOP do you overwrite? Do you have to do this for all backward-jump-NOPs in all loaded executable code, or do you have to determine, which loop the thread in question is executing right now?

Preemption isn't a concept that applies to a task scheduler like Tokio. You can't just inject more states into a finite state machine at runtime.

When does that get released into Go? That sounds cool

I noticed that you call `unsync_load` on the `AtomicU32`, which confused me, and I later saw that there is a custom `AtomicU32` in the loom library. Can you explain what `unsync_load` is and whether it will be provided by the atomics library in `std`?

`unsync_load` reads the memory as if it were a normal field (no atomic operation). The `std` atomic types already provide `get_mut` which gives access to the "raw" field when the caller has a mutable reference to the atomic. The mutable access guarantees there are no concurrent threads that can access the field, so it is safe.

The `unsync_load` is used because, at that point, two things are guaranteed: - The only thread that mutates the field is the `unsync_load` caller - All other threads will only read from that field.

Because of this, we can just do a "plain old" access of the field w/o the atomic overhead.

As for whether or not it should be in `std`, I don't know. It probably could, but it doesn't have to. It's a pretty "advanced" access strategy.

What is the difference with Ordering::Relaxed?

Ordering::Relaxed guarantees atomicity (but not coherence). On 32-bit or 64-bit platforms, a (aligned) 32-bit read or write will always be atomic anyway.

What do you mean by coherence? If it is the property that all updates to a single memory location are seen in a consistent order by all threads then Relaxed guarantees that.

it doesn't. From cppreference (whose model Rust roughly follows): "Relaxed operation: there are no synchronization or ordering constraints imposed on other reads or writes, only this operation's atomicity is guaranteed"

Still I think I am correct. The docs (https://doc.rust-lang.org/std/sync/atomic/enum.Ordering.html...) point to https://llvm.org/docs/Atomics.html#monotonic which states that "It essentially guarantees that if you take all the operations affecting a specific address, a consistent ordering exists." which is what I've said.

Yes, a consistent ordering exists but that ordering isn’t necessarily what you think or want it to be. The consistency is present based off the order the reads and writes were executed in; you’ll never read back a value that wasn’t at some point stored there. Which can happen with non-atomic reads/writes, where you’ll read part of one write and part of the next. Reads can still be reordered before writes, as no memory barriers are issued.

Well that doesn't contradict anything that I have said :) My question remains - what do you mean by coherence? I argue that it is precisely the property that there is a consistent order of operations a single memory memory location so you can't say that Relaxed operations don't satisfy coherence.

You are correct. IIRC Coherency is the only property of relaxed atomic operations, as opposed of plain load/stores where concurrent modification and access is just UB.

An assembly-level read or write will always be atomic anyway, and in fact a relaxed atomic read/write typically compiles down to the exact same assembly as a normal read/write. However, there are compiler optimizations that can break atomicity, such as splitting accesses into multiple parts; using (relaxed) atomics instructs the compiler not to perform those optimizations.

Relaxed ordering impacts the compiler. There are a number of optimizations it cannot make. I am not sure exactly what those are, but it is measurable.

Probably some reordering? Would be interesting to compare generated assembly.

I believe there are some LLVM "bugs" with regards to Relaxed ordering. I don't know the specifics.

The only forbidden optimization I could come up with is:

    x = load-relaxed(a)
    ...
    f(x)

cannot be turned into

    x0 = load-relaxed(a)
    ...
    x1 = load-relaxed(a)
    f(x1)

while this would be possible with normal memory access.

so under register pressure the compiler would be required to spill something onto the stack instead of just reloading `x` from the original location.

Last time I spoke about this topic w/ the rust compiler devs, they mentioned there were some LLVM "bugs" with regards to optimizations and Relaxed, as in LLVM is too conservative.

Is that not an undefined behaviour?

Can't you get some values "out of thin air" (partial updates of some bits.) Or some intermediate values?

(For example, can the compiler decide to use this memory location to store some unrelated temporary result, as it knows it will erase it soon with a final value and that no other threads is supposed to access this)

The compiler cannot use the contents of an `UnsafeCell` for temporary storage. In general, `UnsafeCell` is how data can be shared across threads without synchronization.

I thought `UnsafeCell` is only exempt from the aliasing rules, not the memory model? I.e. the compiler can use it as it wants, if it can prove that it's not accessed in the meantime (which can be difficult without relying aliasing rules, but possible if the code is simple enough)

To be honest, I'm not entirely following what you see as the danger. The compiler can't generate code that randomly goes and writes at pointer locations.

In x86 at least, 32 bit loads and stores are done atomically already.

I know rust is not C or C++, but we are not programming in x86 assembly, but for the language "abstract machine". And if the compiler infer that this memory location is not used by other threads because we don't use an atomic operation, it can perform optimizations that could result in subtle bugs. That's what undefined behaviour is.

Although in this case, I guess this is probably fine since the non-atomic read can't race with a write.

The code is correct both practically and formally. All unordeeed reads are reading values written by the same thread. Even if the writes are atomic there is no violation of the no data races rule.

x86 does do out-of-order execution however, so while it's true that you'll never read a half-written value, it's still important to use the atomic types to ensure that reads/writes across threads are performed in the right order.

That's true but not what is being discussed here.

It's not undefined because the thread doing the reading is the same one that wrote the value in the first place, meaning there is no cross-thread behavior at the moment and therefore the memory model collapses down to the single-threaded model (where all atomic accesses are irrelevant).

Tiny comment: I think the sentence "However, in practice the overhead needed to correctly avoid locks is greater than just using a mutex." should be part of footnote 1, not the main text.

Too bad FFBuffer is not implemented from the FastFlow project. They are using queues without memory fences.

Assuming [this](https://github.com/fastflow/fastflow/blob/master/ff/buffer.h...) is the FFBuffer in question, it looks like it is spsc (which would not support stealing). Also, it would need some kind of synchronization to ensure consistency between the consumer & producer.

Yes, it's an implementation of the paper they're referencing - "An Efficient Unbounded Lock-Free Queue for Multi-core Systems". And they've build a framework around it (all queues implemented using this structure). Their benchmarks shows improvement (as shown in their paper). Might be interesting to use that in Rust. But what I miss is a benchmark for various approaches (in Rust, C++ etc.) with trying to use multi core effectively. What I found is that some of the papers use https://parsec.cs.princeton.edu/overview.htm. Probably still better that what we have now - "X nanosec per push/pop".

The advantage of FF is that it is unbounded, but if you add the required mutual exclusion between pop and steal, it will be as expensive (if not more due to the extra complexity).

Reply on news.ycombinator.com