The performance of com.ibm.icu.text.RuleBasedCollator in 4.0.1 (used in Eclipse 3.5) slowed down about 3 times comparing to 3.8.1 (used in Eclipse 3.4).
The https://bugs.eclipse.org/bugs/show_bug.cgi?id=275170 contains references to the JUnit test that shows this performance degradation.
Move to milestone:4.0.2. This issue was resolved by #5174 after ICU4J 4.0, but not picked up in 4.0.1. ICU4J 4.4 does not have this problem.