Look at Digitalk's VSE 3.1 and above.  It does exactly what you asked for.

-----Original Message-----
From: Stephen Pair [mailto:spair at advantive.com]
Sent: Friday, March 31, 2000 8:09 AM
To: squeak at cs.uiuc.edu
Subject: RE: Musings on Identity


On a related note, how about splitting the collection hieararchy in two, an
implementation hiearcy, and an interface hierarchy.  Since the optimal
implementation of a collection is often dependent on it's size.  It would be
nice to have a set of collection classes, whose instances morph their
implementation (under specified criteria) into something more appropriate
for the characteristics of the collection.

Maybe something like:

Dictionary
	SmallDictionary
	MediumDictionary
	LargeDictionary
	HugeDictionary
	MutableDictionary

Of course, then what do you do with the existing subclasses of Dictionary
(split hieararchy problem).

Someone told me that IBM Smalltalk was like this early on, but dropped it
for some reason.

- Stephen


-----Original Message-----
From: Georg Gollmann [mailto:georg.gollmann at tuwien.ac.at]
Sent: Friday, March 31, 2000 8:58 AM
To: squeak at cs.uiuc.edu
Subject: Musings on Identity


Some ideas for Squeak 3 :-)

Currently the object header contains a 12 bit field for an identity hash.
This is too little and too much at the same time: it takes valuable space in
the object header and it is insufficient for large IdentitySets
or -Dictionaries.

Therefore how about ditching this field alltogether and reimplementing
IdentitySets as arrays sorted by oop ?

Lookup should be reasonably fast using binary search.
Since the garbage collector only shifts objects but does not shuffle them,
the sort order would not be affected by compaction.
Become operations would necessitate resorting of affected sets however.
IdentityDictionaries could be built using parallel arrays for keys and
values.
Insertion and deletion might become slow for very large sets. If this really
becomes an issue those sets could be split into a sorted array of subsets
with a two stage lookup.

Has this been done before ?
Any flaws in the resoning ?

Georg
--
----
Dipl.Ing. Georg Gollmann                TU-Wien, Zentraler Informatikdienst
                                        Wiedner Hauptstr. 8-10
phon:(+43-1) 58801 - 42022              A-1040 Wien
fax: (+43-1) 58801 - 42099
mail:gollmann at zid.tuwien.ac.at
http://macos.tuwien.ac.at/Gollmann.html