[PATCH v2 2/2] RISC-V: lib: Optimize memset performance

[Andrew Jones]

On Fri, May 12, 2023 at 04:51:24PM +0800, zhangfei wrote:
> From: zhangfei <zhangfei at nj.iscas.ac.cn>
> 
> On Thu, May 11, 2023 at 15:43:26PM +0200, Andrew Jones wrote:
> > On Thu, May 11, 2023 at 09:34:53AM +0800, zhangfei wrote:
> > > From: zhangfei <zhangfei at nj.iscas.ac.cn>
> > > 
> > > Optimized performance when the data size is less than 16 bytes.
> > > Compared to byte by byte storage, significant performance improvement has been achieved.
> > > It allows storage instructions to be executed in parallel and reduces the number of jumps.
> > 
> > Please wrap commit message lines at 74 chars.
> > 
> > > Additional checks can avoid redundant stores.
> > > 
> > > Signed-off-by: Fei Zhang <zhangfei at nj.iscas.ac.cn>
> > > ---
> > >  arch/riscv/lib/memset.S | 40 +++++++++++++++++++++++++++++++++++++---
> > >  1 file changed, 37 insertions(+), 3 deletions(-)
> > > 
> > > diff --git a/arch/riscv/lib/memset.S b/arch/riscv/lib/memset.S
> > > index e613c5c27998..452764bc9900 100644
> > > --- a/arch/riscv/lib/memset.S
> > > +++ b/arch/riscv/lib/memset.S
> > > @@ -106,9 +106,43 @@ WEAK(memset)
> > >  	beqz	a2, 6f
> > >  	add	a3, t0, a2
> > >  5:
> > > -	sb	a1, 0(t0)
> > > -	addi	t0, t0, 1
> > > -	bltu	t0, a3, 5b
> > > +       /* fill head and tail with minimal branching */
> > > +       sb      a1,  0(t0)
> > > +       sb      a1, -1(a3)
> > > +       li 	a4, 2
> > > +       bgeu 	a4, a2, 6f
> > > +
> > > +       sb 	a1,  1(t0)
> > > +       sb 	a1,  2(t0)
> > > +       sb 	a1, -2(a3)
> > > +       sb 	a1, -3(a3)
> > > +       li 	a4, 6
> > > +       bgeu 	a4, a2, 6f
> > > +
> > > +       /* 
> > > +        * Adding additional detection to avoid 
> > > +        * redundant stores can lead 
> > > +        * to better performance
> > > +        */
> > > +       sb 	a1,  3(t0)
> > > +       sb 	a1, -4(a3)
> > > +       li 	a4, 8
> > > +       bgeu 	a4, a2, 6f
> > > +
> > > +       sb 	a1,  4(t0)
> > > +       sb 	a1, -5(a3)
> > > +       li 	a4, 10
> > > +       bgeu 	a4, a2, 6f
> > 
> > These extra checks feel ad hoc to me. Naturally you'll get better results
> > for 8 byte memsets when there's a branch to the ret after 8 bytes. But
> > what about 9? I'd think you'd want benchmarks from 1 to 15 bytes to show
> > how it performs better or worse than byte by byte for each of those sizes.
> > Also, while 8 bytes might be worth special casing, I'm not sure why 10
> > would be. What makes 10 worth optimizing more than 11?
> > 
> > Finally, microbenchmarking is quite hardware-specific and energy
> > consumption should probably also be considered. What energy cost is
> > there from making redundant stores? Is it worth it?
> 
> Hi,
> 
> I added a test from 1 to 15 bytes in the benchmarks.The test results are as 
> follows:
> Before optimization(bytes/ns):
> 1B: 0.06  2B: 0.10  3B: 0.12  4B: 0.14  5B: 0.15  6B: 0.17  7B: 0.17 8B: 0.18 
> 9B: 0.19 10B: 0.19 11B: 0.20 12B: 0.20 13B: 0.20 14B: 0.21 15B: 0.21
> After optimization(bytes/ns):
> 1B: 0.05  2B: 0.10  3B: 0.11  4B: 0.15  5B: 0.19  6B: 0.23  7B: 0.23 8B: 0.26 
> 9B: 0.24 10B: 0.27 11B: 0.25 12B: 0.27 13B: 0.28 14B: 0.30 15B: 0.31
> 
> From the above results, it can be seen that the performance of 1-4 bytes is 
> similar, with a significant improvement in 5-15 bytes.At the same time, it can
> be seen that redundant stores does indeed lead to performance degradation, 
> such as at 9 bytes and 11 bytes.
> 
> Next, I modified the code to check 2, 6, 8, 11, 14, as shown below:
> '''
> sb a1, 4(t0)
> sb a1, 5(t0)
> sb a1, -5(a3)
> li a4, 11
> bgeu a4, a2, 6f
> 
> sb a1, 6(t0)
> sb a1, -6(a3)
> sb a1, -7(a3)
> li a4, 14
> bgeu a4, a2, 6f
> '''
> The results obtained in this way are as follows:
> After optimization(bytes/ns):
> 1B: 0.05  2B: 0.10  3B: 0.11  4B: 0.15  5B: 0.19  6B: 0.23  7B: 0.23 8B: 0.27 
> 9B: 0.23 10B: 0.26 11B: 0.29 12B: 0.26 13B: 0.28 14B: 0.29 15B: 0.31
> 
> From the above results, it can be seen that when we modified it to check at 11,
> the performance improved from 0.25 bytes/ns to 0.29 bytes/ns.Is it possible to 
> minimize redundant stores while ensuring parallel stores to achieve optimal 
> performance?
> 
> Therefore, I modified the code to detect 2, 4, 6, 8, 10, 12, 14, as shown below:
> '''        
> sb a1, 4(t0)
> sb a1, -5(a3)
> li a4, 10
> bgeu a4, a2, 6f
> 
> sb a1, 5(t0)
> sb a1, -6(a3)
> li a4, 12
> bgeu a4, a2, 6f
> 
> sb a1, 6(t0)
> sb a1, -7(a3)
> li a4, 14
> bgeu a4, a2, 6f
> '''
> The results obtained in this way are as follows:
> After optimization(bytes/ns):
> 1B: 0.05  2B: 0.10  3B: 0.12  4B: 0.17  5B: 0.18  6B: 0.21  7B: 0.22 8B: 0.25 
> 9B: 0.24 10B: 0.26 11B: 0.25 12B: 0.27 13B: 0.26 14B: 0.27 15B: 0.29
> 
> From the above results, it can be seen that this approach did not achieve the best
> performance.
> 
> Through the above experiment, here is my conclusion:
> 1.This optimization method will inevitably result in duplicate storage. I cannot 
> achieve the optimal state of each byte, for example, when I add checks on 9, 
> the performance of 9 will naturally improve, but 10 and 11 may become worse due 
> to redundant stores.Therefore, I need to make a trade-off between redundant stores
> and parallelism, such as checking 9 or 10, or something else.
> 
> 2.Storing parallelism and reducing jumps will compensate for the cost of redundant
> stores. Based on the current multiple test results, regardless of which bytes I 
> modify to check, its performance is better than byte by byte storage.
> 
> 3.From the above experiment, for the detection of 2, 6, 8, 11, and 14, its overall
> performance is the best.
> 
> Because I am not a chip designer, I find it difficult to answer specific energy 
> consumption costs. Do you have any suggestions and how to conduct testing in this 
> regard? I think although storage has increased, there has been a corresponding 
> reduction in jumps and the use of pipelines.

That's my point. There are so many variables that it's hard to know if it
makes sense to do this micro-optimization at all and certainly hard to
decide if adding the unnecessary branches at 8, 11, and 14 make sense.
I see some value in an 8 branch and maybe a 12, since it seems somewhat
likely memset would get used for data with sizes that are 4-byte aligned.
But even that is just speculation. I think without running comprehensive
benchmarks, and seeing an overall gain, then this isn't worth merging.
That said, if you post again with stronger justification based on these
experiments, then I'll give it a tentative r-b and let the maintainers
decide.

Thanks,
drew