That doesn't sound unreasonable, no -- at some point in the future, Scala's hash array mapped trie will be robust and highly optimized. If your plan is to wait until then, you might be able to speed things up by helping them out yourself.

In the meantime, I benchmarked Yoink's PeristentHashMap against 2.8.0.RC2's immutable.HashMap by a) creating a map of 100,000 sequential keys and then removing them all, and b) creating a map of 100,000 random keys and then removing 100,000 random keys. In the first case, Yoink was 20.7041% (±1.83693%) faster. In the second case, Yoink was 24.7834% (±4.17055%) faster. (Student's t distribution, 95% confidence interval, source is in src/test on the GitHub project and I used ministat for the statistical analysis [a cross-platform port of which is also available on my GitHub page].)

So to summarize, I have a provably faster hash array mapped trie at almost zero cost right now because I spent a few hours with a "good learning experience."