Re: [Caml-list] speeding up matrix multiplication (newbie question)

[Erick Matsen <matsen@berkeley.edu>]

Hello Caml-community--


First of all, big thanks to Will Farr, Mike Lin, Martin Jambon, and Markus
Mottl.

So far, I rewrote things in a non-functional way to avoid unecessary memory
allocation, and then used the float operations directly. This resulted in a 4
fold increase in speed. Second, I moved some of the code to use Bigarrays and
then used the Lacaml BLAS interface. This resulted in another 25% savings. I
didn't have big expectations given Markus' email.

Indeed, he appears to be right:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total
 time   seconds   seconds    calls   s/call   s/call  name
 14.90      9.60     9.60                             caml_ba_offset
 13.82     18.50     8.90 11368070     0.00     0.00  camlFqtree__fun_144
 10.35     25.17     6.67                             caml_ba_get_N
  7.50     30.00     4.83  7456800     0.00     0.00  camlDiagd__fun_309
  7.31     34.71     4.71 456351614     0.00     0.00  caml_copy_double
  6.85     39.12     4.41                             caml_ba_set_aux
  5.84     42.88     3.76 880051135     0.00     0.00  caml_c_call
  4.43     45.73     2.85                             caml_ba_get_1
  3.55     48.02     2.29                             caml_ba_set_1
  1.90     49.24     1.23                             __i686.get_pc_thunk.bx
  1.89     50.47     1.22                             camlVec4_D__of_array_155
  1.87     51.67     1.21                             lacaml_Zlansy_stub_bc
  1.65     52.73     1.06 151152614     0.00     0.00  caml_modify
  1.37     53.61     0.88  9788472     0.00     0.00  caml_adjust_gc_speed
  1.33     54.47     0.86 12992080     0.00     0.00  camlFqtree__calcLikes_87
  0.99     55.11     0.64                             caml_ceil_float
  0.96     55.73     0.62                             lacaml_Dgemv_stub
  0.89     56.30     0.57                             caml_ba_get_2
  0.88     56.88     0.57
camlLacaml_utils__gXmv_get_params_375
  0.80     57.39     0.52                             caml_ba_dim
  0.79     57.90     0.51                             camlLacaml4_D__gemv_227
  0.78     58.41     0.51    46584     0.00     0.00  sweep_slice
  0.76     58.90     0.49  9788472     0.00     0.00  caml_alloc_custom
  0.39     59.15     0.25    43714     0.00     0.00  mark_slice
  0.39     59.40     0.25                             caml_ba_multov

As he suggested would be the case, the code is spending most of its time in the
bigarray stub function responsible for checking bounds and pulling out the
right array element.

I wanted to double check that writing my own implementation in fortran or c
will eliminate such overhead. Or will I still have to do the "fru-fru" he
describes anyway?


Again, thank you all. The improvements have already been quite significant.


Erick


On Fri, Feb 20, 2009 at 2:43 PM, Markus Mottl <markus.mottl@gmail.com> wrote:
> Unless you want to interface C-calls into BLAS/LAPACK directly without
> bounds checking, releasing the OCaml-lock, and other "fru-fru", it
> seems unlikely that you will get much of an advantage using those
> libraries given the small size of your matrices.  E.g. Lacaml is
> optimized for larger matrices (probably > 10x10).
>
> I guess you should be fine rolling your own implementation for such
> small matrices.
>
> Regards,
> Markus
>
> --
> Markus Mottl        http://www.ocaml.info        markus.mottl@gmail.com
>
> _______________________________________________
> 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
>