New List Type

classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

New List Type

Rob Eden
Hi guys -

We've come across a need (and an idea for) a new map at work. Here's  
the skinny:

I have an object with an ID that's a long. I need to have an  
EventList of these. I don't care about order but I need inserts,  
lookups and deletion to be fast. Basically I need a map, but I need  
an EventList. :-) In previous versions we've been using a  
TLongObjectHashMap, but now we need an EventList.

I started out using a SortedList because I figured the lookups would  
be fast. They were -of course- faster than a linear search, but not  
fast enough. Here are the results of 30,000 inserts and then 50,000  
random lookups:
     Trove map:  24 ms
     SortedList: 1280 ms

Not gonna cut it. So, we came up with MapList.

Basically it's a list, but uses a MapListKeyFactory to produce keys  
for the objects being inserted. Once we have that, a map can be kept  
containing the positions of the objects in the list. Since order is  
not important, we can do fast modifications (see attached diagram).
     MapList (backed by HashMap): 155 ms

Better. But I can do ever better than that! :-)

One thing we're still sacrificing by no longer using Trove is that we  
have to create Long's a lot. So, I've implemented MapListDriver which  
looks like this (javadocs omitted, see attached code):

     public abstract class MapListDriver {
         protected abstract int indexOf( Object object,  
MapListKeyFactory key_factory );
         protected abstract int indexOfKey( Object key,  
MapListKeyFactory key_factory );
         protected abstract void updatePosition( Object object, int  
new_index,
             MapListKeyFactory key_factory );
         protected abstract int remove( Object object,  
MapListKeyFactory key_factory );
         protected abstract void clear();
     }

By allowing that driver class to be flexible, we can allow  
implementations that can work entirely on primitives. Here are the  
results:
     MapList (backed by TLongIntHashMap): 95 ms

To recap the results, let me now show the results using 100,000  
inserts and then 500,000 random lookups (note: this is after  
repeating a few times to warm up the compiler):

     Trove map:         284
     SortedList:        12201 (43.0x)
     MapList (HashMap): 1049  ( 3.7x)
     MapList (Trove):   588   ( 2.0x)

As you can see, there's still a little bit of overhead, but it's MUCH  
better.

So, the questions are:
     1) Do you want it?
     2) Do you like the basic design?
     3) How do you want me to package it? These are the
        basic files:
         - MapList
         - MapListKeyFactory (ifc to get key for Object)
         - MapListDriver     (ifc for the smarts)
         - BasicMapListDriver (default implementation)
     4) Class name preferences? (not that you guys ever
        feel strongly about names, wink wink...)

I've attached a diagram to show how it works and source code. NOTE:  
the source code is not release quality. It needs to be documented  
better, cleaned up and unit tested. It's mainly prototype code right  
now. Go easy on me. ;-)

Rob

--

"Let your heart soar as high as it will.
  Refuse to be average."
                            - A. W. Tozer


---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

Reply | Threaded
Open this post in threaded view
|

Re: New List Type

Rob Eden
*ahem* Sorry, here are the attachments.

You'll need Trove (http://trove4j.sourceforge.net/) to compile the  
performance test and Trove implementation of the driver.

Rob

Rob

MapList.pdf (61K) Download Attachment