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). 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] --------------------------------------------------------------------- To unsubscribe from this list, please visit: http://xircles.codehaus.org/manage_email
