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
