last day (16 days later) » 

16:20
0
Q: What structure to use for large 2-D euclidean grid with multithreaded access?

Edward PetersI've got a simulation I'm playing with, in which I have a large (1024x1024 or bigger) euclidean space. Each square of this space can hold various data, of fixed but not totally trivial size. (Below is an example square; while it is very subject to change, I don't expect it to grow more by a fact...

"with a thread handling a single point at a time" - This is a design decision I'd challenge. You most likely want to space-partition your entire grid, so that you handle all points within a region at once by the same thread. You don't even need a mutex for that, you can split_at_mut() them onto different threads dynamically. Or use rayon's parallel iterators to iterate over the vector.
And as @tadman already pointed out, approaching the problem from this side will make it easier to move it to the GPU later.
@tadman My reasoning for the mutex being in the middle was that if it were at the top level, only one thread would be able to do anything at once, but if it were on every element, that would both increase the size and add a ton of overhead of re-acquiring locks when no one is competing.
@EdwardPeters Don't use a mutex at all; if partitioned properly, it's not necessary. With tools like std::thread::scope or Rayon it's possible to distribute your data on threads without mutexes.
If space allows it, you could use double buffering: Duplicate your entire grid, and alternate between them from step to step. Then have one thread compute the new state of every region. If the new state of a region requires data from a different region, no problem: The previous time step is available for all threads, due to being immutable. That's most likely how a GPGPU implementation would look like, as well.
@Finomnis So the reason I don't "handle all points in in a region at once" is that by the current rules of the simulation, there's nothing to do with those points. I edited the question to hopefully make that clearer. To give a bit more detail, in the diagram shown, the red line is a particle that moves around the grid; if certain conditions are met it sticks, thus growing the fern patterns.
@EdwardPeters Then partition those particles in space, and handle those in regions. Migrate them between regions if they drift from one region to another. You need some kind of partitioning if you want to parallelize it efficiently. Of course you could also simply partition the list of particles, but then you would have to lock the cells again. The goal is to avoid locking and breaking the problem down into multiple smaller problems. And space partitioning is ideal for that.
16:20
@Finomnis If I'm understanding you, I think everything you're saying is probably good answers for the bonus question.. I'm trying to think of how it would work with the "small number of drifting particles" thing I've got now.
@EdwardPeters "the threads should be able to operate atomically on the 3x3 space centered on their particle's current position" - what if two particles are close to each other? Which one updates first? Why do you even need partitions, if you operate on particles alone?
@Finomnis If two particles are close to each other, one will get to update, and the other will see the result of that update - I don't care what order it happens in. What I want to avoid is, for instance, both of them eating the same bit of food at once, or trying to grow on the same empty square. I'm not clear on the second question - the particles drive the behavior, but they operate on the grid (reading and writing to it). The partitioning is there so that different particles can operate in different regions in parallel.
Different question: if you only use a hand full of particles, why concern yourself with multithreading? It's most likely faster if updated by a single thread, and you don't need to concern yourself with locking and similar.
So I'd argue: don't do multithreading. Until you have a large enough number of particles that it's worth doing space-partitioning; then partition your space and treat each section again as a single-threaded grid.
@Finomnis I should review the tests, but I have checked and found that the threading is speeding it up (at least, increasing the number of threads does greatly increase the performance). I don't see why it would be faster with a single thread, unless locking was taking up like 7/8 of my time?
@Finomnis " don't do multithreading. Until you have a large enough number of particles that it's worth doing space-partitioning; then partition your space and treat each section again as a single-threaded grid." Sorry, is that not still multithreading? You'd have one thread per section, right?
@EdwardPeters I mean, don't do multithreading until you have a large enough number of particles to partition by space; do not partition by particle. Although that's of course a gut feeling, benchmarking should bring more appropriate answers.
"I don't see why it would be faster with a single thread, unless locking was taking up like 7/8 of my time?" - If that's the case, why ask the question here in the first place? If the overhead of locking is irrelevant in your case, why not just keep your current solution?
I feel like this question is too opinion-based for Stackoverflow; I'd vote to close it. It might be better suited for codereview.
16:20
@Finomnis Well there's a big difference between "The overhead of locking is costly and I'd like to reduce it" and "The overhead of locking is so prohibitive that I don't benefit from having multiple processors running at once". If I have 8 processors and locking is taking up 3/4 of my time, that should still be twice as fast as an unthreaded solution, right?
@EdwardPeters Might be ... but threading is more complicated than that, there is a lot of things that play a role, like cache locality and similar
@Finomnis I'd like to argue that the original question of "What structure is efficient" is answerable - I do think you and I have gotten lost in the weeds a bit, regarding my implementation. But even so I think you're giving me valuable ideas, I'm just not understanding how the space-partioned model would work in a few regards (specifically, communicating that points have moved between regions, or what happens with points on the boundary needing to see both regions)
@Jmb That will introduce a huge deadlock potential if not done correctly, but in principle, you are correct.
@Jmb My first thought is "How big is a mutex?" If it's big, that's going to make cache locality a lot worse. My model also allows for the possibility of a particle grabbing the lock for its region, then using it for a while (until it reaches a boundary, potentially) - that could be one lock acquisition per hundreds of steps, rather than 9 per step.
@EdwardPeters This last answer kind of already explains how to space partition: Now imagine two particles are in the region at once. You could lock that region, update both particles in series by the same thread and then unlock that region again. Your current approach has the same problems as a full space partitioning: If you lock it for hundrets of steps, how do you know that another particle might have entered the region?
16:20
@Finomnis Okay, so thread 1 locks region A, and updates for particles P1 and P2... after some number of timesteps P2 moves to region B. Thread 1 then locks region B, adds P2 to the particles listed there, then continues on with P1? (Presumably occasionally yielding its lock to allow new particles to be added?) Do I have that right? In my solution the entering thread will be left waiting until the first particle leaves the region, resolves, or "pauses" itself to voluntarily yield the thread... that wait can be significant but if there are many more regions than threads, it should be fine.
@EdwardPeters Your question is non-trivial, how to efficiently space-partition and border exchange a particle simulation is a question a lot of papers were already written about. If you do it right, you don't need locks at all. But I think this is a vary complex topic for a stackoverflow post.
Hey
Okay, that's perfectly reasonable - but from my last comment, does it at least sound like I have the high-level view of what you're describing correct? (Regions know what particles they contain and update them all in one thread, and then some mechanism handles moving particles to other regions/particles that are on the border and "see" both regions?)
Yes, in general that is true
Often in large-scale partitions, the grid isn't even constant - especially for particles, often times the grid is created dynamically via a quad-tree (2d) or oct-tree (3d)
And then there is many different methods on how to do border exchanges
The idea behind dynamic grids is that grid cells are larger if only a few particles are in them, and smaller if many particles are in them, to make all grid cells compute in the same magnitude of time
But of course as you bring in a grid based state, together with a range that every particle can interact with that grid, this becomes much more complicated
Minecraft, for example, has the same problem
They call the grid cells "chunks" and a majority of bugs in the game come from the border exchange between chunks
You could also partition your grid into red-black stripes. Like:
ABABAB
ABABAB
Then you could update all non-touching A pieces simultaneously with different threads
Border exchange wouldn't matter because while the A parts get updated, the B parts are passive
Then in the next timestep you could update all B parts, again with no border problems because now the A parts are dormant
That means instead of one full timestep, you would have kind of two half time steps
You could do the same in 2D if you partition it like:

ABABABAB
CDCDCDCD
ABABABAB
CDCDCDCD

And then have 4 sub-timesteps. You can update all A regions in parallel because none of them touch, same for the other regions in the other sub-timesteps.
To achieve that, you could either partition it with split_n_mut, that way you don't need any mutexes. Or of course you use unsafe.
This partitioning of course only works if a particle is slow enough that it can't cross an entire region in a single step; if a particle could move from one A to another in a single step, then of course you would have to be careful about border exchanges again
This kind of optimization does in fact lead to unsafe being used regularly; in many cases it's just too tedious to explain to the borrow checker that what you are doing is sane
I hope that kind of demonstrates, though, how complex of a topic this actually is once you go beyond a primitive implementation
@EdwardPeters Makes sense, somewhat?
17:05
Yeah, I think I get the general idea. It occurs to me that thus far the number of particles I have active has been a function of the number of threads (I have a queue of "waiting to spawn", and only do so when a thread is available.) It'd be a huge redesign and I don't know if I could maintain my current abstractions, but I think it works.
It kind of still leaves me with my original question, though - after all of the re-arrangement of threads and mutex's, is Vec<Vec<Square>> still the right data structure, or do I want to back it with something completely different?

  last day (16 days later) »