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.

Any idea on how to improve lookUp?

Use a concurrent cache. The point is, regardless how good or bad you lookup function is, nothing beats a cache-hit performance wise..

Is there a better way to do simple caching than using withDefault to mutate the underlying map?

getOrElseUpdate(key, value)