Skip to content

DSU round timings

kennyzzhang edited this page Feb 17, 2023 · 3 revisions

Currently, the biggest bottleneck is sketch merging. The question is whether this is due to dsu synchronization, or just raw sketch merging cost

When increasing the number of sketch nodes, query time goes up. Points towards synchronization bottleneck

==> delta_1_sk1 <==
Procesing 21474508 updates took 224.147 seconds, 95805.3 per second
Connected Components algorithm took 4.67538 and found 1 CC
Query: 0.429
DSU Merge: 0.014
Sketch Merge: 3.219
Query: 0.002
DSU Merge: 0.002
Sketch Merge: 0.755
Query: 0
DSU Merge: 0
Sketch Merge: 0.166
Query: 0
DSU Merge: 0
Sketch Merge: 0.029
Query: 0
DSU Merge: 0
Sketch Merge: 0.011
Query: 0
DSU Merge: 0
Sketch Merge: 0.003
Inter-|   Receive                                                |  Transmit
 face |bytes    packets errs drop fifo frame compressed multicast|bytes    packets errs drop fifo colls carrier compressed
    lo: 1916030    1722    0    0    0     0          0         0  1916030    1722    0    0    0     0       0          0
  eth0: 107059889 1965984    0    0    0     0          0         0 2902306523 3883725    0    0    0     0       0          0

==> delta_1_sk2 <==
Procesing 21474508 updates took 209.434 seconds, 102536 per second
Connected Components algorithm took 4.61487 and found 1 CC
Query: 0.494
DSU Merge: 0.015
Sketch Merge: 3.092
Query: 0.002
DSU Merge: 0.002
Sketch Merge: 0.726
Query: 0
DSU Merge: 0
Sketch Merge: 0.184
Query: 0
DSU Merge: 0
Sketch Merge: 0.024
Query: 0
DSU Merge: 0
Sketch Merge: 0.01
Query: 0
DSU Merge: 0
Sketch Merge: 0.006
Query: 0
DSU Merge: 0
Sketch Merge: 0.006
Query: 0
DSU Merge: 0
Sketch Merge: 0.005
Inter-|   Receive                                                |  Transmit
 face |bytes    packets errs drop fifo frame compressed multicast|bytes    packets errs drop fifo colls carrier compressed
    lo: 1912942    1686    0    0    0     0          0         0  1912942    1686    0    0    0     0       0          0
  eth0: 55143704 1002559    0    0    0     0          0         0 1468650515 1979167    0    0    0     0       0          0

==> delta_1_sk4 <==
Procesing 21474508 updates took 162.169 seconds, 132420 per second
Connected Components algorithm took 5.23641 and found 1 CC
Query: 0.545
DSU Merge: 0.014
Sketch Merge: 3.299
Query: 0.002
DSU Merge: 0.002
Sketch Merge: 1.089
Query: 0
DSU Merge: 0
Sketch Merge: 0.159
Query: 0
DSU Merge: 0
Sketch Merge: 0.033
Query: 0
DSU Merge: 0
Sketch Merge: 0.017
Query: 0
DSU Merge: 0
Sketch Merge: 0.013
Query: 0
DSU Merge: 0
Sketch Merge: 0.012
Inter-|   Receive                                                |  Transmit
 face |bytes    packets errs drop fifo frame compressed multicast|bytes    packets errs drop fifo colls carrier compressed
    lo: 3833832    3465    0    0    0     0          0         0  3833832    3465    0    0    0     0       0          0
  eth0: 217589270 3895183    0    0    0     0          0         0 5846109363 7703652    0    0    0     0       0          0

==> delta_1_sk8 <==
Procesing 21474508 updates took 128.492 seconds, 167128 per second
Connected Components algorithm took 13.5317 and found 1 CC
Query: 0.314
DSU Merge: 0.014
Sketch Merge: 11.055
Query: 0.003
DSU Merge: 0.002
Sketch Merge: 1.707
Query: 0.001
DSU Merge: 0
Sketch Merge: 0.207
Query: 0
DSU Merge: 0
Sketch Merge: 0.069
Query: 0
DSU Merge: 0
Sketch Merge: 0.037
Query: 0
DSU Merge: 0
Sketch Merge: 0.031
Query: 0
DSU Merge: 0
Sketch Merge: 0.031
Inter-|   Receive                                                |  Transmit
 face |bytes    packets errs drop fifo frame compressed multicast|bytes    packets errs drop fifo colls carrier compressed
    lo: 2880586    2605    0    0    0     0          0         0  2880586    2605    0    0    0     0       0          0
  eth0: 163623158 2924604    0    0    0     0          0         0 4388677656 5778918    0    0    0     0       0          0

With sketch send and receive threads:

==> delta_4_sk1 <==
Procesing 21474508 updates took 128.651 seconds, 166920 per second
Connected Components algorithm took 20.4047 and found 1 CC
Query: 0.09
DSU Merge: 0.015
Sketch Merge: 17.693
Query: 0.001
DSU Merge: 0.001
Sketch Merge: 2.218
Query: 0.013
DSU Merge: 0
Sketch Merge: 0.228
Query: 0
DSU Merge: 0
Sketch Merge: 0.063
Query: 0
DSU Merge: 0
Sketch Merge: 0.027
Inter-|   Receive                                                |  Transmit
 face |bytes    packets errs drop fifo frame compressed multicast|bytes    packets errs drop fifo colls carrier compressed
    lo: 2859920    2475    0    0    0     0          0         0  2859920    2475    0    0    0     0       0          0
  eth0: 73609999 1284888    0    0    0     0          0         0 1554078864 2550594    0    0    0     0       0          0

==> delta_4_sk2 <==
Procesing 21474508 updates took 105.968 seconds, 202652 per second
Connected Components algorithm took 12.1276 and found 1 CC
Query: 0.044
DSU Merge: 0.016
Sketch Merge: 10.321
Query: 0.003
DSU Merge: 0.001
Sketch Merge: 1.553
Query: 0.012
DSU Merge: 0
Sketch Merge: 0.087
Query: 0
DSU Merge: 0
Sketch Merge: 0.031
Inter-|   Receive                                                |  Transmit
 face |bytes    packets errs drop fifo frame compressed multicast|bytes    packets errs drop fifo colls carrier compressed
    lo: 2863008    2511    0    0    0     0          0         0  2863008    2511    0    0    0     0       0          0
  eth0: 137851434 2488313    0    0    0     0          0         0 3025057229 4975749    0    0    0     0       0          0

==> delta_4_sk4 <==
Procesing 21474508 updates took 76.5214 seconds, 280634 per second
Connected Components algorithm took 11.7554 and found 1 CC
Query: 0.079
DSU Merge: 0.014
Sketch Merge: 9.168
Query: 0.013
DSU Merge: 0.001
Sketch Merge: 2.106
Query: 0.015
DSU Merge: 0
Sketch Merge: 0.203
Query: 0
DSU Merge: 0
Sketch Merge: 0.043
Query: 0
DSU Merge: 0
Sketch Merge: 0.049
Inter-|   Receive                                                |  Transmit
 face |bytes    packets errs drop fifo frame compressed multicast|bytes    packets errs drop fifo colls carrier compressed
    lo: 2866096    2547    0    0    0     0          0         0  2866096    2547    0    0    0     0       0          0
  eth0: 199172734 3636730    0    0    0     0          0         0 4488670808 7295094    0    0    0     0       0          0

==> delta_4_sk4_parallel <==
Procesing 21474508 updates took 74.808 seconds, 287062 per second
Connected Components algorithm took 10.5618 and found 1 CC
Query: 0.196
DSU Merge: 0.016
Sketch Merge: 7.798
Query: 0.015
DSU Merge: 0.001
Sketch Merge: 2.19
Query: 0.015
DSU Merge: 0
Sketch Merge: 0.2
Query: 0.001
DSU Merge: 0
Sketch Merge: 0.041
Query: 0
DSU Merge: 0
Sketch Merge: 0.028
Inter-|   Receive                                                |  Transmit
 face |bytes    packets errs drop fifo frame compressed multicast|bytes    packets errs drop fifo colls carrier compressed
    lo: 4793338    4404    0    0    0     0          0         0  4793338    4404    0    0    0     0       0          0
  eth0: 470372981 8576447    0    0    0     0          0         0 10665043514 17198012    0    0    0     0       0          0

==> delta_4_sk8 <==
Procesing 21474508 updates took 57.4946 seconds, 373505 per second
Connected Components algorithm took 16.8419 and found 1 CC
Query: 0.161
DSU Merge: 0.015
Sketch Merge: 14.261
Query: 0.002
DSU Merge: 0.001
Sketch Merge: 2.086
Query: 0.013
DSU Merge: 0
Sketch Merge: 0.15
Query: 0
DSU Merge: 0
Sketch Merge: 0.038
Query: 0
DSU Merge: 0
Sketch Merge: 0.043
Inter-|   Receive                                                |  Transmit
 face |bytes    packets errs drop fifo frame compressed multicast|bytes    packets errs drop fifo colls carrier compressed
    lo: 3830400    3430    0    0    0     0          0         0  3830400    3430    0    0    0     0       0          0
  eth0: 267427639 4830957    0    0    0     0          0         0 6009071559 9702674    0    0    0     0       0          0