[Caml-list] print_int is too slow

[Caml-list] print_int is too slow

[Diego Olivier Fernandez Pons]

    Team,

I was double checking some OCaml exercises in the France IOI website
(training for the international Olympiads of informatics
http://www.france-ioi.org/)

There is an exercise where my OCaml solution was breaking the time
limit without reason
The issue ended being because print_int seems to be much much slower
than Printf.printf (> 2s for print_int, 0.25s for printf)

The exercise is as follows
A sequence of posters of different lengths L_k are pasted one over the
other (one dimension problem, all starting at the same zero point,
same width, same orientation)
After some time, the program is asked to tell how many posters are still visible

Inputs
- "C %i" means a poster of length x was pasted
- "Q" queries the program for the number of visible posters
Outputs
- number of visible posters after each query

example

input:
12 [number of lines in input]
C 2
Q
C 4
C 2
Q
C 9
Q
C 9
C 2
Q
C 8
Q

output :
1
2
1
2
2

Here is my code

let read_char () = Scanf.scanf " %c " (fun i -> i) in
let read_int () = Scanf.scanf " %i " (fun i -> i) in

let
   length = ref 0 and
   max_queue = ref min_int
in

let rec push v = function
   | [] -> [v]
   | x :: tail when x <= v -> decr length; push v tail (* drop x *)
   | queue -> v :: queue
in

let insert v = function
   | [] | _ when v >= !max_queue ->
      max_queue := v;
      length := 1;
      [v]
   | (x :: _) as queue when v = x -> queue
   | (x :: _) as queue when v < x ->
      incr length;
      v :: queue
   | queue ->
      incr length;
      push v queue
in

let visible = ref [] in

let n = read_int() in
for i = 1 to n do
   match read_char () with
      | 'Q' -> Printf.printf "%i\n" !length
      | 'C' -> visible := insert (read_int()) !visible
      | _ -> failwith "unknown instruction code"
done

If you replace printf by print_int !length; print_newline () the code
is more than 4 times slower.

        Diego Olivier

Re: [Caml-list] print_int is too slow

[Gabriel Scherer]

I have no time for empirical checks right now, but is the problem
really with print_int, or does replacing (print_newline ()) by
(print_string "\n") similarly improves performances? That may very
well be related to when buffering happens.

On Sun, Jun 24, 2012 at 8:40 PM, Diego Olivier Fernandez Pons
<dofp.ocaml@gmail.com> wrote:
>    Team,
>
> I was double checking some OCaml exercises in the France IOI website
> (training for the international Olympiads of informatics
> http://www.france-ioi.org/)
>
> There is an exercise where my OCaml solution was breaking the time
> limit without reason
> The issue ended being because print_int seems to be much much slower
> than Printf.printf (> 2s for print_int, 0.25s for printf)
>
> The exercise is as follows
> A sequence of posters of different lengths L_k are pasted one over the
> other (one dimension problem, all starting at the same zero point,
> same width, same orientation)
> After some time, the program is asked to tell how many posters are still visible
>
> Inputs
> - "C %i" means a poster of length x was pasted
> - "Q" queries the program for the number of visible posters
> Outputs
> - number of visible posters after each query
>
> example
>
> input:
> 12 [number of lines in input]
> C 2
> Q
> C 4
> C 2
> Q
> C 9
> Q
> C 9
> C 2
> Q
> C 8
> Q
>
> output :
> 1
> 2
> 1
> 2
> 2
>
> Here is my code
>
> let read_char () = Scanf.scanf " %c " (fun i -> i) in
> let read_int () = Scanf.scanf " %i " (fun i -> i) in
>
> let
>   length = ref 0 and
>   max_queue = ref min_int
> in
>
> let rec push v = function
>   | [] -> [v]
>   | x :: tail when x <= v -> decr length; push v tail (* drop x *)
>   | queue -> v :: queue
> in
>
> let insert v = function
>   | [] | _ when v >= !max_queue ->
>      max_queue := v;
>      length := 1;
>      [v]
>   | (x :: _) as queue when v = x -> queue
>   | (x :: _) as queue when v < x ->
>      incr length;
>      v :: queue
>   | queue ->
>      incr length;
>      push v queue
> in
>
> let visible = ref [] in
>
> let n = read_int() in
> for i = 1 to n do
>   match read_char () with
>      | 'Q' -> Printf.printf "%i\n" !length
>      | 'C' -> visible := insert (read_int()) !visible
>      | _ -> failwith "unknown instruction code"
> done
>
> If you replace printf by print_int !length; print_newline () the code
> is more than 4 times slower.
>
>        Diego Olivier
>
> --
> Caml-list mailing list.  Subscription management and archives:
> https://sympa-roc.inria.fr/wws/info/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>

Re: [Caml-list] print_int is too slow

[Diego Olivier Fernandez Pons]

    Gabriel,

> I have no time for empirical checks right now, but is the problem
> really with print_int, or does replacing (print_newline ()) by
> (print_string "\n") similarly improves performances? That may very
> well be related to when buffering happens.

You are right, it's print_newline() that is causing the problem

(> 2s) print_int !length; print_newline ()
(0.27s) printf.printf "%i\n" !length
(0.21s) print_int !length; print_string "\n"

I know that is not much of a difference... but it's the IOI training
exercises and time limits are hard.
Besides on this case that difference was larger than what I could gain
with smarter algorithms or better data structure (I tried a dozen
variants)

        Diego Olivier

Re: [Caml-list] print_int is too slow

[Oliver Bandel]

what about

print_string( string_of_int !length ^ "\n")

??




Zitat von "Diego Olivier Fernandez Pons" <dofp.ocaml@gmail.com>:

>     Gabriel,
>
>> I have no time for empirical checks right now, but is the problem
>> really with print_int, or does replacing (print_newline ()) by
>> (print_string "\n") similarly improves performances? That may very
>> well be related to when buffering happens.
>
> You are right, it's print_newline() that is causing the problem
>
> (> 2s) print_int !length; print_newline ()
> (0.27s) printf.printf "%i\n" !length
> (0.21s) print_int !length; print_string "\n"
>
> I know that is not much of a difference... but it's the IOI training
> exercises and time limits are hard.
> Besides on this case that difference was larger than what I could gain
> with smarter algorithms or better data structure (I tried a dozen
> variants)
>
>         Diego Olivier
>
> --
> Caml-list mailing list.  Subscription management and archives:
> https://sympa-roc.inria.fr/wws/info/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>
>

Re: [Caml-list] print_int is too slow

[Diego Olivier Fernandez Pons]

        Oliver

> what about print_string( string_of_int !length ^ "\n")

(> 2s)   print_int !length; print_newline ()
(0.27s) printf.printf "%i\n" !length
(0.22s) print_string (string_of_int !length ^ "\n")
(0.21s) print_int !length; print_string "\n"


        Diego Olivier

Re: [Caml-list] print_int is too slow

[Adrien]

For bigger strings, it could be interesting to use the Buffer module,
and Buffer.output_buffer in particular.
(as usual: benchmark first)

Also, you can change the flushing behaviour iirc (each char, at
newlines, or never flushed automatically).

And also, writing to string (or buffer) and using the Unix module is
probably what would give the most flexibility.

-- 
Adrien Nader

Re: [Caml-list] print_int is too slow

[Diego Olivier Fernandez Pons]

    Christophe,

> The culprit is not with print_int but with “print_newline ()” which
> forces the ouput to be flushed.  As you discovered experimentally,
> doing this often will slow down your output.

During all the years I have been coding, I had never had to worry
about flushing I/O (when / why / how) in any language (C/C++, Java, C#
and OCaml).
I actually had even forgotten those things existed...

        Diego Olivier

Re: [Caml-list] print_int is too slow

[Lukasz Stafiniak]

On Mon, Jun 25, 2012 at 12:19 AM, Diego Olivier Fernandez Pons
<dofp.ocaml@gmail.com> wrote:
>
> During all the years I have been coding, I had never had to worry
> about flushing I/O (when / why / how) in any language (C/C++, Java, C#
> and OCaml).
> I actually had even forgotten those things existed...

You haven't needed to flush output when debugging?

Re: [Caml-list] print_int is too slow

[Anthony Tavener]

[-- Attachment #1: Type: text/plain, Size: 1021 bytes --]

Yeah, this seems surprising. In C I'd often have fflush(stdout); In OCaml I
make use of the %! printf feature. Normally I want output to be buffered,
for efficiency, but I know points where I want to ensure a "sync" so that
I'm not looking at incomplete output. Mind you, I mostly use stdout/stderr
for logging/printf traces...

On Sun, Jun 24, 2012 at 5:06 PM, Lukasz Stafiniak <lukstafi@gmail.com>wrote:

> On Mon, Jun 25, 2012 at 12:19 AM, Diego Olivier Fernandez Pons
> <dofp.ocaml@gmail.com> wrote:
> >
> > During all the years I have been coding, I had never had to worry
> > about flushing I/O (when / why / how) in any language (C/C++, Java, C#
> > and OCaml).
> > I actually had even forgotten those things existed...
>
> You haven't needed to flush output when debugging?
>
> --
> Caml-list mailing list.  Subscription management and archives:
> https://sympa-roc.inria.fr/wws/info/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>
>

[-- Attachment #2: Type: text/html, Size: 1703 bytes --]

Re: [Caml-list] print_int is too slow

[Diego Olivier Fernandez Pons]

    Lukasz,

> You haven't needed to flush output when debugging?

That's called MODERNITY...

This website sits I don't know where in the world, takes my source
code, runs it on data I don't know how it got (random ? predefined and
preloded on a toplevel perpetually up ? read from the web in some XML
file), compares it with a result I don't know how (diffs with existing
flat files ? runs a code known to be correct and compares results ?)
and tells me how my code performed on a testbed, the point where it
started diverging from expected outputs and diffs, while also allowing
me to create my own testbeds. There is also step-by-step execution
(for examples only, hope it will be extended to user code). I also
miss on-hover inspection of variables which I have in other
environments.

On it 17 000 kids I don't know learn programming and algorithms
(mostly in C/C++ but they can choose Caml, Java, Python, etc) and
probably just like me they don't have any compiler installed on their
laptop.

Here is a website I like to program on (http://codepad.org/) as well
as the usual suspects (http://try.ocamlpro.com/,
http://www.tryfsharp.org/).

There is a little trick however... I work mostly in combinatorial
optimization. If your input takes more than 1s to read or write, it
will take the age of the universe to solve given combinatorial
algorithms are exponential in the input size. And there is little
point in putting a printf on a branch-and-bound algorithm that opens
10^6 nodes.


        Diego Olivier

Re: [Caml-list] print_int is too slow

[Goswin von Brederlow]

Diego Olivier Fernandez Pons <dofp.ocaml@gmail.com> writes:

>     Gabriel,
>
>> I have no time for empirical checks right now, but is the problem
>> really with print_int, or does replacing (print_newline ()) by
>> (print_string "\n") similarly improves performances? That may very
>> well be related to when buffering happens.
>
> You are right, it's print_newline() that is causing the problem
>
> (> 2s) print_int !length; print_newline ()
> (0.27s) printf.printf "%i\n" !length
> (0.21s) print_int !length; print_string "\n"
>
> I know that is not much of a difference... but it's the IOI training
> exercises and time limits are hard.
> Besides on this case that difference was larger than what I could gain
> with smarter algorithms or better data structure (I tried a dozen
> variants)
>
>         Diego Olivier

What about printf.printf "%i\n%!" !length? Is that just as slow as
print_newline ()? If so then it truely is just the flushing of buffers.

MfG
        Goswin

Re: [Caml-list] print_int is too slow

[oliver]

On Mon, Jun 25, 2012 at 02:09:47AM +0200, Diego Olivier Fernandez Pons wrote:
[...]
> There is a little trick however... I work mostly in combinatorial
> optimization. If your input takes more than 1s to read or write, it
> will take the age of the universe to solve given combinatorial
> algorithms are exponential in the input size. And there is little
> point in putting a printf on a branch-and-bound algorithm that opens
> 10^6 nodes.
[...]

This looks like you really should use the Buffer-module.

Ciao,
   Oliver

Re: [Caml-list] print_int is too slow

[Gabriel Scherer]

I don't see the point of using Buffer if he does not intend to
postprocess the output; why store the string in full? Just avoid
print_newline() if you don't want buffering, print_string "\n" will be
fine (or Printf.printf without %!, etc.).
Why are we having this conversation?

On Mon, Jun 25, 2012 at 1:39 PM, oliver <oliver@first.in-berlin.de> wrote:
> On Mon, Jun 25, 2012 at 02:09:47AM +0200, Diego Olivier Fernandez Pons wrote:
> [...]
>> There is a little trick however... I work mostly in combinatorial
>> optimization. If your input takes more than 1s to read or write, it
>> will take the age of the universe to solve given combinatorial
>> algorithms are exponential in the input size. And there is little
>> point in putting a printf on a branch-and-bound algorithm that opens
>> 10^6 nodes.
> [...]
>
> This looks like you really should use the Buffer-module.
>
> Ciao,
>   Oliver
>
> --
> Caml-list mailing list.  Subscription management and archives:
> https://sympa-roc.inria.fr/wws/info/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>

Re: [Caml-list] print_int is too slow

[oliver]

On Mon, Jun 25, 2012 at 03:04:56PM +0200, Gabriel Scherer wrote:
> I don't see the point of using Buffer if he does not intend to
> postprocess the output; why store the string in full? Just avoid
> print_newline() if you don't want buffering, print_string "\n" will be
> fine (or Printf.printf without %!, etc.).

I answered on the topic of huge input data.
I doubt that the example which was used here,
with some printng-statements,
will be used all the time.

As it was mentioned, it is some OCaml learning stuff,
and one day it might become more complex and the data read and written
will be more.

Then string-append in the reading part, wihout Buffer module will
become a bottleneck.

> Why are we having this conversation?

Why are you asking this question?


Ciao,
   Oliver

Re: [Caml-list] print_int is too slow

[Florian Weimer]

* Diego Olivier Fernandez Pons:

> During all the years I have been coding, I had never had to worry
> about flushing I/O (when / why / how) in any language (C/C++, Java, C#
> and OCaml).

For decent performance of the standard streams in C++, you have to
decouple them from the C stdio streams, using
std::io_base::sync_with_stdio(false). 8-)