search

softdevteam / lrpar

Rust LR parser
Other
1 stars 0 forks source link

Optimisations #48

Closed ltratt closed 6 years ago

ltratt commented 6 years ago

This PR contains 4 not-very-related optimisations. Collectively they make my standard examples almost exactly 2x faster. They're also very small!

The first commit is more about saving memory than about performance; the second is a Rust-specific performance hack; the third makes use of the properties of our A* search to avoid searching pointless nodes; and the fourth commit turns on link-time optimisation in rustc (which, IMHO, should probably be on by default).

ptersilie commented 6 years ago

Since the offset a node is stored in todo is its cost + heuristic. What?

ltratt commented 6 years ago

The todo list is Vec<Vec<N>>: each entry in the outer vec is "all the nodes to look at at cost-level n".

However, it's a bit more subtle than that. A node N has the current cost its taken C, and a minimum-cost-until-it-can-possibly-hit-success H. Instead of storing N in todo[C] we actually store it at todo[C + H] since there's no point looking at it until then.

Should I rephrase things?

ptersilie commented 6 years ago

Ok, maybe I should have made myself clearer ;-) It was more that the sentence ddidn't parse. There's several words missing it seems.

Edit: Ah, did you mean "Since the offset a node stores is...". That would make sense. I tried to change the sentence while keeping the "is stored" which didn't work that well.

ltratt commented 6 years ago

I think the problem is that it's not clear what are variables/attributes and what aren't. Mea culpa! How about "We don't need to store the cost and heuristic of nodes separately, as we never need to think about the two values individually: we care only about the sum of the two, which we can always infer from the offset the node is stored in the todo list."

ptersilie commented 6 years ago

I can also live with "Since the offset of a node stored in todo is its...".

ltratt commented 6 years ago

Pick whichever you feel is clearest (my complete rewrite, or your suggested tweak) -- I'm fine with either (and too close to know which is best!).

ptersilie commented 6 years ago

You are doing it again! :D infer from the offset the node is stored in the todo list. I'm happy with your rewrite, if you fix the this sentence.

ltratt commented 6 years ago

"the offset that the node"?

ltratt commented 6 years ago

OK, updated that comment after our offline discussion.

ptersilie commented 6 years ago

Merged!