list vs vector

[Sascha Ziemann <ceving@gmail.com>]

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?