| Message ID | 20230223030451.543162-1-senozhatsky@chromium.org (mailing list archive) |
|---|---|
| Headers | show |
| Series | zsmalloc: fine-grained fullness and new compaction algorithm | expand |
On Thu, Feb 23, 2023 at 12:04:45PM +0900, Sergey Senozhatsky wrote: > Hi, > > Existing zsmalloc page fullness grouping leads to suboptimal page > selection for both zs_malloc() and zs_compact(). This patchset > reworks zsmalloc fullness grouping/classification. > > Additinally it also implements new compaction algorithm that is > expected to use CPU-cycles (as it potentially does fewer memcpy-s > in zs_object_copy()). > > TEST > ==== > > It's very challenging to reliably test this series. I ended up > developing my own synthetic test that has 100% reproducibility. > The test generates significan fragmentation (for each size class) > and then performs compaction for each class individually and tracks > the number of memcpy() in zs_object_copy(), so that we can compare > the amount work compaction does on per-class basis. > > Total amount of work (zram mm_stat objs_moved) > ---------------------------------------------- > > Old fullness grouping, old compaction algorithm: > 323977 memcpy() in zs_object_copy(). > > Old fullness grouping, new compaction algorithm: > 262944 memcpy() in zs_object_copy(). > > New fullness grouping, new compaction algorithm: > 213978 memcpy() in zs_object_copy(). > > > Per-class compaction memcpy() comparison (T-test) Just curiosity: What's the T-test? > ------------------------------------------------- > > x Old fullness grouping, old compaction algorithm > + Old fullness grouping, new compaction algorithm > > N Min Max Median Avg Stddev > x 140 349 3513 2461 2314.1214 806.03271 > + 140 289 2778 2006 1878.1714 641.02073 > Difference at 95.0% confidence > -435.95 +/- 170.595 > -18.8387% +/- 7.37193% > (Student's t, pooled s = 728.216) > > > x Old fullness grouping, old compaction algorithm > + New fullness grouping, new compaction algorithm > > N Min Max Median Avg Stddev > x 140 349 3513 2461 2314.1214 806.03271 > + 140 226 2279 1644 1528.4143 524.85268 > Difference at 95.0% confidence > -785.707 +/- 159.331 > -33.9527% +/- 6.88516% > (Student's t, pooled s = 680.132) What's the different with result above? Did you just run two times and shows they are consistent or this is new result based on different testing? Anyway, this is really nice improvement. The comment I had in thread are just minors. Thanks, Sergey!
On (23/02/23 15:53), Minchan Kim wrote: > > TEST > > ==== > > > > It's very challenging to reliably test this series. I ended up > > developing my own synthetic test that has 100% reproducibility. > > The test generates significan fragmentation (for each size class) > > and then performs compaction for each class individually and tracks > > the number of memcpy() in zs_object_copy(), so that we can compare > > the amount work compaction does on per-class basis. > > > > Total amount of work (zram mm_stat objs_moved) > > ---------------------------------------------- > > > > Old fullness grouping, old compaction algorithm: > > 323977 memcpy() in zs_object_copy(). > > > > Old fullness grouping, new compaction algorithm: > > 262944 memcpy() in zs_object_copy(). > > > > New fullness grouping, new compaction algorithm: > > 213978 memcpy() in zs_object_copy(). > > > > > > Per-class compaction memcpy() comparison (T-test) > > Just curiosity: What's the T-test? T-test is a statistical method used to compare the means of two independent groups or samples and determine if the difference between them is statistically significant. > > x Old fullness grouping, old compaction algorithm > > + Old fullness grouping, new compaction algorithm > > > > N Min Max Median Avg Stddev > > x 140 349 3513 2461 2314.1214 806.03271 > > + 140 289 2778 2006 1878.1714 641.02073 > > Difference at 95.0% confidence > > -435.95 +/- 170.595 > > -18.8387% +/- 7.37193% > > (Student's t, pooled s = 728.216) > > > > > > x Old fullness grouping, old compaction algorithm > > + New fullness grouping, new compaction algorithm > > > > N Min Max Median Avg Stddev > > x 140 349 3513 2461 2314.1214 806.03271 > > + 140 226 2279 1644 1528.4143 524.85268 > > Difference at 95.0% confidence > > -785.707 +/- 159.331 > > -33.9527% +/- 6.88516% > > (Student's t, pooled s = 680.132) > > What's the different with result above? Did you just run two times and > shows they are consistent or this is new result based on different > testing? The test is exactly the same, it is designed to have 0 variability, it creates exactly same fragmentation during each run, so we always compare apples to apples. What is being changed (and hence tested) are fullness grouping and compaction algorithm. The first one tests the effect of new compaction algorithm alone: old fullness grouping and old compaction algorithm VS old fullness grouping and new compaction algorithm. The data show that with sufficient level of confidence (95%) we can claim that new compaction does make a statstically significant improvement and reduce the number of memcpy() calls (by 18.3% in this particular case). The second one tests the effect of new fullness grouping and new compaction algorithm. The data show that with sufficient level of confidence we can claim that new fullness grouping and new compaction do make a statstically significant improvement and reduce the number of memcpy() calls (by 33.9% in this particular case).
On Sun, Feb 26, 2023 at 12:50:45PM +0900, Sergey Senozhatsky wrote: > On (23/02/23 15:53), Minchan Kim wrote: > > > TEST > > > ==== > > > > > > It's very challenging to reliably test this series. I ended up > > > developing my own synthetic test that has 100% reproducibility. > > > The test generates significan fragmentation (for each size class) > > > and then performs compaction for each class individually and tracks > > > the number of memcpy() in zs_object_copy(), so that we can compare > > > the amount work compaction does on per-class basis. > > > > > > Total amount of work (zram mm_stat objs_moved) > > > ---------------------------------------------- > > > > > > Old fullness grouping, old compaction algorithm: > > > 323977 memcpy() in zs_object_copy(). > > > > > > Old fullness grouping, new compaction algorithm: > > > 262944 memcpy() in zs_object_copy(). > > > > > > New fullness grouping, new compaction algorithm: > > > 213978 memcpy() in zs_object_copy(). > > > > > > > > > Per-class compaction memcpy() comparison (T-test) > > > > Just curiosity: What's the T-test? > > T-test is a statistical method used to compare the means > of two independent groups or samples and determine if the > difference between them is statistically significant. > > > > x Old fullness grouping, old compaction algorithm > > > + Old fullness grouping, new compaction algorithm > > > > > > N Min Max Median Avg Stddev > > > x 140 349 3513 2461 2314.1214 806.03271 > > > + 140 289 2778 2006 1878.1714 641.02073 > > > Difference at 95.0% confidence > > > -435.95 +/- 170.595 > > > -18.8387% +/- 7.37193% > > > (Student's t, pooled s = 728.216) > > > > > > > > > x Old fullness grouping, old compaction algorithm > > > + New fullness grouping, new compaction algorithm > > > > > > N Min Max Median Avg Stddev > > > x 140 349 3513 2461 2314.1214 806.03271 > > > + 140 226 2279 1644 1528.4143 524.85268 > > > Difference at 95.0% confidence > > > -785.707 +/- 159.331 > > > -33.9527% +/- 6.88516% > > > (Student's t, pooled s = 680.132) > > > > What's the different with result above? Did you just run two times and > > shows they are consistent or this is new result based on different > > testing? > > The test is exactly the same, it is designed to have 0 variability, it > creates exactly same fragmentation during each run, so we always compare > apples to apples. What is being changed (and hence tested) are fullness > grouping and compaction algorithm. > > The first one tests the effect of new compaction algorithm alone: > old fullness grouping and old compaction algorithm VS old fullness > grouping and new compaction algorithm. The data show that with > sufficient level of confidence (95%) we can claim that new compaction > does make a statstically significant improvement and reduce the number > of memcpy() calls (by 18.3% in this particular case). > > The second one tests the effect of new fullness grouping and new > compaction algorithm. The data show that with sufficient level of > confidence we can claim that new fullness grouping and new compaction > do make a statstically significant improvement and reduce the number > of memcpy() calls (by 33.9% in this particular case). Thanks for the explanation, Sergey. Please include the testing result data in the description of the patch you made significant change to achieve it as well as cover letter. Otherwise, zsmalloc-remove-insert_zspage-inuse-optimization.patch has every data now but that patch didn't make such an improvement.
On (23/02/28 14:17), Minchan Kim wrote: > Thanks for the explanation, Sergey. > > Please include the testing result data in the description of the patch > you made significant change to achieve it as well as cover letter. OK, I can include it into the "new compaction algorithm" patch.
On Wed, Mar 01, 2023 at 12:57:51PM +0900, Sergey Senozhatsky wrote: > On (23/02/28 14:17), Minchan Kim wrote: > > Thanks for the explanation, Sergey. > > > > Please include the testing result data in the description of the patch > > you made significant change to achieve it as well as cover letter. > > OK, I can include it into the "new compaction algorithm" patch. Thanks.
Hi, Existing zsmalloc page fullness grouping leads to suboptimal page selection for both zs_malloc() and zs_compact(). This patchset reworks zsmalloc fullness grouping/classification. Additinally it also implements new compaction algorithm that is expected to use CPU-cycles (as it potentially does fewer memcpy-s in zs_object_copy()). TEST ==== It's very challenging to reliably test this series. I ended up developing my own synthetic test that has 100% reproducibility. The test generates significan fragmentation (for each size class) and then performs compaction for each class individually and tracks the number of memcpy() in zs_object_copy(), so that we can compare the amount work compaction does on per-class basis. Total amount of work (zram mm_stat objs_moved) ---------------------------------------------- Old fullness grouping, old compaction algorithm: 323977 memcpy() in zs_object_copy(). Old fullness grouping, new compaction algorithm: 262944 memcpy() in zs_object_copy(). New fullness grouping, new compaction algorithm: 213978 memcpy() in zs_object_copy(). Per-class compaction memcpy() comparison (T-test) ------------------------------------------------- x Old fullness grouping, old compaction algorithm + Old fullness grouping, new compaction algorithm N Min Max Median Avg Stddev x 140 349 3513 2461 2314.1214 806.03271 + 140 289 2778 2006 1878.1714 641.02073 Difference at 95.0% confidence -435.95 +/- 170.595 -18.8387% +/- 7.37193% (Student's t, pooled s = 728.216) x Old fullness grouping, old compaction algorithm + New fullness grouping, new compaction algorithm N Min Max Median Avg Stddev x 140 349 3513 2461 2314.1214 806.03271 + 140 226 2279 1644 1528.4143 524.85268 Difference at 95.0% confidence -785.707 +/- 159.331 -33.9527% +/- 6.88516% (Student's t, pooled s = 680.132) Sergey Senozhatsky (6): zsmalloc: remove insert_zspage() ->inuse optimization zsmalloc: remove stat and fullness enums zsmalloc: fine-grained inuse ratio based fullness grouping zsmalloc: rework compaction algorithm zsmalloc: extend compaction statistics zram: show zsmalloc objs_moved stat in mm_stat Documentation/admin-guide/blockdev/zram.rst | 1 + drivers/block/zram/zram_drv.c | 5 +- include/linux/zsmalloc.h | 2 + mm/zsmalloc.c | 365 ++++++++++---------- 4 files changed, 188 insertions(+), 185 deletions(-)