From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: ludo@gnu.org (Ludovic =?utf-8?Q?Court=C3=A8s?=) Newsgroups: gmane.lisp.guile.devel Subject: Re: vhash speed thread safeness Date: Tue, 29 Oct 2013 18:54:56 +0100 Message-ID: <87zjpsnerz.fsf@gnu.org> References: <3150759.E8ExfKuC24@warperdoze> <87zjpsp86c.fsf@gnu.org> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable X-Trace: ger.gmane.org 1383069311 14983 80.91.229.3 (29 Oct 2013 17:55:11 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Tue, 29 Oct 2013 17:55:11 +0000 (UTC) Cc: guile-devel To: Stefan Israelsson Tampe Original-X-From: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Tue Oct 29 18:55:14 2013 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 1VbDVZ-0005kj-0b for guile-devel@m.gmane.org; Tue, 29 Oct 2013 18:55:13 +0100 Original-Received: from localhost ([::1]:48644 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1VbDVY-0004h7-MO for guile-devel@m.gmane.org; Tue, 29 Oct 2013 13:55:12 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:45932) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1VbDVQ-0004dW-75 for guile-devel@gnu.org; Tue, 29 Oct 2013 13:55:10 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1VbDVK-0005Pm-Cu for guile-devel@gnu.org; Tue, 29 Oct 2013 13:55:04 -0400 Original-Received: from mail2-relais-roc.national.inria.fr ([192.134.164.83]:48630) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1VbDVK-0005PT-6O for guile-devel@gnu.org; Tue, 29 Oct 2013 13:54:58 -0400 X-IronPort-AV: E=Sophos;i="4.93,594,1378850400"; d="scan'208";a="39497224" Original-Received: from unknown (HELO pluto) ([193.50.110.112]) by mail2-relais-roc.national.inria.fr with ESMTP/TLS/AES128-SHA; 29 Oct 2013 18:54:45 +0100 X-URL: http://www.fdn.fr/~lcourtes/ X-Revolutionary-Date: 8 Brumaire an 222 de la =?utf-8?Q?R=C3=A9volution?= X-PGP-Key-ID: 0xEA52ECF4 X-PGP-Key: http://www.fdn.fr/~lcourtes/ludovic.asc X-PGP-Fingerprint: 83C4 F8E5 10A3 3B4C 5BEA D15D 77DD 95E2 EA52 ECF4 X-OS: x86_64-unknown-linux-gnu In-Reply-To: (Stefan Israelsson Tampe's message of "Tue, 29 Oct 2013 15:21:34 +0100") User-Agent: Gnus/5.130007 (Ma Gnus v0.7) Emacs/24.3 (gnu/linux) X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. X-Received-From: 192.134.164.83 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:16700 Archived-At: Stefan Israelsson Tampe skribis: > On Tue, Oct 29, 2013 at 1:34 PM, Ludovic Court=C3=A8s wrot= e: > >> Hi, Stefan, >> >> Stefan Israelsson Tampe skribis: >> >> > I did some tests witha C-based vhash implementation, it's possible to >> > increse the speed by 30x compared to current vlist imlpementation in >> > guile. It would be possible to get this speed today if one implemented >> > vhash-assoc as a VM op. Anyway using the source as a standard lib will >> > get you about 10x speed increase. >> >> As we discussed, I don=E2=80=99t really like the idea of implementing th= at much >> in C. >> > My neither, but it is good to see that in cache friendly cases we can > improve the situation 30x. Gives us a goal to strive for. Also the main > intention is to use vashses for guile-log. For this we can note. OK. [...] >> > Another pressing need is that vhashes are not thread safe, >> >> Section 2.8 of Bagwell=E2=80=99s paper proposes a simple solution. All = that is >> missing AFAICS is an atomic test-and-set VM op to implement it (which >> may also be useful in other places.) >> >> What do you think of this approach? > > > For vlists it's probably a good idea, I don't know if it's enough for > vhashes though. Oooh, right, sorry for overlooking that. > Maybe you need a mutex. But lock overhead will be significant Surely, especially if it=E2=80=99s a fat mutex. Hmm hmm. Of course that could be an argument for doing some C (primitives, not VM ops), but looking at =E2=80=98%vhash-assoc=E2=80=99, th= at would clearly mean reimplementing pretty much all of the vlist + vhash in C, which sucks. I wonder if there=E2=80=99s some other data structure with similar properti= es that doesn=E2=80=99t have the thread-safety issue. Maybe Ian has an idea? The weight-balanced trees in MIT/GNU Scheme look interesting: http://www.gnu.org/software/mit-scheme/documentation/mit-scheme-ref/Weigh= t_002dBalanced-Trees.html Thoughts? Thanks, Ludo=E2=80=99.