From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Sascha Ziemann Newsgroups: gmane.lisp.guile.user Subject: list vs vector Date: Wed, 28 Dec 2022 14:22:16 +0100 Message-ID: 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="6904"; 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 14:23:09 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 1pAWOj-0001cl-Ru for guile-user@m.gmane-mx.org; Wed, 28 Dec 2022 14:23:09 +0100 Original-Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1pAWOB-0002fI-69; Wed, 28 Dec 2022 08:22:35 -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 1pAWO7-0002dO-PK for guile-user@gnu.org; Wed, 28 Dec 2022 08:22:32 -0500 Original-Received: from mail-oi1-x231.google.com ([2607:f8b0:4864:20::231]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1pAWO5-0003p9-T0 for guile-user@gnu.org; Wed, 28 Dec 2022 08:22:31 -0500 Original-Received: by mail-oi1-x231.google.com with SMTP id o66so14800773oia.6 for ; Wed, 28 Dec 2022 05:22:29 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=to:subject:message-id:date:from:mime-version:from:to:cc:subject :date:message-id:reply-to; bh=K0Eu/bd+TCUFHSyRB2k2AVYd4KVfASTp8/hVYQ80S8w=; b=k847ylvNAxsoEQk4+DgToWJh9DYbmVEq30nSaXpSnPhNQEF9HgyL0fS2nzgIZnzg6g jIpzThR7sqhcQ6Y4njzq4RVPNs52CUYLLPWZuPdnjJxJwnUVOVz7HhWpIA4hrrLLlDr9 /ERzBaE3CF1dpYH9g21iZNCturV2q+xhVGrzZNz0pPnDt9oQy1oKvOReufg04lccOQz9 K/mW/mdgqkm0A3Go/+I0gOxf3WmrxIJLIgMN9NkygJ+GoDU1lG1Myy7BWihJU/ufmbzW KbzrfDGg8i6ZJDUKRlWYMDPopZUK4C7rE729HnRe1hEd3jrudP0KP5jUM8co0nEr9nUq mmLA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=to:subject:message-id:date:from:mime-version:x-gm-message-state :from:to:cc:subject:date:message-id:reply-to; bh=K0Eu/bd+TCUFHSyRB2k2AVYd4KVfASTp8/hVYQ80S8w=; b=jcqBR9V5GbHZ1k0FOiJvaxKVGk5oFFE1aclrQ+PF0HvRxfjcOq3t+mM0vFyffLOhhC +jigJ72a14XxsfTLdtbmvQ6EKU2le3p66xm8yF9WXXLzvDT3uTQ2fWuoq7W69W/YJU30 s3nfmrr/KNva45zDvmu1F+hNT3JkqQ37dMiOqgjJlPg21rLJnuRdhD6S/URgp3cW//9p YytU9S+69lZggKAAOTNK+WAGIOuOtBgcpkfPx5BUo012ZHRo3WRx4nhr67pOEILlcOKS MEXE3/7B9IWYBS11ITsNe+VEhRbUYMxliOjtqyygjR+HtccX0MP1cgvl9Rh8rCxZI+p1 rL3w== X-Gm-Message-State: AFqh2kqwFBLnRkOPWDKB9DyEOv0vBO2GULdqqvfSsKdUGrFpAQF/94Yq eWCvuyYN3H1gPZj7Jy12RTJDKW+KzBA18Ou53NycarUeqOU= X-Google-Smtp-Source: AMrXdXvY+wjOOM3mzfP+VztDITfIEFHi4saVFQmzTieYcKSoMtUbqttgK0uz1UNzuisU93CfKTV/vvu5mjhiidkXqSg= X-Received: by 2002:a05:6808:1391:b0:35a:4869:8541 with SMTP id c17-20020a056808139100b0035a48698541mr1788369oiw.87.1672233747896; Wed, 28 Dec 2022 05:22:27 -0800 (PST) Received-SPF: pass client-ip=2607:f8b0:4864:20::231; envelope-from=ceving@gmail.com; helo=mail-oi1-x231.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, 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-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:18800 Archived-At: 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?