METHODS, SYSTEMS, AND ARTICLES OF MANUFACTURE TO AUTONOMOUSLY SELECT DATA STRUCTURES

• US 20200134458A1
• Filed: 12/23/2019
• Published: 04/30/2020
• Est. Priority Date: 12/23/2019
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Gottschlich, Justin
• Granted Patent: US 11,694,077 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 17/18 for evaluating statistical data , e.g. average values, frequency distributions, probability functions, regression analysis forecasting specially adapted for a specific administrative, business or logistic context G06Q10/04
• CPC Class Codes: G06F 18/213 Feature extraction, e.g. by transforming the feature space; Summarisation; Mappings, e.g. subspace methods
• CPC Class Codes: G06F 18/214 Generating training patterns; Bootstrap methods, e.g. bagging or boosting
• CPC Class Codes: G06F 18/217 Validation; Performance evaluation; Active pattern learning techniques
• CPC Class Codes: G06F 8/30 Creation or generation of source code
• CPC Class Codes: G06F 8/427 Parsing
• CPC Class Codes: G06N 20/10 using kernel methods, e.g. support vector machines [SVM]
• CPC Class Codes: G06N 3/044 Recurrent networks, e.g. Hopfield networks
• CPC Class Codes: G06N 3/08 Learning methods
• CPC Class Codes: G06N 5/04 Inference or reasoning models

Abstract

Methods, systems, and articles of manufacture to autonomously select data structures are disclosed. An example apparatus includes an ordinal assigner to assign training code operations to respective first ordered values, and assign candidate data structure types to respective second ordered values, a filter generator to, for a first instruction of the training code operations, generate a Bloom filter bit vector pattern based on (a) one of the first ordered values, (b) one of the second ordered values corresponding to a first one of the candidate data structure types, and (c) a size of the first instruction, a label generator to generate a first model training input feature vector based on the Bloom filter bit vector pattern, data corresponding to the first instruction, and a performance metric of the first one of the candidate data structure types, and a neural network manager to train the data structure selection model with the first model training input feature vector.

Claims

1. An apparatus to train a data structure selection model, the apparatus comprising:

an ordinal assigner to;

assign training code operations to respective first ordered values; and

assign candidate data structure types to respective second ordered values;

a filter generator to, for a first instruction of the training code operations, generate a Bloom filter bit vector pattern based on (a) one of the first ordered values, (b) one of the second ordered values corresponding to a first one of the candidate data structure types, and (c) a size of the first instruction;

a label generator to generate a first model training input feature vector based on the Bloom filter bit vector pattern, data corresponding to the first instruction, and a performance metric of the first one of the candidate data structure types; and

a neural network manager to train the data structure selection model with the first model training input feature vector.

2. The apparatus as defined in claim 1, wherein the filter generator is to:

apply a first hash function as an input to the Bloom filter for a first one of the candidate data structure types; and

apply a second hash function as the input to the Bloom filter for a second one of the candidate data structure types.

3. The apparatus as defined in claim 1, wherein the filter generator is to:

apply a first hash function as an input to the Bloom filter when an operand corresponding to the first instruction satisfies a first threshold metric; and

apply a second hash function as the input to the Bloom filter when the operand corresponding to the first instruction satisfies a second threshold metric.

4. The apparatus as defined in claim 1, further including a program parser to:

inspect an instruction associated with source code, the source code corresponding to real-world code and different from the training code; and

determine whether the instruction includes a data structure agnostic application programming interface (API) placeholder.

5. The apparatus as defined in claim 4, further including an API information extractor to extract feature information from the data structure agnostic API.

6. The apparatus as defined in claim 5, wherein the filter generator is to generate an approximated bit vector based on (a) a source code operation, (b) a source code data structure size and (c) a first candidate data structure type.

7. The apparatus as defined in claim 6, further including an inference manager to apply the feature information and the approximated bit vector to the data structure selection model to generate a first cost estimate for the first candidate data structure type.

8. The apparatus as defined in claim 7, wherein the inference manager is to generate the first cost estimate by emulating the instruction associated with the source code rather than executing the instruction associated with the source code.

9. The apparatus as defined in claim 7, wherein the inference manager is to:

compare the first cost estimate for the first candidate data structure type to a second cost estimate for a second candidate data structure type corresponding to the instruction associated with the source code; and

select one of the first or the second candidate data structure types based on the comparison.

10. The apparatus as defined in claim 1, wherein the neural network manager is to emulate the first instruction with a neural network.

11. A non-transitory computer readable storage medium comprising instructions that, when executed by a processor, cause the processor to at least:

assign training code operations to respective first ordered values;

assign candidate data structure types to respective second ordered values;

generate, for a first instruction of the training code operations, a Bloom filter bit vector pattern based on (a) one of the first ordered values, (b) one of the second ordered values corresponding to a first one of the candidate data structure types, and (c) a size of the first instruction;

generate a first model training input feature vector based on the Bloom filter bit vector pattern, data corresponding to the first instruction, and a performance metric of the first one of the candidate data structure types; and

train the data structure selection model with the first model training input feature vector.

12. The non-transitory computer readable storage medium as defined in claim 11, wherein the instructions, when executed, cause the processor to:

apply a first hash function as an input to the Bloom filter for a first one of the candidate data structure types; and

apply a second hash function as the input to the Bloom filter for a second one of the candidate data structure types.

13. The non-transitory computer readable storage medium as defined in claim 11, wherein the instructions, when executed, cause the processor to:

apply a first hash function as an input to the Bloom filter when an operand corresponding to the first instruction satisfies a first threshold metric; and

apply a second hash function as the input to the Bloom filter when the operand corresponding to the first instruction satisfies a second threshold metric.

14. The non-transitory computer readable storage medium as defined in claim 11, wherein the instructions, when executed, cause the processor to:

inspect an instruction associated with source code, the source code corresponding to real-world code and different from the training code; and

determine whether the instruction includes a data structure agnostic application programming interface (API) placeholder.

15. The non-transitory computer readable storage medium as defined in claim 14, wherein the instructions, when executed, cause the processor to extract feature information from the data structure agnostic API.

16. The non-transitory computer readable storage medium as defined in claim 15, wherein the instructions, when executed, cause the processor to generate an approximated bit vector based on (a) a source code operation, (b) a source code data structure size and (c) a first candidate data structure type.

17. The non-transitory computer readable storage medium as defined in claim 16, wherein the instructions, when executed, cause the processor to apply the feature information and the approximated bit vector to the data structure selection model to generate a first cost estimate for the first candidate data structure type.

18. The non-transitory computer readable storage medium as defined in claim 17, wherein the instructions, when executed, cause the processor to generate the first cost estimate by emulating the instruction associated with the source code rather than executing the instruction associated with the source code.

19. The non-transitory computer readable storage medium as defined in claim 17, wherein the instructions, when executed, cause the processor to:

compare the first cost estimate for the first candidate data structure type to a second cost estimate for a second candidate data structure type corresponding to the instruction associated with the source code; and

select one of the first or the second candidate data structure types based on the comparison.

20. The non-transitory computer readable storage medium as defined in claim 11, wherein the instructions, when executed, cause the processor to emulate the first instruction with a neural network.

21. A method to train a data structure selection model, the method comprising:

assigning training code operations to respective first ordered values;

assigning candidate data structure types to respective second ordered values;

generating, for a first instruction of the training code operations, a Bloom filter bit vector pattern based on (a) one of the first ordered values, (b) one of the second ordered values corresponding to a first one of the candidate data structure types, and (c) a size of the first instruction;

generating a first model training input feature vector based on the Bloom filter bit vector pattern, data corresponding to the first instruction, and a performance metric of the first one of the candidate data structure types; and

training the data structure selection model with the first model training input feature vector.

22. The method as defined in claim 21, further including:

applying a first hash function as an input to the Bloom filter for a first one of the candidate data structure types; and

applying a second hash function as the input to the Bloom filter for a second one of the candidate data structure types.

23-30. -30. (canceled)

31. An apparatus to train a data structure selection model, the apparatus comprising:

means for assigning ordinals to;

assign training code operations to respective first ordered values; and

assign candidate data structure types to respective second ordered values;

means for filter generating to, for a first instruction of the training code operations, generate a Bloom filter bit vector pattern based on (a) one of the first ordered values, (b) one of the second ordered values corresponding to a first one of the candidate data structure types, and (c) a size of the first instruction;

means for label generating to generate a first model training input feature vector based on the Bloom filter bit vector pattern, data corresponding to the first instruction, and a performance metric of the first one of the candidate data structure types; and

means for neural network managing to train the data structure selection model with the first model training input feature vector.

32. The apparatus as defined in claim 31, wherein the filter generating means is to:

apply a first hash function as an input to the Bloom filter for a first one of the candidate data structure types; and

apply a second hash function as the input to the Bloom filter for a second one of the candidate data structure types.

33. The apparatus as defined in claim 31, wherein the filter generating means is to:

apply a first hash function as an input to the Bloom filter when an operand corresponding to the first instruction satisfies a first threshold metric; and

apply a second hash function as the input to the Bloom filter when the operand corresponding to the first instruction satisfies a second threshold metric.

34-40. -40. (canceled)