[sugar] [PATCH] Avoid duplicates in the bundle registry

[Michael Stone]

On Wed, May 28, 2008 at 10:46:45AM +0200, Tomeu Vizoso wrote:
> On Tue, May 27, 2008 at 6:44 PM, Michael Stone <michael at laptop.org> wrote:
> > On Tue, May 27, 2008 at 09:15:39AM +0200, Tomeu Vizoso wrote:
> >> +        for bundle in self._bundles:
> >> +            if new_bundle.get_bundle_id() == bundle.get_bundle_id():
> >
> > Why are we performing repeated linear search instead of storing bundles
> > in a datastructure with sub-linear containment lookups (e.g. a set or a
> > hashtable)?
> 
> Because the patch is simpler this way. Why do you think that using a
> set or a table might be better here?

Because my algorithm (store a dict mapping bundle id to biggest version
yet seen) makes the same decisions yours does with one hash table lookup
instead of O(n) string comparisons? 

NB: naive implementations (i.e. where you decide to create both the list
and the dict) will have creation and maintenance costs in space and time
which could exceed the benefit gained by from cheaper lookups. I haven't
studied the code in enough detail to see what the most appropriate data
structures are. 

Question: does our implementation ever pay attention to the order of the
entries in self._bundles?

> > Why exclude old bundle versions?
> 
> Eben's new design makes very clear that several versions of the same
> bundle need to be installed and the user can manage them as wanted.
> When I started implementing this some months ago, I found some
> problems with identifying bundles other than by its bundle_id. See:
> 
> http://lists.laptop.org/pipermail/sugar/2008-April/004893.html
> 
> I even proposed some patches that partially address this:
> 
> http://lists.laptop.org/pipermail/sugar/2008-April/004894.html
> http://lists.laptop.org/pipermail/sugar/2008-April/004895.html
> http://lists.laptop.org/pipermail/sugar/2008-April/004896.html
> 
> Those patches were not reviewed because it was considered better to
> wait for the discussion about bundle identification to be settled.

Heh. Fair enough.

> > Have you reviewed any of the bundle commentaries that Eben, Jameson, and
> > I have been writing?
> >
> >  http://wiki.laptop.org/go/User:Mstone/Commentaries/Bundles_1
> >  http://wiki.laptop.org/go/User:Mstone/Commentaries/Bundles_2
> 
> Haven't had time to fully read. Can someone summarize the conclusion?

I'll see if I can come up with something for you.

Michael