DEV Community: Daniel Budden

Running WebAssembly outside of the browser

Daniel Budden — Sat, 03 Aug 2019 14:02:33 +0000

This is the third article in a series of posts on Rust, WebAssembly and Genetic Algorithms. If you haven't read the first or second articles in this series it's definitely worth going back to them before continuing. In this article I will talk about Wasmtime, a runtime for executing WebAssembly outside of the browser. I'll take the algorithm developed in the first article in this series, build some extra features for improved command line usage, compile to WebAssembly and run the WebAssembly module from the command line with Wasmtime.

The complete code for this post can be found here.

Photo by Darío Méndez on Unsplash

The first improvement I've made to the Rust code from the first post in this series is to take the algorithm parameters as command line arguments. To enable this I've added the structopt crate, which builds on the popular clap crate, and allows the definition of command line arguments using a struct. To define the CLI arguments a struct is defined and used with a macro and custom derive from structopt.

#[derive(StructOpt)]
#[structopt()]
struct Opt {
    #[structopt(name = "iterations")]
    iterations: usize,
    #[structopt(name = "pop_size")]
    population_size: usize,
    #[structopt(name = "crossover_rate")]
    crossover_rate: f64,
    #[structopt(name = "mutation_rate")]
    mutation_rate: f64,
    #[structopt(name = "survival_rate")]
    survival_rate: f64,
    #[structopt(name = "csv", parse(from_os_str))]
    csv: PathBuf,
}

fn main() {
    let opts = Opt::from_args();
    ...
}

The second change is to parse the list of cities for the travelling salesman problem from a CSV file. The CSV will have two columns, the first being the x co-ordinate and the second being the y co-ordinate for each city. The first row of the CSV file will contain a header with the column names (x and y) and this will allow the rows to be deserialised into the City struct by the csv crate when they are read in.

#[derive(Deserialize)]
pub struct City {
    x: f64,
    y: f64,
}

fn main() {
    ...
    let mut reader = Reader::from_path(opts.csv).unwrap();
    let cities: Vec<City> = reader.deserialize()
        .map(|r| {
            let result: City = r.unwrap();
            result
        })
        .collect();

    ...
}

To get started with Wasmtime you will need to compile it from source. The full details on getting setup can be found here, but for MacOS this involved:

brew install cmake llvm

git clone --recurse-submodules https://github.com/CraneStation/wasmtime.git

cd wasmtime

cargo build

Once Wasmtime is compiled the next step is to ensure the necessary compile target for WebAssembly is available. Wasmtime uses the WebAssembly System Interface (WASI), which provides WebAssembly code with access to operating system features such as the filesystem. Adding the right compile target and compiling the Rust code to WebAssembly is done using:

rustup target add wasm32-wasi

cargo build --target wasm32-wasi --release

And finally running the WebAssembly Genetic Algorithm on the command line with Wasmtime. WebAssembly's security model involves sandboxing, this means that to enable the program to access files from the operating system the Wasmtime runtime needs a list of directories that the program will should be allowed to access. In this case the current directory . is provided so that the WebAssembly module can access the cities.csv file there.

../wasmtime/target/release/wasmtime --dir=. target/wasm32-wasi/release/wasi-genetic.wasm 5000 500 0.4 0.001 0.3 cities.csv

Thanks for reading this series of posts on Rust, WebAssembly and Genetic Algorithm. Any questions, feedback or comments are welcome here or on the repositories listed. The complete code for this post can be found here.

Genetic Algorithm in the browser with WebAssembly

Daniel Budden — Tue, 30 Jul 2019 13:14:09 +0000

This is the second post in my series on Rust and WebAssembly with Genetic Algorithms. In this post I'm going to build on the Genetic Algorithm I have implemented in Rust for the travelling salesman problem. I'll take the Rust implementation and make some adjustments that will allow it to be compiled to WebAssembly and interact with JavaScript and the browser. Then I'll develop a web application that will provide the user interface for running the Genetic Algorithm.

All the code for this post can be found here, and the live demo can be found here.

Photo by Vincent Burkhead on Unsplash

For this project I am using the Rust Webpack Template, which is designed to create monorepo style Web applications which are made up to JavaScript, HTML and Rust-generated WebAssembly. This template relies on a few tools; wasm-pack, npm, and setting up the WebAssembly compile target wasm32-unknown-unknown. More details on the setup can be found in the wasm-pack docs.

To start with, there are a number of changes that need to be made to the Rust code to support compilation to WebAssembly. The first thing is to add wasm-bindgen which will provide the means to define which parts of the Rust code will be exported and accessible from JavaScript. Adding the wasm-bindgen macro to the Simulation struct tells the library to build this as an export from the WebAssembly module, and adding the macro for the constructor allows the Simulation to be created using new Simulation() in JavaScript.

#[wasm_bindgen]
pub struct Simulation {
    population: Vec<Path>,
    city_list: Vec<City>,
    max_iterations: usize,
    crossover_rate: f64,
    mutation_rate: f64,
    survival_rate: f64,
}

#[wasm_bindgen]
impl Simulation {
    #[wasm_bindgen(constructor)]
    pub fn new(
        population_size: usize,
        city_list: String,
        max_iterations: usize,
        crossover_rate: f64,
        mutation_rate: f64,
        survival_rate: f64,
    ) -> Simulation {
        ...
    }
}

The Rust implementation uses the rand crate; luckily the rand crate provides support for the WebAssembly compile target using wasm-bindgen. This can be set in the projects Cargo.toml and as of version 0.7 works seamlessly.

[dependencies.rand]
version = "0.7"
features = [
  "wasm-bindgen",
]

Another useful crate is js_sys, which provides bindings to JavaScripts built-in objects and standard library. This is useful to marshal the results of the simulation to a format the calling JavaScript can understand. The return type of the Simulation's run method becomes Array from js_sys, and an array is constructed with the first entry being the ordered list of nodes visited for the solution, and the second the fitness.

pub fn run(&mut self) -> Array {

      ...

      let array = js_sys::Array::new();
      let order = js_sys::Array::new();
      for o in fittest.order {
          order.push(&JsValue::from(o as u32));
      }

      array.push(&order);
      array.push(&JsValue::from(fittest.fitness));

      array
  }

The web application for running the simulation is designed to be simple; it has inputs for the algorithm parameters, an area where the user may click to add cities, and a preset button which adds a list of default cities.

To prevent the main thread from being blocked while running the WebAssembly, the module is run in a Web Worker. The first step is to change the Webpack config provided by the Rust Webpack template to build the app and worker JavaScript files separately.

const appConfig = {
  target: 'web',
  entry: "./js/index.js",
  output: {
    path: dist,
    filename: '[name].[hash].js',
  },
  devServer: {
    contentBase: dist
  },
  plugins: [
    new HtmlWebpackPlugin({
      template: 'index.html',
      chunks: ['main']
    }),
  ],
  module: {
    rules: [
      {
        test: /\.css$/,
        use: [{ loader: 'style-loader' }, { loader: 'css-loader' }],
      }
    ]
  }
}

workerConfig = {
  target: 'webworker',
  entry: "./js/worker.js",
  output: {
    path: dist,
    filename: 'worker.js',
    globalObject: 'self'
  },
  devServer: {
    contentBase: dist
  },
  resolve: {
    extensions: [".js", ".wasm"]
  },
  plugins: [
    new WasmPackPlugin({
      crateDirectory: path.resolve(__dirname, "crate"),
    }),
  ]
}

module.exports = [appConfig, workerConfig]

The worker code is pretty simple. It imports the WebAssembly module, sets up a message handler to receive data from the main thread with the simulation parameters, runs the Simulation and posts a message back to the main thread with the results.

import("../crate/pkg").then(({ Simulation }) => {

  onmessage = function(msg) {
    const {
      iterations,
      citiesString,
      population_size,
      crossover,
      mutation,
      survival
    } = msg.data

    const s = new Simulation(
      iterations,
      citiesString,
      population_size,
      crossover,
      mutation,
      survival
    )

    const result = s.run()

    self.postMessage({
      path: result[0],
      fitness: result[1]
    })
  }
})

The application code includes a click handler that captures the users clicks inside the drawing space and adds a dot. The position of the dot is stored in data-x and data-y attributes on the DOM elements for passing to the WebAssembly code later.

const draw = document.getElementById('draw')

function addDot(x, y) {
  const dot = document.createElement('div')
  dot.className = 'dot'
  dot.style = `top: ${y}px; left: ${x}px;`
  dot.setAttribute('data-x', x)
  dot.setAttribute('data-y', y)
  draw.appendChild(dot)
}

draw.onclick = function(event) {
  addDot(event.offsetX, event.offsetY)
}

The main part of the application is the onsubmit function for the form. It is responsible for:

capturing the input parameters for the simulation,
extracting the co-ordinates of the cities that the user has drawn,
sending a message to the worker with the parameters,
setting a message handler to receive the results of the simulation run and draw the solution,
drawing the cities on the solution canvas.

form.onsubmit = function(event) {
  event.preventDefault()
  const [iterations, population_size, crossover, mutation, survival] = event.target

  const cities = []
  const count = draw.children.length
  for (let c = 0; c < count; c++) {
    cities.push([
      draw.children[c].getAttribute('data-x'),
      draw.children[c].getAttribute('data-y')
    ])
  }

  const citiesString = cities.map(c => c.join(',')).join(';')

  worker.postMessage({
    iterations: parseInt(iterations.value, 10),
    citiesString,
    population_size: parseInt(population_size.value, 10),
    crossover: parseFloat(crossover.value),
    mutation: parseFloat(mutation.value),
    survival: parseFloat(survival.value)
  })

  worker.onmessage = function(msg) {
    const { path, fitness } = msg.data

    for (let p = 0; p < path.length - 1; p++) {
      const start = cities[path[p]]
      const end = cities[path[p+1]]

      ctx.beginPath()
      ctx.moveTo(start[0], start[1])
      ctx.lineTo(end[0], end[1])
      ctx.stroke()
    }
  }

  const ctx = canvas.getContext('2d')

  cities.map(c => {
    ctx.beginPath()
    ctx.arc(c[0], c[1], 2, 0, 2 * Math.PI, false)
    ctx.fillStyle = 'black'
    ctx.fill()
  })
}

The complete code can be found here, as well as the demo here.

In this article I have shown how to modify Rust code for compilation into WebAssembly and build a web application to use the WebAssembly module. In the last article in this series I will take about running this WebAssembly module outside of the browser with Wasmtime.

Genetic Algorithm in Rust

Daniel Budden — Sun, 28 Jul 2019 10:34:01 +0000

Recently I've been learning Rust and experimenting with compiling it to WebAssembly. In this series of three posts I'm going to relate my journey of building a Genetic Algorithm to solve the travelling salesman problem in Rust, and then the work to compile it into WebAssembly in order to run the algorithm in the browser. I'm still quite new to Rust, so any feedback is welcome in the comments or on the repos provided.

All code for this article can be found here.

Photo by Adrien Converse on Unsplash

A Genetic Algorithm is an optimisation algorithm inspired by the process of natural selection. It uses a population of possible solutions across the search space; the fittest individuals in the population survive, and the processes of breeding and mutation mean that better solutions evolve over successive generations. For more in depth explanation of Genetic Algorithm see this article.

The application that I've chosen for my use of the Genetic Algorithm is the travelling salesman problem, which can be summarised as - Given a list of cities what is the shortest path that visits all cities? The brute force approach of generating all possibilities and evaluating each quickly becomes impractical, as the number of permutations is the factorial of the number of cities. For examples with:

5 cities: 5! = 120 possible solutions
10 cities: 10! = 3 628 800 possible solutions
20 cities: 20! = Approximately 2 quintillion ( ~2.43 x 10^18 )

An optimisation algorithm, such as a Genetic Algorithm, can be used to search for the optimal solution, but unlike with a brute force, or an alternate exact algorithm, there is no guarantee of getting the optimal solution.

The first step is to decide how to structure the solution to our problem. A solution for this problem is an ordered list of nodes to visit. The Path struct stores the ordered list of nodes travelled, as well as the fitness of the solution which will be calculated when the individual is created. The methods that are implemented for Path allow individuals to breed and mutate, and for the fitness of a solution to be calculated.

pub struct Path {
    fitness: f64,
    order: Vec<usize>
}

The fitness of a solution is calculated using the order list of nodes and the city list which stores the coordinates of each city. The cost of the path is calculated as the sum of the cartesian distance between the cities in the list. The aim of the algorithm is to maximise the fitness, in this case the inverse of the cost.

pub struct City {
    x: f64,
    y: f64,
}

impl Path {
    pub fn calculate_fitness(path: &Vec<usize>, city_list: &Vec<City>) -> f64 {
        let path_length = city_list.len();
        let mut cost = 0.0;
        for i in 0..path_length - 1 {
            let a = &city_list[path[i]];
            let b = &city_list[path[i + 1]];
            cost = cost + ((a.x - b.x).powf(2.0) + (a.y - b.y).powf(2.0)).sqrt();
        }

        1.0 / cost
    }
}

An individual will breed with another member of the population, and create an offspring. A uniform probability distribution from the rand crate is used to select a crossover point, the nodes from the mother are selected from the start of the list up to the crossover point, with the remainder selected from the father.

impl Path {
    pub fn breed(&self, other: &Path, city_list: &Vec<City>) -> Path {
        let order = Path::crossover_order(&self.order, &other.order);
        let fitness = Path::calculate_fitness(&order, city_list);

        Path { fitness, order }
    }

    fn crossover_order(mother: &Vec<usize>, father: &Vec<usize>) -> Vec<usize> {
        let mut rng = thread_rng();
        let crossover_point = Uniform::new(0, mother.len()).sample(&mut rng);

        let mother_dna = &mother[0..crossover_point];
        let mut father_dna: Vec<usize> = father.iter().filter_map(|d| {
            if !mother_dna.contains(d) {
                return Some(*d)
            }
            None
        }).collect();

        let mut child = Vec::new();
        child.extend_from_slice(mother_dna);
        child.append(&mut father_dna);

        child
    }
}

Some of the population of each generation will undergo mutation, which involves randomly selecting two nodes in the path and swapping them. After mutating, the Path's fitness is recalculated.

pub fn mutate(&mut self, city_list: &Vec<City>) {
      let mut rng = thread_rng();
      let point_one = Uniform::new(0, self.order.len()).sample(&mut rng);
      let point_two = Uniform::new(0, self.order.len()).sample(&mut rng);

      self.order.swap(point_one, point_two);
      self.fitness = Path::calculate_fitness(&self.order, &city_list);
  }

The Simulation struct is used to orchestrate the creation of successive generations and selection of the best solution. It stores the population along with parameters for the Genetic Algorithm including:

the maximum number of iterations desired,
the crossover rate, the fraction of the population to use for breeding,
the mutation rate, the chance each individual will mutate each iteration,
the survival rate, the fraction of the breeding population that will continue into the next generation.

 pub struct Simulation {
     population: Vec<Path>,
     city_list: Vec<City>,
     max_iterations: usize,
     crossover_rate: f64,
     mutation_rate: f64,
     survival_rate: f64,
 }

The Simulation has a run method which creates the next generation and finds the new fittest individual for each iteration. Generating the next generation involves:

Selecting the breeding population from the best individuals,
Generating offspring,
Selecting the surviving parents from the breeding population,
Selecting a few weak individuals to help genetic diversity,
Mutating individuals in the population.

pub fn run(&mut self) -> () {
      let mut fittest = self.find_fittest();
      println!("starting iterations");

      for _ in 0..self.max_iterations {
          self.generate_next_generation();

          let challenger = self.find_fittest();

          if challenger.fitness > fittest.fitness {
              fittest = challenger;
          }
      }
      println!("{}", fittest);
  }

The complete code can be found here.

In this article I have outlined an approach for a Genetic Algorithm for the travelling salesman in Rust. In the next article in this series I'll take the foundations laid here and build it into a web application using WebAssembly.