First come up with a few good designs from a mathematical and algorithmic perspective.
Prune this selection by consideration of practical matters (like locality of reference).
Finally prototype (that is, do test implementations) a few of the best designs and run them on data sets that will arise in your application for the final fine-tuning.
Use whatever development tools that you have, such as profilers.S