The solution
| That's what C is for, right? |  |
John Melesky (Open Source Bridge, June 2009)
def matrix_mul(a,b)
rows = (0 .. a.size - 1).collect {
|i|
(0 .. b[0].size - 1).collect {
|j|
vij = 0
0.upto(a[i].size - 1) do
|k|
vij += a[i][k] * b[k][j]
end
vij
}
}
return rows
end
(adapted from matrix.rb)
| That's what C is for, right? | |
C is a systems language, intended for use with 30-year-old kernels and drivers, on processors with fewer than 10k transistors (we're currently in the billion-transistor range, thankyouverymuch Moore's Law).
C is a systems language, intended for use with 30-year-old kernels and drivers, on processors with fewer than 10k transistors (we're currently in the billion-transistor range, thankyouverymuch Moore's Law).
In other words, it's fast only as a side effect.
For raw numerics, Fortran still has C beat. APL is pretty dang fast, too.
For complex datatypes, languages like Haskell or ML will all give you better type support, safer usage, and possibly faster code.
Really, almost any language offers benefits over C, whether it's faster, safer, more concise, more advanced, or all of the above.
The only constraint is that your target language needs an FFI (Foreign Function Interface) that allows C to call it. Most awesome languages allow this. I'm going to use Ocaml.
The other material requirements are your language header files (ruby.h, caml/callback.h, etc.), and perserverence.
The only constraint is that your target language needs an FFI (Foreign Function Interface) that allows C to call it. Most awesome languages allow this. I'm going to use Ocaml.
The other material requirements are your language header files (ruby.h, caml/callback.h, etc.), and perserverence.
(You may look warily upon the whole "allows C to call it" thing. This is understandable. Things will get worse before they get better.)
In brief, it's a statically- and strongly- typed, non-pure, strict, functional programming language. It's from the ML family (which includes SML, F#, and some others).
Ocaml's pretty cool at the moment, because it's one of the fastest languages around, routinely rivalling C++ in the Shootout.
let matrix_mul a b =
List.map
(fun row ->
mapn
(fun column ->
List.fold_left (+) 0
(List.map2 ( * ) row column))
b)
a
(cribbed from RosettaCode)
let matrix_mul a b =
List.map
(fun row ->
mapn
(fun column ->
List.fold_left (+) 0
(List.map2 ( * ) row column))
b)
a
We've acheived a 10x speedup, and our code is not actually much more complicated than the Ruby.
This code uses Lists, which are pretty natural to use in functional languages. Arrays would probably be faster, though.
let matrix_mul x y =
let x0 = Array.length x
and y0 = Array.length y in
let y1 = if y0 = 0 then 0 else Array.length y.(0) in
let z = Array.make_matrix x0 y1 0 in
for i = 0 to x0-1 do
for j = 0 to y1-1 do
for k = 0 to y0-1 do
z.(i).(j) <- z.(i).(j) + x.(i).(k) * y.(k).(j)
done
done
done;
z
(also cribbed from RosettaCode)
let matrix_mul x y =
let x0 = Array.length x
and y0 = Array.length y in
let y1 = if y0 = 0 then 0 else Array.length y.(0) in
let z = Array.make_matrix x0 y1 0 in
for i = 0 to x0-1 do
for j = 0 to y1-1 do
for k = 0 to y0-1 do
z.(i).(j) <- z.(i).(j) + x.(i).(k) * y.(k).(j)
done
done
done;
z
Ocaml Arrays are pretty darn fast, and have a great initialization function tailored to this sort of problem (make_matrix).
We've now managed a speedup around 30-35x. And, again, the code is not that much more complex than the original Ruby.
Of course, the Ocaml code is operating on Ocaml types, and Ruby wants to pass it Ruby types. What to do, what to do?
Ruby can call C code...
Ruby can call C code...
Ocaml can be called by C code...
Ruby can call C code...
Ocaml can be called by C code...
They both have facilities to translate their types into C types (and Ocaml vice-versa)...
Many languages provide C type definitions and functions for extensions. There are two problems with this.
Let's work our way out, from Ocaml to Ruby, via C. First, we need to tell Ocaml to export a function to C.
let matrix_mul x y =
let x0 = Array.length x
and y0 = Array.length y in
let y1 = if y0 = 0 then 0 else Array.length y.(0) in
let z = Array.make_matrix x0 y1 0 in
for i = 0 to x0-1 do
for j = 0 to y1-1 do
for k = 0 to y0-1 do
z.(i).(j) <- z.(i).(j) + x.(i).(k) * y.(k).(j)
done
done
done;
z
let _ = Callback.register "ocaml_matrix_mul" matrix_mul;;
Next, we need some C code to call the Ocaml.
#include "caml/callback.h"
void initcaml(void) {
char *dummy_argv[] = {0};
caml_startup(dummy_argv);
}
First we initialize the Ocaml runtime.
int interm_matrix_mul(*a, *b) {
static value *f = NULL;
f = caml_named_value("ocaml_matrix_mul");
if (f == NULL)
return -1;
value r_caml;
r_caml = callback2(*f, a, b);
This is how we grab and execute the exported code. Note that we haven't figured the types for a or b, nor have we converted r_caml to something C-like. Who's up for C arrays of C arrays of C ints? (Or should they be longs?)
From the Ruby side, we'd do something like this.
#include "ruby.h"
VALUE OcamlMatrix = Qnil; // set up the Ruby namespace
// prototype our init and method
void Init_ocamlmatrix();
VALUE method_matrix_mul(VALUE self, VALUE a, VALUE b);
void Init_ocamlmatrix() {
OcamlMatrix = rb_define_module("OcamlMatrix");
rb_define_method(OcamlMatrix, "matrix_mul", method_matrix_mul, 0);
}
VALUE method_matrix_mul(VALUE self, VALUE a, VALUE b) {
// here we would convert a and b to C arrays
c = interm_matrix_mul(conv_a, conv_b);
// and then convert c from C arrays to a Ruby VALUE
return conv_c;
}
You can convert directly from the Ruby types to Ocaml types without C intermediate types. This is nice, because it avoids any need for structs or pointer arithmetic.
You can convert directly from the Ruby types to Ocaml types without C intermediate types. This is nice, because it avoids any need for structs or pointer arithmetic.
But... this only works if you can import both languages' headers without name conflicts (thankfully Ruby's VALUE and Ocaml's value are spelled differently).
VALUE method_matrix_mul(VALUE self, VALUE a, VALUE b) {
CAMLparam0 ();
CAMLlocal2 (caml_a, caml_b);
CAMLlocal1 (caml_interm);
CAMLlocal1 (caml_item);
int x = RARRAY(a)->len;
for (int i = 0; i<x; i++) {
VALUE row = rb_ary_entry(a, i); // row = a[i]
int y = RARRAY(row)->len;
caml_interm = caml_alloc(y, 0);
for (int j = 0; j<y; j++) {
VALUE item = rb_ary_entry(row, j);
long c_item = NUM2LONG(item);
caml_item = Val_long(c_item);
Store_field(caml_interm, j, caml_item);
}
}
// do the same for b
caml_c = interm_matrix_mul(caml_a, caml_b);
// and then convert caml_c from value to a Ruby VALUE
CAMLreturnT(VALUE, ruby_c);
}
Complex data is the problem.
Complex data is the problem.
What if the data was already in Ocaml types when matrix_mul is called?
let new_matrix width height =
Array.make_matrix width height 0
let matrix_assign m x y item =
m.(x).(y) <- item
let matrix_retrieve m x y =
m.(x).(y)
let _ = Callback.register "ocaml_new_matrix" new_matrix
let _ = Callback.register "ocaml_matrix_assign" matrix_assign
let _ = Callback.register "ocaml_matrix_retrieve" matrix_retrieve
let _ = Callback.register "ocaml_matrix_mul" matrix_mul
void Init_ocamlmatrix() {
OcamlMatrix = rb_define_module("OcamlMatrix");
rb_define_singleton_method(OcamlMatrix, "w_new_matrix", singleton_matrix_new, 2);
rb_define_method(OcamlMatrix, "w_matrix_assign", method_assign, 3);
rb_define_method(OcamlMatrix, "w_matrix_retrieve", method_retrieve, 2);
rb_define_method(OcamlMatrix, "w_matrix_mul", method_matrix_mul, 1);
initcaml();
}
VALUE singleton_matrix_new(VALUE class, VALUE width, VALUE height) {
CAMLparam0 ();
CAMLlocal1 (ocaml_m);
ocaml_m = ocaml_new_matrix(Val_long(NUM2LONG(width)),
Val_long(NUM2LONG(height)));
VALUE my_m = Data_Wrap_Struct(class, 0, 0, ocaml_m);
rb_obj_call_init(my_m, 0, NULL);
CAMLreturnT (VALUE, my_m);
}
void method_assign(VALUE self, VALUE x, VALUE y, VALUE item) {
CAMLparam0 ();
CAMLlocal1 (ocaml_m);
Data_Get_Struct(self, value, ocaml_m);
ocaml_matrix_assign(ocaml_m, Val_long(NUM2LONG(x)),
Val_long(NUM2LONG(y)),
Val_long(NUM2LONG(item)));
CAMLreturn0;
}
VALUE method_retrieve(VALUE self, VALUE x, VALUE y) {
CAMLparam0 ();
CAMLlocal1 (ocaml_m);
Data_Get_Struct(self, value, ocaml_m);
VALUE retval = LONG2NUM(Long_val(ocaml_matrix_retrieve(ocaml_m,
Val_long(NUM2LONG(x)),
Val_long(NUM2LONG(y)))
));
CAMLreturnT (VALUE, retval);
}
VALUE method_matrix_mul(VALUE self, VALUE b) {
CAMLparam0 ();
CAMLlocal3 (ocaml_m1, ocaml_m2, ocaml_m3);
Data_Get_Struct(self, value, ocaml_m1);
Data_Get_Struct(b, value, ocaml_m2);
ocaml_m3 = ocaml_matrix_mul(ocaml_m1, ocaml_m2);
VALUE my_m = Data_Wrap_Struct(class, 0, 0, ocaml_m);
rb_obj_call_init(my_m, 0, NULL);
CAMLreturnT (VALUE, my_m);
}
But we have a couple bronze ones.
Inline:: libraries on CPAN.
use Inline "Befunge";
hello();
__END__
__Befunge__
;:hello - print a msg;<q_,#! #:<"Hello world!"a
;
:
a q - ;tcartsbus:;
d
d
;
+ ;not a valid func def;
q
PyCaml, PyObjC.
SciPy, NumPy.
Cython.
Well after i decided on using Ruby and using Ocaml...
Well after i decided on using Ruby and using Ocaml...
... i found Rocaml.
Also available is the Ruby clone of Perl's Inline::, including InlineFortran.
Any questions?
Thanks for coming. Thanks OSBridge for putting together an awesome conference.