Share a Draft: Multi-Threaded Programming 4: A Locking Queue Implementation

[Joseph Simons]

Not a whole lot of text on this one, but I did get the github Gist stuff working and have that interspersed throughout. Also wasn't planning on adding any additional images (I think the code blocks break things up nicely), but if you think this could benefit from some please let me know. So basically I am ready to publish this as-is (but would love any comments and suggestions first, of course):

www.altdevblogaday.com/?p=31268&shareadraft=baba31268_536f8cf8acfa1

Thanks so much!
-Joseph-

[Oliver Franzke]

Hi Joseph.

Yay! I was looking forward to this and it's great!

Since your series is aimed at beginners and intermediate programmers I wonder if it would be better to simplify the code even further. I feel like the templates don't really make the sample easier to read and understand. The code is good and anyone who has been writing these kind of systems will have no problems understanding it, but I could see beginners being confused.

Additionally I think some code that shows how the queue is used (especially if you decide to keep the template-based solution) would further help people to understand what is going on. Again this seems trivial to us, but there are plenty of people who are just starting their multi-threaded programming journey.

Keep up the good work dude!

Oliver.

--
You received this message because you are subscribed to the Google Groups "AltDevAuthors" group.
To unsubscribe from this group and stop receiving emails from it, send an email to altdevauthor...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Joseph Simons]

Hmm, hadn't thought that the templates would be too distracting, but I can sort of see your point. I can update the gists perhaps to remove them, but keep the full source as the template based one so it is a little more useful to people.

I do have code that uses this, though I wasn't planning on posting it until we got to the performance part (well, referring to it mostly). But I can see how it would be beneficial so will use one of my tests and throw that in a gist.

Appreciate the feedback and kind words.

[Paul Evans]

Hi, just quickly flicked through the article. Here's a few of my thoughts.

Would it be worth mentioning what happens while just reading through the structure? 

Also I'm not sure, but it looks like read could be unsafe if it happens between lines 67 and 68 of https://gist.github.com/sigmel/8b0768b2d1f31a039ace ?

As you are mentioning mutex, is it worth while linking that word back to the first part of the series where you overview them and their costs a little?

Is lock_guard pessimistic? If it does do a kernel call to lock each time regardless it would be worth mentioning that and the associated performance penalty.

Keep up the writing :) 

Cheers,

Paul

[Joseph Simons]

Not sure I entirely follow what you mean by: "Would it be worth mentioning what happens while just reading through the structure?"

"Also I'm not sure, but it looks like read could be unsafe if it happens between lines 67 and 68 of https://gist.github.com/sigmel/8b0768b2d1f31a039ace ?"

I assume you mean between 66 & 67. I believe this should still be safe. The worst case I can imagine would be if the list were emptied after executing 66 but before 67. In this scenario, _tail would still be valid (it is a shared_ptr so nothing else will delete it), and _tail->_next would also still be valid because it too is a shared_ptr. Granted, _tail->_next would be _head, which is an odd case, but I don't think this would break anything. In this case, you would be unable to remove any more because _head->_next is null, and you can't add because of the enqueue mutex. I also didn't have any issues with my tests where I think this case might have come up (if not, I think I know a way that might cause it).

"As you are mentioning mutex, is it worth while linking that word back to the first part of the series where you overview them and their costs a little?"

Good idea.

"Is lock_guard pessimistic? If it does do a kernel call to lock each time regardless it would be worth mentioning that and the associated performance penalty."

lock_guard is just a container really for std::mutex that acquires on construction and release on destruction. I'm not too sure how std::mutex works under the hood (and some quick googling didn't provide any info). It is likely library dependent, but I wouldn't think that it would do kernel calls. When I get home I'll look at some disassembly and see if I can glean some more insight. But I am not too worried about performance concerns at this juncture, as I will focus more on that in future posts. But this would be good to know for that.

Good questions.

[Paul Evans]

I meant that you have no locks when traversing the linked list, so explaining why you have them only on write operations as you did in the second paragraph also illustrates when you believe locks are not necessary.

[Alex 'darbotron' Darby]

Hi Joseph

Awesome work! Every time you post I get more likely to do the C++ next low level curriculum post ;)

First thing to say: I completely agree with Oliver that the code is hard to follow, but the templates don't really bother me unduly because I'm used to them ;)

Personally I would lose all the C++ 11 stuff, e.g. the use of std::move, smart pointers etc. 

My main reasoning for this being that it just adds extra stuff for people to make sense of when they're (presumably) already trying to get their heads around the concepts you're introducing to them with some of your code looks like memory leaks to the trained eye - assuming that the trained eye is used to reading code with regular (as opposed to smart) pointers.

Ultimately it's up to you though :)

Alex

[Joseph Simons]

Some day I'll get you there Alex :)

I am going to leave the C++11 stuff in precisely because I have to remove a lot of it to implement the lock-free code. This is due to shared_ptr and unique_ptr not being thread-safe and I would like to touch on that fact to highlight how tricky lock-free stuff gets. Also I'm partially selfish since I've already mucked around with this code a lot and don't want to have to rewrite it yet again.

If I get enough demand in the comments (meaning more than one person) then I might make a non-C++11 version, but until then I want to try it like this first.

[Joseph Simons]

I've updated my draft with the suggestions from people. I think it changed things enough to warrant posting another draft, which can be accessed below:

http://www.altdevblogaday.com/?p=31268&shareadraft=baba31268_5372e598761ef

The main change is adding the Test section with one of my tests and adding a link at the bottom to the source with all the locking queue tests I have.