From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Stefan Israelsson Tampe Newsgroups: gmane.lisp.guile.devel Subject: vhash speed thread safeness Date: Fri, 18 Oct 2013 18:21:04 +0200 Message-ID: <3150759.E8ExfKuC24@warperdoze> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7Bit X-Trace: ger.gmane.org 1382113295 23464 80.91.229.3 (18 Oct 2013 16:21:35 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Fri, 18 Oct 2013 16:21:35 +0000 (UTC) To: guile-devel@gnu.org Original-X-From: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Fri Oct 18 18:21:39 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 1VXCny-0008Pc-UE for guile-devel@m.gmane.org; Fri, 18 Oct 2013 18:21:39 +0200 Original-Received: from localhost ([::1]:58670 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1VXCny-0000oo-FC for guile-devel@m.gmane.org; Fri, 18 Oct 2013 12:21:38 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:48526) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1VXCnm-0000mv-SX for guile-devel@gnu.org; Fri, 18 Oct 2013 12:21:35 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1VXCne-0008PZ-2m for guile-devel@gnu.org; Fri, 18 Oct 2013 12:21:26 -0400 Original-Received: from mail-lb0-x229.google.com ([2a00:1450:4010:c04::229]:40583) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1VXCnd-0008OM-QP for guile-devel@gnu.org; Fri, 18 Oct 2013 12:21:17 -0400 Original-Received: by mail-lb0-f169.google.com with SMTP id z5so3391114lbh.0 for ; Fri, 18 Oct 2013 09:21:16 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=from:to:subject:date:message-id:user-agent:mime-version :content-transfer-encoding:content-type; bh=fSBAbDLa86jQIXwcVahdYQmD+on22QuvfRSFpoKLHwM=; b=kZFPIvG85M4fVRL1r3DSFByMyW/8YhKzCn2tXEq0aDoiMuQ5NYryImV4Dph1MqN1tp 21CVFMuD4g1F9WT1N8jb6vYH2QQdTZBXR1RdFdaX0B8jeKvs/BZQc3A7MOBtCMRhYazI SgXnmJy5v+5Ig3cmItD8PgQRNCgeLx/dE+W4tpbynkIQnOpdXKxltkGLOCBIuzk1Yvqs NHmy4ykLfMDV3e8N4v9k5/2xY0bfnZ0daZawUZ/BQ7L9iDyVJqEYY5W9z0lQFyiYpVCY rWUZjD32MXJN7sBb2Wn/+1jhZ8sPNF7byV+nam0ZXYHfomNY1JoPockjPz7puA1QkD8j z0yg== X-Received: by 10.152.10.99 with SMTP id h3mr3142719lab.13.1382113276064; Fri, 18 Oct 2013 09:21:16 -0700 (PDT) Original-Received: from warperdoze.localnet (1-1-1-39a.veo.vs.bostream.se. [82.182.254.46]) by mx.google.com with ESMTPSA id mr1sm2362445lbc.16.2013.10.18.09.21.13 for (version=TLSv1.1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Fri, 18 Oct 2013 09:21:14 -0700 (PDT) User-Agent: KMail/4.9.5 (Linux/3.5.0-30-generic; KDE/4.9.5; x86_64; ; ) X-detected-operating-system: by eggs.gnu.org: Error: Malformed IPv6 address (bad octet value). X-Received-From: 2a00:1450:4010:c04::229 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:16681 Archived-At: Hi all, 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. Another pressing need is that vhashes are not thread safe, also a downside is that if there are many versions spawned by each vhash the good theoretical properties may not realize. Anyway here is a suggestion of how to make it thread safe: 1. keep two numbers seq-int and thread-id on the block. thread-id is a unique id for a thread. And seq-id is a unique id for a state. 2. At thread-creation in thread 1 spawning thread 2. increment thread 1's seq-id, and allocate a new id to thread 2 and set it's seq-id to zero. 3. Att vhash-cons, if not the vhash seq-id and thread-id matches we must create a new block pointing to the old vhash with size equal to k. 4. this is thread safe and will not waste space, but can create problems with lot's of small blocks linked and essentially get a sort of linked list the computational lookup is o(T), T is the number of threads. 5. If we get an issue with lot's of small block linked together we could detect this and issue a "remake" in order to speed up access times. This is not a problem that is unique to threading but can be seen in a naive use of vhashes for many applications that backtracks and use old copies of vhashes. So a solution of autocompilation would be needed. 6. I plan to add a version of vhashes to guile-log as a replacement of the assoc list. What I will then use is to tag vhash blocks as referenced and when backtracking and the block is not referenced it will simply reset the offset pointer and reuse the block-frame instead of linking another one to it. Some kind of reference counter technique would be used here. n guile-log we have good control on when we reference for storage so this solution would probably work just great. With all this implementing good thread safe ideoms into guile-log would be quite possible. Regards Stefan