to be honest, I forgot about hashing altogether .. embarassed smile :-) ... but, might be good to think through / experiment a bit ... -s.
On Mon, Aug 10, 2009 at 10:07 AM, Thomas E Enebo <[email protected]>wrote: > On Mon, Aug 10, 2009 at 10:04 AM, Thomas E Enebo<[email protected]> > wrote: > > Actually I was interested in trie's because Clojure implements their > > main map data structure as an immutable trie. The best part is when > > Clojure adds a new element to a trie it creates a new root node (with > > some additional children nodes) and then returns the new trie (old > > root may still be retained by something). So his impl ends up having > > multiple roots sharing same data because he makes the structure > > immutable. If we used a trie internally for method storage we could > > simplify method updates (from a concurrency standpoint) by using the > > same technique. We would only lock on an object for writes and reads > > would be lock-free 100% of the time (concurrenthashmap is <100%). > > > > I am surprised you think that the lookup would be faster than a > > hashing algorithm though. I thought that most hashes only used > > basically one name comparison + cheap math (ignoring colliding bucket > > costs)? This is encouraging to me if true (most pages on tries imply > > it can be a little slower than hashing at times). > > Hmmm, I hit send too soon perhaps.... :) > > Actually perhaps if the trie is sparse you will do very few traversals > with one big strcmp at the end (which if interned could be an object > identity check). This could be faster I think in many cases since > there are very few method in classes typically... > > > > > Speeding up lookup will not affect anything which has an inline cache, > > but we have many internal calls without any inline caches. So this > > could help that OR we could try and come up with a way of adding > > inline caches for those sites... > > > > -Tom > > > > On Mon, Aug 10, 2009 at 9:54 AM, Subramanya Sastry<[email protected]> > wrote: > >> Just a quick note so that I don't forget it. > >> > >> Not sure how method lookup is implemented, but it occured to me that a > >> simple optimization might speedup lookup. This is not a big deal when > >> inline caching is implemented, but nevertheless something worth > considering. > >> > >> i.e. given a call "o.foo(args)", normally, you might fetch C = o.class, > and > >> then fetch C.method table and compare "foo" with the method names in > some > >> order. > >> > >> 1. Maintain the method table as a sorted array of method names and do a > >> binary search (taking care to keep the table sorted) > >> 2. Create a trie of method names specifically for method lookup. This > trie, > >> if it implements collapsing of single-character chains (a -> t -> t -> r > -> > >> .. -> e to "attribute") to prefix strings, can give you the method you > want > >> fairly quickly with at most 2 full-string comparisons, and usually much > >> faster than that. > >> > >> Not sure this will give you much performance benefit, but using a trie > for > >> method lookup is a fairly easy optimization. > >> > >> Subbu. > >> > > > > > > > > -- > > blog: http://blog.enebo.com twitter: tom_enebo > > mail: [email protected] > > > > > > -- > blog: http://blog.enebo.com twitter: tom_enebo > mail: [email protected] > > --------------------------------------------------------------------- > To unsubscribe from this list, please visit: > > http://xircles.codehaus.org/manage_email > > >
