8 ms·
Make your program slower with threads (2014)
- tombert 2y agoI feel like it's a rite of passage for every engineer to write a program with the assumption of "more threads = faster", only to find their program going considerably slower.
- mandevil 2y ago“The real problem is that programmers have spent far too much time worrying about efficiency in the wrong places and at the wrong times; premature optimization is the root of all evil (or at least most of it) in programming.”- Donald Knuth, The Art of Computer Programming
- tombert 2y agoWell the last time the thread thing bit me was actually a case where it wasn't premature optimization; I had written the code in such a way that I thought was pretty enough, and we were hitting bottlenecks, so my genius brain thought "ok I'll make this use 20 threads and it'll go faster". It did not.
- asa400 2y agoPretty sure I’ve made exactly the same mistake. I feel like everyone who ever writes concurrent code learns that lesson at some point. It’s absolutely astonishing how much mileage one can get out of thread-per-core-fed-by-work-queues architectures.
- xiasongh 2y agoThere's key parts left out of that quote that changes the tone quite a bit. Here is the full one "Programmers waste enormous amounts of time thinking about, or worrying about, the speed of noncritical parts of their programs, and these attempts at efficiency actually have a strong negative impact when debugging and maintenance are considered. We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3%." - Donald Knuth
- deleted 2y ago[deleted]
- Animats 2y agoKnuth was writing in an era when scientific programs tended to be dominated by inner loops. There was an input part, a compute part that did some number-crunching, and an output part. Only performance in the compute part mattered. Many programs today have no inner loop. Compilers were the first important programs that didn't. Most interactive programs have an outer loop processing events, rather than an inner compute loop. Note that "AI" programs are much more like the scientific problems of Knuth's era. All the compute is in tight loops wrangling matrices.
- foobiekr 2y agoSadly, this no longer really applies. Programmers today do absolutely grotesque things unimaginable to Knuth of that era. One look at any modern pipeline that converts to and from JSON a dozen times, sometimes even inside the same process between modules, would make Knuth recall all of that. Programmers now have done the impossible: written code so consistently bad that there are no hotspots, because the whole codebase is non-performant trash.
- hindsightbias 2y agoI was going to get a t-shirt printed with “Knuth Was Wrong” We’re going to be in a world of hurt when the newest process node doesn’t save us.
- deleted 2y ago[deleted]
- rerdavies 2y agoKnuth was right! Profiling would indicate whether your JSON serialization/deserialization is actually a problem. Maybe it is. Maybe it isn't.
- gbin 2y agoOh with modern architectures this sentence is so wrong. If you don't think about grooming the hardware in the right way from the get go you will never touch peak performance by a couple orders of magnitudes period. See how games are developed and I tell you they don't just use OOP with virtual interfaces and neat indirections all over the place then think oh it is ok we will optimize after the fact.
- fnordpiglet 2y agoThere was a time that was how you achieved throughput. IPC was janky and unreliable and often slow, and threads offered a cleaner interface for cooperative multitasking on a single runtime. That’s changed as IPC and async improved, and the dangers of threaded led to more safety in threading, leading to slower threading performance.
- atrettel 2y agoSimilarly, vectorizing some code doesn't always speed things up. I'm dealing with this problem at work right now. Sometimes complicated loops are pretty well optimized already! That said, vectorization can often make things easier to read.
- loeg 2y agoProbably the lesson I'd take away from this example is that libc specifically often has surprising shared state, and you have to be really careful about using it from multiple contexts. And of course, you should avoid hammering a mutex from multiple threads -- but you already know that.
- stephc_int13 2y agoAll the different flavors of libc, apart from the outdated and cryptic naming style, have many hidden flaws like this one, heavy multithreading was not a central design feature when it was designed, and there are many instances of global state, with workarounds to avoid bugs, at the cost of potential serious performance issues. My opinion is that the standard libc should be used much more as a fallback than a default. And this is especially true about random number generation, there are much better generators out there, and some of them are only a few lines of code. https://www.romu-random.org/code.c https://www.romu-random.org/code.c
- cratermoon 2y agoThe SSL cert for that domain expired over 2 years ago Mar 4 23:59:59 2022 GMT
- fsckboy 2y agohttp://web.archive.org/web/20210118071040/http://www.romu-random.org/code.c http://web.archive.org/web/20210118071040/http://www.romu-ra... what this will do is download the .c file rather than just show it to you, not sure I understand that enirely, but just so you know.
- account42 2y agoI assume the response of the original site depends/depended on the user agent and only showed a HTML page for user agents it recognized as a browser, which doesn't include the IA bot.
- 2y ago
- pclmulqdq 2y agoPRNGs are one of those things that need to have global state if you want to get decent statistics out of them. You cannot have sets of threads fetching the same value from the PRNG - it will totally destroy how random the PRNG is. Thread-local PRNGs with separate seeds is the way to go if you need parallelism, and it was the author's solution, but I can easily see not knowing that and running into this.
- randomonad 2y agoThanks, you answered the question I came here to ask, i.e. why did it need a lock for a random number, what are the tradeoffs of using the non locking version. Makes sense.
- stephc_int13 2y agoThe generator state should either be part of the API or be thread local, but there are probably complex implications regarding the long legacy of libc.
- loeg 2y agoYou can't seed each thread with the same value -- that's all you're saying, right?
- jayd16 2y agoResult distribution (like averaging to zero) only happens at scale. Even if you use a different seed every time you might not see the proper distribution when looking across different generator instances.
- teraflop 2y agoThis reminds me of the fact that Go 1.20 added a clever optimization: If you call `rand.Seed` to seed the global RNG, it's assumed that you want it to produce a single deterministic sequence across all threads/goroutines, which requires locking. But if you never explicitly seed it, you get a different implementation that uses thread-local RNG state without locking. (In practice, there is no way for a program to distinguish this from a single RNG that was initialized with a truly random seed that you can't recover, so it doesn't break backwards compatibility.) Unfortunately, the C standard prescribes that failing to call `srand` must be equivalent to calling `srand(1)`, so I don't think glibc can get away with this trick. Mentioned here: https://go.dev/blog/randv2 https://go.dev/blog/randv2
- skissane 2y ago> Unfortunately, the C standard prescribes that failing to call `srand` must be equivalent to calling `srand(1)`, so I don't think glibc can get away with this trick. I think it could. Just supply two implementations of rand(): a strictly conforming one without this optimisation, and a less than strictly conforming one with it. The second is implemented in a function with a name like `__gnu_rand_optimized`, and then if you `#define __GNU_RAND_OPTIMIZED` before `#include <stdlib.h>`, then that header does `#define rand __gnu_rand_optimized`. All the C standard requires is that you provide a mode of operation which strictly conforms to it. A platform is allowed to provide configuration options which cause it to be violated in various ways. Strictly conforming code won't turn on those options and so will work as the standard prescribes. If you choose to turn on such an option, that's a non-portable extension, and how it works is between you and the platform, the C standard isn't involved.
- rerdavies 2y agoAdd a new function that modifies behavior of an existing one. Or add a new function that provides behavior different from the existing one. The latter is simpler. And safer. And more flexible. And faster, because you don't have a condition to check.
- vlovich123 2y agoI don’t see why it requires locking. You could easily have a TLS seed that gets initialized from the main thread RNG that’s seeded with Rand.seed. No locking required. It’s not like reading from a single RNG state from multiple thread with locks is any extra deterministic over that approach since you fundamentally would have to synchronize at a higher level to guarantee that the RNG is read deterministically across all thread orderings.
- kibwen 2y agoPersonally I think it's kind of silly that we've normalized the idea of PRNGs-as-global-state. I'm not asking everyone to go Full Monad, but please just consider giving each Thing that needs access to randomness its own independent PRNG.
- Taniwha 2y agoit's not just random() - it's stdio, and malloc/free/new/delete (though some implementations use per-thread pools with added complexity)
- reverius42 2y agoSounds like it’s time to go Full Monad then.
- wumbo 2y agoif you have multiple threads working a queue of like-kinded jobs, you’ve given up the determinism of using any sort of global seed you could pull different set lengths of pseudorandom numbers from the different seeds
- owlbite 2y agoThat's what counter-based RNGs are for.
- wging 2y agoThe world seems full of APIs that make it easy to avoid global state. Most of my usage of randomness has been through things like rust's rand::thread_rng or Java's ThreadLocalRandom. (In fact I think even java.util.Random uses its own state: the docs call out perf issues but only if you share the same instance across threads.) Honorable (?) mention goes to (client-side) JavaScript - it's harder to have threading issues if you only have a single thread to work with!
- darby_nine 2y agoHow does being a monad intersect with scope i'm genuinely curious
- starik36 2y agoMany, many, many years ago, my employer needed me to write some code to read 8 COM ports in OS/2. Then based on that, do some operations. So, me, being brand new to OS/2, immediately wanted to try out the new multi-threading features. Without knowing anything about locks and spins or deadlocks or shared state, I plunged into it just using the OS/2 documentation and a programming book I bought. Keep in mind, this was a single CPU machine, probably an Intel 486dx or something like that. I spent the next couple of weeks debugging all sorts of things that should not have been happening. There were crashes, lock up, slow downs, missing variables, etc... that I couldn't resolve. After a while, I gave up and did what the OP did: just put everything in a loop and it solved everything.
- beyonddream 2y agoThis needs 2014 in the title.
- dang 2y agoDiscussed at the time: Make your program slower with threads - https://news.ycombinator.com/item?id=8711162 https://news.ycombinator.com/item?id=8711162 - Dec 2014 (47 comments)
- wonrax 2y agoThis is the exact same problem I encountered back when I was taking the Parallel Computing course, except I was an absolute novice and had no idea about debugging or profiling. I remember it took me several days speculating and searching for an answer to this issue on Google, and I finally found an explanation on Stack Overflow, which also suggested using rand_r. It was one of the first instances where I was introduced to solving and debugging a difficult computer programming problem, and it still sticks with me to this day.
- dkarl 2y ago"There's no semantic reason my program isn't embarrassingly parallel but oh WTF are my libraries/frameworks doing? is it all a lie?" is apparently the pretty universal first experience trying to speed things up with threads. Hopefully we're working towards a future where single threaded legacies don't routinely stab the unwary in the back. I remember in the early 2000s doubling the performance of a CPU-bound C++ program by using two threads, and my boss being shocked that I was able to do it. He had written it off as a naive idea. I was too young and inexperienced to understand why he was surprised; to me it just seemed like he didn't understand what I was doing. In retrospect, now I feel like maybe he had the right default expectation, and I got lucky that it worked out so easily.
- AndyKelley 2y agoIf you used zig you wouldn't have this problem, just grab your entropy from std.crypto.random and you have yourself a thread-local RNG, properly seeded, with fork safety.
- Animats 2y agoI've had trouble with futex congestion. Worst case was under Wine. Wine has DLL files which emulate various Microsoft libc-level functions. They have their own memory allocator. It has three nested locks, some of them have spinlocks, and at least one is locked while a "realloc" call is in progress and a buffer is being recopied. Now try a multi-thread program compute bound program with more threads than CPUs that does Rust vector "push" operations. Push causes an array to grow, locks get set, other threads hit locks, threads go into spinlock mode, threads inside spinlocks context switch, lose control, and performance drops by two orders of magnitude. Most CPU time is going into spinlocks. I'm not convinced that user-space spinlocks are a good idea. If you're never compute-bound, they can work, but if you run out of CPU time and a context switch occurs inside a spinlock, it's all downhill from there. Windows itself doesn't do this; it has a different locking strategy.
- kelnos 2y agoImmediately as I started reading this, my mind said, "random() has global shared state so of course more threads will make it slower". I say this here not to attempt to demonstrate my oh so special advanced knowledge, but just to marvel how bad our abstractions are sometimes. Maybe "bad" is the wrong word. Leaky, inadequate, inscrutable. "Give me a random number" feels like it shouldn't require all this overhead and hidden complexity under the hood. But unless you've read a lot about implementation details, or have been bitten by that exact problem before, how would you know? You wouldn't, of course.
- ketralnis 2y agoI love the fancy modern type systems and all of the superpowers that they give you. But this is an area that I feel isn't adequately explored. If you call a function that calls a function that has side effects, or that closes the file descriptor you're using, or could panic, or that needs global shared state, or spins up a thread, or allocates, we don't have a good way to deal with that. There are some partial and underutilised solutions like monadic IO and linear/affine types and, uh, not having panics. I have some (bad) ideas but I think this is a space that's worth playing in.
- Yoric 2y agoAlgebraic effects?
- hnick 2y agoI had the same thought years ago, I think some people have looked into it a little, but nothing popular yet. Imagine if you could look at a function, and know, undeniably - this, and anything it can call, absolutely cannot alter the file system directly or make a network call or spawn a process. Maybe instead of just types, you need to supply capabilities (much like interfaces on classes). Sounds like it could be a real pain. Would make auditing easier though.
- mrkeen 2y ago> alter the file system directly or make a network call or spawn a process. Those three cases are excluded in pure functions.
- DeathArrow 2y agoI don't know what can we learn from analyzing a poorly written program aside from what not to do. If the program was properly written there wouldn't be any issues with multithreading. The title of the article gives the false impression that multithreading is slowing programs in the general case. In fact poorly written programs are slow and that is true for both multithreaded and singlethreaded programs. If your program runs slow but you don't need it to run fast, don't bother. If your program runs slow and you need it to run fast, go see what optimizations can be done.
- nlitened 2y ago> the false impression that multithreading is slowing programs in the general case. In fact poorly written programs are slow From my experience, in the general case programs are poorly written, so yeah, multithreading makes them 1) more complex, more poorly written, and 2) slower in many cases.
- overfl0w 2y agoGood article, also has references to the glib's source. I've never dived deep into the random() system function before. This is from the man pages: "The random() function should not be used in multithreaded programs where reproducible behavior is required. Use random_r(3) for that purpose." Perhaps the notes should be updated to state that the performance of multi-threaded programs is also affected due to the shared global resource?
- oah 2y agoA sort isn’t necessary. Duplicates can be counted in linear time by using additional memory (e.g. with a hashmap) However, the point of the article still stands.
- InvOfSmallC 2y agoSame happened to me. I used random then deployed to product. I could see the CPU on grafana going nuts. That was one rollback I never forgot.