Re: list vs vector

[Damien Mattei <damien.mattei@gmail.com>]

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?
>
>