Re: [Caml-list] ocaml-3.05: a performance experience

Re: [Caml-list] ocaml-3.05: a performance experience

[Damien Doligez]

>From: "Alexander V. Voinov" <avv@quasar.ipa.nw.ru>

>Compiled with ocaml-3.04 it took 1h40m+-5m of 'user' process time and
>occupied about 340M in RAM. With 3.05 it took 2h40m+-5m and occupied
>250M. 

>Is this the consequence of the new GC strategy? Actually I'd tolerate
>large footprint for the sake of more speed.

Not really.  When debugging the problem of the compactor that would
not trigger, I stumbled on a bug in the way the GC determines its
speed (relative to the program).  In 3.04, when you ask for an
overhead of 42% (the default), the actual overhead is closer to 80%.
In 3.05 I fixed the formulas, but I didn't change the default 42%,
which results in a smaller memory footprint, but slower programs.

Of course, you can even try 100% or more.  Depending on the program,
you might gain a lot of time before you hit the point of diminishing
returns.

If you want to recover the previous behaviour, you should set
something like OCAMLRUNPARAM=o=80.  In 3.06, it will be the default.

Sorry for the inconvenience,

-- Damien
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

[Caml-list] ocaml-3.05: a performance experience

[Alexander V. Voinov]

Hi All,

I have an application, which parses a huge XML file and stores resulting
records to a database.

The file is parsed using PXP, but in a 'pulldom' manner, by extracting
(to a Buffer) first level tags manually with pcre, then an array insert
of 30000 recognized and accumulated records is performed. DB access
takes a small fraction of the run time.

Compiled with ocaml-3.04 it took 1h40m+-5m of 'user' process time and
occupied about 340M in RAM. With 3.05 it took 2h40m+-5m and occupied
250M. 

Is this the consequence of the new GC strategy? Actually I'd tolerate
large footprint for the sake of more speed.

It's also interesting to note, than in the case of 3.04 the footprint of
the application starts from 330M and slowly expands to 350M. With 3.05
it starts with 250M and then almost does not expand till the end.

Sparc Solaris 2.7, gcc 3.0.4.

A previous version of this app, written in Python with PyXML, runs 3-4
times slower than the 3.04 version and takes 20M in RAM.

Alexander
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] ocaml-3.05: a performance experience

[Gerd Stolpmann]

On 2002.08.02 05:33 Alexander V. Voinov wrote:
> Hi All,
> 
> I have an application, which parses a huge XML file and stores resulting
> records to a database.
> 
> The file is parsed using PXP, but in a 'pulldom' manner, by extracting
> (to a Buffer) first level tags manually with pcre, then an array insert
> of 30000 recognized and accumulated records is performed. DB access
> takes a small fraction of the run time.
> 
> Compiled with ocaml-3.04 it took 1h40m+-5m of 'user' process time and
> occupied about 340M in RAM. With 3.05 it took 2h40m+-5m and occupied
> 250M. 
> 
> Is this the consequence of the new GC strategy? Actually I'd tolerate
> large footprint for the sake of more speed.
> 
> It's also interesting to note, than in the case of 3.04 the footprint of
> the application starts from 330M and slowly expands to 350M. With 3.05
> it starts with 250M and then almost does not expand till the end.
> 
> Sparc Solaris 2.7, gcc 3.0.4.
> 
> A previous version of this app, written in Python with PyXML, runs 3-4
> times slower than the 3.04 version and takes 20M in RAM.

I think you observe GC compaction. You can turn it off:
OCAMLRUNPARAM="O=1000000" (or Gc.set).

If XML validation is not needed, you could also rewrite your program
to use the new event-based parsing in PXP-1.1.90. That would completely
avoid to represent the XML tree in memory (and increase the speed, because
GC of large memory footprints is expensive).

Gerd
-- 
----------------------------------------------------------------------------
Gerd Stolpmann      Telefon: +49 6151 997705 (privat)
Viktoriastr. 45             
64293 Darmstadt     EMail:   gerd@gerd-stolpmann.de
Germany                     
----------------------------------------------------------------------------
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] ocaml-3.05: a performance experience

[Alexander V. Voinov]

Hi Gerd,

Gerd Stolpmann wrote:
> I think you observe GC compaction. You can turn it off:
> OCAMLRUNPARAM="O=1000000" (or Gc.set).

Thank you. This eliminated 2/3 of the difference and adding
Gc.space_overhead = 95 returned the app to the numbers of 3.04, both for
the speed and for the footprint.

> If XML validation is not needed, you could also rewrite your program
> to use the new event-based parsing in PXP-1.1.90. That would completely
> avoid to represent the XML tree in memory (and increase the speed, because
> GC of large memory footprints is expensive).

thanks again, but it's not yet officially announced, is it? I managed to
download it, but I didn't find any direct link. Also, it this parsing
mode mentioned in the manual?

Alexander
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] ocaml-3.05: a performance experience

[Gerd Stolpmann]

On 2002.08.04 04:50 Alexander V. Voinov wrote:
> Hi Gerd,
> 
> Gerd Stolpmann wrote:
> > If XML validation is not needed, you could also rewrite your program
> > to use the new event-based parsing in PXP-1.1.90. That would completely
> > avoid to represent the XML tree in memory (and increase the speed, because
> > GC of large memory footprints is expensive).
> 
> thanks again, but it's not yet officially announced, is it? I managed to
> download it, but I didn't find any direct link. Also, it this parsing
> mode mentioned in the manual?

It is experimental code, but event-based parsing will definitely remain
in the parser until the next stable release. Details of the interface may
change, however. (I call a release "stable" when the interface has matured,
and when all regression tests have passed. The experimental releases usually
work, but it is more likely that there is some "overlooked case" in the
code.)

The manual is not yet updated, there is only a description in the mli file,
and a small example. In particular, there is type 

type event =
  | E_start_doc of (string * bool * dtd)
  | E_end_doc
  | E_start_tag of (string * (string * string) list * Pxp_lexer_types.entity_id)
  | E_end_tag   of (string * Pxp_lexer_types.entity_id)
  | E_char_data of  string
  | E_pinstr of (string * string)
  | E_comment of string
  | E_position of (string * int * int)
  | E_error of exn
  | E_end_of_stream

and a function is called back for every of these events. For example, for

<A x="1">Q<B>R</B>S</A>

you would get the events

E_start_doc("1.0",false,dtd)
E_start_tag("A", ["x", "1"], ent_a)
E_char_data "Q"
E_start_tag("B", [], ent_b)
E_char_data "R"
E_end_tag("B", ent_b)
E_char_data "S"
E_end_tag("A", ent_a)

It is already checked that the document is well-formed, so for end E_end_tag
there is always a matching E_start_tag.

Because the parser "pushes" the events to the application, this is a so-called
"push parser". There are plans for a "pull parser", too (the application calls
a next_event function to get the events), as this would allow to create
streams of XML events.

Gerd
-- 
----------------------------------------------------------------------------
Gerd Stolpmann      Telefon: +49 6151 997705 (privat)
Viktoriastr. 45             
64293 Darmstadt     EMail:   gerd@gerd-stolpmann.de
Germany                     
----------------------------------------------------------------------------
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] ocaml-3.05: a performance experience

[John Max Skaller]

Gerd Stolpmann wrote

[XML parser]

>Because the parser "pushes" the events to the application, this is a so-called
>"push parser". 
>

The client must supply callbacks.

>There are plans for a "pull parser", too (the application calls
>a next_event function to get the events), as this would allow to create
>streams of XML events.
>

I'm intrigued by the relationship between these two parsers. In particular,
note that my Felix compiler takes 'pull' code, and automatically 
translates it
to the much more efficient 'push' model: ie. it switches the client/server
relationship around, a process I call control inversion.

I believe there is a deep theoretical relationship between push and pull
code -- some kind of categorical duality -- but I dont know precisely what
it is .... despite being able to actually translate one to the other 
using Felix :-)

I'd be very interested if anyone has any ideas on this.

-- 
John Max Skaller, mailto:skaller@ozemail.com.au
snail:10/1 Toxteth Rd, Glebe, NSW 2037, Australia.
voice:61-2-9660-0850




-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] ocaml-3.05: a performance experience

[Mike Lin]

> I'm intrigued by the relationship between these two parsers. In
particular,
> note that my Felix compiler takes 'pull' code, and automatically
> translates it
> to the much more efficient 'push' model: ie. it switches the client/server
> relationship around, a process I call control inversion.

I'm just curious if you could elaborate on in what respect a push parser is
"much more efficient"? From my experience pull parsers tend to be easier to
use because they don't impose an event-driven model on the driver program,
and also it is trivial to build a push parser on top of a pull parser.

-Mike

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] ocaml-3.05: a performance experience

[Alexander V.Voinov]

Hi All,

It looks like it's time to introduce continuations in OCaml :-).

Alexander

From: "Mike Lin" <mikelin@MIT.EDU>
Subject: Re: [Caml-list] ocaml-3.05: a performance experience
Date: Mon, 5 Aug 2002 12:24:07 -0400

> 
> > I'm intrigued by the relationship between these two parsers. In
> particular,
> > note that my Felix compiler takes 'pull' code, and automatically
> > translates it
> > to the much more efficient 'push' model: ie. it switches the client/server
> > relationship around, a process I call control inversion.
> 
> I'm just curious if you could elaborate on in what respect a push parser is
> "much more efficient"? From my experience pull parsers tend to be easier to
> use because they don't impose an event-driven model on the driver program,
> and also it is trivial to build a push parser on top of a pull parser.
> 
> -Mike
> 
> -------------------
> To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
> Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> 
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] ocaml-3.05: a performance experience

[John Max Skaller]

Mike Lin wrote:

>>I'm intrigued by the relationship between these two parsers. In
>>
> particular,
> 
>>note that my Felix compiler takes 'pull' code, and automatically
>>translates it
>>to the much more efficient 'push' model: ie. it switches the client/server
>>relationship around, a process I call control inversion.
>>
> 
> I'm just curious if you could elaborate on in what respect a push parser is
> "much more efficient"? 


Blocking IO using OS resources is very slow -- O(log N) is good.
User space dispatching is typically very fast: O(1) [using a hashtable]

So if you're parsing XML being read over the internet,
the push technology is superior -- if you can bypass
the high level socket interface (which is non-trivial :-(

>From my experience pull parsers tend to be easier to
> use because they don't impose an event-driven model on the driver program,


	Absolutely! That is why Felix exists. To allow one to
write 'pull' code, which does blocking reads of data, but have the
code translated to 'push' code, where a thread is resumed by a
dispatcher when the data is available.

	For some applications like telephony, where the number
of connections is rather large, event driven code is the ONLY option.
Unix OS are typically incapable of handling millions of threads, a user
space dispatcher has no trouble at all, even on a small Linux PC.
The reason is: client level code 'knows' the encoding of messages
and can sort out where to send it much faster than any generic
OS facilities can: OS schedulers are designed to run arbitrary
mixtures of programs, not millions of threads of the same application.


> and also it is trivial to build a push parser on top of a pull parser.


	Yep. Just write a dispatch loop :-)


-- 
John Max Skaller, mailto:skaller@ozemail.com.au
snail:10/1 Toxteth Rd, Glebe, NSW 2037, Australia.
voice:61-2-9660-0850


-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] ocaml-3.05: a performance experience

[Mike Lin]

> Blocking IO using OS resources is very slow -- O(log N) is good.
> User space dispatching is typically very fast: O(1) [using a hashtable]
> 
> So if you're parsing XML being read over the internet,
> the push technology is superior -- if you can bypass
> the high level socket interface (which is non-trivial :-(

I'm still not sure I understand this. Pull parsers can be structured so
that they don't require blocking I/O. That was the point of all the CPS
stuff in Yaxpo, and what you call "control inversion" (which I'm pretty
sure is also CPS) in Felix.

The controlling system can control the I/O however it wants, but the
interface to the parser still looks like pull.

Do you consider 'select' and 'read' part of the "high level socket
interface" that should be bypassed? (I just want to clarify because
OCaml has even higher level interfaces)

> 	Absolutely! That is why Felix exists. To allow one to
> write 'pull' code, which does blocking reads of data, but have the
> code translated to 'push' code, where a thread is resumed by a
> dispatcher when the data is available.
> 
> 	For some applications like telephony, where the number
> of connections is rather large, event driven code is the ONLY option.
> Unix OS are typically incapable of handling millions of threads, a user
> space dispatcher has no trouble at all, even on a small Linux PC.
> The reason is: client level code 'knows' the encoding of messages
> and can sort out where to send it much faster than any generic
> OS facilities can: OS schedulers are designed to run arbitrary
> mixtures of programs, not millions of threads of the same application.

It would be wise not to eschew the OS scheduler entirely. There are a
number of limitations to this type of purely event-driven model under
heavy load. In particular, it assumes that a "thread" never blocks, but
in fact it may block in many cases that are not under the control of
your scheduler - page faults, garbage collection, and so forth. In such
cases you can squeeze some extra processing time out of the system by
having several OS threads.

If you haven't already, you should have a look at Matt Welsh's work with
SEDA (http://www.cs.berkeley.edu/~mdw/proj/sandstorm/). I'm not sure if
it already does or not, but if it doesn't, it would be very interesting
to have a way to build custom event queue managers into Felix's
scheduler.

-Mike

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] ocaml-3.05: a performance experience

[Noel Welsh]

--- Mike Lin <mikelin@MIT.EDU>, impersonating John Max
Skaller, wrote:
> > I'm intrigued by the relationship between these
> two parsers.

I wonder if this is related to the difference between
lazy and strict evaluation.  It seems that pull code
falls naturally out of a lazy model, and push out of a
strict model.  Given no side effects that
transformation between the two is trivial.  Things get
funky if you allow side effects.  Maybe monads help
here?

Noel

__________________________________________________
Do You Yahoo!?
Yahoo! Health - Feel better, live better
http://health.yahoo.com
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] ocaml-3.05: a performance experience

[Andreas Rossberg]

Noel Welsh wrote:
> 
> > > I'm intrigued by the relationship between these
> > two parsers.
> 
> I wonder if this is related to the difference between
> lazy and strict evaluation.

It is related to implicit data-flow synchronisation via futures (of
which lazy futures are one instance). See:

@article{Halstead:Multilisp,
  author = "Robert Halstead",
  title = "Multilisp: A Language For Concurrent Symbolic Computation",
  journal = "{ACM} Transactions on Programming Languages and Systems",
  volume = 7,
  number = 4,
  pages = "501--538",
  year = 1985,
  month = oct,
}

@inproceedings{Flanagan+Felleisen:SemanticsOfFuture,
    author = "Cormac Flanagan and Matthias Felleisen",
    title = "The Semantics of Future and Its Use in Program
Optimizations",
    booktitle = "22nd {ACM} {SIGPLAN}-{SIGACT} Symposium on Principles
of Programming Languages (POPL'95)",
    address = "San Francisco, California",
    pages = "209--220",
    year = "1995",
    url = "citeseer.nj.nec.com/flanagan95semantics.html"
}

[I believe there is also a more recent journal version of this paper.]

@misc{Niehren+Schwinghammer+Smolka:Futures,
  author = {Joachim Niehren and Jan Schwinghammer and Gert Smolka},
  title = {Concurrent Computation in a Lambda Calculus with Futures},
  institute = {Programming Systems Lab, Universit\"at des Saarlandes},
  year = {2002},
  month = jun,
  note = {Submitted},
  url = "http://www.ps.uni-sb.de/Papers/abstracts/lambdafut.html",
}

-- 
Andreas Rossberg, rossberg@ps.uni-sb.de

"Computer games don't affect kids; I mean if Pac Man affected us
 as kids, we would all be running around in darkened rooms, munching
 magic pills, and listening to repetitive electronic music."
 - Kristian Wilson, Nintendo Inc.
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners