27 ms·
Resource efficient Thread Pools with Zig
- ur-whale 5y agoHow does it compare with a bare-metal C++ threadpool?
- judofyr 5y agoWhat is a bare-metal C++ threadpool? Is that a specific library you're referring to?
- mcnichol 5y agoYou've been spending too much time arguing over virtualization or bare metal. You are at the wrong level of abstraction.
- thechao 5y agoWeellll... I guess you could get rid of the OS and switch to a stack-only ABI with a callee saves-everything policy? Then "thread switching" and "multiprocess" both map onto saving/restoring the stack (on ARM you'd have to have SP/LR motion to stack), and process communication would just be over a unified stack. What'd be cool is if every core (and, thus, affinitized process) had its own virtual address. That way if any single core went down, its neighbors could stand it back up. Of course, you'd have to have some sort of hideous last-level shared virtual addressing scheme — probably with large last level pages — to "migrate" a "process" between cores. EDIT: And security be damned! We need that last .5%!
- dragontamer 5y agoGPUs are practically the "OS-free" compute device of choice these days. The way GPUs work in most cases is through work-queues. The CPU submits work to GPUs (either OpenCL queues or CUDA Streams), and the GPU "plucks" work off of the queue to do. There are dozens of SMs (NVidia) or CUs (AMD GCN) or WGPs (AMD RDNA) that pluck the work off concurrently. The kernels are then run to completion. Upon completion, the stream gets an event that triggers (which often times, automatically enqueues another task). If the CPU has work to do, it can get an async message (or maybe be waiting through blocking behavior). -------- There are other models of course, not everyone runs the standard methodology. "Persistent kernels" start up early on and infinite-loop. You interact with those by passing data over PCIe and the kernel itself contains a queue/load-balancing logic to pickup the data somehow (rather than letting the device drivers / hardware logic do that) ------ The thing about GPU-level tasks is that you have so many little tasks (ex: shoot a ray, or render pixel (0,0), render pixel(1,0), etc. etc.) that just pulling tasks off of a queue is your most efficient methodology. Lots of small, roughly equal-sized tasks can be load balanced with simple methodologies.
- gpderetta 5y agoTo be very pedantic, Vyukov MPSC queue, while indeed awesome in its simplicity and performance, is not technically lock-free, not even obstruction free (and Vyukov never claimed it as such [1]): a producer halting between the atomic swap and atomic store will prevent further nodes enqueued by other producers from ever being dequeued by the consumer. [1] edit: and in fact there is a note exactly on this on the linked Vyukov page.
- kprotty 5y agoI'm aware that it's technically considered blocking due to a producer being preempted between swap and store causing the consumer to see an invalid link and report empty. I address this in the run queue section by noting that it's OK if empty is spuriously reported since the thread waking/waiting mechanism takes care of rescheduling such a case.
- jedisct1 5y agoPretty impressive achievement!
- jorangreef 5y agoIncredible post. Ticks all the boxes and exciting to see this coming to Zig. Protty has got to be a domain specialist when it comes to atomics and threads.
- vanderZwan 5y agoIf they weren't before, they probably are by now after all the work put into this
- Jarred 5y agoRunning the benchmarks locally (zig is fastest, but that's probably expected) zig (~1 week older than HEAD): ./zig-out/bin/qsort filling shuffling running took 177.46ms rust nightly: cargo run --release --bin qsort warning: the cargo feature `edition2021` has been stabilized in the 1.56 release and is no longer necessary to be listed in the manifest See https://doc.rust-lang.org/nightly/cargo/reference/manifest.html#the-edition-field for more information about using this feature. Finished release [optimized] target(s) in 0.02s Running `target/release/qsort` filling shuffling running took 896.91656ms cargo run --release --bin rsort warning: the cargo feature `edition2021` has been stabilized in the 1.56 release and is no longer necessary to be listed in the manifest See https://doc.rust-lang.org/nightly/cargo/reference/manifest.html#the-edition-field for more information about using this feature. Finished release [optimized] target(s) in 0.02s Running `target/release/rsort` filling shuffling running took 212.190694ms go 1.16.3: go run qsort.go filling shuffling running took 222.90356ms on macOS 11.5.2 with a 2.4 GHz 8-Core Intel Core i9
- komuW 5y agoWhen you do `go run qsort.go` you are also timing the time taken by Golang to build/compile the code. I suspect the same applies to `cargo run` You should do something like; `go build . && time ./qsort`
- masklinn 5y agoThe same occurs with Rust, we can even see that the no-op recompilation takes about 20ms. It’s obviously just a rough estimate / comparison otherwise it’d be using hyperfine or something along those lines.
- nessex 5y agoThis is not the case, it measures the time between two points in the code at runtime and prints that[1]. [1] https://github.com/kprotty/zap/blob/blog/benchmarks/rust/rayon_qsort.rs#L14-L17 https://github.com/kprotty/zap/blob/blog/benchmarks/rust/ray...
- kevingadd 5y agoIt's always great to see a robust new threadpool. Most of the stock ones I've used have horrible characteristics - for example on my Threadripper lots of production apps will spawn 48 or more threadpool threads and the scheduling/throughput characteristics on that are generally pretty dire because they needlessly compete for resources, etc. They tend to allocate garbage for every work item too, which makes them a bad choice for realtime scenarios. It's genuinely frustrating that most processes on my machine have 128 threads or more due to unintelligently scaling off ProcessorCount without an upper limit. For example, GIMP's bad threading policy means that operations like resizing an image take seconds instead of 100ms or less. I've been using a custom threadpool for a while now but writing your own without the expertise necessary can be a real pain.
- eptcyka 5y agoI don't think that it's the threadpool's fault that an application uses it incorrectly. Also, I think there are a lot of developers who have not considered that on today's machines, just spawning as many threads as there are cores is the optimal amount of threads in a thread pool for every use case. I wouldn't say it's the case of bad software but rather software that was written for the CPUs of 5 years ago. And generally, I don't think this will be an easy problem to solve due to the variety of heterogeneous and non-heterogeneous topology of modern SoCs. In fact, I don't see this specific threadpool doing anything to optimize for the disparate core clusters of your threadripper, or to acknowledge the disparity between core clusters on the M1.
- matu3ba 5y ago> I don't see this specific threadpool doing anything to optimize for the disparate core clusters of your threadripper, or to acknowledge the disparity between core clusters on the M1. To do that efficiently you need to pin thread groups to cores based on having information of data usage. This smells like over-optimizing architectures to me, if you want to go beyond separating stuff like hyper-threads on io. Additional annoyance: There is no POSIX way to get hyperthreads and physical ones.
- 5y ago
- r0f1 5y agoI know this is off-topic, but does this website not look eerily familiar to dev.to?
- ibraheemdev 5y agoI'm guessing it's using forem, the open-source platform that powers dev.to: https://github.com/forem/forem https://github.com/forem/forem
- andruby 5y agoThat's correct. Both are built on Forem. It's in the footer: Built on Forem — the open source software that powers DEV and other inclusive communities. Made with love and Ruby on Rails. https://github.com/forem/forem https://github.com/forem/forem
- r0f1 5y agoAh I did not know that. Thanks :)
- kristoff_it 5y agoYes, as others have said, it's based on the same open source CMS. I've created zig.news for people who want to write about Zig but who don't necessarily want to maintain their own blog and to the work necessary to publicize it. This should hopefully help more people write down their experience and opinions on using Zig and alleviate the problem of having a "blogger aristocracy" who has a much stronger voice than anyone else. I briefly go over this concept in this 3mins long video: https://www.youtube.com/watch?v=i9pUuj6eiEg https://www.youtube.com/watch?v=i9pUuj6eiEg
- scott_s 5y agoI designed and implemented a mostly lock-free dynamic thread scheduler for streaming runtimes, and I learned some similar lessons: avoid global data and amortize the necessary synchronization that you have to do. One of the main peculiarities of a streaming context is that work-stealing is counter-productive. In a streaming context, it's more like cutting in when the work would be done anyway. It's better to go find a part of the streaming graph that is not currently being executed than to steal some from another thread. The paper describing my design is "Low-Synchronization, Mostly Lock-Free, Elastic Scheduling for Streaming Runtimes", https://www.scott-a-s.com/files/pldi2017_lf_elastic_scheduling.pdf https://www.scott-a-s.com/files/pldi2017_lf_elastic_scheduli.... The source code for the product implementation is now open source. Most is in https://github.com/IBMStreams/OSStreams/blob/main/src/cpp/SPL/Runtime/ProcessingElement/ScheduledQueue.h https://github.com/IBMStreams/OSStreams/blob/main/src/cpp/SP... and https://github.com/IBMStreams/OSStreams/blob/main/src/cpp/SPL/Runtime/ProcessingElement/ScheduledQueue.cpp https://github.com/IBMStreams/OSStreams/blob/main/src/cpp/SP....
- goodpoint 5y agoHow does it compare to Nim's Weave thread manager?
- chris_st 5y agoNim newby here -- does Nim have something analogous to Go's channels for inter-thread communication?
- goodpoint 5y agoYes, it has channels as a built-in: https://nim-lang.org/docs/channels.html https://nim-lang.org/docs/channels.html Things like Weave abstract away the need to manage threads and messaging explicitly.
- feffe 5y agoA pet peeve of mine is calling something using atomic operations lock less. It's very common but once it click that atomic operations are just locks on the instruction level it feels very wrong to call most algorithms lock less. There's still the same concerns to avoid contention when using atomic operations as with regular mutexes. A mutex lock in the uncontended case never enters the kernel and is just an atomic operation... The main strategy regardless of if using locks or atomics directly is to avoid contention. The only truly lock less algorithm that I'm aware of (for most CPU archs) is RCU in the read case.
- gpderetta 5y agoAtomic instructions are not locks on the instruction level (the lock prefix on x86 is just an historical artefact). edit also lock-free has not much to do with locks.
- feffe 5y agoIt's a lock associated with the cache line that the atomic operation operates on. This is because they are built on top of the cache coherency mechanism, a synchronous blocking operation on the hardware level to implement an asynchronous mechanism on the software level. The big frustration with today's multi core CPUs is that there's simply not efficient way to communicate using message passing mechanisms. I think this is something the hardware guys should focus on :-) Provide an async mechanism to communicate between cores, not relying on the cache coherency.
- gpderetta 5y agoThere is no lock associated with the cache line. The coherency protocol guarantees that a core can own in exclusive mode a cache line for a bounded number of cycles, this guarantees forward progress and it is different from an unbounded critical section. It has also nothing to do with the lock prefix and also applies to normal non atomic writes. What the lock prefix does is delay the load associated with the RMW so that it is executed together with the store before the core has a chance to lose the ownership of the line (technically this can also be implemented optimistically with speculation and replays, but you still need a pessimistic fallback to maintain forward progress). A message passing feature would be nice, but it would be necessarily non coherent which means you can only use it to pass serialised values, not pointers to other threads. An alternative more usable solution would be to aggressively speculate around memory barriers as the memory subsystem is already highly asynchronous.
- egberts1 5y agoThis is the first four-state-machine thread algorithm. And I like what I am seeing. Hopefully all transitions between states have been tested. Good work.
- matu3ba 5y agoDrawing them could help figuring out all (invalid) state transitions. Certainly would make a cool drawing.
- sn9 5y agoUsing a formal methods tool [0] like Alloy [1] would honestly be ideal. [0] https://www.hillelwayne.com/tags/formal-methods/ https://www.hillelwayne.com/tags/formal-methods/ [1] https://www.hillelwayne.com/tags/alloy/ https://www.hillelwayne.com/tags/alloy/
- StreamBright 5y agoIs there a IoC / CSP (ala core.async in Clojure) in Zig yet? Is it planned to have something like this? I could not find too much about that online.
- matu3ba 5y agoThe former (Inversion of Control) is a general method and too unspecific to answer. I can only hint that one of the biggest caveats of async is brittle composability due to missing cancellation routines. This will eventually be addressed. The latter (communicating sequential processes) is a formal language, but it looks like it is for IPC: https://arild.github.io/csp-presentation/#1 https://arild.github.io/csp-presentation/#1
- randyrand 5y agoplease have Thread Priority a native feature. See GCD.
- riofoxx 5y agoT.o a.s.s.i.s.t y.o.u i.n t.r.a.d.e.s f.o.r b.e.t.t.e.r i.m.p.r.o.v.e.m.e.n.t on c.r.y.p.t.o.c.u.r.r.e.n.c.y W.h.a.t.s.A.p.p (+13052395906)
- posharma 5y agoHow does this compare to OpenMP? Does it support nested parallelism? (disclaimer: haven't read the post thoroughly).
- omazurov 5y agoIncreasing the size of the array 10x (100_000_000) and filling a glaring omission: Go (go1.17.1 darwin/amd64) took 5.591593544s took 5.285948722s took 5.218750076s took 5.239224787s took 5.131232207s Zig (0.9.0-dev.959+f011f1393) took 3.48s took 3.37s took 3.44s took 3.43s took 3.49s Java (openjdk version "17-ea") Time: 2684 ms Time: 2654 ms Time: 2840 ms Time: 2676 ms Time: 2649 ms MacBook Pro Early 2013, 2.7 GHz Quad-Core Intel Core i7, 16 GB 1600 MHz DDR3
- gavinray 5y agoIs this using JVM/JIT or using Graal to make a native-image binary and calling that? You'd get better results due to shaving off startup time with that if it does include it. I think .NET 6 latest preview would slightly beat out Java here as well. This isn't exactly apples-to-apples since Zig/Rust/Go are considered "systems languages", but the JVM has GraalVM for compiling to native binaries/libraries and even importing/exporting C functions and structs. And .NET of course has .NET Native + "Dotnet Native Exports", including the LLVM experiment where it uses LLVM bitcode instead of Ryu. So you can make the argument that writing a native binary or a library which exported this benchmark function as a C-callable method with a C header in each language would technically equivalent. The JVM and .NET ones would have a large size (several MB each) but would otherwise still fill this requirement.
- vips7L 5y agoThis is most likely using HotSpot as I don’t believe Graal has released anything past Java 11. I don’t know if native-image would perform better. I’ve mostly found that it performs worse than HotSpot overall, especially once you start generating garbage and the heap gets larger the Serial GC won’t keep up with G1.
- fiddlerwoaroof 5y agoYeah, I think people seriously underestimate the abilities of the JVM
- 5y ago
- lmb 5y agoWhat does tail latency for the Zig pool look like? It seems like any Task that ends up in one of the overflow queues will stay there until at some ring buffer is emptied. Put another way, during a period of more push than pop some tasks may see a very long delay before being worked on?
- kprotty 5y agoId encourage you to try recording them yourself. The results can vary depending on your system, how much concurrent tasks it can make parallel, if scheduling resources are being used elsewhere, etc. The zig code contains an example of using timers + the spawning and joining is in quickSort() function so it should hopefully be easy to add the timing logic. I can answer questions regarding it if you hop on the IRC or Discord. In regards to the overflow queue, yes some pathologica tasks may see long delyas but this is true for any mostly-FIFO or sharded queue scenario. Both Golang and Tokio overflow from their local buffer into a shared lock-protected linked list (tokio is a bit more eager in this regard) so they can suffer similar fates. They actually do an optimization which is to check the shared queue before the local buffer every few local scheduling ticks (% 61 or 64 for each task run iirc) to decrease the change of local starvation. Could try adding that to Zig's thread pool after the timing logic and see if that helps tail latencies. I'm curious about the outcome either way, but I may not have time to work on that.