Methods of graph-type specialization and optimization in graph algorithm DSL compilation

Patent metadata

Field	Value
Publication number	US-10585945-B2
Application number	US-201715666310-A
Country	US
Kind code	B2
Filing date	Aug 1, 2017
Priority date	Aug 1, 2017
Publication date	Mar 10, 2020
Grant date	Mar 10, 2020

Abstract

Techniques herein generate, such as during compilation, polymorphic dispatch logic (PDL) to switch between specialized implementations of a polymorphic graph algorithm. In an embodiment, a computer detects, within source logic of a graph algorithm, that the algorithm processes an instance of a generic graph type. The computer generates several alternative implementations of the algorithm. Each implementation is specialized to process the graph instance as an instance of a respective graph subtype. The computer generates PDL that performs dynamic dispatch as follows. At runtime, the PDL receives a graph instance of the generic graph type. The PDL detects which particular graph subtype is the graph instance. The PDL then invokes whichever alternative implementation that is specialized to process the graph instance as an instance of the detected particular graph subtype. In embodiments, the source logic is expressed in a domain specific language (DSL), e.g. for analysis, traversal, or querying of graphs.

First claim

What is claimed is:

1. A method comprising:
detecting, within source logic of an algorithm, that the algorithm processes a graph as an instance of a generalized graph type of a plurality of graph subtypes;
generating a plurality of alternate implementations of the algorithm, wherein each implementation of the plurality of alternate implementations is specialized to process same said graph instance as an instance of a respective graph subtype of the plurality of graph subtypes;
generating polymorphic dispatch logic configured to:
receive a particular graph that is an instance of the generic graph type;
detect which particular graph subtype of the plurality of graph subtypes is the particular graph;
invoke only one implementation, of the plurality of alternate implementations of the algorithm, that is specialized to process the particular graph as an instance of the particular graph subtype;

wherein the method is performed by one or more computers.

2. The method of claim 1 wherein generating the plurality of alternate implementations of the algorithm comprises generating at least one of: C++ source logic, Java source logic, or Java bytecode.

3. The method of claim 1 wherein the source logic of the algorithm comprises a domain specific language (DSL).

4. The method of claim 3 wherein the DSL comprises Green-Marl.

5. The method of claim 3 wherein generating the plurality of alternate implementations of the algorithm comprises transforming the source logic into a transformed source logic for the DSL.

6. The method of claim 1 wherein the plurality of graph subtypes comprises both of: a directed graph subtype and an undirected graph subtype.

7. The method of claim 1 wherein the plurality of graph subtypes comprises both of: a multigraph graph subtype that has parallel edges and a graph subtype that does not have parallel edges.

8. The method of claim 1 wherein:
the generic graph type is a bipartite graph comprising:
a first graph subtype that contains vertices of a first vertex type, and
a second graph subtype that contains vertices of a second vertex type;

the plurality of graph subtypes comprises at least the first graph subtype and the second graph subtype.

9. The method of claim 1 wherein generating the plurality of alternate implementations of the algorithm comprises generating logic to translate a first identifier of an edge of the particular graph to a second identifier of the edge of the particular graph.

10. The method of claim 1 wherein generating the plurality of alternate implementations of the algorithm comprises generating a plurality of subroutines that share an overloaded subroutine name and do not share a same signature.

11. One or more non-transitory computer-readable media storing instructions that, when executed by one or more processors, cause:
detecting, within source logic of an algorithm, that the algorithm processes a graph as an instance of a generalized graph type of a plurality of graph subtypes;
generating a plurality of alternate implementations of the algorithm, wherein each implementation of the plurality of alternate implementations is specialized to process same said graph as an instance of a respective graph subtype of the plurality of graph subtypes;
generating polymorphic dispatch logic configured to:
receive a particular graph that is an instance of the generic graph type;
detect which particular graph subtype of the plurality of graph subtypes is the particular graph;

invoke only one implementation, of the plurality of alternate implementations of the algorithm, that is specialized to process the particular graph as an instance of the particular graph subtype.

12. The one or more non-transitory computer-readable media of claim 11 wherein generating the plurality of alternate implementations of the algorithm comprises generating at least one of: C++ source logic, Java source logic, or Java bytecode.

13. The one or more non-transitory computer-readable media of claim 11 wherein the source logic of the algorithm comprises a domain specific language (DSL).

14. The one or more non-transitory computer-readable media of claim 13 wherein the DSL comprises Green-Marl.

15. The one or more non-transitory computer-readable media of claim 13 wherein generating the plurality of alternate implementations of the algorithm comprises transforming the source logic into a transformed source logic for the DSL.

16. The one or more non-transitory computer-readable media of claim 11 wherein the plurality of graph subtypes comprises both of: a directed graph subtype and an undirected graph subtype.

17. The one or more non-transitory computer-readable media of claim 11 wherein the plurality of graph subtypes comprises both of: a multigraph graph subtype that has parallel edges and a graph subtype that does not have parallel edges.

18. The one or more non-transitory computer-readable media of claim 11 wherein:
the generic graph type is a bipartite graph comprising:
a first graph subtype that contains vertices of a first vertex type, and
a second graph subtype that contains vertices of a second vertex type;

the plurality of graph subtypes comprises at least the first graph subtype and the second graph subtype.

19. The one or more non-transitory computer-readable media of claim 11 wherein generating the plurality of alternate implementations of the algorithm comprises generating logic to translate a first identifier of an edge of the particular graph to a second identifier of the edge of the particular graph.

20. The one or more non-transitory computer-readable media of claim 11 wherein generating the plurality of alternate implementations of the algorithm comprises generating a plurality of subroutines that share an overloaded subroutine name and do not share a same signature.

Assignees

• Oracle Int Corp

Inventors

• Sevenich Martin
• Hong Sungpack
• Weld Alexander
• Chafi Hassan
• Dwars Martijn

Classifications

• G06F8/4441

  Reducing the execution time required by the program code · CPC title

• G06F16/9024 Primary

  Graphs; Linked lists (G06F16/9027 takes precedence) · CPC title

• G06F16/2453

  Query optimisation · CPC title

• G06F8/34 Primary

  Graphical or visual programming · CPC title

• G06F8/30

  Creation or generation of source code · CPC title