From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Clinton Ebadi Newsgroups: gmane.lisp.guile.devel Subject: Re: Locks and threads Date: Wed, 11 Mar 2009 23:09:11 -0400 Message-ID: <87ocw7igiw.fsf@unknownlamer.org> References: <87mycsd2rj.fsf@arudy.ossau.uklinux.net> <87vdqovofz.fsf@arudy.ossau.uklinux.net> <87vdqhc4oi.fsf@arudy.ossau.uklinux.net> <87mybrwqmj.fsf@arudy.ossau.uklinux.net> <87iqmfwohh.fsf@arudy.ossau.uklinux.net> <3ae3aa420903111829u2970b35w63b567dd2fc95752@mail.gmail.com> NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: ger.gmane.org 1236827388 23064 80.91.229.12 (12 Mar 2009 03:09:48 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Thu, 12 Mar 2009 03:09:48 +0000 (UTC) Cc: linasvepstas@gmail.com To: Guile Development Original-X-From: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Thu Mar 12 04:10:59 2009 Return-path: Envelope-to: guile-devel@m.gmane.org Original-Received: from lists.gnu.org ([199.232.76.165]) by lo.gmane.org with esmtp (Exim 4.50) id 1LhbJq-00072Y-Jk for guile-devel@m.gmane.org; Thu, 12 Mar 2009 04:10:50 +0100 Original-Received: from localhost ([127.0.0.1]:57640 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1LhbIU-00079l-Le for guile-devel@m.gmane.org; Wed, 11 Mar 2009 23:09:26 -0400 Original-Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1LhbIR-00079W-AR for guile-devel@gnu.org; Wed, 11 Mar 2009 23:09:23 -0400 Original-Received: from exim by lists.gnu.org with spam-scanned (Exim 4.43) id 1LhbIP-00079K-1c for guile-devel@gnu.org; Wed, 11 Mar 2009 23:09:22 -0400 Original-Received: from [199.232.76.173] (port=34626 helo=monty-python.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1LhbIO-00079H-UC for guile-devel@gnu.org; Wed, 11 Mar 2009 23:09:20 -0400 Original-Received: from deleuze.hcoop.net ([69.90.123.67]:51033) by monty-python.gnu.org with esmtps (TLS-1.0:RSA_AES_256_CBC_SHA1:32) (Exim 4.60) (envelope-from ) id 1LhbIO-0007mn-K7 for guile-devel@gnu.org; Wed, 11 Mar 2009 23:09:20 -0400 Original-Received: from cpe-024-211-230-216.nc.res.rr.com ([24.211.230.216] helo=rvannith) by deleuze.hcoop.net with esmtpsa (TLS-1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.63) (envelope-from ) id 1LhbIL-0007Cb-OW; Wed, 11 Mar 2009 23:09:17 -0400 In-Reply-To: <3ae3aa420903111829u2970b35w63b567dd2fc95752@mail.gmail.com> (Linas Vepstas's message of "Wed, 11 Mar 2009 20:29:12 -0500") User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/23.0.91 (gnu/linux) X-detected-operating-system: by monty-python.gnu.org: GNU/Linux 2.6 (newer, 1) X-BeenThere: guile-devel@gnu.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: "Developers list for Guile, the GNU extensibility library" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Original-Sender: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Errors-To: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.lisp.guile.devel:8264 Archived-At: Linas Vepstas writes: > An alternative idea is to try to apply some principles from > functional programming, e.g. "copy on write" (COW): when > the obarray needs to be updated, make a copy of it. Any > readers in other threads continue to safely use the > original version. When the new obarray is fully constructed, > new readers will use it. The old obarray is garbage-collected > in due time. I dunno if this could be applied for this case; > at least we have garbage collection, which removes one > major stumbling block for using COW. If the obarray were implemented as a persistent tree instead of hash table you wouldn't even need to copy it--the only operation that would need to be atomic would be committing the change--swap the pointer to the root, but only if the current root is the same as when you started modifying the obarray; otherwise merge your changes into what is presently the root if it changed in the meantime (alternatively, lock around the entire insertion/replace block). Lookup time would be increased from amortized O(1) to O(logN) and generate a bit of garbage on every insert (depth(tree) nodes), but minimizes potentially expensive locking (e.g. if multiple concurrent readers are allowed while writing to the hash table you have to handle locking everyone out when the table needs rehashing--with the persistent tree approach readers *never* block). I suppose the best way to find out would be to implement it, and I may do so as an experiment (it would require modifying some C, however, which I am not so inclined to use for a mere thought experiment). -- Lindsay (Carlton): should i eat more post its