recursion in XML parser

[David Brownell]

Marcelo Cantos wrote:
> 
> I can't speak for the JVM, but it is far from safe to generalise and
> state that a function call is as fast as a stack push, particularly
> when the programmer knows exactly what needs to be pushed.

There's no reason a nonvirtual function call shouldn't compile to be
just the stack operation.

If you're using a virtual function call, the same reasoning applies
as for a C++/Obj-C/... virtual function call.  Namely, that one can't
just say "it's not free"; a comparison needs to include the cost of
an alternative with the same functionality.  And curiously enough,
when you do those comparisons, the functionality seems to be relatively
cheaper when packaged as a "virtual function call" than when packaged
as an if/then/else/... set of data operations, or other alternatives.


This discussion seems pretty odd to me.  Exactly what alternative is
being advocated?  Remember that per-element state _must_ be maintained
when parsing XML, and the model is a stack.  Whether that stack gets
maintained using the CPU stack or explicit emulation in some other
memory data structure, it'll be there.  Function calls use the CPU
stack, and clean up very efficiently.  Explicit emulation uses a
different memory segment; and needs more work to GC correctly.


> Moreover, modern architectures often penalise you heavily for deep
> recursion.  For instance, the SPARC architecture uses register
> windowing.  ...

Which can be bypassed by modern compilers for those applications
where it matters.  For example, graphics algorithms tend to need
lots of registers (e.g. VIS code) and device drivers need to have
predictable latencies (that is, they can't afford to flush windows
in a time-critical interrupt handler).

In short, that argument doesn't wash; it's a code generation issue,
not a problem with recursion.

- Dave

xml-dev: A list for W3C XML Developers. To post, mailto:xml-dev at ic.ac.uk
Archived as: http://www.lists.ic.ac.uk/hypermail/xml-dev/ and on CD-ROM/ISBN 981-02-3594-1
To (un)subscribe, mailto:majordomo at ic.ac.uk the following message;
(un)subscribe xml-dev
To subscribe to the digests, mailto:majordomo at ic.ac.uk the following message;
subscribe xml-dev-digest
List coordinator, Henry Rzepa (mailto:rzepa at ic.ac.uk)