- 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

-- - 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

>

>

> - 2013/06/04, Gabriel Scherer wrote:
> You could take as parameters

Not really.

> ~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?

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

-- - 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

>

>

>