[BUG]Collection>>removeAll:

Stephan Rudlof sr at evolgo.de
Wed Aug 28 14:07:11 UTC 2002


Richard A. O'Keefe wrote:

<snipped>

> So we find that
> 
>  - x copyWithoutAll: y is already O(1) when x isEmpty
>    without adding any special test;
> 
>  - x removeAll: y must not make a special case when x isEmpty
>    (unless y isEmpty also), in fact, if x is empty and y isn't
>    an error will be reported after O(1) work so there isn't
>    even a performance problem finding the error;
> 
>  - x removeAllFoundIn: y is the only remaining method where
>    removing a large y from an empty x could be expensive,
>    but then *in context* that's likely to be dominated by the
>    cost of building y in the first place.

Agreed.

> 
> Personally, I'm all in favour of special cases in implementations
> when they solve real problems.
> 
>     a := (1 to: 200*1000) asArray.
>     e := OrderedCollection new.
>     [e removeAllFoundIn: a] timeToRun
> ==> 4 seconds
>     [e removeAllFoundInSR: a] timeToRun "really had 200000 timesRepeat:"
> ==> 4 milliseconds
> 
> So yes, sticking a (self isEmpty) check in #removeAllFoundIn: can save
> as much time as you like (just make the argument as big as you want);
> the question is, does that happen often enough to pay off.

Agreed.

> 
> Several of the sends to #removeAllFoundIn: in the system have arguments 
> that are obviously very short or are obviously shorter than the receiver
> or else are called infrequently.  I have no idea how other people use
> #removeAllFoundIn:.

And in most cases the shortcut probably wouldn't be one, since the receiver
is not empty.
If the programmer *knows*, that he/she wants to send #removeAllFoundIn: to a
potentially empty collection with potentially very big args, he/she is free
to check for emptyness before making this.

So (my current opinion ;-) ): let it be (the self isEmpty check).


But I stay voting for asserts in the addAll:/removeAll: family making the
implicit precondition explicit.


Greetings,

Stephan

> 
> 
-- 
Stephan Rudlof (sr at evolgo.de)
   "Genius doesn't work on an assembly line basis.
    You can't simply say, 'Today I will be brilliant.'"
    -- Kirk, "The Ultimate Computer", stardate 4731.3




More information about the Squeak-dev mailing list