Skip to content
This repository has been archived by the owner on May 20, 2022. It is now read-only.

fontcrunch is slow because I can't handle references and lifetimes #35

Closed
simoncozens opened this issue Jun 9, 2021 · 8 comments
Closed

fontcrunch is slow because I can't handle references and lifetimes #35

simoncozens opened this issue Jun 9, 2021 · 8 comments

Comments

@simoncozens
Copy link
Owner

The ported version of fontcrunch is much slower than the original, particularly in glyphs which go down this O(n^2) loop:

fonttools-rs/crates/fonttools-cli/src/bin/fontcrunch.rs

Lines 322 to 332 in 0400715

for i in 1..n + 1 {
let mut j = i - 1;
loop {
println!("{:?}, {:?}", i, j);
try_line_quad(&mut states, j, i, self, &breaks[j], &breaks[i], penalty);
if j == 0 {
break;
}
j -= 1;
}
}

I'm sure it's because of this clone:

fonttools-rs/crates/fonttools-cli/src/bin/fontcrunch.rs

Line 366 in 0400715

self.prev = Box::new(newprev.cloned());

The clone is only there because I can't work out the lifetimes required for storing Statelets as references within a Statelet and moving them around. If I put what I think are the right lifetimes on the State and Statelet types, I get a confusing error like so:

431 |     states: &mut Vec<State>,
    |             --------------- these two types are declared with different lifetimes...
...
454 |         states[this].sts.push(sl);
    |                               ^^ ...but data from `states` flows into `states` here
@simoncozens
Copy link
Owner Author

@cmyr If you have any advice I would appreciate it. :-/

@cmyr
Copy link
Collaborator

cmyr commented Jun 9, 2021

Can take a look in a few minutes. 👍

@simoncozens
Copy link
Owner Author

Thank you! I just had a flash of inspiration when washing up and I think the answer might be "change the data structure to avoid using a linked list".

If we use a Vec<Vec<Statelet>> inside State instead of Vec<Statelet>, we might be able to handle all the information we need within State.

@cmyr
Copy link
Collaborator

cmyr commented Jun 9, 2021

avoiding a linked list is definitely the first thing I would try. taking a look now, will see if I have any more concrete advice..

@simoncozens
Copy link
Owner Author

Original C++ is here if it helps: https://github.com/googlefonts/fontcrunch/blob/main/src/fontcrunch/quadopt.cc

I just realised one of the Vec's was being used as an Option, so fixed that.

@cmyr
Copy link
Collaborator

cmyr commented Jun 9, 2021

There's a lot going on here, and I don't know a ton of the details, but some thoughts:

if any of these vecs are fixed size, or have generally small sizes, I would look into using either an array or some sort of 'smallvec' type, like smallvec.

Instead of a linked list, my first thought would be to have a big shared vec (or Rc<[]>) of statelets, and then instead of passing around statelets themselves you'd pass around indices into this big shared sequence?

@simoncozens
Copy link
Owner Author

Thanks for this. I have now switched it to using an Rc to hold the Statelet to ensure copies are cheap, but the performance problem is the same, so my intuition (copying the statelet lots of time was slow) doesn't seem to have been correct. Time to actually use a profiler and find out what's going on.

@simoncozens
Copy link
Owner Author

OK, I was kind of optimizing the wrong thing. Moving to Rc did make it faster, but the real problem was indeed allocating lots of tiny vecs in the rk4 function. I'm sure there are still optimisations we can do in that whole routine - arclen / measure now being the big hotspot - but we're 25% faster than python/C++ now, so I'll take that.

Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
2 participants
@simoncozens @cmyr