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: Re: Better generator and iterator support in guile w.r.t. speed Date: Wed, 06 Mar 2013 19:44:37 +0100 Message-ID: <7212145.rFsnDxKx1H@warperdoze> References: <4559439.WT9qmlgVD5@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 1362595502 16428 80.91.229.3 (6 Mar 2013 18:45:02 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Wed, 6 Mar 2013 18:45:02 +0000 (UTC) To: guile-devel@gnu.org Original-X-From: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Wed Mar 06 19:45:20 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 1UDJL5-00005x-OJ for guile-devel@m.gmane.org; Wed, 06 Mar 2013 19:45:19 +0100 Original-Received: from localhost ([::1]:49684 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1UDJKk-0003Fa-38 for guile-devel@m.gmane.org; Wed, 06 Mar 2013 13:44:58 -0500 Original-Received: from eggs.gnu.org ([208.118.235.92]:36235) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1UDJKb-0003AB-Hy for guile-devel@gnu.org; Wed, 06 Mar 2013 13:44:54 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1UDJKV-0008OE-US for guile-devel@gnu.org; Wed, 06 Mar 2013 13:44:49 -0500 Original-Received: from mail-la0-x233.google.com ([2a00:1450:4010:c03::233]:51891) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1UDJKV-0008NZ-Hl for guile-devel@gnu.org; Wed, 06 Mar 2013 13:44:43 -0500 Original-Received: by mail-la0-f51.google.com with SMTP id fo13so7805059lab.10 for ; Wed, 06 Mar 2013 10:44:41 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=x-received:from:to:subject:date:message-id:user-agent:in-reply-to :references:mime-version:content-transfer-encoding:content-type; bh=rrJmSV5grEFVC2KRd2zHYUfY7lT5hgT1A/l66FyjjlI=; b=gqd8LHsR335lbDxLjairzmyju1zRfpmkAOcAvn0jF6WmtIToJsc/wufjUDs6JUGo98 4EPVXDsDgH6K8fhIg61Y4p32xgjt7O3H/1PwrmA9cmslQGthCOy2qXOWIILf4nLd/Yka yURJqzgh/Lnd93OR0YnrKlerczC4ePNBjqqmZua+G4zBFFVCH9tWCYWjHBAdqrxUAXC7 05w06CryN8vkI/SpuLwm+0Vv56OB+6sm6iVEUJgiWsp/U8gij0+5qShulGqB/R2BRG6l d+CetXyJ0Ko/HCLWBurrygAdqNvxdaZptv79zL0ctsoRn0r8JOr4kqZCjXXt/nj4EzRH /f+g== X-Received: by 10.112.28.101 with SMTP id a5mr8041950lbh.0.1362595481637; Wed, 06 Mar 2013 10:44:41 -0800 (PST) Original-Received: from warperdoze.localnet (1-1-1-39a.veo.vs.bostream.se. [82.182.254.46]) by mx.google.com with ESMTPS id fz16sm16376173lab.5.2013.03.06.10.44.39 (version=TLSv1.1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Wed, 06 Mar 2013 10:44:40 -0800 (PST) User-Agent: KMail/4.9.4 (Linux/3.5.0-25-generic; KDE/4.9.4; x86_64; ; ) In-Reply-To: <4559439.WT9qmlgVD5@warperdoze> X-detected-operating-system: by eggs.gnu.org: Error: Malformed IPv6 address (bad octet value). X-Received-From: 2a00:1450:4010:c03::233 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:15877 Archived-At: Hi all, In my previous mail I did some discussions about what structure to use in order to allow efficient implementatin og generators and one main observation is that the curretn rtl strategy can be used. Now Have you all thought about the stack beeing a must to execute funcitons. Well we have threads but we can get lightweight in process threads quite naturally in the rtl version of guile. We could call it a coroutine and let it be an object co = (code,stack,ip,outer-stack) The idea here is that the code will have a fixed sized stack that is just enough room to store all locals and intermediate variables e.g. all the registers needed to execute the function. Any call would then need to hook onto the outer stack. The stack is typically of the form stack = [IP OUTER-FP LOCALS ...] At the creation, IP points to the starting code position and then after each exit the next ip is stored in IP and so on. To support this we need a few new operations * MULTIMOVE, from the local stack to outer stack * MULTIMOVE, to the local stack from the outer stack * OUTER-TAIL-CALL This re-uses the outer call frame used to call this coroutine and resets the IP to the initial value * OUTER-CALL This will setup a new call frame on the outer stack execute the function there * RESET-IP RESET the IP value to the initial start value * STORE-IP Store an local ip adress in IP using a label. * OUTER-RETURN Simply return using the OUTER-FP and make sure * CALL-CO This will call a CO routine by setting up the * TAIL-CALL-CO call frame or reusing the current one (in tail context) then set the OUTER-FP and jump to the IP value if a number else throw an error. And then setting IP to #f and start executing This will probably work quite ok. But the question is how well it play with call/cc and classic prompts as well as usage of the same object many times. 1. This object can only be located one time in the stack because when in use IP = #f and another application of the object down the stack would throw an error at the application 2. call/cc prompt code dynwinds and fluids inside co needs to have special versions 3. When one store the stack space one need to make sure that the co routines also get copied. To note is that these objects should be able to live immersed in the stack space for quick allocation when we inline them inside functions. ---------------------------------- Anyway I will explore this concept semewhat more and see if all scheme features can be made to interop in a good way with it. ---------------------------------- I would also come back to the question if we should have a special tree-il concept that can be used to model this behavior. I'm now inclined to concider something like. (lexical-prompts ((g #:exits (a ...) #:body (th thunk) #:exit-case (((a) (lambda (k kind arg ...) code2)) ...)) ...) code ...) The default expansion of this woule then be something like (letrec ((g . l) (let* ((tag (make-tag)) (th thunk)) (call-with-prompts tag (apply th l) (lambda (k kind arg ...) (case kind ((a) code2 ...) ...))))) ...) code ...) So if we can prove: 1. The only references of g ... inside th is through e.g. (a g arg ...) where we mean ( g arg ...) = (abort-to-prompt tag 'a g arg ...). 2. these (a ...) forms is not included in any lambda definitions or entering any funciton via it's argumnets. 3. g is never feeded as an argument to a function or located inside a closure definition anywhere in the form. 4. in ((code2 ...) ...) ... any applications of g ... is located in tail position. 5.th is always setted to either k or the initial thunk or never setted in any of the ((a) ...) forms. with these things satisfied we should be able to inline the co routine or generator inside of the function with quite good characteristic. This is interesting this should be a logically step up in generality from CL's tagbody. Of cause there is a lot of substructure and combination of the general construct. >From the rtl code we would manage just ok with the old instructions just fine except for the need to be be able to store a label value and goto to a stored label value aka named goto. WDYT? /Stefan