search

yukiregista / ConsensusProj

MIT License
2 stars 0 forks source link

Pruning: メモリ計測 #64

Open yukiregista opened 1 month ago

yukiregista commented 1 month ago

以下を別の$n,N$の各サンプルに対して$K$を変化させつつ報告していただきたいです。

他に良いものがなければ valgrind の massifツール (or gperftools の heap_profile) を使ってもらえると助かります。ただし、結構時間がかかると思うので、サイズが大きいものに関してはもっと簡易的な計り方（usr/bin/timeなど）でも構いません。

期待としては、$O(nNK)$になっていて欲しい！

yukiregista commented 1 month ago

Mammals data での実験：17GBくらい使っていた模様

--------------------------------------------------------------------------------
Command:            python test_big.py
Massif arguments:   (none)
ms_print arguments: --threshold=100 --x=40 --y=10 massif.out.7775
--------------------------------------------------------------------------------

    GB
16.79^                                       :
     |                                 :::@:@#
     |    ::::::@:::::::::::::::@:::::@:::@:@#
     |  @@::::::@:::::::::::::::@:::::@:::@:@#
     |  @ ::::::@:::::::::::::::@:::::@:::@:@#
     |  @ ::::::@:::::::::::::::@:::::@:::@:@#
     |  @ ::::::@:::::::::::::::@:::::@:::@:@#
     | @@ ::::::@:::::::::::::::@:::::@:::@:@#
     | @@ ::::::@:::::::::::::::@:::::@:::@:@#
     |@@@ ::::::@:::::::::::::::@:::::@:::@:@#
   0 +--------------------------------------->Ti
     0                                   1.736

Number of snapshots: 86
 Detailed snapshots: [1, 2, 3, 4, 13, 33, 40, 45, 48, 58, 60, 70, 74 (peak), 84]

--------------------------------------------------------------------------------
  n        time(i)         total(B)   useful-heap(B) extra-heap(B)    stacks(B)
--------------------------------------------------------------------------------
  0              0                0                0             0            0
  1 34,408,450,812    3,010,049,472    2,916,705,110    93,344,362            0
96.90% (2,916,705,110B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc.
->96.90% (2,916,705,110B) in 10+ places, all below ms_print's threshold (100.00%)

--------------------------------------------------------------------------------
  n        time(i)         total(B)   useful-heap(B) extra-heap(B)    stacks(B)
--------------------------------------------------------------------------------
  2 65,404,055,625    6,101,880,552    5,910,466,938   191,413,614            0
96.86% (5,910,466,938B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc.
->96.86% (5,910,466,938B) in 8+ places, all below ms_print's threshold (100.00%)

--------------------------------------------------------------------------------
  n        time(i)         total(B)   useful-heap(B) extra-heap(B)    stacks(B)
--------------------------------------------------------------------------------
  3 108,013,617,166   10,340,021,360   10,014,341,426   325,679,934            0
96.85% (10,014,341,426B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc.
->96.85% (10,014,341,426B) in 8+ places, all below ms_print's threshold (100.00%)

--------------------------------------------------------------------------------
  n        time(i)         total(B)   useful-heap(B) extra-heap(B)    stacks(B)
--------------------------------------------------------------------------------
  4 142,879,564,917   13,799,108,176   13,363,976,448   435,131,728            0
96.85% (13,363,976,448B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc.
->96.85% (13,363,976,448B) in 8+ places, all below ms_print's threshold (100.00%)

--------------------------------------------------------------------------------
  n        time(i)         total(B)   useful-heap(B) extra-heap(B)    stacks(B)
--------------------------------------------------------------------------------
  5 191,282,146,122   16,124,934,440   15,584,016,664   540,917,776            0
  6 219,501,526,675   16,124,934,440   15,584,016,664   540,917,776            0
  7 275,942,372,689   16,124,934,440   15,584,016,664   540,917,776            0
  8 321,093,614,173   16,124,934,440   15,584,016,664   540,917,776            0
  9 348,630,496,408   16,124,934,456   15,584,016,664   540,917,792            0
 10 390,586,218,839   16,124,934,456   15,584,016,664   540,917,792            0
 11 436,356,121,164   16,124,934,440   15,584,016,664   540,917,776            0
 12 470,683,440,362   16,124,934,456   15,584,016,664   540,917,792            0
 13 497,382,519,699   16,124,934,440   15,584,016,664   540,917,776            0
96.65% (15,584,016,664B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc.
->96.65% (15,584,016,664B) in 8+ places, all below ms_print's threshold (100.00%)

--------------------------------------------------------------------------------
  n        time(i)         total(B)   useful-heap(B) extra-heap(B)    stacks(B)
--------------------------------------------------------------------------------
 14 528,368,173,873   16,124,934,440   15,584,016,664   540,917,776            0
 15 578,321,516,201   16,124,934,456   15,584,016,664   540,917,792            0
 16 614,439,717,407   16,124,934,456   15,584,016,664   540,917,792            0
 17 641,106,980,518   16,124,934,440   15,584,016,664   540,917,776            0
 18 681,107,910,964   16,124,934,440   15,584,016,664   540,917,776            0
 19 714,442,186,884   16,124,934,440   15,584,016,664   540,917,776            0
 20 737,776,170,677   16,124,934,456   15,584,016,664   540,917,792            0
 21 771,662,280,904   16,124,934,456   15,584,016,664   540,917,792            0
 22 797,490,843,387   16,124,934,440   15,584,016,664   540,917,776            0
 23 837,286,683,425   16,124,934,440   15,584,016,664   540,917,776            0
 24 888,136,575,280   16,124,934,440   15,584,016,664   540,917,776            0
 25 925,150,415,395   16,124,934,440   15,584,016,664   540,917,776            0
 26 962,235,005,222   16,124,934,456   15,584,016,664   540,917,792            0
 27 1,016,435,592,585   16,124,934,456   15,584,016,664   540,917,792            0
 28 1,050,667,417,959   16,124,934,456   15,584,016,664   540,917,792            0
 29 1,078,342,203,972   16,124,934,456   15,584,016,664   540,917,792            0
 30 1,133,691,467,881   16,124,934,440   15,584,016,664   540,917,776            0
 31 1,161,366,797,888   16,124,934,456   15,584,016,664   540,917,792            0
 32 1,216,716,757,262   16,124,934,440   15,584,016,664   540,917,776            0
 33 1,253,418,003,633   16,124,934,456   15,584,016,664   540,917,792            0
96.65% (15,584,016,664B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc.
->96.65% (15,584,016,664B) in 8+ places, all below ms_print's threshold (100.00%)

--------------------------------------------------------------------------------
  n        time(i)         total(B)   useful-heap(B) extra-heap(B)    stacks(B)
--------------------------------------------------------------------------------
 34 1,307,804,698,037   16,124,934,440   15,584,016,664   540,917,776            0
 35 1,350,116,856,320   16,124,934,456   15,584,016,664   540,917,792            0
 36 1,396,660,204,360   16,124,934,440   15,584,016,664   540,917,776            0
 37 1,430,509,892,296   16,124,934,456   15,584,016,664   540,917,792            0
 38 1,455,897,078,002   16,124,934,456   15,584,016,664   540,917,792            0
 39 1,489,746,582,443   16,124,934,456   15,584,016,664   540,917,792            0
 40 1,546,308,211,299   16,124,934,456   15,584,016,664   540,917,792            0
96.65% (15,584,016,664B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc.
->96.65% (15,584,016,664B) in 8+ places, all below ms_print's threshold (100.00%)

--------------------------------------------------------------------------------
  n        time(i)         total(B)   useful-heap(B) extra-heap(B)    stacks(B)
--------------------------------------------------------------------------------
 41 1,579,747,646,096   16,528,721,864   15,988,294,356   540,427,508            0
 42 1,622,265,649,724   16,535,470,232   15,995,042,708   540,427,524            0
 43 1,653,603,799,271   16,540,364,952   15,999,935,828   540,429,124            0
 44 1,704,043,016,523   16,548,205,336   16,007,773,716   540,431,620            0
 45 1,732,854,056,241   16,715,381,448   16,165,920,580   549,460,868            0
96.71% (16,165,920,580B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc.
->96.71% (16,165,920,580B) in 9+ places, all below ms_print's threshold (100.00%)

--------------------------------------------------------------------------------
  n        time(i)         total(B)   useful-heap(B) extra-heap(B)    stacks(B)
--------------------------------------------------------------------------------
 46 1,774,064,659,067   17,027,893,936   16,429,407,566   598,486,370            0
 47 1,805,063,629,489   17,276,182,776   16,638,445,094   637,737,682            0
 48 1,840,919,307,485   17,568,138,344   16,882,571,608   685,566,736            0
96.10% (16,882,571,608B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc.
->96.10% (16,882,571,608B) in 11+ places, all below ms_print's threshold (100.00%)

--------------------------------------------------------------------------------
  n        time(i)         total(B)   useful-heap(B) extra-heap(B)    stacks(B)
--------------------------------------------------------------------------------
 49 1,842,780,888,299   17,583,674,304   16,895,537,504   688,136,800            0
 50 1,844,640,035,628   17,596,387,120   16,906,358,660   690,028,460            0
 51 1,846,499,203,826   17,614,518,144   16,921,475,160   693,042,984            0
 52 1,848,360,804,034   17,627,896,408   16,932,750,976   695,145,432            0
 53 1,850,221,035,236   17,640,357,656   16,943,518,768   696,838,888            0
 54 1,852,080,308,553   17,656,927,832   16,957,400,168   699,527,664            0
 55 1,853,940,838,908   17,668,830,832   16,967,596,880   701,233,952            0
 56 1,855,799,991,781   17,685,854,440   16,981,816,272   704,038,168            0
 57 1,857,660,708,623   17,700,615,416   16,994,216,304   706,399,112            0
 58 1,859,519,936,752   17,716,030,288   17,007,048,564   708,981,724            0
96.00% (17,007,048,564B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc.
->96.00% (17,007,048,564B) in 11+ places, all below ms_print's threshold (100.00%)

--------------------------------------------------------------------------------
  n        time(i)         total(B)   useful-heap(B) extra-heap(B)    stacks(B)
--------------------------------------------------------------------------------
 59 1,861,380,510,483   17,731,330,256   17,019,778,400   711,551,856            0
 60 1,862,875,550,427   17,743,833,424   17,030,189,928   713,643,496            0
95.98% (17,030,189,928B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc.
->95.98% (17,030,189,928B) in 11+ places, all below ms_print's threshold (100.00%)

--------------------------------------------------------------------------------
  n        time(i)         total(B)   useful-heap(B) extra-heap(B)    stacks(B)
--------------------------------------------------------------------------------
 61 1,864,735,872,216   17,759,867,056   17,043,524,256   716,342,800            0
 62 1,866,596,093,643   17,776,296,104   17,057,194,784   719,101,320            0
 63 1,868,455,514,977   17,789,128,144   17,067,876,536   721,251,608            0
 64 1,870,314,664,643   17,802,480,376   17,078,985,600   723,494,776            0
 65 1,872,173,929,449   17,815,931,840   17,090,183,496   725,748,344            0
 66 1,874,034,630,176   17,829,856,288   17,101,770,696   728,085,592            0
 67 1,875,893,778,033   17,843,620,840   17,113,221,640   730,399,200            0
 68 1,877,753,536,908   17,855,244,104   17,122,894,208   732,349,896            0
 69 1,879,612,702,180   17,867,331,656   17,132,960,800   734,370,856            0
 70 1,881,472,166,910   17,879,761,264   17,143,299,168   736,462,096            0
95.88% (17,143,299,168B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc.
->95.88% (17,143,299,168B) in 12+ places, all below ms_print's threshold (100.00%)

--------------------------------------------------------------------------------
  n        time(i)         total(B)   useful-heap(B) extra-heap(B)    stacks(B)
--------------------------------------------------------------------------------
 71 1,883,331,602,832   17,891,519,208   17,153,082,544   738,436,664            0
 72 1,885,190,754,803   17,904,701,272   17,164,057,624   740,643,648            0
 73 1,887,050,015,092   17,917,526,376   17,174,733,088   742,793,288            0
 74 1,887,631,034,494   17,921,300,336   17,177,876,264   743,424,072            0
95.85% (17,177,876,264B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc.
->95.85% (17,177,876,264B) in 12+ places, all below ms_print's threshold (100.00%)

--------------------------------------------------------------------------------
  n        time(i)         total(B)   useful-heap(B) extra-heap(B)    stacks(B)
--------------------------------------------------------------------------------
 75 1,889,490,272,042   17,933,368,232   17,187,911,936   745,456,296            0
 76 1,891,349,677,448   17,945,678,200   17,198,155,312   747,522,888            0
 77 1,893,208,824,771   17,958,705,920   17,209,000,356   749,705,564            0
 78 1,895,068,179,741   17,970,926,168   17,219,257,216   751,668,952            0
 79 1,896,927,367,714   17,981,170,912   17,227,784,808   753,386,104            0
 80 1,898,786,603,360   17,995,842,600   17,239,990,016   755,852,584            0
 81 1,900,645,750,754   18,006,743,360   17,249,232,340   757,511,020            0
 82 1,902,691,418,716   18,018,183,384   17,258,837,808   759,345,576            0
 83 1,904,551,639,620   18,029,345,464   17,268,365,680   760,979,784            0
 84 1,906,410,786,949   10,161,786,296    9,658,487,293   503,299,003            0
95.05% (9,658,487,293B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc.
->95.05% (9,658,487,293B) in 15+ places, all below ms_print's threshold (100.00%)

--------------------------------------------------------------------------------
  n        time(i)         total(B)   useful-heap(B) extra-heap(B)    stacks(B)
--------------------------------------------------------------------------------
 85 1,908,290,568,598      903,321,384      901,930,208     1,391,176            0
yukiregista commented 1 month ago

n=10000, N=10での実験：1.16GBしか使っていない。やはりちゃんとlinear memory usageになっていそう？

-> 後に書いた「exclude, includeをNULLにする」改善によって200MBくらいまで減った。

--------------------------------------------------------------------------------
Command:            python test_big.py
Massif arguments:   (none)
ms_print arguments: --threshold=100 massif.out.22392
--------------------------------------------------------------------------------

    GB
1.185^                                      ::::@                             
     |        #:::::::@@:::::::::::@@::::@::: ::@:::::::@:::@:::::::::@::::::@
     |        # ::: ::@ :::: : :: :@ : ::@: : ::@:::: ::@:: @: :::::::@::::::@
     |        # ::: ::@ :::: : :: :@ : ::@: : ::@:::: ::@:: @: :::::::@::::::@
     |        # ::: ::@ :::: : :: :@ : ::@: : ::@:::: ::@:: @: :::::::@::::::@
     |      ::# ::: ::@ :::: : :: :@ : ::@: : ::@:::: ::@:: @: :::::::@::::::@
     |      : # ::: ::@ :::: : :: :@ : ::@: : ::@:::: ::@:: @: :::::::@::::::@
     |      : # ::: ::@ :::: : :: :@ : ::@: : ::@:::: ::@:: @: :::::::@::::::@
     |     :: # ::: ::@ :::: : :: :@ : ::@: : ::@:::: ::@:: @: :::::::@::::::@
     |     :: # ::: ::@ :::: : :: :@ : ::@: : ::@:::: ::@:: @: :::::::@::::::@
     |     :: # ::: ::@ :::: : :: :@ : ::@: : ::@:::: ::@:: @: :::::::@::::::@
     |     :: # ::: ::@ :::: : :: :@ : ::@: : ::@:::: ::@:: @: :::::::@::::::@
     |     :: # ::: ::@ :::: : :: :@ : ::@: : ::@:::: ::@:: @: :::::::@::::::@
     |   :::: # ::: ::@ :::: : :: :@ : ::@: : ::@:::: ::@:: @: :::::::@::::::@
     |   : :: # ::: ::@ :::: : :: :@ : ::@: : ::@:::: ::@:: @: :::::::@::::::@
     |   : :: # ::: ::@ :::: : :: :@ : ::@: : ::@:::: ::@:: @: :::::::@::::::@
     |  :: :: # ::: ::@ :::: : :: :@ : ::@: : ::@:::: ::@:: @: :::::::@::::::@
     |  :: :: # ::: ::@ :::: : :: :@ : ::@: : ::@:::: ::@:: @: :::::::@::::::@
     |  :: :: # ::: ::@ :::: : :: :@ : ::@: : ::@:::: ::@:: @: :::::::@::::::@
     |  :: :: # ::: ::@ :::: : :: :@ : ::@: : ::@:::: ::@:: @: :::::::@::::::@
   0 +----------------------------------------------------------------------->Gi
     0                                                                   188.5

Number of snapshots: 69
 Detailed snapshots: [1, 6 (peak), 13, 25, 29, 35, 42, 45, 57, 67]

--------------------------------------------------------------------------------
  n        time(i)         total(B)   useful-heap(B) extra-heap(B)    stacks(B)
--------------------------------------------------------------------------------
  0              0                0                0             0            0
  1  3,479,268,578       25,922,072       25,712,401       209,671            0
99.19% (25,712,401B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc.
->99.19% (25,712,401B) in 7+ places, all below ms_print's threshold (100.00%)

--------------------------------------------------------------------------------
  n        time(i)         total(B)   useful-heap(B) extra-heap(B)    stacks(B)
--------------------------------------------------------------------------------
  2  6,034,115,604      254,912,064      242,005,272    12,906,792            0
  3  9,760,445,727      469,344,944      449,666,696    19,678,248            0
  4 14,502,860,630      790,269,952      760,541,292    29,728,660            0
  5 17,884,835,102    1,003,991,976      967,607,252    36,384,724            0
  6 22,718,610,148    1,260,680,944    1,217,534,596    43,146,348            0
96.58% (1,217,534,596B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc.
->96.58% (1,217,534,596B) in 9+ places, all below ms_print's threshold (100.00%)

--------------------------------------------------------------------------------
  n        time(i)         total(B)   useful-heap(B) extra-heap(B)    stacks(B)
--------------------------------------------------------------------------------
  7 25,273,781,305    1,272,649,608    1,228,712,252    43,937,356            0
  8 28,293,676,543    1,272,649,608    1,228,712,252    43,937,356            0
  9 31,829,571,320    1,272,649,608    1,228,712,252    43,937,356            0
 10 36,525,849,046    1,272,649,608    1,228,712,252    43,937,356            0
 11 39,880,950,613    1,272,649,656    1,228,712,040    43,937,616            0
 12 42,229,213,527    1,272,649,656    1,228,712,040    43,937,616            0
 13 46,254,475,239    1,272,649,656    1,228,712,040    43,937,616            0
96.55% (1,228,712,040B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc.
->96.55% (1,228,712,040B) in 9+ places, all below ms_print's threshold (100.00%)

--------------------------------------------------------------------------------
  n        time(i)         total(B)   useful-heap(B) extra-heap(B)    stacks(B)
--------------------------------------------------------------------------------
 14 51,108,276,902    1,272,649,656    1,228,712,040    43,937,616            0
 15 53,432,196,322    1,272,649,656    1,228,712,040    43,937,616            0
 16 56,685,446,098    1,272,649,784    1,228,712,292    43,937,492            0
 17 59,009,094,023    1,272,649,784    1,228,712,292    43,937,492            0
 18 61,797,640,118    1,272,649,784    1,228,712,292    43,937,492            0
 19 65,515,612,268    1,272,649,784    1,228,712,292    43,937,492            0
 20 67,374,920,397    1,272,649,784    1,228,712,292    43,937,492            0
 21 70,949,018,101    1,272,649,784    1,228,712,292    43,937,492            0
 22 74,090,389,162    1,272,649,688    1,228,712,052    43,937,636            0
 23 78,802,503,117    1,272,649,688    1,228,712,052    43,937,636            0
 24 81,944,099,904    1,272,649,688    1,228,712,052    43,937,636            0
 25 84,300,233,451    1,272,649,688    1,228,712,052    43,937,636            0
96.55% (1,228,712,052B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc.
->96.55% (1,228,712,052B) in 9+ places, all below ms_print's threshold (100.00%)

--------------------------------------------------------------------------------
  n        time(i)         total(B)   useful-heap(B) extra-heap(B)    stacks(B)
--------------------------------------------------------------------------------
 26 88,227,134,360    1,272,649,688    1,228,712,052    43,937,636            0
 27 92,939,456,213    1,272,649,368    1,228,711,836    43,937,532            0
 28 96,866,296,103    1,272,649,368    1,228,711,836    43,937,532            0
 29 100,007,893,196    1,272,649,368    1,228,711,836    43,937,532            0
96.55% (1,228,711,836B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc.
->96.55% (1,228,711,836B) in 9+ places, all below ms_print's threshold (100.00%)

--------------------------------------------------------------------------------
  n        time(i)         total(B)   useful-heap(B) extra-heap(B)    stacks(B)
--------------------------------------------------------------------------------
 30 103,934,884,214    1,272,649,368    1,228,711,836    43,937,532            0
 31 107,076,424,885    1,272,649,896    1,228,712,256    43,937,640            0
 32 109,432,439,567    1,272,649,896    1,228,712,256    43,937,640            0
 33 112,872,745,491    1,272,649,896    1,228,712,256    43,937,640            0
 34 116,313,155,817    1,272,649,896    1,228,712,256    43,937,640            0
 35 118,606,931,329    1,272,649,896    1,228,712,256    43,937,640            0
96.55% (1,228,712,256B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc.
->96.55% (1,228,712,256B) in 9+ places, all below ms_print's threshold (100.00%)

--------------------------------------------------------------------------------
  n        time(i)         total(B)   useful-heap(B) extra-heap(B)    stacks(B)
--------------------------------------------------------------------------------
 36 122,047,546,097    1,272,649,464    1,228,711,972    43,937,492            0
 37 125,487,886,053    1,272,649,464    1,228,711,972    43,937,492            0
 38 128,928,391,937    1,272,649,464    1,228,711,972    43,937,492            0
 39 131,222,084,152    1,272,649,464    1,228,711,972    43,937,492            0
 40 135,809,289,500    1,272,649,464    1,228,711,972    43,937,492            0
 41 139,249,589,624    1,272,649,624    1,228,712,004    43,937,620            0
 42 141,543,130,452    1,272,649,624    1,228,712,004    43,937,620            0
96.55% (1,228,712,004B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc.
->96.55% (1,228,712,004B) in 9+ places, all below ms_print's threshold (100.00%)

--------------------------------------------------------------------------------
  n        time(i)         total(B)   useful-heap(B) extra-heap(B)    stacks(B)
--------------------------------------------------------------------------------
 43 144,983,414,517    1,272,649,624    1,228,712,004    43,937,620            0
 44 148,423,936,754    1,272,649,624    1,228,712,004    43,937,620            0
 45 153,011,182,587    1,272,649,624    1,228,712,004    43,937,620            0
96.55% (1,228,712,004B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc.
->96.55% (1,228,712,004B) in 9+ places, all below ms_print's threshold (100.00%)

--------------------------------------------------------------------------------
  n        time(i)         total(B)   useful-heap(B) extra-heap(B)    stacks(B)
--------------------------------------------------------------------------------
 46 156,451,720,660    1,272,649,320    1,228,711,768    43,937,552            0
 47 161,038,799,651    1,272,649,320    1,228,711,768    43,937,552            0
 48 163,332,537,897    1,272,649,320    1,228,711,768    43,937,552            0
 49 166,773,127,857    1,272,649,320    1,228,711,768    43,937,552            0
 50 168,632,513,747    1,272,649,320    1,228,711,768    43,937,552            0
 51 170,491,898,630    1,272,649,320    1,228,711,768    43,937,552            0
 52 172,351,438,949    1,272,649,736    1,228,712,116    43,937,620            0
 53 174,210,946,683    1,272,649,736    1,228,712,116    43,937,620            0
 54 176,070,327,800    1,272,649,736    1,228,712,116    43,937,620            0
 55 177,929,836,921    1,272,649,736    1,228,712,116    43,937,620            0
 56 179,789,187,748    1,272,649,736    1,228,712,116    43,937,620            0
 57 181,648,577,045    1,272,649,736    1,228,712,116    43,937,620            0
96.55% (1,228,712,116B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc.
->96.55% (1,228,712,116B) in 9+ places, all below ms_print's threshold (100.00%)

--------------------------------------------------------------------------------
  n        time(i)         total(B)   useful-heap(B) extra-heap(B)    stacks(B)
--------------------------------------------------------------------------------
 58 183,507,962,098    1,272,649,736    1,228,712,116    43,937,620            0
 59 185,367,312,926    1,272,649,736    1,228,712,116    43,937,620            0
 60 187,244,195,229    1,243,271,984    1,202,718,488    40,553,496            0
 61 189,304,073,682    1,243,623,760    1,203,070,264    40,553,496            0
 62 191,235,385,981    1,243,928,880    1,203,375,384    40,553,496            0
 63 193,118,693,075    1,244,219,376    1,203,665,880    40,553,496            0
 64 194,980,004,064    1,247,020,464    1,206,463,304    40,557,160            0
 65 196,839,610,986    1,247,037,512    1,206,480,080    40,557,432            0
 66 198,698,969,594    1,247,421,664    1,206,863,338    40,558,326            0
 67 200,559,934,565    1,247,799,016    1,207,239,146    40,559,870            0
96.75% (1,207,239,146B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc.
->96.75% (1,207,239,146B) in 10+ places, all below ms_print's threshold (100.00%)

--------------------------------------------------------------------------------
  n        time(i)         total(B)   useful-heap(B) extra-heap(B)    stacks(B)
--------------------------------------------------------------------------------
 68 202,420,035,219    1,248,937,904    1,208,296,562    40,641,342            0
yukiregista commented 1 month ago

なんかnewNodeにあるinclude, excludeがすごいメモリをくってるぽい

prof

yukiregista commented 1 month ago

excludeとincludeをNULLにしたらだいぶ減った（1ノードにつき256個もNode*を確保していた模様） prof

一方でまだnewNodeのメモリが大きい。