Skip to content

solver-ginsberg: Rework dictionary cache again

Antoine Belvire requested to merge feature/faster_dictionary_cache into master

Context

Reworked again dictionary cache management in croiseur-solver-ginsberg.

This MR introduces a cache of words satisfying patterns. This is close to what xwords-rs does and this is extremely effective to avoid slow filtering of initial candidates.

Raw performance gain is a factor of ~ 5. Still slower than xwords-rs by an order of magnitude but this opens new perspective of optimisations, since now other hotspots can be seen and worked on.

See attached flamegraph (to be compared with e.g. flamegraph present on #53 (closed) – Trie.findAndUpdateNextWord is not the main hotspot anymore).

What has changed?

Main Changes

croiseur-solver-ginsberg

  • Introduces a new cache by pattern à la xwords-rs.

Merge request reports