lisp is winner in DOM parsing contest! 8-]

[Alex Mizrahi]

Hello, All!

i have 3mb long XML document with about 150000 lines (i think it has about
200000 elements there) which i want to parse to DOM to work with.
first i thought there will be no problems, but there were..
first i tried Python.. there's special interest group that wants to "make
Python become the premier language for XML processing" so i thought there
will be no problems with this document..
i used xml.dom.minidom to parse it.. after it ate 400 meg of RAM i killed
it - i don't want such processing.. i think this is because of that fat
class impementation - possibly Python had some significant overhead for each
object instance, or something like this..

then i asdf-installed s-xml package and tried it with it. it ate only 25
megs for lxml representation. i think interning element names helped a lot..
it was CLISP that has unicode inside, so i think it could be even less
without unicode..

then i tried C++ - TinyXML. it was fast, but ate 65 megs.. ye, looks like
interning helps a lot 8-]

then i tried Perl XML::DOM.. it was better than python - about 180megs, but
it was slowest.. at least it consumed mem slower than python 8-]

and java.. with default parser it took 45mbs.. maybe it interned strings,
but there was overhead from classes - storing trees is definitely what's
lisp optimized for 8-]

so lisp is winner.. but it has not standard way (even no non-standard but
simple) way to write binary IEEE floating point representation, so common
lisp suck and i will use c++ for my task.. 8-]]]

With best regards, Alex 'killer_storm' Mizrahi.

[Hans Nowak]

Alex Mizrahi wrote:

i have 3mb long XML document with about 150000 lines (i think it has about
200000 elements there) which i want to parse to DOM to work with.
first i thought there will be no problems, but there were..
first i tried Python.. there's special interest group that wants to "make
Python become the premier language for XML processing" so i thought there
will be no problems with this document..
i used xml.dom.minidom to parse it.. after it ate 400 meg of RAM i killed
it - i don't want such processing.. i think this is because of that fat
class impementation - possibly Python had some significant overhead for each
object instance, or something like this..

Have you tried ElementTree?

http://effbot.org/zone/element-index.htm

HTH,

--
Hans Nowak (ha**@zephyrfal con.org)
http://zephyrfalcon.org/

[Alex Mizrahi]

(message (Hello 'Hans)
(you :wrote :on '(Sun, 11 Jul 2004 21:32:11 -0400))
(

i have 3mb long XML document with about 150000 lines (i think it has
about 200000 elements there) which i want to parse to DOM to work
with.
first i thought there will be no problems, but there were..
first i tried Python.. there's special interest group that wants to
"make
Python become the premier language for XML processing" so i thought
there will be no problems with this document..
i used xml.dom.minidom to parse it.. after it ate 400 meg of RAM i
killed it - i don't want such processing.. i think this is because of
that fat class impementation - possibly Python had some significant
overhead for each object instance, or something like this..

HN> Have you tried ElementTree?

no..
just tried it - it eats 133 megs and parses for quite a long time, however
it works..
i'll consider using it because processing xml in c++ appears to be pain in
ass..

)
(With-best-regards '(Alex Mizrahi) :aka 'killer_storm)
(prin1 "Jane dates only Lisp programmers"))

[Peter Hansen]

Alex Mizrahi wrote:

i have 3mb long XML document with about 150000 lines (i think it has about
200000 elements there) which i want to parse to DOM to work with.

Often, problems with performance come down the using the
wrong algorithm, or using the wrong architecture for the
problem at hand.

Are you absolutely certain that using a full in-memory DOM
representation is the best for your problem? It seems
very unlikely to me that it really is...

For example, there are approaches which can read in the
document incrementally (and I'm not just talking SAX here),
rather than read the whole thing at once.

I found your analysis fairly simplistic, on the whole...

-Peter

[Paul Rubin]

Peter Hansen <pe***@engcorp. com> writes:

For example, there are approaches which can read in the
document incrementally (and I'm not just talking SAX here),
rather than read the whole thing at once.

Rather than either reading incrementally or else slurping in the
entire document in many-noded glory, I wonder if anyone's implemented
a parser that scans over the XML doc and makes a compact sequential
representation of the tree structure, and then provides access methods
that let you traverse the tree as if it were a real DOM, by fetching
the appropriate strings from the (probably mmap'ed) disk file as you
walk around in the tree.

[John Lenton]

On Mon, 12 Jul 2004 03:19:03 +0300, Alex Mizrahi <ud******@hotma il.com> wrote:

Hello, All!

i have 3mb long XML document with about 150000 lines (i think it has about
200000 elements there) which i want to parse to DOM to work with.
first i thought there will be no problems, but there were..
first i tried Python.. there's special interest group that wants to "make
Python become the premier language for XML processing" so i thought there
will be no problems with this document..
i used xml.dom.minidom to parse it.. after it ate 400 meg of RAM i killed
it - i don't want such processing.. i think this is because of that fat
class impementation - possibly Python had some significant overhead for each
object instance, or something like this..

in my experience xml.dom.minidom is a hog; there are several other DOM
and tree-building (i.e., DOMish) parsers out there, most of them
better from a performance point of view; my own personal favourite is
libxml2, but google for the issue and you'll even come across people
who have compared the different things.

--
John Lenton (jl*****@gmail. com) -- Random fortune:
bash: fortune: command not found

[Tim Bradshaw]

Paul Rubin <http://ph****@NOSPAM.i nvalid> wrote in message news:<7x******* *****@ruckus.br ouhaha.com>...

Rather than either reading incrementally or else slurping in the
entire document in many-noded glory, I wonder if anyone's implemented
a parser that scans over the XML doc and makes a compact sequential
representation of the tree structure, and then provides access methods
that let you traverse the tree as if it were a real DOM, by fetching
the appropriate strings from the (probably mmap'ed) disk file as you
walk around in the tree.

I dunno if this has been done recently, but this is the sort of thing
that people used to do for very large SGML documents. I forget the
details, but I remember things that were some hundreds of MB (parsed
or unparsed I'm not sure) which would be written out in some parsed
form into large files, which could then be manipulated as if the whole
object was there. Of course no one would care about a few hundred MB
of memory now, but they did then (this was 91-92 I think).

I had a theory of doing this all lazily, so you wouldn't have to do
the (slow) parsing step up-front but would just lie and say `OK, I
parsed it', then actually doing the work only on demand.

--tim

[Alex Mizrahi]

(message (Hello 'Peter)
(you :wrote :on '(Sun, 11 Jul 2004 22:15:50 -0400))
(

i have 3mb long XML document with about 150000 lines (i think it has
about 200000 elements there) which i want to parse to DOM to work
with.

PH> Often, problems with performance come down the using the wrong
PH> algorithm, or using the wrong architecture for the problem at hand.

i see nothing wrong in loading 3 mb data into RAM. however, implementation
details made it 100 times larger and it was the problem..

PH> Are you absolutely certain that using a full in-memory DOM
PH> representation is the best for your problem? It seems very unlikely
PH> to me that it really is...

format i'm dealing with is quite chaotic and i'm going to work with it
interactively - track down myself where data i need lie and see how can i
extract data..
it's only a small part of task and it's needed only temporarily, so i don't
need best thing possible - i need something that just works..

)
(With-best-regards '(Alex Mizrahi) :aka 'killer_storm)
(prin1 "Jane dates only Lisp programmers"))

[Alex Mizrahi]

(message (Hello 'Paul)
(you :wrote :on '(11 Jul 2004 20:13:42 -0700))
(

For example, there are approaches which can read in the document
incrementally (and I'm not just talking SAX here), rather than read
the whole thing at once.

PR> Rather than either reading incrementally or else slurping in the
PR> entire document in many-noded glory, I wonder if anyone's
PR> implemented a parser that scans over the XML doc and makes a compact
PR> sequential representation of the tree structure, and then provides
PR> access methods that let you traverse the tree as if it were a real
PR> DOM, by fetching the appropriate strings from the (probably mmap'ed)
PR> disk file as you walk around in the tree.

that would be nice.. i remember i've did something like this for one binary
chunky format - thingie avoided allocating new memory as long as possible..

)
(With-best-regards '(Alex Mizrahi) :aka 'killer_storm)
(prin1 "Jane dates only Lisp programmers"))

[Richie Hindle]

[Paul]

Rather than either reading incrementally or else slurping in the
entire document in many-noded glory, I wonder if anyone's implemented
a parser that scans over the XML doc and makes a compact sequential
representation of the tree structure, and then provides access methods
that let you traverse the tree as if it were a real DOM, by fetching
the appropriate strings from the (probably mmap'ed) disk file as you
walk around in the tree.

It's not exactly what you describe here, but xml.dom.pulldom is roughly
this. You access the higher-level nodes by SAX, thus not using massive
amounts of memory, but you can access the children of those higher-level
elements using DOM. The canonical example is processing a large number of
XML records - the XML document is arbitrarily large but the individual
records aren't. Pulldom passes each record to you SAX-style, and you use
DOM to process the record.

Uche Ogbuji has a short article on xml.dom.pulldom here:
http://www-106.ibm.com/developerwork...tipulldom.html

Here's the example from that article. Line 16 is the key to it - that's the
point at which you switch from SAX to DOM:

1 #Get the first line in Act IV, scene II
2
3 from xml.dom import pulldom
4
5 hamlet_file = open("hamlet.xm l")
6
7 events = pulldom.parse(h amlet_file)
8 act_counter = 0
9 for (event, node) in events:
10 if event == pulldom.START_E LEMENT:
11 if node.tagName == "ACT":
12 act_counter += 1
13 scene_counter = 1
14 if node.tagName == "SCENE":
15 if act_counter == 4 and scene_counter == 2:
16 events.expandNo de(node)
17 #Traditional DOM processing starts here
18 #Get all descendant elements named "LINE"
19 line_nodes = node.getElement sByTagName("LIN E")
20 #Print the text data of the text node
21 #of the first LINE element
22 print line_nodes[0].firstChild.dat a
23 scene_counter += 1
--
Richie Hindle
ri****@entrian. com