From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED!not-for-mail From: Amirouche Boubekki Newsgroups: gmane.lisp.guile.user Subject: Re: optimizing lazy sequences: srfi-41 vs delayed continuation with values + promise vs delayed continuation with cons + lambda Date: Sun, 25 Feb 2018 15:30:16 +0100 Message-ID: References: NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII; format=flowed Content-Transfer-Encoding: 7bit X-Trace: blaine.gmane.org 1519568931 9401 195.159.176.226 (25 Feb 2018 14:28:51 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Sun, 25 Feb 2018 14:28:51 +0000 (UTC) User-Agent: Roundcube Webmail/1.1.2 Cc: guile-user To: Guile User Original-X-From: guile-user-bounces+guile-user=m.gmane.org@gnu.org Sun Feb 25 15:28:47 2018 Return-path: Envelope-to: guile-user@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by blaine.gmane.org with esmtp (Exim 4.84_2) (envelope-from ) id 1epxID-0001es-7y for guile-user@m.gmane.org; Sun, 25 Feb 2018 15:28:45 +0100 Original-Received: from localhost ([::1]:54592 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1epxKD-0007aK-Jk for guile-user@m.gmane.org; Sun, 25 Feb 2018 09:30:49 -0500 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:51439) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1epxJn-0007Zu-0f for guile-user@gnu.org; Sun, 25 Feb 2018 09:30:24 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1epxJl-0000hT-PH for guile-user@gnu.org; Sun, 25 Feb 2018 09:30:23 -0500 Original-Received: from relay5-d.mail.gandi.net ([2001:4b98:c:538::197]:49968) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1epxJi-0000dA-TP; Sun, 25 Feb 2018 09:30:19 -0500 Original-Received: from webmail.gandi.net (webmail7-d.mgt.gandi.net [10.58.1.147]) (Authenticated sender: amirouche@hypermove.net) by relay5-d.mail.gandi.net (Postfix) with ESMTPA id 9140741C08A; Sun, 25 Feb 2018 15:30:16 +0100 (CET) In-Reply-To: X-Sender: amirouche@hypermove.net X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] X-Received-From: 2001:4b98:c:538::197 X-BeenThere: guile-user@gnu.org X-Mailman-Version: 2.1.21 Precedence: list List-Id: General Guile related discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: guile-user-bounces+guile-user=m.gmane.org@gnu.org Original-Sender: "guile-user" Xref: news.gmane.org gmane.lisp.guile.user:14461 Archived-At: On 2018-02-25 15:16, Amirouche Boubekki wrote: > Hello all, > > I know it's not good to optimize first, but I got into it > and now I need to know. > > A few months ago, I created a lazy sequence library that retains > history based on delayed continuation, it can be summarized > as follow: > > (define-public (list->traversi lst) > (let loop ((lst lst)) > (lambda () > (if (null? lst) > '() > ;; here the car of the pair contains the first value > ;; and an empty list as history > (cons (cons (car lst) '()) (loop (cdr lst))))))) > > (define-public (traversi->list traversi) > (let loop ((traversi traversi) > (out '())) > (match (traversi) > ('() (reverse out)) > ((item . next) (loop next (cons (car item) out)))))) > > (define-public (traversi-map proc traversi) > (let loop ((traversi traversi)) > (lambda () > (match (traversi) > ('() '()) > ((item . next) (cons (cons (proc (car item)) item) (loop > next))))))) > > They are other procedures, but that is the gist of it. > > I tested it on a parser combinator for csv and it seemed much > faster than the srfi-41 based parser combinators [0]. > > [0] https://git.dthompson.us/guile-parser-combinators.git > > Now, I got another idea what if I replace the 'cons' returned > by the traversi procedures by 'values' and replace the > lambda with 'delay' with some use of 'force' at the correct > places. It will result in the following procedures: > > (define-public (list->stream lst) > (let loop ((lst lst)) > (if (null? lst) > (delay (values #f #f)) > (delay (values (car lst) (loop (cdr lst))))))) > > (define-public (stream->list stream) > (let loop ((stream stream) > (out '())) > (call-with-values (lambda () (force stream)) > (lambda (value next) > (if next > (loop next (cons value out)) > (reverse! out)))))) > > (define-public (stream-map proc stream) > (let loop ((stream stream)) > (call-with-values (lambda () (force stream)) > (lambda (value next) > (if next > (delay (values (proc value) (loop next))) > (delay (values #f #f))))))) > > I tested those procedures in the REPL with ,time and > the results are not conclusive: > > scheme@(guile-user)> (define (nop o) #t) > > > scheme@(guile-user)> ,time (nop (traversi->list (traversi-map (lambda > (x) (1+ x)) (list->traversi (iota (expt 2 10)))))) > $1 = #t > ;; 0.028090s real time, 0.037698s run time. 0.012421s spent in GC. > scheme@(guile-user)> ,time (nop (traversi->list (traversi-map (lambda > (x) (1+ x)) (list->traversi (iota (expt 2 10)))))) > $2 = #t > ;; 0.025622s real time, 0.025614s run time. 0.000000s spent in GC. > scheme@(guile-user)> ,time (nop (traversi->list (traversi-map (lambda > (x) (1+ x)) (list->traversi (iota (expt 2 10)))))) > $3 = #t > ;; 0.034165s real time, 0.034146s run time. 0.000000s spent in GC. > > scheme@(guile-user)> ,time (nop (stream->list (stream-map (lambda (x) > (1+ x)) (list->stream (iota (expt 2 10)))))) > $4 = #t > ;; 0.031616s real time, 0.041882s run time. 0.014514s spent in GC. > scheme@(guile-user)> ,time (nop (stream->list (stream-map (lambda (x) > (1+ x)) (list->stream (iota (expt 2 10)))))) > $5 = #t > ;; 0.026148s real time, 0.026141s run time. 0.000000s spent in GC. > scheme@(guile-user)> ,time (nop (stream->list (stream-map (lambda (x) > (1+ x)) (list->stream (iota (expt 2 10)))))) > $6 = #t > ;; 0.028477s real time, 0.037107s run time. 0.011057s spent in GC. I forgot the srfi-41 because they are worse: scheme@(guile-user)> (use-modules (srfi srfi-41))scheme@(guile-user)> (define (nop o) #t) scheme@(guile-user)> ,time (nop (stream->list (stream-map (lambda (x) (1+ x)) (list->stream (iota (expt 2 10)))))) $1 = #t ;; 0.034429s real time, 0.043788s run time. 0.012689s spent in GC. scheme@(guile-user)> ,time (nop (stream->list (stream-map (lambda (x) (1+ x)) (list->stream (iota (expt 2 10)))))) $2 = #t ;; 0.033329s real time, 0.041973s run time. 0.010852s spent in GC. scheme@(guile-user)> ,time (nop (stream->list (stream-map (lambda (x) (1+ x)) (list->stream (iota (expt 2 10)))))) $3 = #t ;; 0.056261s real time, 0.064563s run time. 0.010440s spent in GC. > Q: What in theory should be faster? > > Q: How can I test / proove that one approach must be faster? > > From the usability & readability point of view I find the > values + promise much more readable and easier to code. > > TIA! -- Amirouche ~ amz3 ~ http://www.hyperdev.fr