Skip to content

Optimise simplification algorithms #807

Open
@urschrei

Description

@urschrei

At the moment, our simplification algorithms work like this:

If we want retained indices:

  1. We create a vec of wrapper structs of indices and coordinates by iterating over the input
  2. The simplification algorithm iterates over that vec as a slice, calculating the retained points and indices, storing them in a new vec
  3. We iterate over this vec, extracting the indices into a new vec.

If we want retained coordinates:

  1. See (1) and (2) above
  2. We iterate over this vec, extracting the coordinates into a new vec.

So at the moment we're performing 3n iterations – compiler optimisations notwithstanding – in the worst case: 1x for wrapper struct creation, 1x when the simplification algorithm runs, and 1x to extract the results, which might be equal in length to the input.

Some Things We Could Try

I remember from writing the new implementation that we have to create the input indices ahead of time for RDP (not sure about VW) because it's recursive,
but if we could invert our RdpIndex usage by re-writing it into a struct-of-vecs instead of a using a vec-of-structs we could:

  1. Directly create a Vec<usize> instead of iterating in order to produce the input indices. Perhaps the compiler optimises iteration to this anyway, but it's worth trying and benchmarking
  2. Return the retained values or indices by replacing them with empty vecs using mem::replace instead of iterating again

Metadata

Metadata

Assignees

No one assigned

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions