Loading ...
Sorry, an error occurred while loading the content.

interpolation with ints

Expand Messages
  • Florent Monnier
    Hi, Usually interpolations for mutlimedia programming are done with floats, but I m trying to make it with ints in order to make it deterministic and also it s
    Message 1 of 4 , Jun 3, 2013
    • 0 Attachment
      Hi,

      Usually interpolations for mutlimedia programming are done with
      floats, but I'm trying to make it with ints in order to make it
      deterministic and also it's maybe faster for the RPi.

      So I'm trying to see how I could avoid the calculus that are done several times.
      Either with partial application, creating a closure, or even keeping
      the intermediate calculus (v_diff, t_diff) the stress test shows that
      the simplest (naive?) one is the fastest.

      Is there a way to optimise this?

      $ cat interpolint.mli
      (** Interpolation with ints *)

      val inter :
      t1:int -> t2:int ->
      v1:int -> v2:int -> int -> int
      (** simple interpolation *)

      type inter_func = int -> int

      val interp :
      t1:int -> t2:int ->
      v1:int -> v2:int -> inter_func
      (** interpolation with partial application *)

      type inter_value

      val interv :
      t1:int -> t2:int ->
      v1:int -> v2:int -> inter_value

      val intervf : inter_value -> int -> int
      (** interpolation with intermediate calculus done *)

      $ cat interpolint.ml

      let inter ~t1 ~t2 ~v1 ~v2 t =
      ((v2 - v1) * (t - t1)) / (t2 - t1) + v1

      type inter_func = int -> int

      let interp ~t1 ~t2 ~v1 ~v2 =
      let v_diff = (v2 - v1)
      and t_diff = (t2 - t1) in
      function t ->
      (v_diff * (t - t1)) / t_diff + v1

      type inter_value = int * int * int * int

      let interv ~t1 ~t2 ~v1 ~v2 =
      let v_diff = (v2 - v1)
      and t_diff = (t2 - t1) in
      (t1, v1, v_diff, t_diff)

      let intervf (t1, v1, v_diff, t_diff) t =
      (v_diff * (t - t1)) / t_diff + v1

      $ cat stress.ml
      open Interpolint

      let timeit n f s =
      let t0 = Unix.gettimeofday () in
      for i = 1 to n do f () done;
      let t1 = Unix.gettimeofday () in
      Printf.printf "time(%s): %f\n%!" s (t1 -. t0)

      let stress0 () =
      for t = 1000 to 1200 do
      let _ = inter ~t1:1000 ~t2:1200 ~v1:2 ~v2:8 t in
      ()
      done

      let stress1 () =
      let f = inter ~t1:1000 ~t2:1200 ~v1:2 ~v2:8 in
      for t = 1000 to 1200 do
      let _ = f t in
      ()
      done

      let stress2 () =
      let fi = interp ~t1:1000 ~t2:1200 ~v1:2 ~v2:8 in
      for t = 1000 to 1200 do
      let _ = fi t in
      ()
      done

      let stress3 () =
      let v = interv ~t1:1000 ~t2:1200 ~v1:2 ~v2:8 in
      for t = 1000 to 1200 do
      let _ = intervf v t in
      ()
      done

      let () =
      timeit 100_000 stress0 "stress0";
      timeit 100_000 stress1 "stress1";
      timeit 100_000 stress2 "stress2";
      timeit 100_000 stress3 "stress3";
      ;;

      $ ./stress.opt
      time(stress0): 0.267789
      time(stress1): 0.320826
      time(stress2): 0.287542
      time(stress3): 0.287472

      --
    • Gabriel Scherer
      You could take as parameters ~t1 ~tdiff ~v1 ~vdiff but I don t think this will make a big difference (this purely-integer calculus is very fast already). Does
      Message 2 of 4 , Jun 3, 2013
      • 0 Attachment
        You could take as parameters
        ~t1 ~tdiff ~v1 ~vdiff
        but I don't think this will make a big difference (this purely-integer
        calculus is very fast already).

        Does this particular function already show high in your profile?


        On Mon, Jun 3, 2013 at 9:57 PM, Florent Monnier
        <fmonnier@...> wrote:
        > Hi,
        >
        > Usually interpolations for mutlimedia programming are done with
        > floats, but I'm trying to make it with ints in order to make it
        > deterministic and also it's maybe faster for the RPi.
        >
        > So I'm trying to see how I could avoid the calculus that are done several times.
        > Either with partial application, creating a closure, or even keeping
        > the intermediate calculus (v_diff, t_diff) the stress test shows that
        > the simplest (naive?) one is the fastest.
        >
        > Is there a way to optimise this?
        >
        > $ cat interpolint.mli
        > (** Interpolation with ints *)
        >
        > val inter :
        > t1:int -> t2:int ->
        > v1:int -> v2:int -> int -> int
        > (** simple interpolation *)
        >
        > type inter_func = int -> int
        >
        > val interp :
        > t1:int -> t2:int ->
        > v1:int -> v2:int -> inter_func
        > (** interpolation with partial application *)
        >
        > type inter_value
        >
        > val interv :
        > t1:int -> t2:int ->
        > v1:int -> v2:int -> inter_value
        >
        > val intervf : inter_value -> int -> int
        > (** interpolation with intermediate calculus done *)
        >
        > $ cat interpolint.ml
        >
        > let inter ~t1 ~t2 ~v1 ~v2 t =
        > ((v2 - v1) * (t - t1)) / (t2 - t1) + v1
        >
        > type inter_func = int -> int
        >
        > let interp ~t1 ~t2 ~v1 ~v2 =
        > let v_diff = (v2 - v1)
        > and t_diff = (t2 - t1) in
        > function t ->
        > (v_diff * (t - t1)) / t_diff + v1
        >
        > type inter_value = int * int * int * int
        >
        > let interv ~t1 ~t2 ~v1 ~v2 =
        > let v_diff = (v2 - v1)
        > and t_diff = (t2 - t1) in
        > (t1, v1, v_diff, t_diff)
        >
        > let intervf (t1, v1, v_diff, t_diff) t =
        > (v_diff * (t - t1)) / t_diff + v1
        >
        > $ cat stress.ml
        > open Interpolint
        >
        > let timeit n f s =
        > let t0 = Unix.gettimeofday () in
        > for i = 1 to n do f () done;
        > let t1 = Unix.gettimeofday () in
        > Printf.printf "time(%s): %f\n%!" s (t1 -. t0)
        >
        > let stress0 () =
        > for t = 1000 to 1200 do
        > let _ = inter ~t1:1000 ~t2:1200 ~v1:2 ~v2:8 t in
        > ()
        > done
        >
        > let stress1 () =
        > let f = inter ~t1:1000 ~t2:1200 ~v1:2 ~v2:8 in
        > for t = 1000 to 1200 do
        > let _ = f t in
        > ()
        > done
        >
        > let stress2 () =
        > let fi = interp ~t1:1000 ~t2:1200 ~v1:2 ~v2:8 in
        > for t = 1000 to 1200 do
        > let _ = fi t in
        > ()
        > done
        >
        > let stress3 () =
        > let v = interv ~t1:1000 ~t2:1200 ~v1:2 ~v2:8 in
        > for t = 1000 to 1200 do
        > let _ = intervf v t in
        > ()
        > done
        >
        > let () =
        > timeit 100_000 stress0 "stress0";
        > timeit 100_000 stress1 "stress1";
        > timeit 100_000 stress2 "stress2";
        > timeit 100_000 stress3 "stress3";
        > ;;
        >
        > $ ./stress.opt
        > time(stress0): 0.267789
        > time(stress1): 0.320826
        > time(stress2): 0.287542
        > time(stress3): 0.287472
        >
        > --
        >
        >
        > ------------------------------------
        >
        > Archives up to December 31, 2011 are also downloadable at http://www.connettivo.net/cntprojects/ocaml_beginners
        > The archives of the very official ocaml list (the seniors' one) can be found at http://caml.inria.fr
        > Attachments are banned and you're asked to be polite, avoid flames etc.Yahoo! Groups Links
        >
        >
        >
      • Florent Monnier
        ... Not really. with (((v2 - v1) * (t - t1)) / (t2 - t1) + v1) there are 6 operations, but 4 would be enough ((v_diff * (t - t1)) / t_diff + v1) so I thought I
        Message 3 of 4 , Jun 4, 2013
        • 0 Attachment
          2013/06/04, Gabriel Scherer wrote:
          > You could take as parameters
          > ~t1 ~tdiff ~v1 ~vdiff
          > but I don't think this will make a big difference (this purely-integer
          > calculus is very fast already).
          >
          > Does this particular function already show high in your profile?

          Not really.
          with (((v2 - v1) * (t - t1)) / (t2 - t1) + v1) there are 6 operations,
          but 4 would be enough ((v_diff * (t - t1)) / t_diff + v1)
          so I thought I could easily save a little there without making the
          code too much complex.

          Also I noticed that replacing /. 2.0 by *. 0.5 saves by twice. This
          simple trick makes save a lot on my desktop computer, but there's not
          that much difference there on the RPi.


          $ cat >> interpolint.ml

          let interg ~t1 ~t2 ~v1 ~v2 =
          let v_diff = (v2 - v1)
          and t_diff = (t2 - t1) in
          (v_diff, t_diff)

          let intervg ~t1 ~t_diff ~v1 ~v_diff t =
          (v_diff * (t - t1)) / t_diff + v1

          $ cat >> interpolint.mli

          val interg :
          t1:int -> t2:int ->
          v1:int -> v2:int -> int * int

          val intervg :
          t1:int -> t_diff:int ->
          v1:int -> v_diff:int -> int -> int
          (** interpolation with intermediate calculus done,
          not given as tuple *)

          $ cat >> stress.ml

          let stress4 () =
          let t1, t2, v1, v2 = (1000, 1200, 2, 8) in
          let v_diff, t_diff = interg ~t1 ~t2 ~v1 ~v2 in
          for t = 1000 to 1200 do
          let _ = intervg
          ~t1 ~t_diff
          ~v1 ~v_diff t
          in
          ()
          done

          $ ./stress.opt
          time(stress0): 0.267789
          time(stress1): 0.320826
          time(stress2): 0.287542
          time(stress3): 0.287472
          time(stress4): 0.293996

          --
        • Gabriel Scherer
          I wrote the following program: let stress6 () = let t1 = 1000 and t2 = 1200 and v1 = 2 and v2 = 8 in let tdiff = t2 - t1 and vdiff = v2 - v1 in let acc = ref
          Message 4 of 4 , Jun 5, 2013
          • 0 Attachment
            I wrote the following program:

            let stress6 () =
            let t1 = 1000 and t2 = 1200 and v1 = 2 and v2 = 8 in
            let tdiff = t2 - t1 and vdiff = v2 - v1 in
            let acc = ref (v1 * tdiff) in
            for t = t1 to t2 do
            let _ = !acc / tdiff in
            acc := !acc + vdiff;
            done

            The time is the same as with stress0, because the compiler is too
            clever here: it inlines everything, then does constant propagation,
            and eg. the (/ tdiff) division becomes (/ 200) (for all the
            implementations except f1 that was probably judged too complex to be
            inlining, and that therefore pays a Division_by_zero check that the
            other avoid).

            You should try to measure the results with non-constant values (eg.
            (int_of_string Sys.argv.(k)).

            On Tue, Jun 4, 2013 at 11:25 PM, Florent Monnier
            <fmonnier@...> wrote:
            > 2013/06/04, Gabriel Scherer wrote:
            >> You could take as parameters
            >> ~t1 ~tdiff ~v1 ~vdiff
            >> but I don't think this will make a big difference (this purely-integer
            >> calculus is very fast already).
            >>
            >> Does this particular function already show high in your profile?
            >
            > Not really.
            > with (((v2 - v1) * (t - t1)) / (t2 - t1) + v1) there are 6 operations,
            > but 4 would be enough ((v_diff * (t - t1)) / t_diff + v1)
            > so I thought I could easily save a little there without making the
            > code too much complex.
            >
            > Also I noticed that replacing /. 2.0 by *. 0.5 saves by twice. This
            > simple trick makes save a lot on my desktop computer, but there's not
            > that much difference there on the RPi.
            >
            >
            > $ cat >> interpolint.ml
            >
            > let interg ~t1 ~t2 ~v1 ~v2 =
            > let v_diff = (v2 - v1)
            > and t_diff = (t2 - t1) in
            > (v_diff, t_diff)
            >
            > let intervg ~t1 ~t_diff ~v1 ~v_diff t =
            > (v_diff * (t - t1)) / t_diff + v1
            >
            > $ cat >> interpolint.mli
            >
            > val interg :
            > t1:int -> t2:int ->
            > v1:int -> v2:int -> int * int
            >
            > val intervg :
            > t1:int -> t_diff:int ->
            > v1:int -> v_diff:int -> int -> int
            > (** interpolation with intermediate calculus done,
            > not given as tuple *)
            >
            > $ cat >> stress.ml
            >
            > let stress4 () =
            > let t1, t2, v1, v2 = (1000, 1200, 2, 8) in
            > let v_diff, t_diff = interg ~t1 ~t2 ~v1 ~v2 in
            > for t = 1000 to 1200 do
            > let _ = intervg
            > ~t1 ~t_diff
            > ~v1 ~v_diff t
            > in
            > ()
            > done
            >
            > $ ./stress.opt
            > time(stress0): 0.267789
            > time(stress1): 0.320826
            > time(stress2): 0.287542
            > time(stress3): 0.287472
            > time(stress4): 0.293996
            >
            > --
            >
            >
            > ------------------------------------
            >
            > Archives up to December 31, 2011 are also downloadable at http://www.connettivo.net/cntprojects/ocaml_beginners
            > The archives of the very official ocaml list (the seniors' one) can be found at http://caml.inria.fr
            > Attachments are banned and you're asked to be polite, avoid flames etc.Yahoo! Groups Links
            >
            >
            >
          Your message has been successfully submitted and would be delivered to recipients shortly.