Thoughts on making things faster

[jgraley]

More hinting

This will get fiddly very quickly, and benefits are unclear. For example:

• We could hint on non-stars in sequences that are near front or back
• But the first mismatch exception that will usually be thrown is the one for wrong cadence
• At this point we may not even have the base sequence x_seq needed for the hint
• Alternative approaches could be used like generating candidate hints at the top, but the plan was keep that close to the point of generating the exception.
• Anyway, non-star at front or back is rare
• Situation for collections similar or worse

Move star/decision stuff out of StandardAgent's NLQ

• Actually this is pretty fast - it never loops over the container
• Probably should do anyway for architectural reasons - there's a clean split of NLQ impl between parts needed for CSP solver and for regeneration
• This will save on wasted time doing "bureaucracy" - could be a *2 speedup? Update: have split out Regeneration Queries from NLQ as a separate vcall. Not sure if there was much speedup

Don't repeat Knowledge accesses

• Overhead of unordered_map lookups
• Try to make code cleaner in the process
• Cleanest to cache in TheKnowledge #273

Slow steps

• Tried watching runs. Slow:
  • Steps involving disjunctions
  • Steps with multiple # or #=1
  • Steps with multiple separate islands of non-star in sequences
• For disjunctions, I note we're not yet doing MMAX first. This should help
• If we're going to order the searches, why not add an ordering on all the nodes, eg
  • Depth-first and breadth-first - extend hints from #, #=1 and SA to include ranges on these
  • By category - all nodes can hint their root
  • By depth into tree - test values in this order, so shallower variables match sooner - does this help though? Is there some other obvious test order?

[jgraley]

More about search order

• Why not just put all the X nodes in standard depth-first traversal order, same as the variables. Then:
  • For most variables, search begins after previous hit
  • Except in-place patterns like overlay-through etc, so maybe begin at previous hit
  • Conjunctions would be an exception - need to rewind
  • Maybe always begin at parent hit?
  • MMAX and Y nodes need to be available. MMAX comes first, unsure about Y nodes

Not sure it helps that much - misses still traverse everything, and elements in containers can be spaced far apart in a depth first walk.

Another possibility: alternating forward/backward ordering whereby if we just did 5, we try 5, 6, 4, 7, 3, 8, 2, 9, 1 for example.

Update: tried forward/backward plus MMAX first, no real speed-up, see comment below

[jgraley]

Don't retest constraints

Only test constraints that constrain the variable just assigned.

Update: tried this, reduced runtime by about a third

[jgraley]

Regarding search order performance

This made little difference, probably because time taken is dictated by searches that have to run to completion. Even when there is a match, we still have to go to the end before returning. We need reliable reductions in candidate values, so that we can stop when we get to the end of them.

[jgraley]

Obsolete