MEMOIZING WEB-BROWSING COMPUTATION WITH DOM-BASED ISOMORPHISM

• US 20110258532A1
• Filed: 04/28/2011
• Published: 10/20/2011
• Est. Priority Date: 03/31/2009
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Cascaval, Gheorghe C., Mandyam, Vikram, Ruotsi, Wendell, Dhillon, Chetan S., Mahan, Michael P., CEZE, Luis, Wang, Bin
• Granted Patent: US 9,171,097 B2
• Time in Patent Office: Days
• US Class Current: 715/234
• CPC Class Codes: G06F 16/9574 of access to content, e.g. by caching

Abstract

Methods and devices for accelerating webpage rendering by a browser store document object model (DOM) tree structures and computations of rendered pages, and compare portions of a DOM tree of pages being render to determining if portions of the DOM tree structures match. If a DOM tree of a webpage to be rendered matches a DOM tree stored in memory, the computations associated with the match DOM tree may be recalled from memory, obviating the need to perform the calculations to render the page. A tree isomorphism algorithm may be used to recognize DOM trees stored in memory that match the DOM tree of the webpage to be rendered. Reusing rendering computations may significantly reducing the time and resources required for rendering web pages. Identifying reusable portions of calculation results based on DOM tree isomorphism enables the browser to reuse stored webpage rendering calculations even when URLs do not match.

Claims

1. A method for rendering a page on a computing device, comprising:

receiving, in a processor of the computing device, a request to display a web page;

determining if a portion of a document object model (DOM) tree associated with the web page is stored in cache memory;

retrieving from the cache memory a reusable portion of the stored DOM tree;

composing the requested webpage using the retrieved portion of the stored DOM tree and dynamically processed portions of the DOM tree; and

displaying the requested web page on an electronic display of the computing device.

2. The method of claim 1, further comprising:

receiving HTML code corresponding to the requested web page; and

parsing the received HTML code to generate a DOM tree,

wherein determining if a portion of a DOM tree associated with the web page is stored in cache memory comprises determining if a portion of the generated DOM tree is isomorphic with one or more portions of a DOM tree stored in memory, and

wherein retrieving from the cache memory a reusable portion of the stored DOM tree comprises retrieving from memory previously stored calculations associated with isomorphic portions of the DOM tree when it is determined that a portion of generated DOM tree is isomorphic with one or more portions of a DOM tree stored in memory.

3. The method of claim 2, wherein determining if a portion of generated DOM tree is isomorphic with one or more portions of a DOM tree stored in memory comprises comparing the generated DOM tree with DOM tree structures stored in memory using a tree isomorphism comparison algorithm.

4. The method of claim 2, wherein determining if a portion of generated DOM tree is isomorphic with one or more portions of a DOM tree stored in a memory comprises determining if the portion of the generated DOM tree has a structure that is identical to one or more portions of DOM trees stored in memory.

5. The method of claim 2, wherein determining if a portion of generated DOM tree is isomorphic with one or more portions of a DOM tree stored in memory comprises determining if the portion of the generated DOM tree is structurally similar to one or more portions of the DOM tree stored in the memory.

6. The method of claim 2, further comprising determining whether key values and input values used to create computation results of a DOM tree in memory equal key values and input values of the generated DOM tree,

wherein retrieving from memory previously stored calculations associated with isomorphic portions of the DOM trees is perform only when it is determined that the key values and input values used to create computation results of a DOM tree in memory equal key values and input values of the generated DOM tree.

7. The method of claim 2, wherein retrieving from memory previously stored calculations associated with isomorphic portions of the DOM trees comprises accessing the cache memory storing the computation results of the portions of the DOM trees such that they are indexed by a computed hash value based on a DOM sub-tree structure corresponding to portions of the DOM trees.

8. The method of claim 2, further comprising:

completing HTML code computations for the generated DOM tree when it is determined that the generated DOM tree is not isomorphic with any of the one or more portions of the DOM tree stored in memory; and

storing the results of the HTML computations indexed with the generated DOM tree in memory.

9. The method of claim 8, wherein storing the generated DOM tree comprises storing at least a portion of the generated DOM tree in a key-value data structure in which DOM tree elements are stored in association with corresponding HTML computation results.

10. The method of claim 9, wherein the structured cache is implemented using a hash-map data structure.

11. The method of claim 9, wherein the key-value data structure comprises a hash-map data structure.

12. The method of claim 11, wherein retrieving previously stored calculations from the memory comprises evaluating hash-keys associated with nodes of the stored DOM tree that are isomorphic with the portion of the generated DOM tree.

13. A computing device, comprising:

means for receiving a request to display a web page;

means for determining if a portion of a document object model (DOM) tree associated with the web page is stored in cache memory;

means for retrieving from the cache memory a reusable portion of the stored DOM tree;

means for composing the requested webpage using the retrieved portion of the stored DOM tree and dynamically processed portions of the DOM tree; and

means for displaying the requested web page on an electronic display.

14. The computing device of claim 13, further comprising:

means for receiving HTML code corresponding to the requested web page; and

means for parsing the received HTML code to generate a DOM tree,

wherein means for determining if a portion of a DOM tree associated with the web page is stored in cache memory comprises means for determining if a portion of the generated DOM tree is isomorphic with one or more portions of a DOM tree stored in memory, and

wherein means for retrieving from the cache memory a reusable portion of the stored DOM tree comprises means for retrieving from memory previously stored calculations associated with isomorphic portions of the DOM tree when it is determined that a portion of generated DOM tree is isomorphic with one or more portions of a DOM tree stored in memory.

15. The computing device of claim 14, wherein means for determining if a portion of generated DOM tree is isomorphic with one or more portions of a DOM tree stored in memory comprises means for comparing the generated DOM tree with DOM tree structures stored in memory using a tree isomorphism comparison algorithm.

16. The computing device of claim 14, wherein means for determining if a portion of generated DOM tree is isomorphic with one or more portions of a DOM tree stored in a memory comprises means for determining if the portion of the generated DOM tree has a structure that is identical to one or more portions of DOM trees stored in memory.

17. The computing device of claim 14, wherein means for determining if a portion of generated DOM tree is isomorphic with one or more portions of a DOM tree stored in memory comprises means for determining if the portion of the generated DOM tree is structurally similar to one or more portions of the DOM tree stored in the memory.

18. The computing device of claim 14, further comprising means for determining whether key values and input values used to create computation results of a DOM tree in memory equal key values and input values of the generated DOM tree,

wherein means for retrieving from memory previously stored calculations associated with isomorphic portions of the DOM trees comprises means for retrieving the stored calculations associated with isomorphic portions of the DOM trees only when it is determined that the key values and input values used to create computation results of a DOM tree in memory equal key values and input values of the generated DOM tree.

19. The computing device of claim 14, wherein means for retrieving from memory previously stored calculations associated with isomorphic portions of the DOM trees comprises means for accessing the cache memory storing the computation results of the portions of the DOM trees such that they are indexed by a computed hash value based on a DOM sub-tree structure corresponding to portions of the DOM trees.

20. The computing device of claim 14, further comprising:

means for completing HTML code computations for the generated DOM tree when it is determined that the generated DOM tree is not isomorphic with any of the one or more portions of the DOM tree stored in memory; and

means for storing the results of the HTML computations indexed with the generated DOM tree in memory.

21. The computing device of claim 20, wherein means for storing the generated DOM tree comprises means for storing at least a portion of the generated DOM tree in a key-value data structure in which DOM tree elements are stored in association with corresponding HTML computation results.

22. The computing device of claim 21, further comprising means for implementing the structured cache using a hash-map data structure.

23. The computing device of claim 21, wherein means for storing at least a portion of the generated DOM tree in a key-value data structure comprising means for storing at least a portion of the generated DOM tree in a hash-map data structure.

24. The computing device of claim 23, wherein means for retrieving previously stored calculations from the memory comprises means for evaluating hash-keys associated with nodes of the stored DOM tree that are isomorphic with the portion of the generated DOM tree.

25. A computing device, comprising:

a memory; and

a processor coupled to the memory, wherein the processor is configured with processor-executable instructions to perform operations comprising;

receiving a request to display a web page;

determining if a portion of a document object model (DOM) tree associated with the web page is stored in cache memory;

retrieving from the cache memory a reusable portion of the stored DOM tree;

composing the requested webpage using the retrieved portion of the stored DOM tree and dynamically processed portions of the DOM tree; and

displaying the requested web page.

26. The computing device of claim 25, wherein the processor is configured with processor-executable instructions to perform operations further comprising:

receiving HTML code corresponding to the requested web page;

parsing the received HTML code to generate a DOM tree;

wherein the processor is configured with processor-executable instructions such that;

determining if a portion of a DOM tree associated with the web page is stored in cache memory comprises determining if a portion of the generated DOM tree is isomorphic with one or more portions of a DOM tree stored in memory, and

retrieving from the cache memory a reusable portion of the stored DOM tree comprises retrieving from memory previously stored calculations associated with isomorphic portions of the DOM tree when it is determined that a portion of generated DOM tree is isomorphic with one or more portions of a DOM tree stored in memory.

27. The computing device of claim 26, wherein the processor is configured with processor-executable instructions such that determining if a portion of generated DOM tree is isomorphic with one or more portions of a DOM tree stored in memory comprises comparing the generated DOM tree with DOM tree structures stored in memory using a tree isomorphism comparison algorithm.

28. The computing device of claim 27, wherein the processor is configured with processor-executable instructions such that determining if a portion of generated DOM tree is isomorphic with one or more portions of a DOM tree stored in a memory comprises determining if the portion of the generated DOM tree has a structure that is identical to one or more portions of DOM trees stored in memory.

29. The computing device of claim 27, wherein the processor is configured with processor-executable instructions such that determining if a portion of generated DOM tree is isomorphic with one or more portions of a DOM tree stored in memory comprises determining if the portion of the generated DOM tree is structurally similar to one or more portions of the DOM tree stored in the memory.

30. The computing device of claim 27, wherein the processor is configured with processor-executable instructions to perform operations further comprising determining whether key values and input values used to create computation results of a DOM tree in memory equal key values and input values of the generated DOM tree,

wherein the processor is configured with processor-executable instructions such that retrieving from memory previously stored calculations associated with isomorphic portions of the DOM trees is perform only when it is determined that the key values and input values used to create computation results of a DOM tree in memory equal key values and input values of the generated DOM tree.

31. The computing device of claim 27, wherein the processor is configured with processor-executable instructions such that retrieving from memory previously stored calculations associated with isomorphic portions of the DOM trees comprises accessing the cache memory storing the computation results of the portions of the DOM trees such that they are indexed by a computed hash value based on a DOM sub-tree structure corresponding to portions of the DOM trees.

32. The computing device of claim 27, wherein the processor is configured with processor-executable instructions to perform operations further comprising:

completing HTML code computations for the generated DOM tree when it is determined that the generated DOM tree is not isomorphic with any of the one or more portions of the DOM tree stored in memory; and

storing the results of the HTML computations indexed with the generated DOM tree in memory.

33. The computing device of claim 32, wherein the processor is configured with processor-executable instructions such that storing the generated DOM tree comprises storing at least a portion of the generated DOM tree in a key-value data structure in which DOM tree elements are stored in association with corresponding HTML computation results.

34. The computing device of claim 33, wherein the processor is configured with processor-executable instructions such that the structured cache is implemented using a hash-map data structure.

35. The computing device of claim 33, wherein the processor is configured with processor-executable instructions such that the key-value data structure comprises a hash-map data structure.

36. The computing device of claim 35, wherein the processor is configured with processor-executable instructions such that retrieving previously stored calculations from the memory comprises evaluating hash-keys associated with nodes of the stored DOM tree that are isomorphic with the portion of the generated DOM tree.

37. A non-transitory computer readable storage medium having stored thereon processor-executable software instructions configured to cause a processor of a computing device to perform operations comprising:

receiving a request to display a web page;

determining if a portion of a document object model (DOM) tree associated with the web page is stored in cache memory;

retrieving from the cache memory a reusable portion of the stored DOM tree;

composing the requested webpage using the retrieved portion of the stored DOM tree and dynamically processed portions of the DOM tree; and

displaying the requested web page on an electronic display.

38. The non-transitory computer readable storage medium of claim 37, wherein the stored processor-executable instructions are configured to cause a processor of a computing device to perform operations further comprising:

receiving HTML code corresponding to the requested web page;

parsing the received HTML code to generate a DOM tree,

wherein the stored processor-executable instructions are configured such that;

determining if a portion of a DOM tree associated with the web page is stored in cache memory comprises determining if a portion of the generated DOM tree is isomorphic with one or more portions of a DOM tree stored in memory, and

retrieving from the cache memory a reusable portion of the stored DOM tree comprises retrieving from memory previously stored calculations associated with isomorphic portions of the DOM tree when it is determined that a portion of generated DOM tree is isomorphic with one or more portions of a DOM tree stored in memory.

39. The non-transitory computer readable storage medium of claim 38, wherein the stored processor-executable instructions are configured to cause a processor of a computing device to perform operations such that determining if a portion of generated DOM tree is isomorphic with one or more portions of a DOM tree stored in memory comprises comparing the generated DOM tree with DOM tree structures stored in memory using a tree isomorphism comparison algorithm.

40. The non-transitory computer readable storage medium of claim 38, wherein the stored processor-executable instructions are configured to cause a processor of a computing device to perform operations such that determining if a portion of generated DOM tree is isomorphic with one or more portions of a DOM tree stored in a memory comprises determining if the portion of the generated DOM tree has a structure that is identical to one or more portions of DOM trees stored in memory.

41. The non-transitory computer readable storage medium of claim 38, wherein the stored processor-executable instructions are configured to cause a processor of a computing device to perform operations such that determining if a portion of generated DOM tree is isomorphic with one or more portions of a DOM tree stored in memory comprises determining if the portion of the generated DOM tree is structurally similar to one or more portions of the DOM tree stored in the memory.

42. The non-transitory computer readable storage medium of claim 38, wherein the stored processor-executable instructions are configured to cause a processor of a computing device to perform operations further comprising determining whether key values and input values used to create computation results of a DOM tree in memory equal key values and input values of the generated DOM tree,

wherein the stored processor-executable instructions are configured to cause a processor of a computing device to perform operations such that retrieving from memory previously stored calculations associated with isomorphic portions of the DOM trees is perform only when it is determined that the key values and input values used to create computation results of a DOM tree in memory equal key values and input values of the generated DOM tree.

43. The non-transitory computer readable storage medium of claim 38, wherein the stored processor-executable instructions are configured to cause a processor of a computing device to perform operations such that retrieving from memory previously stored calculations associated with isomorphic portions of the DOM trees comprises accessing the cache memory storing the computation results of the portions of the DOM trees such that they are indexed by a computed hash value based on a DOM sub-tree structure corresponding to portions of the DOM trees.

44. The non-transitory computer readable storage medium of claim 38, wherein the stored processor-executable instructions are configured to cause a processor of a computing device to perform operations further comprising:

completing HTML code computations for the generated DOM tree when it is determined that the generated DOM tree is not isomorphic with any of the one or more portions of the DOM tree stored in memory; and

storing the results of the HTML computations indexed with the generated DOM tree in memory.

45. The non-transitory computer readable storage medium of claim 44, wherein the stored processor-executable instructions are configured to cause a processor of a computing device to perform operations such that storing the generated DOM tree comprises storing at least a portion of the generated DOM tree in a key-value data structure in which DOM tree elements are stored in association with corresponding HTML computation results.

46. The non-transitory computer readable storage medium of claim 45, wherein the stored processor-executable instructions are configured to cause a processor of a computing device to perform operations such that the structured cache is implemented using a hash-map data structure.

47. The non-transitory computer readable storage medium of claim 45, wherein the stored processor-executable instructions are configured to cause a processor of a computing device to perform operations such that the key-value data structure comprises a hash-map data structure.

48. The non-transitory computer readable storage medium of claim 47, wherein the stored processor-executable instructions are configured to cause a processor of a computing device to perform operations such that retrieving previously stored calculations from the memory comprises evaluating hash-keys associated with nodes of the stored DOM tree that are isomorphic with the portion of the generated DOM tree.