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?
