optimization

[stas]

So here's Java WTF of the day. The code in AbstractSet.java:

   public boolean removeAll(Collection<?> c) {
        Objects.requireNonNull(c);
        boolean modified = false;

        if (size() > c.size()) {
            for (Iterator<?> i = c.iterator(); i.hasNext(); )
                modified |= remove(i.next());
        } else {
            for (Iterator<?> i = iterator(); i.hasNext(); ) {
                if (c.contains(i.next())) {
                    i.remove();
                    modified = true;
                }
            }
        }
        return modified;
    }

Can you spot any potential problems here? Seems logical, right? You choose the smaller collection, go over it and everything is fine. What could be the problem?



Well, imagine one of the collections a HashSet - O(1) lookup - and another is ArrayList, O(n) lookup. Do you see how linear performance turns into а quadratic one with this "optimization"? Of course, since the incoming type is a "Collection", you can't know which one is which, the "optimization" applies regardless.
And if you rely on Java doing "the right thing" in this case, your code eventually will get stuck in production on seemingly innocent "removeAll" call you you'd be at loss wtf could happen there.

  P.S. Turns out it is known and documented behavior. Sigh.

Comments

Re: #такойвопросспалил (для интервью)

[stas]

Ну, можно сделать это дело полиморфным, наверное - для каких-то типов с оптимизацией, для каких-то без.