Much speed up was from using the right data structure for the task, e.g. Vec rather than HashMap and BitSet rather than HashSet.