Re: [PATCH v2 0/5] f2fs: improve performance of NAT/SIT flushing during cp

[Hou Pengyang <houpengyang@huawei.com>]

On 2017/5/24 12:14, Jaegeuk Kim wrote:
> Hi Pengyang,
>
> Could you please shed a light on some performance gains by this?

Hi, Jaegeuk,
Sorry for replying so late.

I've tested the duration of nat-radix-tree traveling and list-sort of
nat-entry, it is about *100us* averagely during fragmentation(arm64 mobile).

100us seems nobody for CP, but I still think it make senses for scenario
where massive dirty nat_entries exist in system(corner case, hard to 
produce).

Thanks,
>
> Thanks,
>
> On 05/20, Hou Pengyang wrote:
>> This patches are to designed to optimize NAT/SIT flushing procedure:
>>
>> patch 1) -- patch 3):
>>
>> during flush_nat_entries, we do:
>> 1) gang_lookup a radix tree, find all the dirty nat_entry_set;
>> 2) sort nat_entry_set by nat_entry_set->entry_cnt, in order to
>>      write to journal as much as possible to avoid unnessary IO.
>>
>> This patch optimize the look_up & sort algorithm by introducing an array:
>>
>>      f2fs_nm_info->dirty_set[NAT_ENTRY_PER_BLOCK+1];
>>      (struct list_head dirty_set[NAT_ENTRY_PER_BLOCK + 1])
>>
>> dirty_set[1] links all nat_entry_set whose entry_cnt is 1
>> dirty_set[2] links all nat_entry_set whose entry_cnt is 2
>> ......
>> dirty_set[N] links all nat_entry_set whose entry_cnt is N
>>
>> as one NAT block has NAT_ENTRY_PER_BLOCK entries at MOST, so there should NOT
>> be one nat_entry_set whose entry_cnt is larger than NAT_ENTRY_PER_BLOCK.
>>
>> So it is enough for f2fs_nm_info->dirty_set to link all nat_entry_sets in system.
>>
>> Update:
>>      we update nat_entry_set in real-time, e.g originally nat_entry_set->entry_cnt is
>> 1, and licked by dirty_set[1]; then call __set_nat_cache_dirty to increase nat_entry's
>> entry_cnt, we move this nat_entry_set ot dirty_set[2]'s tail, no need to compare.
>>
>> Flush:
>>      when flush dirty nat_entry_set, we just flush nat_entry_set from
>> f2fs_nm_info->dirty_set[0] to f2fs_nm_info->dirty_set[NAT_ENTRY_PER_BLOCK], where
>> gang_lookup and sort can be avoid.
>>
>> footprint of this algorithm:  sizeof(struct list_head)*NAT_ENTRY_PER_BLOCK
>>                                = 8*455 = 3.6k bytes
>>
>> Same for SIT.
>>
>> In patch 5), we use array to manage sit_entry_sets instead of list, which
>> can avoid list travel, and there is no need to alloc/free lab memory.
>> It is low footrpint consuming.
>>
>> Hou Pengyang (5):
>>    f2fs: use bucket sort to avoid tree lookup and list sort when nat flushing
>>    f2fs: reconstruct sit flushing code
>>    f2fs: use bucket sort to avoid list sort when flush sit entries
>>    f2fs: avoid unnecessary to_journal checking
>>    f2fs: use an array to record sit_entry_set info to make sort fast
>>
>>   fs/f2fs/f2fs.h    |   5 +-
>>   fs/f2fs/node.c    |  79 ++++++++-----------
>>   fs/f2fs/segment.c | 227 ++++++++++++++++++++++++++----------------------------
>>   fs/f2fs/segment.h |   2 +-
>>   4 files changed, 147 insertions(+), 166 deletions(-)
>>
>> --
>> 2.10.1
>>
>>
>> ------------------------------------------------------------------------------
>> Check out the vibrant tech community on one of the world's most
>> engaging tech sites, Slashdot.org! http://sdm.link/slashdot
>> _______________________________________________
>> Linux-f2fs-devel mailing list
>> Linux-f2fs-devel@lists.sourceforge.net
>> https://lists.sourceforge.net/lists/listinfo/linux-f2fs-devel
>
> .
>



------------------------------------------------------------------------------
Check out the vibrant tech community on one of the world's most
engaging tech sites, Slashdot.org! http://sdm.link/slashdot