This could be faster: we currently ignore that fromMutable owns the underlying mutable structure. If we don't ignore that, we never need to copy: we could make a wrapper that delegates to the mutable Map and implements the map traits, which I think there are only  like 3: http://www.scala-lang.org/api/current/index.html#scala.collection.immutable.Map.

That might be worth the work?