4 ms·

Partition your data structure to be per-CPU and get rid of any sharing.

• MuffinFlavored 3y ago
  how is this done in rust or c?
  • flatline 3y ago
    MPI partitioning by rank? I’m curious what other solutions there may be.
  • bottled_poe 3y ago
    This is not a language problem. It’s an algorithm design problem. There’s no silver bullet. The basic principle is to divide the problem space into independent blocks of work. How to achieve that depends on the problem.
    • fooker 3y ago
      Algorithm design problems, when general enough, warrant being treated as language problems! Every feature of programming languages started in this fashion.
      • bottled_poe 3y ago
        Indeed, the holy grail (or perhaps the rapture) of programming languages is a compiler which generates the entire program with zero human-written code. I fear it may be on the horizon.
    • inopinatus 3y ago
      There are programming languages e.g. occam designed with the intention of exposing parallelism algebraically, but I wouldn't call them a silver bullet either.
      • j16sdiz 3y ago
        They are great in theory, but sucks in practice. We don't have good optimising compiler for that
    • cyber_kinetist 3y ago
      For a good example, there's a tricky parallelization problem in physical simulation, which you have update edge/triangle/bending wing forces in a mesh structure without any race conditions. (This becomes especially thorny if you want to parallelize your algorithm to the GPU.) A surprising solution for this is graph coloring, where you "color" each element without having two elements that interfere with each other the same color. Then you can safely parellelize the updates of all elements inside each color group, since the same color guarantees absolutely no interference.
  • inopinatus 3y ago
    For something small like a counter you can use thread_local since C11, but for substantial parallelized computation, designing the division of work to avoid shared writes typically entails a scheduling function that parcels up the work, sets up memory allocation in advance to avoid conflict, and then hands an entirely unshared execution context for each thread to the thread start function, most likely as a pointer to a app-specific struct (since that is what pthread_create allows for), and then subsequently applies a combination operation in the thread reaper loop to collate results (extra brownie points accrue when a reduce function is written to vectorize). The memory allocator plays a significant role, since allocation strategy needs to be per-thread-/per-CPU-cache-aware. Choosing and then tuning a different malloc (e.g. tcmalloc, jemalloc) to the one in your platform's default library is a non-trivial matter but may have enormous impact both on overall performance and memory demand. In addition, when you design computation this way it is relatively easy to hadoopify it later, since it's basically map-reduce writ small.
  • deleted 3y ago
    [deleted]
  • pitaj 3y ago
    In rust, you can usually use the rayon library which handles partitioning and scheduling for you.
    • MuffinFlavored 3y ago
      that's just multi-threading in general i feel like the post i was responding to was talking about handling/pinning a thread to a specific CPU core?
• otabdeveloper4 3y ago
  > Just don't use any shared state, bro Thank you, Sherlock. But for the rest of us: when you need shared state, lockfree atomic spinlocks are roughly 1000 times more performant than mutexes. (Not a scientific estimate, numbers taken from real-word experience.)
  • petters 3y ago
    > spinlocks are roughly 1000 times more performant than mutexes That is absolutely not universal. See e.g. but there are of course many places discussing this: https://news.ycombinator.com/item?id=21970050 https://news.ycombinator.com/item?id=21970050
    • saagarjha 3y ago
      Locking is hard in general. Don’t do an unbounded spin in userspace is typically good advice though. The typical mutex construction these days will spin for a little while in an attempt to take advantage of mostly uncontended locks and then yield to the kernel.
    • happymellon 3y ago
      This immediately popped into my head too when I saw the comment. Spinlocks are terrible, and written by people who are trying to do quick hacks because they work in terrible environments and are taught to do bad things. There is a reason that most GPU drivers are just lists of hacks to get games working correctly.
      • imtringued 3y ago
        Yeah, spinlocks sound cool but actually they are terrible. Hybrid locks are generally quite good. The only way to get better is to pin cores and let nothing else run on them. Only then will spinlocks have a chance to increase performance by a tiny bit.
  • Ono-Sendai 3y ago
    mutexes are not that slow. Uncontested (single thread): incrementing using atomics took 0.002011 s (0.2513 ns / increment) incrementing using mutex took 0.005515 s (0.6894 ns / increment) Contested (8 threads trying to increment a single protected integer): incrementing using atomics took 0.1069 s (13.36 ns / increment) incrementing using mutex took 1.970 s (246.3 ns / increment) So mutexes are roughly the same speed in the uncontested case, and about 20x slower in this heavily contested case. This is on Windows.
• stevefan1999 3y ago
  aka share-nothing architecture