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: optimizing lazy sequences: srfi-41 vs delayed continuation with values + promise vs delayed continuation with cons + lambda Date: Sun, 25 Feb 2018 15:16:48 +0100 Message-ID: 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 1519568115 2714 195.159.176.226 (25 Feb 2018 14:15:15 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Sun, 25 Feb 2018 14:15:15 +0000 (UTC) User-Agent: Roundcube Webmail/1.1.2 To: Guile User Original-X-From: guile-user-bounces+guile-user=m.gmane.org@gnu.org Sun Feb 25 15:15:11 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 1epx55-00006L-HS for guile-user@m.gmane.org; Sun, 25 Feb 2018 15:15:11 +0100 Original-Received: from localhost ([::1]:54574 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1epx77-0005MK-O6 for guile-user@m.gmane.org; Sun, 25 Feb 2018 09:17:17 -0500 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:49631) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1epx6i-0005M1-IT for guile-user@gnu.org; Sun, 25 Feb 2018 09:16:53 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1epx6h-0005qi-CI for guile-user@gnu.org; Sun, 25 Feb 2018 09:16:52 -0500 Original-Received: from relay4-d.mail.gandi.net ([2001:4b98:c:538::196]:60878) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1epx6h-0005om-5J for guile-user@gnu.org; Sun, 25 Feb 2018 09:16:51 -0500 Original-Received: from webmail.gandi.net (webmail7-d.mgt.gandi.net [10.58.1.147]) (Authenticated sender: amirouche@hypermove.net) by relay4-d.mail.gandi.net (Postfix) with ESMTPA id 1B47D17209A for ; Sun, 25 Feb 2018 15:16:48 +0100 (CET) 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::196 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:14460 Archived-At: 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. 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!