setIndexFromMember followup (was Re: Lists

[Paul E. Johnson]

"Marcus G. Daniels" wrote:
> 
> >>>>> "D3" == donalson  <address@hidden> writes:
> 
> D3> This overwrites the previous list link and screws
> D3> up any list instance into which the agent1 instance has previously
> D3> been inserted.
> 
> D3> Yea or Nay?
> 
> Yeperooni.  member_t is the glue that holds a given list together, and
> each list needs its own glue.
> 
Ok, I understood this.  What I want is a better understanding of when
doing the setIndexFromMemberLoc: is going to make a difference and when
it is a bad idea.

When it makes a difference: when using an index to find and remove
specific objects from a list.

A command like [list remove: someParticularObject] is just as slow with
a regular list or one with the setIndexFromMemberLoc:. WHen Doug
observed that [remove: anObject] in the source for List was still O(n),
this is what he discovered.  

However, operations with indexes are accelerated.  Anything should work
faster when it is required to find a specific object. Not only [index
remove] but also  [index findNext: particularObject].  
I'm looking in the swarm source for how the index works differently
depending on whether setIndexFromMemberLoc: is defined, but I've not
found it yet. Since Marcus's example does work, I believe it is true.

Now, when is this a bad thing to do?  

1. When objects of different classes are to be added to the list, they
must have the member_t variable in exactly the same spot. Or else the
index will be no good. Correct?

2. Is there a heavy memory usage penalty to setIndexFromMemberLoc:?  I
don't think so.  For storage of one member_t, an array of 2 pointers is
allocated in each object.  If there are millions of objects, I guess
that would add up.  

3. Most Swarm collections objects will allow an object to be added to a
list more than once. The setIndexFromMemberLoc: will give strange
results, depending on the type of collection.


I think there was something in some of the older notes about this, and
mainly I'm just writing it to see if I understand and to leave the
record clear on this topic.  Specifically, one should not expect a
speedup from [list remove: anObject] but rather from [index remove]
defined from the same list.

-- 
Paul E. Johnson                         email: address@hidden
Dept. of Political Science              http://lark.cc.ukans.edu/~pauljohn
University of Kansas                    Office: (785) 864-9086
Lawrence, Kansas 66045                  FAX: (785) 864-5700

                  ==================================
   Swarm-Support is for discussion of the technical details of the day
   to day usage of Swarm.  For list administration needs (esp.
   [un]subscribing), please send a message to <address@hidden>
   with "help" in the body of the message.