[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: list vs vector
From: |
Damien Mattei |
Subject: |
Re: list vs vector |
Date: |
Wed, 28 Dec 2022 19:29:31 +0100 |
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 <ceving@gmail.com> 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?
>
>