From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Damien Mattei Newsgroups: gmane.lisp.guile.user Subject: Re: list vs vector Date: Wed, 28 Dec 2022 19:29:31 +0100 Message-ID: References: Mime-Version: 1.0 Content-Type: text/plain; charset="UTF-8" Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="32204"; mail-complaints-to="usenet@ciao.gmane.io" To: guile-user@gnu.org Original-X-From: guile-user-bounces+guile-user=m.gmane-mx.org@gnu.org Wed Dec 28 19:30:24 2022 Return-path: Envelope-to: guile-user@m.gmane-mx.org Original-Received: from lists.gnu.org ([209.51.188.17]) by ciao.gmane.io with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1pAbC3-0008Et-Hh for guile-user@m.gmane-mx.org; Wed, 28 Dec 2022 19:30:23 +0100 Original-Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1pAbBU-0003nG-GW; Wed, 28 Dec 2022 13:29:48 -0500 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1pAbBT-0003n4-F5 for guile-user@gnu.org; Wed, 28 Dec 2022 13:29:47 -0500 Original-Received: from mail-ej1-x62d.google.com ([2a00:1450:4864:20::62d]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1pAbBR-0002Xu-DR for guile-user@gnu.org; Wed, 28 Dec 2022 13:29:47 -0500 Original-Received: by mail-ej1-x62d.google.com with SMTP id kw15so39995981ejc.10 for ; Wed, 28 Dec 2022 10:29:44 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=to:subject:message-id:date:from:in-reply-to:references:mime-version :from:to:cc:subject:date:message-id:reply-to; bh=HkZwInbBC1WkEaxhcb2OZEfU81KFV1PLbs7+XfDfHLk=; b=dio7iieour/xLdFmX80g5yfk2qa389kD+tw5ztNcDd1F8FU6BH/AHbreRJg+THkmdA lSBpFjzIiPjzUroFi2q66L+HrzIgue93Io3iMdNLLlv3oCa8QpecUm11QqSJ4uAfHEuJ iBEbgJEV2R6HSUBJcspKJu6tZQFY9/jRqUdQL1dZaHJteMZHw8DnhLsZa2bXQpjAzwce zPeReAsZgBcZFafTNFs5HsySwC7YhE+iSQQn0lj6Ruxu96GlwEIA9mA6++SLkDmLcYZW 4/vHI29MzKetc0qZbwpzbA/FaZlGBbHDT6VKjVkq1Pjl4XT3+uS3WyQP8hYvWCug/Utv 0WRA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=to:subject:message-id:date:from:in-reply-to:references:mime-version :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=HkZwInbBC1WkEaxhcb2OZEfU81KFV1PLbs7+XfDfHLk=; b=svvobi0oOP+Q20AZAXVT7+nZYVJ4ii2HDunwYbVg7QO8q7LHHA4Kf8xzyknIsSJPE1 5VcoUdgvjW1e5+eL0TOAuHdaKeeu0UbEMDiAzxotXkRQQrIwpsYcfPjfmBY7g14Np1xO AO9HxlmMIYjKzMGzcyeEsmLbiUpSCHLlHzvDPpEkgfpLTVhS8mU68SmqjMtFdYaZ2Yyh JRIn66g8KGtPUlDj6iFM5GQMcw7yLqk7e4nrfTJPg4MdPBx65PEDzfxhhvCjmyFaKbOP CaAObzOQWURMvmBwuggNis61Kj0394lH032Aa/GElaecMjWAHbAvMY5z41LXv3k+4Qau cSgQ== X-Gm-Message-State: AFqh2koJvx/FXj4pAGFQhWg6WHQXTg3EG3e9XEx+vW2fxB4OQTP1+kWA Z98QtXizTMbEBevXf4oSxNYWkmt1ErqxKyjCj5MddQXQyxPMrg== X-Google-Smtp-Source: AMrXdXuH64zyyRoJskQ5i+qZTPuHZnJzB+TV3jRCbRLwLgxjPbkwZ5ge6pfR/8RAjPc/1EvypfGS35MLGR6mfnr8i5w= X-Received: by 2002:a17:906:9518:b0:814:2bd6:2f91 with SMTP id u24-20020a170906951800b008142bd62f91mr2469128ejx.395.1672252182420; Wed, 28 Dec 2022 10:29:42 -0800 (PST) In-Reply-To: Received-SPF: pass client-ip=2a00:1450:4864:20::62d; envelope-from=damien.mattei@gmail.com; helo=mail-ej1-x62d.google.com X-Spam_score_int: -20 X-Spam_score: -2.1 X-Spam_bar: -- X-Spam_report: (-2.1 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001 autolearn=ham autolearn_force=no X-Spam_action: no action X-Content-Filtered-By: Mailman/MimeDel 2.1.29 X-BeenThere: guile-user@gnu.org X-Mailman-Version: 2.1.29 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-mx.org@gnu.org Original-Sender: guile-user-bounces+guile-user=m.gmane-mx.org@gnu.org Xref: news.gmane.io gmane.lisp.guile.user:18802 Archived-At: i have no idea, at the opposite, in one of my program i experienced a vector implementation faster than the list one. Regards, Damien On Wed, Dec 28, 2022 at 2:23 PM Sascha Ziemann wrote: > I spent my Christmas vacation playing with XML and tree traversal. And > I have observed some strange timings, while measuring the execution > time of different algorithms. My test file is the XCB XML schema: > > https://cgit.freedesktop.org/xcb/proto/plain/src/xcb.xsd > > And my test program is this: > > https://gist.github.com/ceving/6eb3792c64e505909f43858039ae18f8 > > I load the XSD file with "(sxml simple)" and traverse the XML tree in > order to remove all white-spaces. During the traversal of the tree I > visit each element and destructure each element with the following > procedure: > > (define (sxml:call-with-element node proc) > (if (sxml:element? node) > (let ((name (car node)) > (rest (cdr node))) > (if (pair? rest) > (let ((maybe-attributes (car rest))) > (if (sxml:attributes? maybe-attributes) > (proc name (cdr maybe-attributes) (cdr rest)) > (proc name '() rest))) > (proc name '() '()))) > node)) > > This is necessary, because in SXML the first child of an element may > be an attribute list of an actual child element. After I had written > the procedure, I had the impression that it might be faster to work > with vectors instead of lists, because the version with vectors looks > much simpler: > > (define (vxml:call-with-element node proc) > (if (vxml:element? node) > (proc (vxml:element-name node) > (vxml:element-attributes node) > (vxml:element-children node)) > node)) > > But after I compared the two traversals, I had to realize that the > list-version is a bit faster than the vector-version. Although the > list-version does much testing, caring and cdring, the straight > forward vector-ref's are slower. Can anybody explain? > >