Fred, On Wednesday 21 March 2007 17:05, Fred Dushin wrote: > I'm not sure about that. TreeMaps are pretty lightweight -- they > only allocate an Entry (cons cell, effectively) for each entry in the > map. In-order traversals are O(n); lookups are O(lgn) (probably > \Theta(lgn)), but lookups are the degenerate case. > > I actually just did a little performance comparison -- Trees vs > Hashes, and for anything smaller than 10-15 entries, the comparative > cost of lookup is negligible, and the memory footprint is smaller > with sortable collections. Anyone want the test code? Just ask.
I'm more concerned with the cost of the iterators of the "Thread Safe" variants of the various types: (the value set iterator on the maps) CopyOnWriteArrayList CopyOnWriteArraySet ConcurrentHashMap Collections.syncronizedMap(new TreeMap()) Technically, I'd also argue that the TreeMap and HashMaps are NOT appropriate. The Lists provide and order of how the stuff are added into the chain. Thus, the only map that would really meet that is: Collections.syncronizedMap(new LinkedHashMap()) Dan > > -Fred > > On Mar 21, 2007, at 4:29 PM, Daniel Kulp wrote: > > On Wednesday 21 March 2007 15:42, Fred Dushin wrote: > >> Someone else mentioned that it might be nice to have he notion of > >> an interceptor id, which I'd fully agree with, so that you could do > >> a lookup by id. Your interceptor lists are then just (sortable) > >> maps (or multimaps, as the case may be), and lookup can be done in > >> O(lg n). But that's a pretty disruptive change to the whole > >> architecture. OTOH, better to do it now than once the cat is out > >> of the bag... > > > > It also has nasty performance impacts as the traversals would be > > much more expensive. Since those traversals happen on EVERY SINGLE > > message, > > that would be really bad. Also, maps use significantly more memory > > than the ArrayLists do. > > > > My only real thought on this would be to change from List to Set > > and use > > the CopyOnWriteArraySet. That keeps the performance of the > > ArrayList for the traversals. It also gives you the guarantee of > > uniqueness in the Set. (providing you write an appropriate > > .equals(...) method) The main cost is more expensive "add", > > "remove", and "contains" methods. > > However, that should be a startup cost in 95% of the cases. > > > > Anyway, it's a thought. > > > > -- > > J. Daniel Kulp > > Principal Engineer > > IONA > > P: 781-902-8727 C: 508-380-7194 > > [EMAIL PROTECTED] > > http://www.dankulp.com/blog -- J. Daniel Kulp Principal Engineer IONA P: 781-902-8727 C: 508-380-7194 [EMAIL PROTECTED] http://www.dankulp.com/blog
