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

Commit Message

zhangfei May 11, 2023, 1:34 a.m. UTC

From: zhangfei <[e-mail]>

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.
Additional checks can avoid redundant stores.

Signed-off-by: Fei Zhang <[e-mail]>
---
 arch/riscv/lib/memset.S | 40 +++++++++++++++++++++++++++++++++++++---
 1 file changed, 37 insertions(+), 3 deletions(-)

Comments

Andrew Jones May 11, 2023, 7:43 a.m. UTC | #1

On Thu, May 11, 2023 at 09:34:53AM +0800, zhangfei wrote:
> From: zhangfei <[e-mail]>
> 
> 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 <[e-mail]>
> ---
>  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?

Thanks for cleaning up the patch series, but I'm still not 100%
convinced we want it.

> +
> +       sb 	a1,  5(t0)
> +       sb 	a1,  6(t0)
> +       sb 	a1, -6(a3)
> +       sb 	a1, -7(a3)
> +       li 	a4, 14
> +       bgeu 	a4, a2, 6f
> +       
> +       /* store the last byte */
> +       sb 	a1,  7(t0)
>  6:
>  	ret
>  END(__memset)
> -- 
> 2.33.0
>

Thanks,
drew

zhangfei May 12, 2023, 8:51 a.m. UTC | #2

From: zhangfei <[e-mail]>

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 <[e-mail]>
> > 
> > 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 <[e-mail]>
> > ---
> >  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.

Thanks,
Fei Zhang

Andrew Jones May 12, 2023, 9:52 a.m. UTC | #3

On Fri, May 12, 2023 at 04:51:24PM +0800, zhangfei wrote:
> From: zhangfei <[e-mail]>
> 
> 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 <[e-mail]>
> > > 
> > > 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 <[e-mail]>
> > > ---
> > >  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

David Laight May 12, 2023, 11:04 a.m. UTC | #4

From: zhangfei
> Sent: 12 May 2023 09:51
...
> 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.

I'm surprised the RISC-V cpu support parallel stores.
Typical x86 desktop cpu can only do single store (and two loads) every clock.
Clearly doing writes offset from both ends of the buffer does
reduce the number of control instructions relative to the stores.

Since memory writes can easily be queued I'd expect that your
'aim' would be one write every clock.
Achieving that requires knowledge of which instructions can execute in
parallel and the delays associated with correctly predicted branches.
That will very much depend on which RISV-V cpu you have.
Since any loop is at least two instructions (addi+blt) you almost
certainly need at least two writes per iteration.

I do think you are missing a trick though.
IIRC some RISC-V cpu properly support misaligned writes.
In that case, for long enough memset you can do something like:
	end = start + length;
	*(u64 *)start = 0
	start = (start + 24) & ~15;
	do {
		*(u64 *)(start - 16) = 0;
		*(u64 *)(start - 8) = 0;
		start += 16;
	} while (start < end);
	*(u64 *)(end - 16) = 0;
	*(u64 *)(end - 8) = 0;

> 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.

Energy use will pretty much depend on the number of clocks.
Anything else will be 2nd order noise.

What does make a difference is that increasing the code size
evicts other code from the I-cache.
This has a knock-on effect on overall system performance.
So while massively unrolling a loop will improve a benchmark
(especially if it is run 'hot-cache') there can be negative
effects on overall system performance.
The code size here probably won't have a measurable effect but
unroll to many kb and the effect can get pronounced.

	David

-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
Registration No: 1397386 (Wales)

Patch

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
+
+       sb 	a1,  5(t0)
+       sb 	a1,  6(t0)
+       sb 	a1, -6(a3)
+       sb 	a1, -7(a3)
+       li 	a4, 14
+       bgeu 	a4, a2, 6f
+       
+       /* store the last byte */
+       sb 	a1,  7(t0)
 6:
 	ret
 END(__memset)