Decision tree ensemble compilation

• US 8,918,771 B2
• Filed: 09/25/2012
• Issued: 12/23/2014
• Est. Priority Date: 09/25/2012
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Inventors: Dunn, Jeffrey S., Sagula, Rafael L.
• Primary Examiner(s): Nguyen, Phillip H
• Application Number:
  US13/626,340
• Publication Number:
  US 20140089908A1
• Time in Patent Office: 819 Days
• Field of Search: 717/139, 717/151, 717/153, 717/158
• US Class Current: 717/151
• CPC Class Codes: G06F 8/41 Compilation
• CPC Class Codes: G06F 8/443 Optimisation
• CPC Class Codes: G06F 9/45508 Runtime interpretation or emulation, e g. emulator loops, bytecode interpretation
• CPC Class Codes: G06F 9/45516 Runtime code conversion or optimisation

Abstract

In one embodiment, a decision tree is evaluated in interpreted mode while statistics are collected. The decision tree is then represented as source code, and each decision in the decision tree is annotated with instructions determined based on the collected statistics. The source code is compiled into machine code, and the machine code is optimized based on the instructions annotating each decision in the decision tree.

Claims

1. A method comprising, by a computing device:

evaluating a decision tree in interpreted mode;

collecting statistics while the decision tree is evaluated in interpreted mode;

representing the decision tree as source code;

annotating each decision in the decision tree with instructions determined based on the collected statistics; and

compiling the source code into machine code, the machine code being optimized based on the instructions annotating each decision in the decision tree.

2. The method of claim 1, wherein the decision tree is evaluated multiple times in interpreted mode.

3. The method of claim 1, wherein the collected statistics comprise, for each decision in the decision tree having a plurality of possible outcomes, a probability that each possible outcome of the decision is actually realized while the decision tree is evaluated in interpreted mode.

4. The method of claim 3, wherein the compiling the source code into the machine code comprises:

for each decision in the decision tree, ordering the machine code representing the plurality of possible outcomes of the decision based on the total number of times each possible outcome of the decision is actually realized while the decision tree is evaluated in interpreted mode.

5. The method of claim 1, further comprising verifying the machine code by:

evaluating the decision tree in interpreted mode;

executing the machine code; and

comparing result of executing the machine code with result of evaluating the decision tree in interpreted mode.

6. The method of claim 5, wherein the machine code is verified multiple times.

7. The method of claim 1, further comprising:

executing the machine code in place of evaluating the decision tree in interpreted mode.

8. The method of claim 1, wherein the decision tree is a part of a decision tree ensemble comprising a plurality of decision trees, and each decision tree in the decision tree ensemble is represented as machine code.

9. The method of claim 8, further comprising:

ranking a set of search results by executing the machine code representing one or more decision trees in the decision tree ensemble.

10. One or more computer-readable non-transitory storage media embodying software that is operable when executed to:

evaluate a decision tree in interpreted mode;

collect statistics while the decision tree is evaluated in interpreted mode;

represent the decision tree as source code;

annotate each decision in the decision tree with instructions determined based on the collected statistics; and

compile the source code into machine code, the machine code being optimized based on the instructions annotating each decision in the decision tree.

11. The media of claim 10, wherein the decision tree is evaluated multiple times in interpreted mode.

12. The media of claim 10, wherein the collected statistics comprise, for each decision in the decision tree having a plurality of possible outcomes, a probability that each possible outcome of the decision is actually realized while the decision tree is evaluated in interpreted mode.

13. The media of claim 12, wherein the software operable when executed to compile the source code into the machine code comprises software that is operable when executed to:

for each decision in the decision tree, order the machine code representing the plurality of possible outcomes of the decision based on the total number of times each possible outcome of the decision is actually realized while the decision tree is evaluated in interpreted mode.

14. The media of claim 10, wherein the software is further operable when executed to verify the machine code by performing operations to:

evaluate the decision tree in interpreted mode;

execute the machine code; and

compare result of executing the machine code with result of evaluating the decision tree in interpreted mode.

15. The media of claim 10, wherein the software is further operable when executed to:

execute the machine code in place of evaluating the decision tree in interpreted mode.

16. The media of claim 10, wherein the decision tree is a part of a decision tree ensemble comprising a plurality of decision trees, and each decision tree in the decision tree ensemble is represented as machine code.

17. The media of claim 16, wherein the software is further operable when executed to:

rank a set of search results by executing the machine code representing one or more decision trees in the decision tree ensemble.

18. The media of claim 10, wherein the machine code is verified multiple times.

19. A system comprising:

one or more processors; and

a memory coupled to the processors comprising instructions executable by the processors, the processors being operable when executing the instructions to;

evaluate a decision tree in interpreted mode;

collect statistics while the decision tree is evaluated in interpreted mode;

represent the decision tree as source code;

annotate each decision in the decision tree with instructions determined based on the collected statistics; and

compile the source code into machine code, the machine code being optimized based on the instructions annotating each decision in the decision tree.

20. The system of claim 19, wherein the decision tree is evaluated multiple times in interpreted mode.

21. The system of claim 19, wherein the collected statistics comprise, for each decision in the decision tree having a plurality of possible outcomes, a probability that each possible outcome of the decision is actually realized while the decision tree is evaluated in interpreted mode.

22. The system of claim 21, wherein the processors being operable when executing the instructions to compile the source code into the machine code comprises the processors being operable when executing the instructions to:

for each decision in the decision tree, order the machine code representing the plurality of possible outcomes of the decision based on the total number of times each possible outcome of the decision is actually realized while the decision tree is evaluated in interpreted mode.

23. The system of claim 19, the processors further being operable when executing the instructions to verify the machine code by executing instructions to:

evaluate the decision tree in interpreted mode;

execute the machine code; and

compare result of executing the machine code with result of evaluating the decision tree in interpreted mode.

24. The system of claim 23, wherein the machine code is verified multiple times.

25. The system of claim 19, the processors further being operable when executing the instructions to:

execute the machine code in place of evaluating the decision tree in interpreted mode.

26. The system of claim 19, wherein the decision tree is a part of a decision tree ensemble comprising a plurality of decision trees, and each decision tree in the decision tree ensemble is represented as machine code.

27. The system of claim 26, the processors further being operable when executing the instructions to:

rank a set of search results by executing the machine code representing one or more decision trees in the decision tree ensemble.