I learned Rust yesterday and begin to to think of problems that can be written nicely in C but which cause problems to Rust. For example consider a problem where a large vector is modified by a pair of threads, each thread accessing a different subset of elements. This subset could be the even indices in the first iteration, the 0,1 mod 4 in the second iteration and so on.
I have written programs to solve this example task in C and in (two different ways) Rust.
// gcc vectorsubset.c -lpthread -O3
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
void operate(float *v, long n, long iteration, long selection, float x)
{
long size=1<<iteration;
for(long i=0;i<n;i++)
{
if((i/size)%2==selection)v[i]*=x;
}
}
struct info
{
float *v;
long n;
long iteration;
};
void *operate_child(void *data)
{
struct info *info=data;
operate(info->v,info->n,info->iteration,1,3.0);
}
int main()
{
long k=23;
long n=1<<k;
float *v=malloc(n*sizeof(float));
for(long i=0;i<n;i++)v[i]=1.0;
for(int iteration=0;iteration<k;iteration++)
{
pthread_t child;
struct info info={v,n,iteration};
pthread_create(&child, NULL, operate_child, (void *)&info);
operate(v,n,iteration,0,2.0);
pthread_join(child,NULL);
}
float total=0.0;
for(long i=0;i<n;i++)total+=v[i];
printf("total=%f\n",total);
}
// rustc -O vectorsubset.rs
use std::{mem,thread,ptr};
fn separate<'a>(v: &'a mut Vec<f32>, f:&Fn(usize)->bool ) -> (Vec<&'a mut f32>,Vec<&'a mut f32>)
{
let n=v.len();
let mut r1=Vec::new();
let mut r2=Vec::new();
let mut w : &mut [f32] =v;
for iteration in 0..n
{
let tmp=mem::replace(&mut w,&mut []);
let (head,tail) = tmp.split_at_mut(1);
w=tail;
if f(iteration)
{
r1.push(&mut head[0]);
}
else
{
r2.push(&mut head[0]);
}
}
(r1,r2)
}
fn operate(v : Vec<&mut f32>, x: f32)
{
for elem in v.into_iter()
{
*elem *= x;
}
}
static mut theVector : *mut Vec<f32>=0 as *mut Vec<f32>;
extern "C" {
fn malloc(input: i64) -> *mut f32;
}
fn create_static_vector(n:usize)
{
unsafe{
theVector = malloc((n*4) as i64) as *mut Vec<f32>;
ptr::write(theVector,vec![1.0;n]);
}
}
fn get_static_vector() -> &'static mut Vec<f32>
{
unsafe{
&mut *theVector
}
}
fn main()
{
let k=23;
let n=2u32.pow(k);
create_static_vector(n as usize);
for iteration in 0..k
{
let size=2u32.pow(iteration);
let f = |i| (i/size as usize)%2==0;
let (A,B) = separate(get_static_vector(),&f);
let handle=thread::spawn(move||{
operate(B,3.0);
});
operate(A,2.0);
handle.join();
}
let total : f32 = get_static_vector().iter().sum();
println!("total={}",total);
}
// rustc -O vectorsubset2.rs
use std::{mem,thread,ptr};
struct TrueIt<'a>
{
v : &'a Vec<f32>,
f : &'a (Fn(usize,u32)->bool + Send + Sync + 'static),
curr : usize,
data: u64,
aux: u32,
}
struct FalseIt<'a>
{
v : &'a Vec<f32>,
f : &'a (Fn(usize,u32)->bool + Send + Sync + 'static),
curr : usize,
data: u64,
aux: u32,
}
impl<'a> Iterator for TrueIt<'a>
{
type Item = &'a mut f32;
fn next(&mut self) -> Option<&'a mut f32>
{
while self.curr<self.v.len() && !(*self.f)(self.curr,self.aux)
{
self.curr+=1;
}
if self.curr<self.v.len()
{
let tmp=unsafe{
&mut *((self.data +4*(self.curr as u64)) as *mut f32)
};
self.curr+=1;
Some(tmp)
}
else
{
None
}
}
}
impl<'a> Iterator for FalseIt<'a>
{
type Item = &'a mut f32;
fn next(&mut self) -> Option<&'a mut f32>
{
while self.curr<self.v.len() && (*self.f)(self.curr,self.aux)
{
self.curr+=1;
}
if self.curr<self.v.len()
{
let tmp=unsafe{
&mut *((self.data +4*(self.curr as u64)) as *mut f32)
};
self.curr+=1;
Some(tmp)
}
else
{
None
}
}
}
fn separate<'a>(v:&'a mut Vec<f32>, f:&'a (Fn(usize,u32)->bool+Send+Sync+'static), aux:u32) -> (TrueIt<'a>, FalseIt<'a>)
{
let data=&mut v[0] as *mut f32 as u64;
let tr=TrueIt{
v: v,
f: f,
curr: 0,
data: data,
aux: aux,
};
let fa=FalseIt{
v: v,
f: f,
curr: 0,
data: data,
aux: aux,
};
(tr,fa)
}
static mut theVector : *mut Vec<f32>=0 as *mut Vec<f32>;
extern "C" {
fn malloc(input: i64) -> *mut f32;
}
fn create_static_vector(n:usize)
{
unsafe{
theVector = malloc((n*4) as i64) as *mut Vec<f32>;
ptr::write(theVector,vec![1.0;n]);
}
}
fn get_static_vector() -> &'static mut Vec<f32>
{
unsafe{
&mut *theVector
}
}
fn selection_function(i:usize, size:u32) -> bool
{
(i/size as usize)%2==0
}
fn main()
{
let k=23;
let n=2u32.pow(k);
create_static_vector(n as usize);
for iteration in 0..k
{
let size=2u32.pow(iteration);
let (A,B) = separate(get_static_vector(),&selection_function,size);
let handle=thread::spawn(move||{
for elem in B
{
*elem*=3.0;
}
});
for elem in A
{
*elem*=2.0;
}
handle.join();
}
let total : f32 = get_static_vector().iter().sum();
println!("total={}",total);
}
The C code is very simple. The first Rust program creates Vec<&'a mut f32>) to select where each thread works. I have needed to unsafely allocate a vector as static so that it has life to be passed to the thread; perhaps this can be solved in a safe way. The second Rust program creates some iterators thereby avoiding the creation of the vector of references. However, the creation of these iterators is similar to that of split_at_mut, and hence, it seems to be necessary to make some unsafe operations.
It is nice to see that compiling with optimizations Rust's times are just a little above than C's times.
I would like to know if this problem can be solved in a cleaner way.
