Now it's faster (addendum to "Performance-question")

Now it's faster (addendum to "Performance-question")

[Oliver Bandel]

Hello,

only to complete the thread...

...I have switched from one suspicious
function that uses lists to one that uses Maps,
but this was not brininging much speed-up.
So my list-based implementation seems to be not that bad.

Then I switched from a string appending function
that uses "^" to the Buffer-module, because I remembered
that it helped my in other programs also to speed up.

I have now about 1/3 less running time for the tool,
and I have not all occurences of the "^" using function
weeped out. So this will bring even more speedup,
when making theses changes complete. :-)

But the general behavour that in the middle of the run
there is a slow-down did not go away so far. gprof also
shows similar percentage values. But possibly the remaining
"^"-applications stops somewhere and somehow, when some very long
strings are concatenated? I will see, when throwing out that stuff
completely.

Ciao,
   Oliver

Re: [Caml-list] Now it's faster (addendum to "Performance-question")

[Oliver Bandel]

Hello,

I should have changed the Subject to: "Shocking Performance!!!"

but then possibly the spam-filter would become active ;-)


The performance dramatically increased now!

I first had about 3min34  on my dataset.
After throwing out some of the "^"-using
functions, the time was about 1min55.

Now, after I threw out the rest of that "^"-stuff
(which btw. made more of the catanations then
the first thrown out functions, but was not called
as often as trhe other functions) I'm under 20 seconds!
(17..18 seconds!)

That's amazing! :-)

Especially, because my dataset is about 300 times bigger
than the normal data which the tool will see, I think,
it's nice now :-)


   ......aaaaaaaaand the winneeeeer iiiiis:   OCaml !!!   :-)

Yes, that's coooooool! :)


Hurray, party :-)


Ciao,
  Oliver

Re: [Caml-list] Now it's faster (addendum to "Performance-question")

[Vincent Hanquez]

On Wed, Feb 06, 2008 at 12:55:04PM +0100, Oliver Bandel wrote:
> Hello,
> 
> I should have changed the Subject to: "Shocking Performance!!!"
> 
> but then possibly the spam-filter would become active ;-)
> 
> 
> The performance dramatically increased now!
> 
> I first had about 3min34  on my dataset.
> After throwing out some of the "^"-using
> functions, the time was about 1min55.
> 
> Now, after I threw out the rest of that "^"-stuff
> (which btw. made more of the catanations then
> the first thrown out functions, but was not called
> as often as trhe other functions) I'm under 20 seconds!
> (17..18 seconds!)
> 
> That's amazing! :-)


well i'm pretty sure you could go down even further with your own
implementation of a buffer library.

the buffer library is actually pretty bad since it's actually just a
simple string. each time the buffer need to grow, the string is
reallocated and the previous one is copied to the new string.
and you got the 16mb limit (max_string_length) on 32bit.

if you implement a growing array of fixed sized string (4K for example),
you just don't need to copy data each time your buffer need to grow. I
suspect it might be even faster than the normal buffer in your case
(lots of data appending), but depends on what you do with your buffer
afterwards.

-- 
Vincent Hanquez

Re: [Caml-list] Now it's faster (addendum to "Performance-question")

[David Teller]

A possible improvement of the buffer library (along with a ropes
library) may be a good future subject for OSR. Well, once we have
answered the already-asked questions, of course.

Cheers,
 David

On Wed, 2008-02-06 at 13:04 +0100, Vincent Hanquez wrote:
> well i'm pretty sure you could go down even further with your own
> implementation of a buffer library.
> 
> the buffer library is actually pretty bad since it's actually just a
> simple string. each time the buffer need to grow, the string is
> reallocated and the previous one is copied to the new string.
> and you got the 16mb limit (max_string_length) on 32bit.
> 
> if you implement a growing array of fixed sized string (4K for example),
> you just don't need to copy data each time your buffer need to grow. I
> suspect it might be even faster than the normal buffer in your case
> (lots of data appending), but depends on what you do with your buffer
> afterwards.
> 
-- 
David Teller
 Security of Distributed Systems
  http://www.univ-orleans.fr/lifo/Members/David.Teller
 Angry researcher: French Universities need reforms, but the LRU act brings liquidations. 

Re: [Caml-list] Now it's faster (addendum to "Performance-question")

[Oliver Bandel]

Well,


I didn't say the buffer library is slow.
I said, it's much faster than using "^".

For not-that-intensive string-concat's,
2^" is fast enough, but when you do often
concat strings, then buffer-module is
faster.

Do you mean the buffer module should be made better or do you think,
the "^" operator should be implemented differently?
If Buffer-module might be even faster, when it's changed,
that's fine, but IMHO it's quite fast.

Ciao,
   Oliver

Zitat von David Teller <David.Teller@univ-orleans.fr>:

> A possible improvement of the buffer library (along with a ropes
> library) may be a good future subject for OSR. Well, once we have
> answered the already-asked questions, of course.
>
> Cheers,
>  David
>
> On Wed, 2008-02-06 at 13:04 +0100, Vincent Hanquez wrote:
> > well i'm pretty sure you could go down even further with your own
> > implementation of a buffer library.
> >
> > the buffer library is actually pretty bad since it's actually just
> a
> > simple string. each time the buffer need to grow, the string is
> > reallocated and the previous one is copied to the new string.
> > and you got the 16mb limit (max_string_length) on 32bit.
> >
> > if you implement a growing array of fixed sized string (4K for
> example),
> > you just don't need to copy data each time your buffer need to
> grow. I
> > suspect it might be even faster than the normal buffer in your case
> > (lots of data appending), but depends on what you do with your
> buffer
> > afterwards.
> >
> --
> David Teller
>  Security of Distributed Systems
>   http://www.univ-orleans.fr/lifo/Members/David.Teller
>  Angry researcher: French Universities need reforms, but the LRU act
> brings liquidations.
>
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>

Re: [Caml-list] Now it's faster (addendum to "Performance-question")

[David Teller]

I was answering Vincent Hanquez who seemed to have ideas wrt Buffer.

Cheers,
 David

On Sat, 2008-02-09 at 11:03 +0100, Oliver Bandel wrote:
> Do you mean the buffer module should be made better or do you think,
> the "^" operator should be implemented differently?
> If Buffer-module might be even faster, when it's changed,
> that's fine, but IMHO it's quite fast.

-- 
David Teller
 Security of Distributed Systems
  http://www.univ-orleans.fr/lifo/Members/David.Teller
 Angry researcher: French Universities need reforms, but the LRU act
brings liquidations. 

Re: [Caml-list] Now it's faster (addendum to "Performance-question")

[Oliver Bandel]

Hello Vincent,

Zitat von Vincent Hanquez <tab@snarc.org>:

> On Wed, Feb 06, 2008 at 12:55:04PM +0100, Oliver Bandel wrote:
> > Hello,
> >
> > I should have changed the Subject to: "Shocking Performance!!!"
> >
> > but then possibly the spam-filter would become active ;-)
> >
> >
> > The performance dramatically increased now!
> >
> > I first had about 3min34  on my dataset.
> > After throwing out some of the "^"-using
> > functions, the time was about 1min55.
> >
> > Now, after I threw out the rest of that "^"-stuff
> > (which btw. made more of the catanations then
> > the first thrown out functions, but was not called
> > as often as trhe other functions) I'm under 20 seconds!
> > (17..18 seconds!)
> >
> > That's amazing! :-)
>
>
> well i'm pretty sure you could go down even further with your own
> implementation of a buffer library.
[...]

Possibly, but I have no reason to start such an implementation,
if the current possibilities are fast enough.
IMHO optimization comes at the end. When things are working
well and fast enough, optimization is wasted time.
If the software needs optimization, it can be done then.

This is from a practical perspective.
The academic perspective might be different.
And when I have some time to do it, I may
change the datastructures again, to be faster and cleaner.
But that would be not really necessary for the program that
was the reason to ask here. It would be fine to do it better,
but also can be used as it is now.


>
> the buffer library is actually pretty bad since it's actually just a
> simple string.

IMHO it's differently, but I didn't looked at the code.


> each time the buffer need to grow, the string is
> reallocated and the previous one is copied to the new string.

Are you talking about Buffer-module or the "^"-operator?

> and you got the 16mb limit (max_string_length) on 32bit.

For me that limit would be ok.
The strings I use are not that big, but bigger than expected.
And there are a lot of strings that I concat'ed.
I think because of that there was so much allocation/deallocation
work to do.
With Buffer-module it was much faster.
And even the current implementation could be done more efficient,
because I use Buffer.create() locally. I could use it module-global
and use Buffer.clear() or Buffer.reset().
But when performance is not an nissue, I chose for the cleaner way,
which means: not even module global stuff, if possible.

In a library the decision would be differently.




>
> if you implement a growing array of fixed sized string (4K for
> example),
> you just don't need to copy data each time your buffer need to grow.
> I
> suspect it might be even faster than the normal buffer in your case
> (lots of data appending), but depends on what you do with your buffer
> afterwards.

I only do use that string to write it to a dbm-database.
I need a certain layout of the strings, because more
than one data-item must be stored for each key.
It's not a complicated format, but the strings must be concated.
I did this with "^" first, because I didn't expected
that the string-stuff needs that much time. I thought my
mathematical operations (statistical things) need most time,
but my expectation was wrong. The calculations were done very fast.
So using Bufeer-module instead of "^" for the concat's
did bring a good performance boost.

Ciao,
   Oliver

P.S.:

===============================================
# Sys.max_string_length;;
- : int = 144115188075855863
#
===============================================

Re: [Caml-list] Now it's faster (addendum to "Performance-question")

[Vincent Hanquez]

On Sat, Feb 09, 2008 at 11:18:11AM +0100, Oliver Bandel wrote:
> Possibly, but I have no reason to start such an implementation,
> if the current possibilities are fast enough.
> IMHO optimization comes at the end. When things are working
> well and fast enough, optimization is wasted time.
> If the software needs optimization, it can be done then.

i though that's what you were doing ;)

> This is from a practical perspective.
> The academic perspective might be different.

i was talking on pratical perspective. i don't care about academic
research. i seen pratical problem with the 16mb limit, and also breaking
the 16mb limit means you have a faster implementation. i'ld though i
mentions it, but obviously the buffer is good enough on some usage.

> > the buffer library is actually pretty bad since it's actually just a
> > simple string.
> 
> IMHO it's differently, but I didn't looked at the code.

well i've looked at the code, and it's a string ;)
 
> > each time the buffer need to grow, the string is
> > reallocated and the previous one is copied to the new string.
> 
> Are you talking about Buffer-module or the "^"-operator?

Buffer module.

> I only do use that string to write it to a dbm-database.
> I need a certain layout of the strings, because more
> than one data-item must be stored for each key.
> It's not a complicated format, but the strings must be concated.
> I did this with "^" first, because I didn't expected
> that the string-stuff needs that much time. I thought my
> mathematical operations (statistical things) need most time,
> but my expectation was wrong. The calculations were done very fast.
> So using Bufeer-module instead of "^" for the concat's
> did bring a good performance boost.

I wasn't saying the contrary; string concatenation is really really bad
for appending obviously, since 1 string is reallocated and 2 are blitted
into this new string. obviously the buffer is much faster, because the
re-allocation doesn't happens everytimes. But the reallocation can be
avoided in another implementation, making thing even faster, depend on the
usage you have with your data.

> P.S.:
> 
> ===============================================
> # Sys.max_string_length;;
> - : int = 144115188075855863
> #
> ===============================================

you're running a 64bit version, so obviously you don't have the 16mb
limit.


-- 
Vincent Hanquez

Re: [Caml-list] Now it's faster (addendum to "Performance-question")

[Jean-Christophe Filliâtre]

Vincent Hanquez wrote:
> the buffer library is actually pretty bad since it's actually just a
> simple string. each time the buffer need to grow, the string is
> reallocated and the previous one is copied to the new string.
> and you got the 16mb limit (max_string_length) on 32bit.

Just for fun, I wrote a ropes-based implementation of Buffer. The
interface is exactly the same. Differences between the two
implementations are the following:

 - Contrary to ocaml's standard library, a buffer size is not limited to
      [Sys.max_string_length], but to [max_int] (sizes are represented
      internally using native ocaml integers).

 - [contents] and [sub] raise [Invalid_argument] if the resulting string
      would be larger than [Sys.max_string_length] bytes.

 - The meaning of [create]'s argument is not exactly the same,
    though its value only affects performances, as for [Buffer];
    see below.

 - An additional function [print] is provided.

The code is here:

	http://www.lri.fr/~filliatr/ftp/ocaml/ds/rbuffer.mli
	http://www.lri.fr/~filliatr/ftp/ocaml/ds/rbuffer.ml

For general-purpose ropes, see

	http://www.lri.fr/~filliatr/software.en.html

-- 
Jean-Christophe

Re: [Caml-list] Now it's faster (addendum to "Performance-question")

[Vincent Hanquez]

On Mon, Feb 11, 2008 at 11:01:37AM +0100, Jean-Christophe Filliâtre wrote:
> Just for fun, I wrote a ropes-based implementation of Buffer. The
> interface is exactly the same. Differences between the two
> implementations are the following:
> 
>  - Contrary to ocaml's standard library, a buffer size is not limited to
>       [Sys.max_string_length], but to [max_int] (sizes are represented
>       internally using native ocaml integers).
> 
>  - [contents] and [sub] raise [Invalid_argument] if the resulting string
>       would be larger than [Sys.max_string_length] bytes.
> 
>  - The meaning of [create]'s argument is not exactly the same,
>     though its value only affects performances, as for [Buffer];
>     see below.
> 
>  - An additional function [print] is provided.

that's nice. how's the performance compare to plain buffer ?

one nit, keeping compatibility is good, however, the contents function
is quite evil (runtime failure), and removing it would be nice as well.
people should use other thing to "iterate" over the contents (even if
contents is quite practical)

Cheers,
-- 
Vincent Hanquez

Re: [Caml-list] Now it's faster (addendum to "Performance-question")

[Jean-Christophe Filliâtre]

Vincent Hanquez wrote:
> On Mon, Feb 11, 2008 at 11:01:37AM +0100, Jean-Christophe Filliâtre wrote:
>> Just for fun, I wrote a ropes-based implementation of Buffer. The
>> interface is exactly the same. Differences between the two
>> implementations are the following:
> 
> that's nice. how's the performance compare to plain buffer ?

I made few tests, but performance since to be roughly the same. But
there is a caveat: when creating a buffer, the value passed to create
does not have the same meaning as in Buffer, and may result in bad
performances if it is too small.

With Buffer, it will be doubled until the buffer is large enough,
involving a few string copies.

With Rbuffer, the value passed to create is the size of each chunk in
the rope (roughly), so passing a value such as 10 and then appending
millions of characters will result in a lot of allocations for rope
nodes, and will make Rbuffer less efficient than Buffer. But if you pass
a value large enough, i.e. of the same order of magnitude as the size of
the final buffer, then it should be as efficient as Buffer.

> one nit, keeping compatibility is good, however, the contents function
> is quite evil (runtime failure), and removing it would be nice as well.

I agree that a failure of "contents" can be surprising, but I don't like
the idea of removing it at all (in particular because you may want to be
able to substitute Rbuffer for Buffer in yours programs to compare
efficiencies).

> people should use other thing to "iterate" over the contents (even if
> contents is quite practical)

do you mean something like "iter : t -> (char -> unit) -> unit"?

(It could be implemented more efficiently than a repeated use of "nth")

-- 
Jean-Christophe Filliâtre
http://www.lri.fr/~filliatr/

Re: [Caml-list] Now it's faster (addendum to "Performance-question")

[Vincent Hanquez]

On Mon, Feb 11, 2008 at 03:34:34PM +0100, Jean-Christophe Filliâtre wrote:
> With Rbuffer, the value passed to create is the size of each chunk in
> the rope (roughly), so passing a value such as 10 and then appending
> millions of characters will result in a lot of allocations for rope
> nodes, and will make Rbuffer less efficient than Buffer. But if you pass
> a value large enough, i.e. of the same order of magnitude as the size of
> the final buffer, then it should be as efficient as Buffer.

maybe in this case you should add a minimum limit, so that people
doesn't create rbuffer with 10 or something.

just a simple:
let create sz =
	let sz = max sz my_rbuffer_limit in

> > one nit, keeping compatibility is good, however, the contents function
> > is quite evil (runtime failure), and removing it would be nice as well.
> 
> I agree that a failure of "contents" can be surprising, but I don't like
> the idea of removing it at all (in particular because you may want to be
> able to substitute Rbuffer for Buffer in yours programs to compare
> efficiencies).

I don't really like removing it either, but people need to know that
contents (as in Rbuffer.t -> string) could be evil.

> > people should use other thing to "iterate" over the contents (even if
> > contents is quite practical)
> 
> do you mean something like "iter : t -> (char -> unit) -> unit"?
> 
> (It could be implemented more efficiently than a repeated use of "nth")

iterate in a broad sense; beeing able to do something with what's inside
the buffer.  it could be a list of string, chunks, char, etc ...

-- 
Vincent Hanquez