Hash table dispatch mechanism for interface methods

• US 20020108107A1
• Filed: 05/16/2001
• Published: 08/08/2002
• Est. Priority Date: 11/16/1998
• Status: Active Grant

• Current Assignee: RPX Corporation
• Original Assignee: Insignia Solutions Plc (America's Suppliers, Inc.)
• Inventors: Wynn, Michael John, Alec Dias, Blaise Abel, Rautenbach, Keith, Darnell, Stephen, Plummer, Wayne, Sexton, Jeremy James, Kramskoy, Jeremy Paul, Charnell, William Thomas, Thomas, Stephen Paul, Guthrie, Philippa Joy
• Granted Patent: US 6,862,728 B2
• Time in Patent Office: Days
• US Class Current: 717/153
• 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

10. A computer system comprising:

a program having a plurality of interface Methods;

a plurality of dispatch tables;

an interface hash table for at least one of the plurality of dispatch tables, the interface hash table having a pointer as an index for one of the group consisting of a specific location in the corresponding dispatch table and one interface Method of the program.

11. A computer system as claimed in claim 10, further comprising a recovery Method for resolving conflicts when two or more slots in the interface hash table contain clashing values.

12. 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.

13. 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.

14. 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.

16. A computer system as claimed in claim 15, further comprising a recovery Method for resolving conflicts when two or more slots in the interface hash table contain clashing values.

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

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

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

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

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

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

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

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

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

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

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

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

15. A computer system comprising:

a program having a plurality of interface Methods;

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;

a plurality of dispatch tables;

an interface hash table for at least one of the plurality of dispatch tables, the interface hash table having a pointer as an index for one of the group consisting of a specific location in the corresponding dispatch table and one interface Method of the program.

27. A method of invoking an interface Method for an object of a program, the method comprising:

creating a plurality of dispatch tables;

creating an interface hash table for at least one of the plurality of dispatch tables, the interface hash table having a pointer as an index for one of the group consisting of a specific location in the corresponding dispatch table and a Method of the program, the interface hash table having an address and a plurality of slots, each slot having a hash value related to one interface Method; and

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

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

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

performing a virtual invocation.

30. A method of compiling an object-oriented language program, the program having a plurality of interface Methods, the method 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;

compiling the one fragment of the program;

creating a plurality of dispatch tables;

creating an interface hash table for at least one of the plurality of dispatch tables, the interface hash table having a pointer as an index for one of the group consisting of a specific location in the corresponding dispatch table and one interface Method of the program; and

when the program executes an instruction requiring one of the interface Methods, looking up the one of the interface Methods using the interface hash table.

1. A method of reducing dispatch times during the execution of an object-oriented language program, the program having a plurality of interface Methods, the method comprising:

creating a plurality of dispatch tables;

creating an interface hash table for at least one of the plurality of dispatch tables, the interface hash table having a pointer as an index for one of the group consisting of a specific location in the corresponding dispatch table and one interface Method of the program; and

when the program executes an instruction requiring one of the interface Methods, looking up the one of the interface Methods using the interface hash table.

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 number 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.

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

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

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

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

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

36. A method as claimed in claim 30, 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.

37. A method as claimed in claim 30, further comprising performing an exception check.

38. A method as claimed in claim 37, further comprising performing a code optimization.

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

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

41. A method as claimed in claim 40, further comprising passing control to an interpreter.

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

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

33-1. A method as claimed in claim 30, further comprising running the compiler on a thread that is separate from the thread of the interpreter.