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,gmane.lisp.guile.user Subject: guile-log directions Date: Sat, 19 Oct 2013 18:20:31 +0200 Message-ID: <197460556.cXDhcVV7V2@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 1382199656 29234 80.91.229.3 (19 Oct 2013 16:20:56 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Sat, 19 Oct 2013 16:20:56 +0000 (UTC) To: guile-devel@gnu.org, guile-user@gnu.org Original-X-From: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Sat Oct 19 18:21:00 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 1VXZGu-0000aF-7U for guile-devel@m.gmane.org; Sat, 19 Oct 2013 18:21:00 +0200 Original-Received: from localhost ([::1]:33809 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1VXZGt-0004zx-Q1 for guile-devel@m.gmane.org; Sat, 19 Oct 2013 12:20:59 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:43258) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1VXZGi-0004zK-12 for guile-devel@gnu.org; Sat, 19 Oct 2013 12:20:56 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1VXZGZ-0002G2-IJ for guile-devel@gnu.org; Sat, 19 Oct 2013 12:20:47 -0400 Original-Received: from mail-la0-x232.google.com ([2a00:1450:4010:c03::232]:53682) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1VXZGY-0002Du-Ru; Sat, 19 Oct 2013 12:20:39 -0400 Original-Received: by mail-la0-f50.google.com with SMTP id ec20so883835lab.37 for ; Sat, 19 Oct 2013 09:20:37 -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=zNPhDNf6CSWQ5w9nLW5hW/j202rUOE4dE9z2bJkajb8=; b=yPTMX0J/QMwoJYPoMhgt4e7EW4KEBgpH+aArrUofnZ+l/D9la6LUwAWN/Nh5HYfqS4 y0bc68lLQ8/QoAXUDNmec80ti0w54V/GIX8lXXcKbL8aWDtqpbCPwuOat2Fkob0SfwQW kMMix3qm9U8fOpF1y1ilpvLj1gRM8OtMc2EPRnDWQ2BR2edAhtZ+Dq8Vgtc73B3+13lx mXn1SmHp7CDa/GGKD8avBl9DqjRL7fHZFA10aAqmp1F8zpiJGpKBivR7A0L8xF5ZpTbj ZPbwQv63pReh2E8EInQdG06o3+Ine6197AeWJNNy8ldfkMONULuIOaZZy8g7MrRC0T8d zBKA== X-Received: by 10.112.55.173 with SMTP id t13mr223175lbp.39.1382199637584; Sat, 19 Oct 2013 09:20:37 -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 b6sm7030089lae.0.2013.10.19.09.20.35 for (version=TLSv1.1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Sat, 19 Oct 2013 09:20:36 -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:c03::232 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:16684 gmane.lisp.guile.user:10852 Archived-At: Hi all, I'm just about to introduce a new feature for guile-log. A fast threadsafe version that scales well + suitable ideoms to do logic programming in parallell. Now what do we do today. There is two possibilities to produce a normal logical variable in guile-log, 1. A super fast version that is not thread safe that scales badly for interleaving constructs and delimeted continuaitons. 2. A really slow version that scales badly but is thread safe. Those following the guile-log devel list will note that I've been working on improving on guile's vlist/vhash implementation. vlists/vhashes scales (normally) well when it comes to lookups of available keys, but vhashes are not thread safe and also vlists scales badly in backtracking usage. So what I've been doing is to make vhashes threadsafe and introduced, (vlist-truncate! vlist) (vhash-truncate! vhash) (vlist-refcount++ vlist/vhash) (vlist-refcount-- vlist/vhash) All these constructs beeing thread safe. What truncate does is that it will try to truncate a list to the position it references to (the underlying vector might be shared with another ref and hence one would need to link in a new frame to it and loose scalability) The reason that truncate! is a good ideom is that at backtracking normally all later refs is void and one can safely truncate. But not always and that is what vlist-refcount++ and vlist-refcount-- is targetting. if refcount is > 0 then the truncate operation is void e.g. it signals that the vlist is used higher up. Because we have such a good control on when we store a ref or not in guile-log the API proposed is well designed and will enable fast versions of vlist to be used as an assoc for variable values. So the not super-fast, but fast version of variables will be objects,val pairs stored in a vhash Thread safeness and high speed at the same time might cause a red alert when getting the description of the truncate operation. But we do not loos to much on employing this scheme fot the single threaded case. (Mainly a set of fast bit operations, but no extra memory lookup) Also the code is optimized for 64 bits, it will probably be slower on 32bit platforms. Anyhow how is thread safeness reached? the answer is that each vector containing data is guarded by a thread id and a thread seq. At each thread creation the current threads seq number will be incremented and the new thread will get a new different id with a seq number of zero. So when we create a bin we associate the current thread id and and the seq id to the bin. And then when we try to mutate, the id's have to match else we will just produce a link to the datastructure. This means that thread safeness is reached (almost). If one have to transport vhashes between threads at a later stage then thread creation, one can enter a command (vlist-freeze vhash/vlist) before moving the hash to the other thread and all would be thread safe. What this operation does is to decrement the seq in all live bins that the current thread owns. The problem with this is that for some thread applications, we might end up with long chaines of bins and loose the good propoerties vhashes have. One solution woulod be for the user to use a binary functional tree instead. Or that we produce a new ideom e.g. new-vhash,key.val <- (vhash-assoc key vhash) where essentially a new vhash is constructed combining many small ones in order to improve lookup performance according to some heuristic. This is not done, but is an interesrting idea. So my message is that we can fix the problem with vhashes and use it in even more projects, and I'm willing to supply a patch for vlist.scm is people on the list agree that the ideas above is sound. Else I will add vhashes to guile-log, because I belive that they in their right incarnation will shine there. Anyhow there might be improvements that you see on this scheme of getting it all to work, please feel free to suggest these improvements. Highly Happy Hacking to you all, Stefan