Exercise 52.1: Dining philosophers

[njr0]

I'm really happy there's a section on concurrency: it's one of my favourite topics (well, parallelism is, anyway) and this is nice.

You probably won't want to change your solution, but I solved the probably a very different way and have a some quibbles with your solution (that you may not care about).

You avoid deadlock by "breaking the symmetry" by swapping left and right for one of the philosophers. This works fine, but I would argue that the code is misleading/confusing, because the philosopher in question is now (depending on how you think about it) mistakenly picking up the right fork when he claims to/believes he is picking up the left one. I realise this is a bit nit-picky, but concurrent code is confusing enough. Although it would be slightly more code, I think it would be better to make that philosopher just "deliberately" pick up the forks in the other order (which is what your code is tricking him into doing, albeit benignly). (I realise this is wildly anthropomorphic.)

I avoided deadlock a completely different way, but having the each philosopher grab the left fork and then use a try_lock to get the right one. If that failed, that philosopher released the lock and tried again. I thought I might need to put a delay in for this to be safe, but it turns I can't make it deadlock or even run slowly even without this.

Out of interest, I build release versions of both and there's a surprisingly big performance difference:

$ time ./ex52_1/target/release/ex52_1 > /dev/null

real	0m3.144s
user	0m3.034s
sys	0m0.018s

time ./ex52_1_model/target/release/ex52_1_model > /dev/null

real	0m4.744s
user	0m0.017s
sys	0m0.069s

The first one, ex51_1 is my code, whereas the second, ex52_1_model, is your solution. The times for your are always over 4s (4.4s - 5.0s) whereas mine are always always under 4 (3.1 to 3.5). On the other hand, looking at the user time, clearly my implementation is soaking up cycles spinning. If I add a microsecond delay before retrying the lock, it seems to run just as fast while consuming fewer cycles:

$ time ./ex52_1/target/release/ex52_1 > /dev/null  # with 1us delay

real	0m3.014s
user	0m0.215s
sys	0m0.917s

I don't suppose it matters in this case, but it's a factor of 4 or somethingthe performance difference is actually non-trivial, so highlights that how you solve these things makes a difference. (Hanging onto a lock you can't use feels a bit like an anti-pattern to me.)

If this exercise is just about concurrency and avoiding deadlock, I guess it's fine. But in terms of parallelism/speed, it's pretty bad. If you ran it sequentially, you'd expect it to take a hare over 5 seconds since each philosopher eats 100 times taking 10 microseconds for each. So each philosopher needs a second of eating time. The 4.7 I'm getting (Mac Studio, fwiw) is only about 5% faster than that.

You can have a maximum of two philosophers eating at a time, so 2 seconds is a lower bound on total time, but 4.75s is obviously miles from that. 3s is better, but still not great. Part of the problem is that this is (perhaps deliberately) maximizing contention by making the philosophers think for almost no time—just however long it takes to send a string. You used a sychronous channel, whereas I used an async one (because, why would you want to wait?) But that means that almost immediately after eating, a philosopher tries to grab the fork again, so that philosopher's neighbour can't hang about in trying to grab the lock, so it's backing off and pausing, that pause can't be long. If I increase from 1us to 500us, things take ages because of this. The exercise is more interesting (I think) if you make the philosophers take at least some time (e.g. 1ms) to think (on top of whatever the communication costs). If I do that, I can get the times down to about 2.5s, e.g.

time ./target/release/ex52_1 > /dev/null

real	0m2.542s
user	0m0.239s
sys	0m0.998s
0 gardot:$ time ./target/release/ex52_1 > /dev/null

That's better than it sounds because now each philosopher needs 1.1 seconds (1 second eating and .1 seconds thinking in total), so the sequential time would be 5.5s. So by adding a small thinking delay (which reduces contention) I can reduce the total time and the speed-up from concurrency/parallelism. I suppose in principle the "perfect parallelism" limit is still around 2 seconds (because thinking can be perfectly parallel), but this is getting more respectable. I can decrease the poll frequency too here, a bit, to reduce the system time, but it's still using more CPU than your version where every philosopher greedily grabs and holds locks.

The other minor point was that I (probably incorrectly) didn't use Fork. I didn't notice it, TBH, and just used () for the Mutex. I can see from an philosophical/educational perspective that (a) you might think it's clearer to call it fork and (b) from a type-safe perspective, if there were multiple memberless structs, using Fork would let the compiler detect that you'd used the wrong Mutex if you used (say) Spoon where Fork was required. But on the other hand, Fork is really not doing anything here, and indeed, there is only one kind of () in use, so I don't know. I mean, we could Box all our integers and require people to use the right kind of integers in the right places. (Actually, was it this course that talked about doing that for units? Can't remember.)

Anyway, not sure you need to do anything there, but maybe the feedback is useful/interesting.

[mgeisler]

You avoid deadlock by "breaking the symmetry" by swapping left and right for one of the philosophers. This works fine, but I would argue that the code is misleading/confusing, because the philosopher in question is now (depending on how you think about it) mistakenly picking up the right fork when he claims to/believes he is picking up the left one. I realise this is a bit nit-picky, but concurrent code is confusing enough. Although it would be slightly more code, I think it would be better to make that philosopher just "deliberately" pick up the forks in the other order (which is what your code is tricking him into doing, albeit benignly). (I realise this is wildly anthropomorphic.)

I see what you mean 😄 we're no longer modelling the world correct with this "trick".

I avoided deadlock a completely different way, but having the each philosopher grab the left fork and then use a try_lock to get the right one. If that failed, that philosopher released the lock and tried again. I thought I might need to put a delay in for this to be safe, but it turns I can't make it deadlock or even run slowly even without this.

I actually like the idea of using try_lock a lot! I would let people work with more common concurrency primitives instead of showing people a "trick".

The exercise is more interesting (I think) if you make the philosophers take at least some time (e.g. 1ms) to think (on top of whatever the communication costs).

I would like that.

[njr0]

I was about to apologise for using "his" to refer to the philosophers, but then I looked and all the ones you use were men!

If you wanted to make it more inclusive, Hypatia is probably the best known early Greek female philosopher (Rachael Weisz in the fil Agora). There's also (slightly earlier) Themistoclea/Aristoclea (https://en.wikipedia.org/wiki/Themistoclea, though I'd never heard of her, TBH).

[mgeisler]

Sure, I'll be happy to include her! I don't know much about philosophy, so the names you see here are from a quick search on Wikipedia 🙂 It would be great if you could make a PR for this.

[djmitche]

What a great deep-dive into this exercise! I think this is a clear demonstration that the course provides jumping-off-spots for students to go forth and learn more. Within the context of an instructor-led session, time is limited, but I wonder if there's a use for some kind of "explore more" content that would be useful for instructor-less readers. Maybe that could be a # More to Explore section in the speaker notes?

There are a few other slides that get into rather excruciating detail in the speaker notes; for example, enum sizes. As an instructor I feel like that slide wants me to spend 20 minutes getting into the minutae of stacked niche optimizations, but in reality I only mention the niche optimization and move on. The intent might be a little clearer if that was behind # More to Explore -- a reader could get into that detail, or if a student asked I could use that material as reference to answer their question.

[mgeisler]

There are a few other slides that get into rather excruciating detail in the speaker notes; for example, enum sizes. As an instructor I feel like that slide wants me to spend 20 minutes getting into the minutae of stacked niche optimizations, but in reality I only mention the niche optimization and move on. The intent might be a little clearer if that was behind # More to Explore

Yes, that's a great idea!

Perhaps it would be even more flexible to have full slides for this? That would make it less strongly connected with any particular slide, but it would let us add more content.

[djmitche]

I wouldn't want those to get in the "flow" of the course, but perhaps an appendix (maybe one per day?) with links from the speaker notes?

I feel like a lot of the PRs we get have the feeling of "there's this neat thing about Rust that we simply must talk about!" and I think "great, add it in a new more-to-explore slide!" is a good answer to that.

[mgeisler]

I feel like a lot of the PRs we get have the feeling of "there's this neat thing about Rust that we simply must talk about!" and I think "great, add it in a new more-to-explore slide!" is a good answer to that.

Yes, I notice this too: everybody would like to have their favorite feature covered. Which is very natural 😄 So having an answer for this would be very helpful!

[djmitche]

@mgeisler how do you think we should track work from this discussion?

[mgeisler]

I think we can start with two changes:

• explain what a # More to Explore section means in the notes
• move the large notes for the enum sizes into such a new section

That will set a precedent and others can then follow up with more such changes.

[mgeisler]

I created #1369 for this.

[mgeisler]

With #1345, #1346, and #1369 all merged, I think we're pretty good here! Thanks for the very helpful input @njr0 and @djmitche!