Hash table dispatch mechanism for interface methods

• US 6,862,728 B2
• Filed: 05/16/2001
• Issued: 03/01/2005
• Est. Priority Date: 11/16/1998
• Status: Expired due to Term

• Current Assignee: RPX Corporation
• Original Assignee: Esmertec AG (Myriad Group AG)
• Inventors: Guthrie, Philippa Joy, Dias, Blaise Abel Alec, Plummer, Wayne, Charnell, William Thomas, Darnell, Stephen, Thomas, Stephen Paul, Rautenback, Keith, Wynn, Michael John, Sexton, Jeremy James, Kramskoy, Jeremy Paul
• Primary Examiner(s): Das, Chameli C.
• Application Number:
  US09/859,133
• Publication Number:
  US 20020108107A1
• Time in Patent Office: 1,385 Days
• Field of Search: 717/139, 717/140, 717/148, 717/158, 717/151, 717/162, 717/165, 717/167, 717/166, 717/153, 717/765, 717/136, 717/138, 719/328, 719/332, 719/331, 719/330, 707/11, 365/733, 712/204, 712/214
• US Class Current: 717/148
• CPC Class Codes: G06F 11/3612 by runtime analysis performance monitoring G06F11/3466
• CPC Class Codes: G06F 12/0269 Incremental or concurrent garbage collection, e.g. in real-time systems G06F12/0261 takes precedence
• CPC Class Codes: G06F 2209/481 Exception handling
• CPC Class Codes: G06F 8/4442 Reducing the number of cache misses; Data prefetching cache prefetching G06F12/0862
• CPC Class Codes: G06F 8/445 Exploiting fine grain parallelism, i.e. parallelism at instruction level run-time instruction scheduling G06F9/3836
• CPC Class Codes: G06F 9/4484 Executing subprograms
• CPC Class Codes: G06F 9/449 Object-oriented method invocation or resolution
• CPC Class Codes: G06F 9/4491 Optimising based on receiver type
• CPC Class Codes: G06F 9/455 Emulation; Interpretation; Software simulation, e.g. virtualisation or emulation of application or operating system execution engines
• CPC Class Codes: G06F 9/45516 Runtime code conversion or optimisation
• CPC Class Codes: G06F 9/4812 by interrupt, e.g. masked
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99956 File allocation

Abstract

A hash table dispatch mechanism for interface Methods. The mechanism reduces dispatch times during the execution of an object-oriented language program. An interface hash table having a pointer as an index for either a specific location in a corresponding dispatch table or an interface Method of the program is created for a dispatch table. The interface hash table has an address and a plurality of slots having a hash value related to an interface Method. The mechanism includes a recovery Method for resolving conflicts when two or more slots in the interface hash table contain clashing values.

Claims

1. A method of reducing the dispatch times of a virtual dispatch during the execution of an object-oriented language program in a system having a host machine and a virtual machine, the program having interface Methods and functions including individual functions and associated functions associated with the interface Methods, the method comprising:

providing hierarchical relationships between functions represented by super class and sub class definitions of the functions, wherein super class functions have super class attributes, and sub class functions have inherited sub class attributes inherited from a corresponding super class function and non inherited class attributes not inherited from a super class function;

creating a plurality of dispatch tables including interface Methods and individual functions having both inherited attributes and non inherited attributes;

creating an interface hash table for a dispatch table, the interface hash table having a pointer as an index for a selected one of an interface Method or an individual function and recovery and search routines for recovering from a hash table collision and searching a list of functions;

the dispatch table receiving and re-routing the call to the interface hash table during a call of a virtual dispatch requiring an interface Method or requiring an individual function;

determining whether a collision has occurred in the hash table in response to the call and selectively executing the recovery routine or the fallback routine in response to the collision determination;

the interface hash table selecting one of the interface Methods or one of the individual functions to provide a selected routine; and

executing the selected routine in accordance with both the inherited attributes and the non inherited attributes.

2. A method as claimed in claim 1, further comprising determining whether two or more hash values in the interface hash table conflict.

3. A method as claimed in claim 2, further comprising calling a recovery Method when two or more hash values in the interface hash table conflict.

4. A method as claimed in claim 1, further comprising creating hash values that reduce the frequency of conflicts between two or more hash values in the interface hash table.

5. A method as claimed in claim 4, further comprising creating hash values for the interface hash table by deriving pseudo-random values based on the attributes of the interface Methods.

6. A method as claimed in claim 1, further comprising choosing a starting hash value and allocating other hash values sequentially from the starting hash value.

7. A method as claimed in claim 1, further comprising configuring the interface hash table to contain one of the group of a slot numbers of the dispatch table and function pointers.

8. A method as claimed in claim 1, further comprising defining each class of the program and a set of the interface Methods implemented by each class.

9. A method as claimed in claim 8, further comprising creating a fixed size interface hash table for each class, each fixed size interface hash table mapping an interface Method hash value to a dispatch table index.

10. A method as claimed in claim 1, in a system comprising:

a compiler for compiling code of the program, the compiler arranged to compile a fragment of the code of the program;

a compiler manager coupled to the compiler;

an interpreter for interpreting the code of the program;

the interpreter coupled to an execution history recorder;

the execution history recorder arranged to record the number of times a fragment of code is executed, to record information regarding execution of fragments of code;

and to alert the compiler manager when a fragment of code has been executed a threshold number of times.

11. A computer system as claimed in claim 10, wherein the interface hash table includes values derived from pseudo-random values based on attributes of the interface Methods.

12. A computer system as claimed in claim 10, wherein the interface hash table includes a starting hash value and a plurality of other hash values allocated sequentially from the starting hash value.

13. A computer system as claimed in claim 10, wherein the interface hash table includes one of the group consisting of a slot number of the dispatch table and function pointers.

14. A computer system as claimed in claim 10, wherein the execution history recorder is arranged to record a path of execution from a first fragment to a second fragment.

15. A computer system as claimed in claim 10, wherein the system is multi-threaded and the compiler runs on a thread separate from the thread executing the code.

16. A computer system as claimed in claim 10, further comprising a queue coupled to the compiler.

17. A computer system as claimed in claim 10, wherein the compiler, compiler manager and interpreter are part of the virtual machine.

18. A computer system as claimed in claim 10, further comprising a memory manager that monitors memory available to the compiler.

19. A computer system as claimed in claim 18, further comprising a deleter coupled to the memory manager.

20. A computer system as claimed in claim 18, wherein only dominant path or near dominant path fragments of code are compiled.

21. A method of reducing the dispatch times of a virtual dispatch during the execution of an object-oriented language program in a system having a host machine and a virtual machine, the program having interface Methods and functions including individual functions and associated functions associated with the interface Methods, the method comprising:

providing hierarchical relationships between functions represented by super class and sub class definitions of the functions, wherein super class functions have super class attributes, and sub class functions have inherited sub class attributes inherited from a corresponding super class function and non inherited class attributes not inherited from a super class function;

creating a plurality of dispatch tables including interface Methods and individual functions having both inherited attributes and non inherited attributes;

creating an interface hash table for a dispatch table, the interface hash table having a pointer as an index for a selected one of an interface Method or an individual function and recovery and search routines for recovering from a hash table collision and searching a list of functions, an address and a plurality of slots, each slot having a hash value related to one interface Method or one individual friction;

the dispatch table receiving and re-routing the call to the interface hash table during a call of a virtual dispatch requiring an interface Method or requiring an individual function;

determining whether a collision has occurred in the hash table in response to the call and selectively executing the recovery routine or the fallback routine in response to the collision determination;

loading the address of the interface hash table in a memory location;

retrieving a slot number for a particular interface Method or individual function using its respective hash value;

loading a unique identifier for a destination interface Method and individual function into a register; and

performing a virtual invocation using its respective hash value in accordance with the inherited and non inherited attributes.

22. A method as claimed in claim 21, wherein the interface hash table is included in at least one of the plurality of dispatch tables.

23. A method as claimed in claim 21, wherein the interface hash table includes Method pointers.

24. A method as claimed in claim 21, comprising:

establishing an execution threshold;

executing a number of fragments of the program;

recording the number of times each of the fragments of the program is executed;

queuing one fragment of the program for compilation when the number of times the one fragment of the program has been executed matches the threshold; and

compiling the one fragment of the program.

25. A method as claimed in claim 24, further comprising adjusting the threshold after it is established.

26. A method as claimed in claim 24, further comprising monitoring memory available to the compiler.

27. A method as claimed in claim 24, further comprising deleting code from memory to meet the requirements of the compiler.

28. A method as claimed in claim 24, further comprising running the compiler on a thread that is separate from the thread of the interpreter.

29. A method as claimed in claim 24, further comprising recording a transfer of control into one fragment of code and a transfer out of the one fragment of code.

30. A method as claimed in claim 24, further comprising searching cache for preexisting compiled versions of fragments of code.

31. A method as claimed in claim 24, wherein the computer code includes at least one interface Method, and at least one of the fragments of code includes less than the entire at least one Method.

32. A method as claimed in claim 24, further comprising performing an exception check.

33. A method as claimed in claim 24, further comprising performing a code optimization.

34. A method as claimed in claim 24, further comprising interpreting exception code when an exception occurs.

35. A method as claimed in claim 24, further comprising establishing a link to a bailout device.

36. A method as claimed in claim 35, further comprising passing control to an interpreter.

37. A method as claimed in claim 24, further comprising updating condition states.

38. A method as claimed in claim 37, further comprising interpreting exception code after updating the condition states.