Binary compatibility and finding compiled classes

[Andrew Haley]

Bryce McKinlay writes:
 > Andrew Haley wrote:
 > 
 > >Bryce McKinlay writes:
 > > > >
 > > > Exactly, the code generated by the compiler already knows which otable 
 > > > slot to use. The hashtable would be used to speed up the look-up of 
 > > > methods when the runtime is filling out the tables when linking a class. 
 > > > Currently, to go from a {ClassName,MethodName,Signature} to a _Jv_Method 
 > > > requires linear searching through the class hierarchy. This would speed 
 > > > up method lookups in reflection and JNI, too. Personally, I'm not 100% 
 > > > sure that the gains from hash look-ups will outweigh the cost and extra 
 > > > memory of generating the hash tables, but its definitely something we 
 > > > need to keep an eye on - linking needs to be as efficient as possible.
 > >
 > >I'm not sure these are comparable, because the hash tables for class
 > >and method lookups can be generated at compile time and don't need to
 > >occupy significantly more memory than the linear lists we have at the
 > >moment.  As far as I can tell, except for the time taken to write the
 > >code this is a win-win.
 > 
 > OK - but can a hashtable really be made to take up no more space than a 
 > list and still be an efficient hash?

Almost, yes.  You need an auxiliary table, but it's far smaller than
the symbols.

 > Wouldn't it be just as efficient to have the compiler emit the
 > methods in sorted order, and do a binary search?

I don't think so.  Say you have 32 methods: you'll expect to find the
right one with 4 probes with a binary search but usually only 1 or 2
probes with a hash.  There's the cost of computing that hash, but it's
reading memory and doing the comparisons that hurts.

Andrew.