From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Mateusz Kowalczyk Newsgroups: gmane.lisp.guile.devel Subject: Re: Concurrent MVars for Guile Date: Fri, 17 Jan 2014 06:33:42 +0000 Message-ID: <52D8CEC6.9080800@fuuzetsu.co.uk> References: <87fvtn1wv8.fsf@tines.lan> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="------------080308060609060505030004" X-Trace: ger.gmane.org 1389940436 31143 80.91.229.3 (17 Jan 2014 06:33:56 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Fri, 17 Jan 2014 06:33:56 +0000 (UTC) To: guile-devel@gnu.org Original-X-From: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Fri Jan 17 07:34:03 2014 Return-path: Envelope-to: guile-devel@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1W430F-0003zV-2j for guile-devel@m.gmane.org; Fri, 17 Jan 2014 07:34:03 +0100 Original-Received: from localhost ([::1]:36419 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1W430E-0001Mq-Kd for guile-devel@m.gmane.org; Fri, 17 Jan 2014 01:34:02 -0500 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:46647) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1W4304-0001BJ-2V for guile-devel@gnu.org; Fri, 17 Jan 2014 01:33:58 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1W42zx-0007Xk-UE for guile-devel@gnu.org; Fri, 17 Jan 2014 01:33:52 -0500 Original-Received: from mailex.mailcore.me ([94.136.40.62]:43911) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1W42zx-0007XZ-IV for guile-devel@gnu.org; Fri, 17 Jan 2014 01:33:45 -0500 Original-Received: from host86-129-173-145.range86-129.btcentralplus.com ([86.129.173.145] helo=[192.168.1.15]) by mail11.atlas.pipex.net with esmtpa (Exim 4.71) (envelope-from ) id 1W42zu-0002wx-RM for guile-devel@gnu.org; Fri, 17 Jan 2014 06:33:43 +0000 User-Agent: Mozilla/5.0 (X11; Linux i686; rv:24.0) Gecko/20100101 Thunderbird/24.1.0 In-Reply-To: <87fvtn1wv8.fsf@tines.lan> X-Enigmail-Version: 1.6 X-Mailcore-Auth: 11603993 X-Mailcore-Domain: 1390428 X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6.x X-Received-From: 94.136.40.62 X-BeenThere: guile-devel@gnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: "Developers list for Guile, the GNU extensibility library" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Original-Sender: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.lisp.guile.devel:16810 Archived-At: This is a multi-part message in MIME format. --------------080308060609060505030004 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit On 02/09/13 08:55, Mark H Weaver wrote: > Hello all, > > I've attached a preliminary implementation of MVars à la Concurrent > Haskell for Guile. I made a few small changes to the API to better > match Scheme conventions, and added atomicity guarantees for 'read-mvar' > and 'swap-mvar'. I also added the interface 'try-read-mvar'. > > Note that the fairness of this implementation relies upon the fairness > of Guile's mutexes and condition variables, which I have not checked. > > Comments and suggestions welcome. > > I was thinking that maybe we should add something like this to core > Guile. What do you think? > > Mark > > Hi all, We've just had a little discussion in the #guile IRC channel about this and I'm seeking some confirmation. First of all, let's quickly outline something that Guilers might not be familiar with: MVars are based on an important property of the GHC's (GHC is the main Haskell compiler) thread scheduling mechanism, that is its fairness policy. GHC uses a round-robin scheduler which means that all threads will eventually get to run (although not with equal CPU slices). A book by Simon Marlow, the person who has for many many years been the main brain behind GHC's RTS says this: “No thread can be blocked indefinitely on an MVar unless another thread holds that MVar indefinitely”.[1] Further down we find out the consequences of this guarantee: “A consequence of the fairness implementation is that, when multiple threads are blocked in takeMVar and another thread does a putMVar, only one of the blocked threads becomes unblocked”. I think it's rather clear why this property is desirable: we don't want to wake every thread waiting on an MVar whenever we put into it or we'll have a huge performance hit. As Simon himself says, these properties are why we simply aren't using STM instead. Keeping all this in mind, my questions are: What's Guile's scheduling policy? Can we get a single wakeup and this kind of fairness guarantee? Unfortunately, Mark was not able to tell me what's the case. If this is to make it into core language as Mark suggests, I think it's important that it's first confirmed that the foundation on which MVars are built upon is actually present in Guile. I'm posting on this list in an attempt to find the person who knows how Guile's scheduler works and can answer my questions. Of course tests can be written and it can be eyed whether or not the behaviour seems similar but I think a definitive ‘yes, we do this’ or ‘no, we don't do this’ is still necessary. In case that Guile does _not_ support such scheduling, I think it's important to note this in any relevant documentation. You can find examples of simple programs one could try to implement as part of tests for this in Chapters 7 and 8 of [1]. Thanks [1]: http://chimera.labs.oreilly.com/books/1230000000929 -- Mateusz K. --------------080308060609060505030004 Content-Type: application/pgp-keys; name="0x2ADA9A97.asc" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="0x2ADA9A97.asc" -----BEGIN PGP PUBLIC KEY BLOCK----- Version: GnuPG v2.0.22 (GNU/Linux) mQINBFEKtg4BEAC6rcAHsOlFSwES8AqBk3Mu1vI+cIcsB740lsMxiyCHgISRHtrT l7EWhfblH65lAjsa/7ze7dQAmVPYJF2sZv7GTKJyiH2OG/tfFXwZHKeNFB4yjFBq axy9+A0UQKmM3yU5DyEctpK/LlJ10SNH6hmPbqJ/EX8lKMG7oifPQnq69nc5T63T bF0oJfpxmrq9PIJ9p/7hKJhjc57P7h2OmI9nxZ2EIk5VljC4zvXrAY5wtEx2lx7Y 2e/oMVz3JcVug9B8o6Ox0734N6TEIPgj6oYV9CwBzrxMVd/Sx5yAX11yuJ0qWQoN fHo5JBwHbGT6nZqeIld1m4MSCFnMHBaAeJTzwypv8QtcRnbeDxcdwMZMroG7vo5X 9mNGMJO0CPJhzCbAB/afSpkR38p5WJB4uIdUYmiiWgb7EGcs/OvEHdqZJY9PfeOW 6wiVtB1wuc/pO1XcAZ/qf2vmmSsB5yiHqhQV4J6//RpogZKwbTu049I5T/YK0ehT IbAmcevFyjTdkwXkZmeZ9zdvu5fr7Oknl79QCKQMk4TKeezwv6YqTns5Nwo/nl5p OY7Syb/ecTg+oCiv5/iWLaT17XsVJd0JMbIKDLPz/IGgUUvRBu2yU/VMqnHn1up/ LAdWrl2oZ8/vIqtgey76nqnNtSmYenJaSx/V1EBUudevEyRBBXN/n5SZEQARAQAB tDZNYXRldXN6IEtvd2FsY3p5ayAoTWFpbiBrZXkpIDxmdXV6ZXRzdUBmdXV6ZXRz dS5jby51az6JAjwEEwECACYCGwMHCwkIBwMCAQYVCAIJCgsEFgIDAQIeAQIXgAUC UVnxPgIZAQAKCRDNZrnDKtqalwTWD/9s9GNMMzQzfkeQmmA7BnDBCAGXObihVXIg xCDuxX+eE8bAXnKCVJxcl9IEarTXcLAYYjyH1JYEGTtHU5RZmF709hyB/oRK6bWp Wt6i5wa5f2lm7CaOHdqzlAbfC+XGvK7X/Xyz9Zy74wpJZYiUy3UV8xNpPqnyAZie IbnHC7gcp5V1cqbc2Z8NnLPf+1PLWzcD8WpNl+YPvc1aiiPEXZ33qnPAO7PXsNK5 qBbD0fl3GXs/6XGqFW2OUCfpdNzHxUHw7PWuTn4Os8CjX3MOi5TuY6Nom/RQP5RX RRDdMfbDXLSk/bFjs9U8ok+AlEX6JpvGMS7Sk+KsR//fIOWFffTN8gpUC1VhLj0f bcu89T8R1g/KZUzct1OKCCjthqRyYBvDdZjSr+Sjx+XgOmN8Ef+DXn68exlFxVNI +d2EZzdmQc5Cga/vFFwUV5jx3xd5w5kukXJeUnxwvV06YKrjnlnBm5xsFZ7aC+sv Fbpco/btZYzzjwOAfT8Dm9khcOxyyUWVFlpT3GcZHKT3JY2Rdjcyicd2P3BLLkb6 hisx8A5YPDjQ0gr1Af6olarUoLDTnUpUrryWYGe13Qaqq/n8F0ACggURhgb9Bgdp QNokKFzPMerhj+lBfB/+Q0iYMUYEpLnF22lZp5eywj4Y7lEpvDyQwjKbbaeTkwim GpmvUkyjuIkCOQQTAQIAIwUCUQq2DgIbAwcLCQgHAwIBBhUIAgkKCwQWAgMBAh4B AheAAAoJEM1mucMq2pqXpMgP/1YRMMEn5kerD0glAM//jG338x8gaIXCuZ/+Pj9g Mmt/DbiRb9sFETooWIHf8vbzpMEjEXgqpyPfeL7wFderWXwvvkiYnYB7hXNliCkW T7hC7C7ljgmX0ojWAE8A3g84Q8GSbAyCIL28FBVlxugBUVZxYY35pFOlfLz7JCgA 9WuyY37L7q2lzr7JUhmeg16IhuG9DWuyB9FmGCPeG9h6/eGN/CXmbfUlFNT93tTn BFoHVyK0p/QaAQMG2ClqlQA0hvSQZSmLQjxd50VPv2z4M1hY6dZZItz188p2XX11 pxNp/tqGh752w7yPli7py338ihvTLtMVgat7BILQbtEZ0EWmZkTBnUGTGwcyvf/G pbHPmqHdIPQ+UKGkXBcGo3HRcQ4E56wZwp902o5DvYg4YNcm7VmSzGyLAqvqByW0 qO8mdQO7wKDrpZKLPxZkw/TEUXlrBSkpCBo0Vpt1tNK8+gaDix2RkssNrHwLPe1m u0oLg9itvedi+LJxCcMkwY1yDXWJsWEwuoc862+IFJsexu2C2nv1n2xhRjxEz/ZT EYWDoXCMtQALT4J/UmHb7jS6T2bxpPfHgRBpRgcykBSwdAl5gE2Q+JCydcnXdSMN jRoxVri6NX6TPOlrrm+TQBkAOwiG9SpsinZJZ8zmLVM56YmKM6+K2P6GimD+fDEP nwR5tEVNYXRldXN6IEtvd2FsY3p5ayAoQmF0aCBVbml2ZXJzaXR5IGUtbWFpbCBh ZGRyZXNzKSA8bWs0NDBAYmF0aC5hYy51az6JAjkEEwECACMFAlFZ7/ECGwMHCwkI BwMCAQYVCAIJCgsEFgIDAQIeAQIXgAAKCRDNZrnDKtqalwFLD/9mZZxFYS6Rp88w D1kL3/wIZTizyzDFMhlx7AV3Wv9CdKyRL6en5QhwNTEd6VaCOwq45PzWRqL3tNNQ ux/kcxdCel9pUSTuizoD0JJN7CMSW7RDsdZsBO+1MpH6xY+tegWXkna+V3MVziDs XNpump4vCWjkTRVG4D3bI+f0GGkrO6mogUTJ3ps9T16rx+zi5M89buKSB/tsdvVB 0DnrSICuguKQ3qdHZhzNueIZA8cUix4BBpqhshx0DLbG1SsNglgMJ94VjtlKogmT mlBsRFKokvcYQGcvsyeZCxTeFyCr2x2vdR46G+3JLIURVXAg0Ykb2jTIl7JSWdxq vjQr3N+wZ7+RxSBx+w3HV55JW/JYJ/pbvCDnWofvg+TL7sIPP0IzscrEni/kMFu6 Fc9Z4Uo0Tzeqnvify0R2J2HJOluLWb19acaaU096J0v28ywcv8O6Tiai1reH44KX qL9LCyE7EUG8xuuJkEwQHBP57dNzXB2MlJDfgymT+dp8bMmT2y8QmVS4+LliJd+t tV/9Ye/aMQHqm1R74OaIR2m/buNitSRBdthnunGE4wwzh7zYqThM+Sw6qhUt4SkD O9o/lk5/4+fMryHhkjyP81gyBsQIiW8LQX4xdI8PPPZ49fMKXk4OGc624+xbSeWM CuVydFNECtvcqsgmFlFLsOnQwdUmYLQrTWF0ZXVzeiBLb3dhbGN6eWsgPGZ1dXpl dHN1QG1lbWJlci5mc2Yub3JnPokCOQQTAQIAIwUCUatfTAIbAwcLCQgHAwIBBhUI AgkKCwQWAgMBAh4BAheAAAoJEM1mucMq2pqXH0gQAKUsR2q3VFEiYfLZYFxhqEI7 pl1FO7QRw+NZ/oZ9EXPuTx5ZUd93ahDV2px3ZVV+3POjrt067p4y8NCC0KKsZBuo Ax63M27py6WtvQ2kp1UhilzGFQ8AP2f+vtWv2bJwSkUapgEqwSDxflfITPT4yHnK R5hxiadvJLVfpbOsecbsihkQVIq1qr5pf1+9dldmPujaYMKD8J4E5MZ16N8XDBSi R9zTO4NIA/sYH7kEgOhtr8QRUUbIeQpnQnxlvo4DWHvmIZekVFDFDkWRFIsLo4HY l14MTcjJS2fRLF9/mVcCJCTQrthVjQ2Tn676J2ECMqH5D20T4abqQCdQf0fe/4R9 Ktj5BpBYzdN0+qX8q0/qRM9t8hjK+7cltqoRD6ZRTeNKhEp6HyxOLeZp/9CP0DW9 TBEKxVwq9gYZPKwX+KPd/vBIeKtBZpiCDuT3ZlQl9yZriODKD99eZqQCtObPcyFV zCWoPOSayXTZeKPFT4/9G/+2yDo5fqNORlKCDgNDlP7/9i/Y+Ei0a+gSNlAdOWfH ltiGbhr3MdgwaDats+yHBgoWG5Wuxkjs/iNAwSTww2hQy8CtOEqUd5nz1KI27tvR fUuVY16EF2lx5AgPnnknCGT72YkjtIOw/twNl6rOqDgGjPr6bUfnO2d8yHm6jX3g rRdZQ1An89H2GkpBcM8auQINBFEKtg4BEADONAGlGBh4IuPnew0GTBDyIHZ0UOc8 aPWDGg1U84OoZzDnrf+GNhHkYSdiy157Iov7HDxLqwMVsc63AuOvJ0sWFaXzAQVV a1lMEjlGvw6suuLG06/Ftno9TqmbhcMH1T1/guW51vFDWSqAMHUNYhHd4xlaur2A i0l9qorxE1mDP5j9Btkeb5X06dwoAqfqqUfbCLdzEDzHo+ir651Ge9bRo5xqOsIH uIi1C4ncmleykuWV86r6Lzw5xuXGpOx4zFbpxcTmlcc40hqWppIR72yo9v3wETaX kJRF3MU4jBqlLfFH1Fpj5KZQj9ag14IgU+QEctprw/QyL0G0XzEpeEwOq8U+Yn28 1vveXK3XE5O57tHRdvh41gfcZmDRmwfeXt4gyMCOfg21YYlicBdZtudP7ru8Os/d hCWD9+ux1+ZiMc2Zrxq0OaQRTUOCtc+vytLtGsYC3uDxXvWhnCqWUYnHeqngjzzX YcUrsRyrHoz+JcRBUEdE+2zos+Y43rc1lzYL3IB5gsBJlvMpwHyvSkckAZ74X6s1 cDrtBLI82EpHJW79vyYW7cvIXUxs8Rgd7FeZVy1c2qAoMThcm3A7uaEkT7VOXDJ0 AsEJ3/7Zycde8cwwrhSDWb401cVFdAWSWuFqnQ3fVhIPEe+8d9RPMcjr5JjobxSK OYAJqloSUd6/wwARAQABiQIfBBgBAgAJBQJRCrYOAhsMAAoJEM1mucMq2pqX/NIP +QGUnUTypVrnIMFIKMs4P39PktTX5DJ7A2XANUhLBBnDcdjtXVgPLDg1G1mXir4L xU7vqrIAirGY+im6Iqj702/YsTzPXewadpLriAUuyCsH44uJwbKos1YKHnzwdPU/ ZFIVgVUMVcBGIfWQKfopQVKJeTYleT1v1hlUn3xYRrFgMBoWh8lXGp2vDWWGX5Lb IcnPKa3l2+W9avvowqrvXDPKZF2Zh5cJdglPDK7OOb44STsZoqrj+ANEVab9aVrw aMaNshTWMRb825pmzABHekX1ZXyCPTxsefgQqXpeIms40GOJcB4RfbMCoMO8aSkN TMc4v7L9Qsj3TVuMlFGuZZreLBnK2ABYlZDtz6wzPrtpdCXDkgtv5k0dCKArCZ+k B6alrlVF4SojtP97N+1u9UO1xpJeyhFv5iZq2TVyK897VRCvQRLVhPlD50FHudI1 +8MSHVwF8q7pQ6J2DK+u0/eHUT644uZDluhC8qsxv8esmS0/K6DtBSN5VTu2MOjF EYHwwnszhJmFgHPCbhgiqhw8lMgDukYBI0DAexVnbZ5Yvk/63c3vjZ3RQg/VrlVd Ei4HLbbDUIKVVqK5guZncT+71C831sGMp0cF26aEqnLPieNZBE2rDq2w+LmDqB+5 qnYq49CYPs+JW7EI+ubqYPVTrWT0CwlCf4NICcRqGfzZ =fUL/ -----END PGP PUBLIC KEY BLOCK----- --------------080308060609060505030004--