Expression tree interning

Patent metadata

Field	Value
Publication number	US-10318511-B2
Application number	US-201514952589-A
Country	US
Kind code	B2
Filing date	Nov 25, 2015
Priority date	Nov 25, 2015
Publication date	Jun 11, 2019
Grant date	Jun 11, 2019

Abstract

In non-limiting examples of the present disclosure, systems and methods for interning expression trees are provided. Hash code for a plurality of expression tree nodes is recursively computed and a determination is made as to whether hash code for each of a plurality of expression tree nodes is stored in a cached intern pool. Upon determining that at least one of a plurality of expression tree nodes is not stored in a cached intern pool, one or more functions may be run on at least one of a plurality of expression tree nodes for determining whether at least one of a plurality of expression tree nodes should be stored in a cached intern pool. Normalization of expression trees may also be employed to effectuate effective sharing of expression tree nodes.

First claim

We claim:

1. A system comprising:
at least one processor; and
a memory operatively connected with the at least one processor, the memory comprising computer executable instructions that, when executed by the at least one processor, perform a method comprising:
recursively computing hash code for a plurality of expression tree nodes of an expression tree;
determining whether hash code for each of the plurality of expression tree nodes is stored in a cache;
upon determining that at least one of the plurality of expression tree nodes is not stored in the cache, determining whether the at least one of the plurality of expression tree nodes should be stored in the cache; and
based on the determination, storing the at least one of the plurality of expression tree nodes in the cache, wherein the at least one of the plurality of expression tree nodes stored in the cache may be reused to construct additional expression trees.

2. The system according to claim 1 , further comprising normalizing the expression tree prior to recursively computing the hash code.

3. The system according to claim 1 , further comprising, determining that at least one node of the expression trees is sharable amongst a plurality of expression trees.

4. The system according to claim 3 , wherein determining that at least one node of the expression tree is sharable amongst the plurality of expression trees further comprises determining whether the at least one sharable node of the expression tree is desirable to share.

5. The system according to claim 4 , wherein determining whether the at least one sharable node of the expression tree is desirable to share further comprises:
analyzing the memory costs associated with storing the at least one sharable node; and
performing a live metrics analysis to determine how frequently the at least one sharable node is utilized.

6. The system according to claim 5 , further comprising performing a live metrics analysis to determine whether the at least one sharable node is amongst a most recently used expression tree node.

7. The system according to claim 3 , wherein upon determining that at least one node of the expression tree is sharable amongst a plurality of expression trees, determining whether at least one shared parameter associated with at least one of the plurality of expression trees from the cache should be evicted.

8. The system according to claim 7 , further comprising evicting at least one shared parameter associated with at least one of the plurality of expression trees from the cache.

9. A computer-implemented method for interning expression trees comprising:
recursively computing at least one hash codes for a plurality of expression tree nodes of an expression tree;
determining whether the at least one hash code for each of the plurality of expression tree nodes is stored in one or more intern pools;
upon determining that at least one of the plurality of expression tree nodes is not stored in the one or more intern pools, running at least one function on at least one of the plurality of tree nodes for determining whether the at least one of the plurality of expression tree nodes should be stored in the one or more intern pools; and
based on the determination, storing the at least one of the plurality of expression tree nodes in the one or more intern pools, wherein the at least one of the plurality of expression tree nodes stored in the cache may be reused to construct additional expression trees.

10. The computer-implemented method according to claim 9 , further comprising performing normalization amongst the plurality of expression trees that have matching parameter types.

11. The computer implemented method according to claim 10 , wherein performing normalization amongst the plurality of expression trees further comprises reusing at least one inner lambda expression for at least one portion of at least one of the plurality of expression trees.

12. The computer implemented method according to claim 11 , wherein performing normalization amongst the plurality of expression trees further comprises utilizing De Bruijn indices to erase lambda parameters based on names by an index-based scheme.

13. The computer implemented method according to claim 9 , further comprising, determining that at least one node of the expression trees is sharable amongst a plurality of expression trees.

14. The computer implemented method according to claim 13 , wherein determining that at least one node of the expression tree is sharable amongst a plurality of expression trees further comprises determining whether the at least one sharable node of the expression tree is desirable to share.

15. The computer implemented method according to claim 14 , wherein determining whether the at least one sharable node of the expression tree is desirable to share further comprises:
analyzing the memory cost associated with storing the at least one sharable node; and
performing a live metrics analysis to determine how frequently the at least one sharable node is utilized.

16. The computer implemented method according to claim 15 , further comprising performing a live metrics analysis to determine whether the at least one sharable node is amongst a most recently used expression tree node.

17. The computer implemented method according to claim 13 , wherein upon determining that at least one node of the expression tree is sharable amongst a plurality of expression trees, determining whether at least one shared parameter associated with at least one of the plurality of expression trees from the cache should be evicted.

18. The computer implemented method according to claim 17 , further comprising evicting at least one shared parameter associated with at least one of the plurality of expression trees from the cache.

19. The computer implemented method according to claim 17 , wherein determining whether at least one shared parameter associated with at least one of the plurality of expression trees from the cache should be evicted further comprises:
analyzing the memory cost associated with storing the at least one shared parameter; and
calculating how frequently the at least one shared parameter has been utilized.

20. A computer-storage medium encoding computer executable instructions that, when executed by at least one processor, perform a method for interning expression trees comprising:
recursively computing hash code for a plurality of expression tree nodes of an expression tree;
determining whether hash code for each of the plurality of expression tree nodes is stored in an intern pool;
upon determining that at least one of the plurality of expression tree nodes is not stored in the intern pool, running at least one function on at least one of the plurality of tree nodes for determining whether the at least one of the plurality of expression tree nodes should be stored in the intern pool; and
based on the determination, storing the at least one of the plurality of expression tree nodes in the intern pool, wherein the at least one of the plurality of expression tree nodes stored in the cache may be reused to construct additional expression trees.

Assignees

• Microsoft Technology Licensing Llc

Inventors

• De Smet Bart
• Rozell Eric Anthony

Classifications

• G06F16/24552

  Database cache management · CPC title

• G06F16/2255

  Hash tables · CPC title

• G06F16/2246 Primary

  Trees, e.g. B+trees · CPC title

• G06F16/24542 Primary

  Plan optimisation · CPC title

• G06F16/24524

  Access plan code generation and invalidation; Reuse of access plans · CPC title