Affects Version/s: Scala 2.9.0
Fix Version/s: None
Component/s: Misc Library
$ java -version
java version "1.6.0_24"
Java(TM) SE Runtime Environment (build 1.6.0_24-b07)
Java HotSpot(TM) 64-Bit Server VM (build 19.1-b02, mixed mode)
$ scalac -version
Scala compiler version 184.108.40.206 - Copyright 2002-2011, LAMP/EPFLShowUbuntu 10.10 $ java -version java version "1.6.0_24" Java(TM) SE Runtime Environment (build 1.6.0_24-b07) Java HotSpot(TM) 64-Bit Server VM (build 19.1-b02, mixed mode) $ scalac -version Scala compiler version 220.127.116.11 - Copyright 2002-2011, LAMP/EPFL
indexOfSlice is implemented using operations that have horrible performance characteristics for mutable data structures, including Array, and for slow-to-index data structures, including List.
One problem (I'm not sure if it's the only problem) is that SeqLike's indexOf method (in the SeqLike companion) is used, which blindly uses drop and slice even if you're not actually slicing anything, then launches into an index-based searcher that shouldn't need the sliced data (and is slow as molasses for List anyway). So, for arrays you make a bunch of extra copies when none are needed, and for lists, you traverse the list a bunch of times when this is not needed. (lastIndexOfSlice is even worse, because it reverses the entire data structure instead of searching backwards.)
The changes needed are:
(1) Move the search logic from SeqLike.KMP into SeqLike.indexOf, so you can use indexing without copying, or at least use views.
(2) Move the SeqLike stuff into IndexedSeqOptimized and implement the routines differently for SeqLike (probably with an iterator on the main collection).
(3) Write a backwards-KMP or at least use views so you don't need to copy huge data structures to see something at the end.
I will write a patch if given a specific go-ahead and/or directions on what is considered acceptable and what is not. I'm actually too busy right now to write a patch, but will make an exception (i.e. get that much less sleep) if I am reasonably confident it will be included and benefit me and others in a reasonable timeframe.