Q) Any idea on how to improve lookUp?
A) Use a concurrent cache:
https://gist.github.com/brikis98/5842766
Point is, regardless how good or bad you lookup function is, nothing beats a cache-hit performance wise..
Q) Is there a better way to do simple caching than using withDefault to mutate the underlying map?
A) getOrElseUpdate(key, value)
Hope someone else is able to provide you good answers for the remaining questions. Good luck.