[GraphBolt] Partitioned S3-FIFO Feature Cache implementation

mfbalin commented 6 days ago

Description

The S3-FIFO cache policy logic is serial for now. The partitioned policy partitions the keys in a deterministic manner to different cache policies we construct, so that each policy can run in parallel. Since performance is important, phmap hash table is used instead of std::unordered_map, which is available as a submodule. I went ahead and updated it to the latest available version to take advantage of potential bug fixes and performance improvements.

40 threads lead to a speedup of around 17x in my preliminary experiments with no change to the cache miss rate.

Checklist

Please feel free to remove inapplicable items for your PR.

[ ] The PR title starts with [$CATEGORY] (such as [NN], [Model], [Doc], [Feature]])
[ ] I've leverage the tools to beautify the python and c++ code.
[ ] The PR is complete and small, read the Google eng practice (CL equals to PR) to understand more about small PR. In DGL, we consider PRs with less than 200 lines of core code change are small (example, test and documentation could be exempted).
[ ] All changes have test coverage
[ ] Code is well-documented
[ ] To the best of my knowledge, examples are either not affected by this change, or have been fixed to be compatible with this change
[ ] Related issue is referred in this PR
[ ] If the PR is for a new model/paper, I've updated the example index here.

Changes

dgl-bot commented 6 days ago

To trigger regression tests:

@dgl-bot run [instance-type] [which tests] [compare-with-branch]; For example: @dgl-bot run g4dn.4xlarge all dmlc/master or @dgl-bot run c5.9xlarge kernel,api dmlc/master

dgl-bot commented 6 days ago

Commit ID: cf8c07216582eff63fc5b851c17adcd7d907fd0e

Build ID: 1

Status: ❌ CI test failed in Stage [CPU Build (Win64)].

Report path: link

Full logs path: link

dgl-bot commented 6 days ago

Commit ID: 6973add5dfd73a58d3f0f79ee3aee90ea3ddb84b

Build ID: 2

Status: ✅ CI test succeeded.

Report path: link

Full logs path: link

dgl-bot commented 6 days ago

Commit ID: 18dff26542c532640fe94e8c17cd01e4b4706363

Build ID: 3

Status: ✅ CI test succeeded.

Report path: link

Full logs path: link

dgl-bot commented 6 days ago

Commit ID: 82550ba9b56b8e54c08cdddb26351a6f54d87541

Build ID: 4

Status: ✅ CI test succeeded.

Report path: link

Full logs path: link

dgl-bot commented 5 days ago

Commit ID: d0560f246635c031e5c572bf1656d68729a15093

Build ID: 5

Status: ✅ CI test succeeded.

Report path: link

Full logs path: link

dgl-bot commented 5 days ago

Commit ID: e0d96299e7d724eaba3adfeee41dc65234e6e670

Build ID: 6

Status: ✅ CI test succeeded.

Report path: link

Full logs path: link

dgl-bot commented 4 days ago

Commit ID: c14d5878b8ace976f546baaf2f442822981fc5e1

Build ID: 7

Status: ⚪️ CI test cancelled due to overrun.

Report path: link

Full logs path: link

dgl-bot commented 4 days ago

Commit ID: fe4066d1aba004d4fca28a908fdbbe20432aee2b

Build ID: 8

Status: ⚪️ CI test cancelled due to overrun.

Report path: link

Full logs path: link

dgl-bot commented 4 days ago

Commit ID: 9d4dbc9d918b7ab4cea17aa81bb861809c33fb7a

Build ID: 9

Status: ✅ CI test succeeded.

Report path: link

Full logs path: link

dgl-bot commented 3 days ago

Commit ID: 6486a040293a89c91a150b31963e12f162bd071c

Build ID: 10

Status: ⚪️ CI test cancelled due to overrun.

Report path: link

Full logs path: link

dgl-bot commented 3 days ago

Commit ID: fd861342416db49edd31c7459ff1e7dce57b8df3

Build ID: 11

Status: ⚪️ CI test cancelled due to overrun.

Report path: link

Full logs path: link

dgl-bot commented 3 days ago

Commit ID: ac66d3a28164a24eba0575af4c86db7c4238f630

Build ID: 12

Status: ✅ CI test succeeded.

Report path: link

Full logs path: link

dgl-bot commented 2 days ago

Commit ID: b4438c5b6c4396621d16ff84b681b00123fdfa3d

Build ID: 13

Status: ⚪️ CI test cancelled due to overrun.

Report path: link

Full logs path: link

dgl-bot commented 2 days ago

Commit ID: 19dcc0f105b8a8698683718307517861fa217151

Build ID: 14

Status: ⚪️ CI test cancelled due to overrun.

Report path: link

Full logs path: link

dgl-bot commented 2 days ago

Commit ID: 4ede2a9d42be6a7456dc7e6519fce9269d368aaa

Build ID: 15

Status: ✅ CI test succeeded.

Report path: link

Full logs path: link

dgl-bot commented 2 days ago

Commit ID: e85af493ecc998ccdda82ed5e0641ae9b94ccf79

Build ID: 16

Status: ⚪️ CI test cancelled due to overrun.

Report path: link

Full logs path: link

dgl-bot commented 2 days ago

Commit ID: b48bcc8ee998c1761273545c2f7898bddb8b4946

Build ID: 17

Status: ⚪️ CI test cancelled due to overrun.

Report path: link

Full logs path: link

dgl-bot commented 2 days ago

Commit ID: 3490041d0c8000e8ec9428399a3cf7ad993c3d65

Build ID: 18

Status: ✅ CI test succeeded.

Report path: link

Full logs path: link

mfbalin commented 1 day ago

https://github.com/dmlc/dgl/pull/7492#discussion_r1663506205

@frozenbugs What do you mean here? The member functions defined inside class are inline by default.

dgl-bot commented 1 day ago

Commit ID: cd7bc751f35630afca80ef518dfb7f5983086fd0

Build ID: 19

Status: ❌ CI test failed in Stage [CPU Build].

Report path: link

Full logs path: link

dgl-bot commented 1 day ago

Commit ID: 0583e14df9c9523846888bbac8f20b9d5d73a9fc

Build ID: 20

Status: ⚪️ CI test cancelled due to overrun.

Report path: link

Full logs path: link

dgl-bot commented 1 day ago

Commit ID: d9c6e23920bd57960e9f99ff2f9c7fefb0473e8e

Build ID: 21

Status: ⚪️ CI test cancelled due to overrun.

Report path: link

Full logs path: link

dgl-bot commented 1 day ago

Commit ID: bfe83a439ea2af84748ea5070a005aeb14306250

Build ID: 22

Status: ⚪️ CI test cancelled due to overrun.

Report path: link

Full logs path: link

dgl-bot commented 1 day ago

Commit ID: 9979026bb243e8996168d9d58319420a10b529e1

Build ID: 23

Status: ⚪️ CI test cancelled due to overrun.

Report path: link

Full logs path: link

dgl-bot commented 1 day ago

Commit ID: cff790d960698ea47dc55a446aa9784dcc61be0a

Build ID: 24

Status: ⚪️ CI test cancelled due to overrun.

Report path: link

Full logs path: link

dgl-bot commented 1 day ago

Commit ID: cddcab59ab3fce71f5d0711ac5bfa5ad612d42f5

Build ID: 25

Status: ⚪️ CI test cancelled due to overrun.

Report path: link

Full logs path: link

dgl-bot commented 1 day ago

Commit ID: 6d0f8fa3f4b004d9ff728383744fcd0a8548cc3d

Build ID: 26

Status: ✅ CI test succeeded.

Report path: link

Full logs path: link

dgl-bot commented 1 day ago

Commit ID: 8624ca2aca01cf4ffab7df3e4770d9777467cbd0

Build ID: 27

Status: ⚪️ CI test cancelled due to overrun.

Report path: link

Full logs path: link

dgl-bot commented 1 day ago

Commit ID: b702f967415db3bb47694c61b1782339a2c4495c

Build ID: 28

Status: ✅ CI test succeeded.

Report path: link

Full logs path: link

dgl-bot commented 22 hours ago

Commit ID: 84fb6994d4244251108f97a195ed6af715ba029e

Build ID: 29

Status: ⚪️ CI test cancelled due to overrun.

Report path: link

Full logs path: link

dgl-bot commented 21 hours ago

Commit ID: c525519b4a72cd6411628f387e3152b7646e3bf3

Build ID: 30

Status: ✅ CI test succeeded.

Report path: link

Full logs path: link

dgl-bot commented 19 hours ago

Commit ID: b266a1b9b315252255dc9c7c8318cd8100db0259

Build ID: 31

Status: ⚪️ CI test cancelled due to overrun.

Report path: link

Full logs path: link

dgl-bot commented 19 hours ago

Commit ID: 59eba55a4392a372503e081993afacf27650f85b

Build ID: 32

Status: ✅ CI test succeeded.

Report path: link

Full logs path: link

mfbalin commented 18 hours ago

There is no way to force from a base class so that all derived classes have the same constructor @frozenbugs. So I don't have a way to force derived classes to have a constructor that take a single capacity parameter.

mfbalin commented 17 hours ago

With the most recent changes, the PartitionedCachePolicy class is compiled only once even if more cache policies are added in the future, since we are using polymorphism now.

dgl-bot commented 17 hours ago

Commit ID: 4ae58f633e768f21bc3e3f9b304b7b34526e2f32

Build ID: 33

Status: ⚪️ CI test cancelled due to overrun.

Report path: link

Full logs path: link

dgl-bot commented 17 hours ago

Commit ID: a4183d5999c2d4523e51066e2b4c75ec89c99842

Build ID: 34

Status: ✅ CI test succeeded.

Report path: link

Full logs path: link

dmlc / dgl