Hi Jaegeuk, On 2017/12/21 4:39, Jaegeuk Kim wrote: > On 12/20, Gaoxiang (OS) wrote: >> Hi Jaegeuk, >> >> On 2017/12/20 10:31, Jaegeuk Kim wrote: >>> On 12/20, Gaoxiang (OS) wrote: >>>> Hi Jaegeuk, >>>> >>>> On 2017/12/20 7:40, Jaegeuk Kim wrote: >>>>> On 12/17, gaoxiang (P) wrote: >>>>>> clean up some redundant repeat code in build_sit_entries >>>>>> and seperate some logic into new functions: >>>>>> - build_discard_entries >>>>>> - build_sec_entries >>>>> >>>>> This patch makes another big loop redundantly? >>>>> >>>> "condition & jump" is the fundamental of "if" and loop. >>>> In the worst case, both f2fs_discard_en(sbi) and sbi->segs_per_sec > 1 >>>> are true, and I think, we have: >>>> - the original approach: >>>> MAIN_SEGS <-- loop condition >>>> MAIN_SEGS <-- f2fs_discard_en(sbi) >>>> MAIN_SEGS <-- sbi->segs_per_sec > 1 >>>> >>>> sits_in_cursum(journal) <-- loop_condition >>>> sits_in_cursum(journal) <-- f2fs_discard_en(sbi) >>>> sits_in_cursum(journal) <-- sbi->segs_per_sec > 1 >>>> it takes about 3*(MAIN_SEGS + sits_in_cursum(journal)) jumps effort. >>>> - this patch: >>>> MAIN_SEGS <-- loop condition >>>> sits_in_cursum(journal) <-- loop_condition >>>> >>>> MAIN_SEGS <-- f2fs_discard_en(sbi) >>>> MAIN_SEGS <-- sbi->segs_per_sec > 1 >>>> it takes abourt 3*MAIN_SEGS + sits_in_cursum(journal) jumps effort. >>>> >>>> and in the best case, both f2fs_discard_en(sbi) and sbi->segs_per_sec > >>>> 1 are false, and we have: >>>> - this patch >>>> MAIN_SEGS <-- loop condition >>>> >>>> sits_in_cursum(journal) <-- loop_condition >>>> See >>>> https://stackoverflow.com/questions/1462710/can-c-compilers-optimize-if-statements-inside-for-loops >>> >>> Interesting! >>> >>> What I can think of the worst case looks like: >>> >>> In current code, >>> for (N) { >>> do_something; >>> if (f2fs_discard_en()) >>> do _something; >>> if (sbi->segs_per_sec > 1) >>> do_something; >>> } >>> for (sits_in_cursum()) { >>> do_something; >>> if (f2fs_discard_en()) >>> do _something; >>> if (sbi->segs_per_sec > 1) >>> do_something; >>> } >>> => O(N + sits_in_cursum()) >> >> In the worst case Its 3(1 -- exit condition < MAIN_SEG, 2 -- f2fs_discard_en(), 3 -- >> sbi->segs_per_sec > 1) *N + 3*sits_in_cursum() if condition & jump >> instuctions at runtime. >> >> If we use Big O notion, yes I think O(N + sits_in_cursum()) >> >>> >>> Once compiler unrolled the loop, we can expect most of jumps could be hit by >>> branch predictor, since the loop does not have many branches. >> >> The current code, if the compiler decides to unroll the loop, it could unroll it into, I guess >> for (N) { >> do_something; >> } >> if (f2fs_discard_en()) { >> for(N) { >> do _something; >> } >> } >> if (sbi->segs_per_sec > 1) { >> for(N) { >> do_something; >> } >> } >> ... >> for (sits_in_cursum()) { >> do_something; >> } >> if (f2fs_discard_en()) { >> for (N) { >> do _something; >> } >> } >> if (sbi->segs_per_sec > 1) { >> for (N) { >> do_something; >> } >> } > > Unrolled loop would be something like: > for (N/n) { > do_something #1; > if (f2fs_discard_en()) > do_something; > if (sbi->segs_per_sec > 1) > do_something; > ... > do_something #n; > if (f2fs_discard_en()) > do_something; > if (sbi->segs_per_sec > 1) > do_something; > } > > And, branch predictor can avoid three branch conditions by BTB. > > do_something #1; > if (f2fs_discard_en()) > do _something; > if (sbi->segs_per_sec > 1) > do_something; > do_something #2; > if (f2fs_discard_en()) > do _something; > if (sbi->segs_per_sec > 1) > do_something; > ... > do_something #N; > if (f2fs_discard_en()) > do _something; > if (sbi->segs_per_sec > 1) > do_something; > > Anyway, I don't see huge benefit regarding to performance and code readability, > but do worry about potential patch conflicts when backporting this. > ok, I think it depends on the kind and complexity of BTB the target processor or architecture uses and how the target architecture enhances parallelization. I am new to f2fs, curious about the f2fs detailed implementation. I'm more focused on the code readability since some code with jumps are a little bit hacky. :) Thanks, >> Taking branch predictor into consideration, I think the unrolled one is more easier to predict >> than the current rolled one. (as you say, the current has more conditions in the loop >> and a exit condition to predict) >> >>> >>> In the patch, >>> for (N) >>> do_something; >>> for (sits_in_cursum()) >>> do_something; >>> >>> if (f2fs_discard_en()) { >>> for (N) >>> do_something; >>> } >>> if (sbi->segs_per_sec > 1) { >>> for (N) >>> do_something; >>> } >>> => O(3*N + sits_in_cursum()) >> >> If we use Big O notion, I think O(N + sits_in_cursum()) too. >>> >>> BTW, build_discard_entries(struct f2fs_sb_info *sbi) is more likely to split >>> the loops, as you describe. >>> >>> In build_discard_entries(), >>> for (N) { >>> if (CP_TRIMMED_FLAG) >>> do_something; >>> else >>> do_semething_else; >>> } >>> Thanks, >>> >> >> I think so, yet CP_TRIMMED_FLAG comes from a function argument, so I think compiler >> cannot decide whether it is constant. >> >> I think if we count the runtime condition & jump instruction at runtime. >> the unrolls above are beneficial, I think. >> >> Thanks. >> >>>> >>>> In addtion, this approach is easier to read than the original >>>> one, so splitting the loop would be beneficial. >>>> >>>> Thanks >>>> >>>>>> >>>>>> Note that "if (f2fs_discard_en(sbi))" and "if (sbi->segs_per_sec > 1)" >>>>>> are all taken out of the loops they are unchangable. >>>>>> >>>>>> Signed-off-by: Gao Xiang <gaoxiang25@xxxxxxxxxx> >>>>>> --- >>>>>> fs/f2fs/segment.c | 80 +++++++++++++++++++++++++------------------------------ >>>>>> 1 file changed, 37 insertions(+), 43 deletions(-) >>>>>> >>>>>> diff --git a/fs/f2fs/segment.c b/fs/f2fs/segment.c >>>>>> index 40e1d20..bcd8a40 100644 >>>>>> --- a/fs/f2fs/segment.c >>>>>> +++ b/fs/f2fs/segment.c >>>>>> @@ -3476,12 +3476,39 @@ static int build_curseg(struct f2fs_sb_info *sbi) >>>>>> return restore_curseg_summaries(sbi); >>>>>> } >>>>>> >>>>>> +static void build_discard_entries(struct f2fs_sb_info *sbi) >>>>>> +{ >>>>>> + unsigned segno; >>>>>> + >>>>>> + for (segno = 0; segno < MAIN_SEGS(sbi); ++segno) { >>>>>> + struct seg_entry *se = get_seg_entry(sbi, segno); >>>>>> + >>>>>> + if (is_set_ckpt_flags(sbi, CP_TRIMMED_FLAG)) >>>>>> + memset(se->discard_map, 0xff, SIT_VBLOCK_MAP_SIZE); >>>>>> + else { >>>>>> + memcpy(se->discard_map, se->cur_valid_map, >>>>>> + SIT_VBLOCK_MAP_SIZE); >>>>>> + >>>>>> + sbi->discard_blks += sbi->blocks_per_seg - >>>>>> + se->valid_blocks; >>>>>> + } >>>>>> + } >>>>>> +} >>>>>> + >>>>>> +static void build_sec_entries(struct f2fs_sb_info *sbi) >>>>>> +{ >>>>>> + unsigned segno; >>>>>> + >>>>>> + for (segno = 0; segno < MAIN_SEGS(sbi); ++segno) >>>>>> + get_sec_entry(sbi, segno)->valid_blocks += >>>>>> + get_seg_entry(sbi, segno)->valid_blocks; >>>>>> +} >>>>>> + >>>>>> static void build_sit_entries(struct f2fs_sb_info *sbi) >>>>>> { >>>>>> struct sit_info *sit_i = SIT_I(sbi); >>>>>> struct curseg_info *curseg = CURSEG_I(sbi, CURSEG_COLD_DATA); >>>>>> struct f2fs_journal *journal = curseg->journal; >>>>>> - struct seg_entry *se; >>>>>> struct f2fs_sit_entry sit; >>>>>> int sit_blk_cnt = SIT_BLK_CNT(sbi); >>>>>> unsigned int i, start, end; >>>>>> @@ -3498,67 +3525,34 @@ static void build_sit_entries(struct f2fs_sb_info *sbi) >>>>>> struct f2fs_sit_block *sit_blk; >>>>>> struct page *page; >>>>>> >>>>>> - se = &sit_i->sentries[start]; >>>>>> page = get_current_sit_page(sbi, start); >>>>>> sit_blk = (struct f2fs_sit_block *)page_address(page); >>>>>> sit = sit_blk->entries[SIT_ENTRY_OFFSET(sit_i, start)]; >>>>>> f2fs_put_page(page, 1); >>>>>> >>>>>> check_block_count(sbi, start, &sit); >>>>>> - seg_info_from_raw_sit(se, &sit); >>>>>> - >>>>>> - /* build discard map only one time */ >>>>>> - if (f2fs_discard_en(sbi)) { >>>>>> - if (is_set_ckpt_flags(sbi, CP_TRIMMED_FLAG)) { >>>>>> - memset(se->discard_map, 0xff, >>>>>> - SIT_VBLOCK_MAP_SIZE); >>>>>> - } else { >>>>>> - memcpy(se->discard_map, >>>>>> - se->cur_valid_map, >>>>>> - SIT_VBLOCK_MAP_SIZE); >>>>>> - sbi->discard_blks += >>>>>> - sbi->blocks_per_seg - >>>>>> - se->valid_blocks; >>>>>> - } >>>>>> - } >>>>>> >>>>>> - if (sbi->segs_per_sec > 1) >>>>>> - get_sec_entry(sbi, start)->valid_blocks += >>>>>> - se->valid_blocks; >>>>>> + seg_info_from_raw_sit(&sit_i->sentries[start], &sit); >>>>>> } >>>>>> start_blk += readed; >>>>>> } while (start_blk < sit_blk_cnt); >>>>>> >>>>>> down_read(&curseg->journal_rwsem); >>>>>> for (i = 0; i < sits_in_cursum(journal); i++) { >>>>>> - unsigned int old_valid_blocks; >>>>>> - >>>>>> start = le32_to_cpu(segno_in_journal(journal, i)); >>>>>> - se = &sit_i->sentries[start]; >>>>>> sit = sit_in_journal(journal, i); >>>>>> >>>>>> - old_valid_blocks = se->valid_blocks; >>>>>> - >>>>>> check_block_count(sbi, start, &sit); >>>>>> - seg_info_from_raw_sit(se, &sit); >>>>>> - >>>>>> - if (f2fs_discard_en(sbi)) { >>>>>> - if (is_set_ckpt_flags(sbi, CP_TRIMMED_FLAG)) { >>>>>> - memset(se->discard_map, 0xff, >>>>>> - SIT_VBLOCK_MAP_SIZE); >>>>>> - } else { >>>>>> - memcpy(se->discard_map, se->cur_valid_map, >>>>>> - SIT_VBLOCK_MAP_SIZE); >>>>>> - sbi->discard_blks += old_valid_blocks - >>>>>> - se->valid_blocks; >>>>>> - } >>>>>> - } >>>>>> - >>>>>> - if (sbi->segs_per_sec > 1) >>>>>> - get_sec_entry(sbi, start)->valid_blocks += >>>>>> - se->valid_blocks - old_valid_blocks; >>>>>> + seg_info_from_raw_sit(&sit_i->sentries[start], &sit); >>>>>> } >>>>>> up_read(&curseg->journal_rwsem); >>>>>> + >>>>>> + /* build discard map only one time */ >>>>>> + if (f2fs_discard_en(sbi)) >>>>>> + build_discard_entries(sbi); >>>>>> + >>>>>> + if (sbi->segs_per_sec > 1) >>>>>> + build_sec_entries(sbi); >>>>>> } >>>>>> >>>>>> static void init_free_segmap(struct f2fs_sb_info *sbi) >>>>>> -- >>>>>> 2.1.4
