Edward Peters

Feb 4, 2023 01:08
@tadman So I'm probably getting ahead of myself, but in terms of implementation, does this mean Vec<(usize, usize, usize, usize)>? Something like docs.rs/macroquad/0.3.7/macroquad/texture/struct.Texture2D.h‌​tml , with an interface clearly intended for actual visuals? I know a smidge of the theory, but nothing about the actual atoms of putting it to practice.
Feb 4, 2023 01:08
@tadman I know nothing about GPU programming, but this is a good candidate for me to learn. That said, what structure would represent a 2d texture? Quick googling shows me a bunch of very image-specific stuff that does not look like what I want...
Feb 4, 2023 01:08
@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.
Feb 4, 2023 01:08
@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.
Feb 4, 2023 01:08
@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)
Feb 4, 2023 01:08
@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?
Feb 4, 2023 01:08
@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?
Feb 4, 2023 01:08
@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?
Feb 4, 2023 01:08
@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.
Feb 4, 2023 01:08
@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.
Feb 4, 2023 01:08
@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.
Feb 4, 2023 01:08
@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.
Feb 3, 2023 17:06
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?
Feb 3, 2023 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.
Feb 3, 2023 16:23
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?)
Feb 3, 2023 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.
Feb 3, 2023 16:20
@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.
Feb 3, 2023 16:20
@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)
Feb 3, 2023 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?
Feb 3, 2023 16:20
@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?
Feb 3, 2023 16:20
@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?
Feb 3, 2023 16:20
@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.
Feb 3, 2023 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.
Feb 3, 2023 16:20
@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.
Feb 3, 2023 16:20
@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.
 
Feb 3, 2023 23:46
That representation is more or less correct - "depth" is not an attribute of "Point" to me, just something I included in the example that was done as part of the recursion.
Feb 3, 2023 22:07
I don't know if you read the long discussion thread, but we did eventually agree that if this returned an Iterator instead of pre-emptively collecting, it would not generate stack frames of this function - instead it would return a deeply-nested Iterator with a lot of Flattens in it, and the evaluation of those would be just as deep. (I'm trying to actually implement that, if you know how)
Feb 3, 2023 22:06
Complicated answer, two reasons. One, I think that the recursive representation is often clearer, especially if mixed functions come into play. Two, while I'm a newbie at Rust, my day job does involve writing stack-safe interpreters for IR that may itself not be stack safe - so I know this can be done, and I'm curious as to rusts behind-the-scenes behavior here.
Feb 3, 2023 22:00
I'm not sure what you mean about "avoiding something iterative". Are you referring to the "use a loop and two mut Vec thing I mentioned in the question, or the discussion of what it would look like if I returned an Iterator?
Feb 3, 2023 21:57
I should have used vec![] there, the point was only that it was empty (and thus ultimately the result was empty) - so it's not the result that's consuming the stack (or the heap), it's the recursive calls.
Feb 3, 2023 21:54
@Finomnis yes. It's a Vec, so it's heap allocated. :) (I checked that even making the base case empty, so the result is trivial in both heap and stack, still smashes the stack - see the commented line in the latest edit.)
Feb 3, 2023 21:54
@Finomnis I've edited in additional explanation of the example. If you need there to be an actual tree-as-data I can provide that (though it takes some work as the tree growth itself cannot be recursive), but this is actually a closer fit to the original, as children are computed in the recursive call rather than being natively pre-defined.
Feb 3, 2023 21:54
@Finomnis I've edited in what I believe to be parallel behavior as an MRE.
Feb 3, 2023 21:54
@SvenMarnach So it's Rust's implementation of flatten making the recursive calls? Looking at the source that seems possible. My only doubt is that I'm pretty sure I could write an interpreter (ignoring a laundry list of thing like user-defined iterators, thread safety, and everything else that Rust supports) that would evaluate this without a recursive call - for instance, Flatten.next is tail recursive, so it's certainly possible. (Also, rust supports tail recursion it's just not guaranteed, correct?)
Feb 3, 2023 21:54
@SvenMarnach I was just considering that possibility - why would it only reduce the recursion depth by 1? Assuming I'm correct in understanding that Iterators are lazy, that would mean the recursive call was never made before the function returned. Wouldn't that mean that my code never contributed additional stack frames?
Feb 3, 2023 21:54
@Ry- So there are two reasons I'm asking rather than doing that. One, testing is a pain, and the stuff I omitted to not bog SO down with unnecessary details makes it a little less trivial a rewrite. Two, and more importantly, I'm trying to gain insight into the workings of Rust, and I think I'll learn more by making this work recursively (or getting a definite answer why it can't.) FWIW, I did due dilligence making sure this is the issue - lldb shows a stack trace lousy with get_descendent_leaves calls, and printlns showed several threads deeply recursed in this function at once.
Feb 3, 2023 21:54
@SvenMarnach So to answer your laziness question: The function can theoretically return without having called that closure. The closure could then be called at some future point, again lazily returning a structure that includes some number of closures. At no point would any execution of this function then be nested beneath another in the call stack.
 
Dec 9, 2022 00:41
price = (Cmax-(d[i]-lastStop))**2 - I think you have that backwards. That will give you a price based on how much you have left, not how much you need to fill. I think you also need to include some logic to handle cases where you actually go over the max (there's a few ways to handle that, easiest is to just return a cost of MAX_INT, tho that's a bit messy)
Dec 8, 2022 17:29
Do you understand why I'm claiming it's unnecessary?
Dec 8, 2022 17:29
My answer is still the same as before - you're making your life difficult by keeping track of the C parameter, get rid of it. This is often the case in coding - it is easier to compute things once when you need them, than to try to "keep them accurate" by having a mutable value which you update to reflect underlying changes. You should really only do the latter as a performance thing, and in this case the calculation is so cheap there's no reason to.
Dec 8, 2022 01:48
I notice your naive_cost algorithm is not recursive - it is calling the _cost algorithm. It's probably not a good idea to mix the two.
Dec 8, 2022 01:46
Again, I think you're only hurting yourself by keeping this C variable around. Properly updating it is going to be a pain, don't bother. You have to refill completely at each oasis you stop at, so your remaining water is just a function of your max, your current position, and the the position you last stopped at. It's a lot easier to just compute it when you need it than try to update it to remain correct. Generally that's a good habit to get into.
Dec 8, 2022 01:43
Those three things really go together. Any time you break one of those rules (which you are, with your loop), you'll confuse other programmers and invite off-by-one errors where your code disagrees with the standard every library or piece of input uses.
Dec 8, 2022 01:42
Okay, so this looks like a greedy algorithm, but probably greedy in the wrong way. There's also some probable off-by-one errors there. Almost always (pay attention to this bit :P ):
- Loops should use `< upperBound` as their limit (not `<= upperBound`)
- `len(d)` or anything that returns the size of an array or list gives the number of elements in the list
- an array of list has elements at indices from `0` to `length - 1` inclusive
Dec 7, 2022 20:07
I think I see a few places where you're mis-using or miss-assigning C, but it's really not worth going over them. It's better to just get rid of that parameter altogether.
Dec 7, 2022 20:01
In general you have too many parameters. There should be a total of four: The maximum water (cMax), the array of oases (d), the position of the last stop (lastStop), and the index of the current stop (i). You have an additional three - oasis1, oasis2 and C, none of which are needed, and including them will only make it harder to figure out what the recursive call should be.
Dec 7, 2022 19:56
C is the current amount of water remaining, right? I still think that's not a useful parameter. Look at your function header: oasis1, oasis2, lastStop, d, Cmax, C, i. d is where we are now, right? And you can never refill to less than full. So the current water we have remaining will always be Cmax - (d[i] - lastStop) - i.e., less by the distance since the last stop. There's no need to track C as its own parameter, and I think doing so will only lead to bugs.
Dec 7, 2022 09:19
For this problem, I suggest your sub-problem relationship should be framed as cost(current, lastStop) = min(cost(next, lastStop), cost(next, current) + distance(lastStop, current)**2). Try just implementing that recursively, then see about saving the results of sub-problems in some sort of array.
Dec 7, 2022 09:19
I do think you've gotten some logic crossed - I'm not really able to see the algorithm you're trying to use, from reading your code. Dynamic programming is all about breaking problems up into sub-problems, such that the solutions to those sub problems can be re-used. I think you have some of that there, but you'd be better off - I think - tossing your current code, really reviewing the logic on paper, and then re-implementing. Trying to fix a mess (even a mild mess) is much harder than starting over.
Dec 7, 2022 09:19
Also, as a general word of advice, the sooner you stop naming variables things like d_i0_i1 the happier everyone will be - give them verbose names if you have to, but give them clear names. (Eventually you'll get in the habit of having fewer variables, because you'll be reusing more code in neatly composed functions.)