asArray method in Sets (please ignore previous draft if you receive it)

Ralph Boland rpboland at gmail.com
Mon Oct 17 04:49:50 UTC 2005


I use Sets (and its subclasses like Dictionary) a lot and desire that
they be efficient. (I am currently using Squeak 3.6)

I discovered that Set inherits the 'asArray' method from Collection
which is written as follows:

"
       | anArray index |
       anArray := Array new: self size.
       index := 0.
       self associationsDo: [:each | anArray at: (index := index + 1)
put: each].
       ^ anArray
"

Since Set does not have an 'associationsDo:' method  the corresponding
method in Collection is used which just invokes the 'do:' method which
is implemented in Set.

I felt that this was too inefficient so I implemented 'asArray' in Set
as follows:

"
                       | anArray newIndex |

       anArray := Array new: self size.
       newIndex := 1.
       1 to: array size do:  [:index |
                    | elem |
             (elem := array at: index)   ifNotNil: [
                   anArray at: newIndex put: elem.
                   newIndex := newIndex + 1].
             ].

       ^ anArray
"

This causes 'asArray' in class Dictionary to fail because it now
inherits the asArray method from Set instead of Collection
so I copied verbatum the asArray method from Collection to Dictionary.
So far everything appears to work.
I have the following questions:

1)  For me the cost of the extra code was worth the gain in efficientcy
    (I believe;  I didn't actually do any measurements).
    Given the importance of Sets and its subclasses (like Dictionary) is this
    modification not worth being in Squeak itself?
    Note that I find there are many places in Squeak where I would have
    reimplemented  a method rather then use inheritance so I am
    probably at variance with the Squeak community.
    Even so, the above case seems to me to be especially bad.
    Comments?

 2)  I was forced to reimplement the asArray method in Dictionary
      even though I used the exact same code as in Dictionary's
      super super class (Collection).
     I could have avoided this by implementing a method
     'skipSetAsArray' in Set  written:   "^super asArray"
     and implemented 'asArray' in Dictionary as
     "^self skipSetAsArray".  This is ugly but what I would have used
      had 'asArray' been a method containing a lot of code.
     Comments on this solution?

3)   An alternative to 2) would be if there was some way to control from which
     class a method is inherited.  Say, for example we could write 'asArray' in
     Dictionary as  "^super(Collection) asArray"  implying that
     the version of 'asArray' in the super class of Dictionary
     called Collection is to be used.
     This seems to me to be a simple and efficient solution.
     Comments?

4)  When I finally release my code, anybody who loads it will have my
     implementations of 'asArray' in Set and Dictionary added to their
     images.  If my code is not implemented properly it could break their
     images and even if it is implemented properly it could still break their
     images (if for example they created a subclass of Set which relies
     on inheritance to invoke the version of 'asArray' in Collection.
     i.e.  they could get burned the same way Dictionary was).
     How am I expected to deal with these issues?
        a) Undo my changes?
        b) Work to have my changes made a permanent part of Squeak?
        c) Document the possible effects of this change so the user
            will be aware of it (if s(he) reads the documentation that is).
        d) Let the users figure it out for themselves (probably faster than
            reading the documentation especially since only a small portion
            of users are likely to be affected).
     Perhaps there thould be a standard special section in
     documentation where this kind of change is noted.

Thanks in advance for  any comments received.

Ralph Boland



More information about the Squeak-dev mailing list