* [musl] memset_riscv64
@ 2023-04-11 2:17 张飞
2023-04-11 9:48 ` Pedro Falcato
0 siblings, 1 reply; 10+ messages in thread
From: 张飞 @ 2023-04-11 2:17 UTC (permalink / raw)
To: musl
[-- Attachment #1: Type: text/plain, Size: 399 bytes --]
Hello,
Currently, there is no assembly implementation of the memset function for riscv64 in Musl.
This patch is a riscv64 assembly implementation of the memset function, which is implemented using the basic instruction set and
has better performance than the c language implementation in Musl. I hope it can be integrated into Musl.
Please review it and look forward to your reply.
Fei Zhang
[-- Attachment #2: memset_riscv64.patch --]
[-- Type: application/octet-stream, Size: 1845 bytes --]
diff -uprN src/string/riscv64/memset.S src/string/riscv64/memset.S
--- src/string/riscv64/memset.S 1970-01-01 08:00:00.000000000 +0800
+++ src/string/riscv64/memset.S 2023-04-11 09:43:05.733274437 +0800
@@ -0,0 +1,95 @@
+.global memset
+.type memset,@function
+
+#define SZREG 8
+#define REG_S sd
+
+memset:
+ mv t0, a0
+
+ sltiu a3, a2, 16
+ bnez a3, 4f
+
+ addi a3, t0, SZREG-1
+ andi a3, a3, ~(SZREG-1)
+ beq a3, t0, 2f
+ sub a4, a3, t0
+
+1:
+ sb a1, 0(t0)
+ addi t0, t0, 1
+ bltu t0, a3, 1b
+ sub a2, a2, a4
+
+2:
+ andi a1, a1, 0xff
+ slli a3, a1, 8
+ or a1, a3, a1
+ slli a3, a1, 16
+ or a1, a3, a1
+ slli a3, a1, 32
+ or a1, a3, a1
+
+ andi a4, a2, ~(SZREG-1)
+ add a3, t0, a4
+
+ andi a4, a4, 31*SZREG
+ beqz a4, 3f
+ neg a4, a4
+ addi a4, a4, 32*SZREG
+
+ sub t0, t0, a4
+
+ la a5, 3f
+ srli a4, a4, 1
+ add a5, a5, a4
+ jr a5
+
+3:
+ REG_S a1, 0(t0)
+ REG_S a1, SZREG(t0)
+ REG_S a1, 2*SZREG(t0)
+ REG_S a1, 3*SZREG(t0)
+ REG_S a1, 4*SZREG(t0)
+ REG_S a1, 5*SZREG(t0)
+ REG_S a1, 6*SZREG(t0)
+ REG_S a1, 7*SZREG(t0)
+ REG_S a1, 8*SZREG(t0)
+ REG_S a1, 9*SZREG(t0)
+ REG_S a1, 10*SZREG(t0)
+ REG_S a1, 11*SZREG(t0)
+ REG_S a1, 12*SZREG(t0)
+ REG_S a1, 13*SZREG(t0)
+ REG_S a1, 14*SZREG(t0)
+ REG_S a1, 15*SZREG(t0)
+ REG_S a1, 16*SZREG(t0)
+ REG_S a1, 17*SZREG(t0)
+ REG_S a1, 18*SZREG(t0)
+ REG_S a1, 19*SZREG(t0)
+ REG_S a1, 20*SZREG(t0)
+ REG_S a1, 21*SZREG(t0)
+ REG_S a1, 22*SZREG(t0)
+ REG_S a1, 23*SZREG(t0)
+ REG_S a1, 24*SZREG(t0)
+ REG_S a1, 25*SZREG(t0)
+ REG_S a1, 26*SZREG(t0)
+ REG_S a1, 27*SZREG(t0)
+ REG_S a1, 28*SZREG(t0)
+ REG_S a1, 29*SZREG(t0)
+ REG_S a1, 30*SZREG(t0)
+ REG_S a1, 31*SZREG(t0)
+ addi t0, t0, 32*SZREG
+ bltu t0, a3, 3b
+ andi a2, a2, SZREG-1
+
+4:
+ beqz a2, 6f
+ add a3, t0, a2
+
+5:
+ sb a1, 0(t0)
+ addi t0, t0, 1
+ bltu t0, a3, 5b
+
+6:
+ ret
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [musl] memset_riscv64
2023-04-11 2:17 [musl] memset_riscv64 张飞
@ 2023-04-11 9:48 ` Pedro Falcato
2023-04-19 5:33 ` 张飞
0 siblings, 1 reply; 10+ messages in thread
From: Pedro Falcato @ 2023-04-11 9:48 UTC (permalink / raw)
To: musl
On Tue, Apr 11, 2023 at 3:18 AM 张飞 <zhangfei@nj.iscas.ac.cn> wrote:
>
> Hello,
>
> Currently, there is no assembly implementation of the memset function for riscv64 in Musl.
> This patch is a riscv64 assembly implementation of the memset function, which is implemented using the basic instruction set and
> has better performance than the c language implementation in Musl. I hope it can be integrated into Musl.
Hi!
Do you have performance measurements here? What exactly is the difference?
As far as I know, no one is actively optimizing on riscv yet, only
some movements in the upstream kernel (to prepare for vector extension
stuff, unaligned loads/stores) and the corresponding glibc patches.
Mainly because it's still super unobtanium and in very early stages,
so optimizing is very hard.
So what hardware did you use? Is there a large gain here? Given that
your memset looks so simple, wouldn't it just be easier to write this
in C?
--
Pedro
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: Re: [musl] memset_riscv64
2023-04-11 9:48 ` Pedro Falcato
@ 2023-04-19 5:33 ` 张飞
2023-04-19 9:02 ` Szabolcs Nagy
0 siblings, 1 reply; 10+ messages in thread
From: 张飞 @ 2023-04-19 5:33 UTC (permalink / raw)
To: musl
[-- Attachment #1: Type: text/plain, Size: 6261 bytes --]
Hi！
I have revised the implementation of memset, which includes two versions of the basic instruction set and
vector instruction implementation, and used macro definitions to determine whether riscv hardware
supports vector extension.
The reason for implementing two versions is to hope that the memset implemented
using the basic instruction set can be applicable to all RISCV architecture CPUs, and the vector version can
accelerate the hardware supporting vector expansion.
At present, the riscv vector extension instruction set is in a frozen state, and the instruction set is stable.
In other open source libraries, such as openssl and openCV, riscv vector optimization is available.
I conducted tests on different data volumes and compared the performance of memset functions implemented
in C language, basic instruction set, and vector instruction set.The test case is test_memset.c
Performance comparison between C language implementation and assembly implementation was tested on
Sifive chips(RISC-V SiFive U74 Dual Core 64 Bit RV64GC ISA Chip Platform).
The test results are as follows.when it is less than 16 bytes, the performance of C language implementation is
better; From 16 bytes to 32768 bytes, the basic instruction implementation performance is better, with an average
improvement of over 30%; When it is greater than 32768 bytes, the performance of both is equivalent.
--------------------------------------------------------------------------------
length(byte) C language implementation(s) Basic instruction implementation(s)
--------------------------------------------------------------------------------
4 0.00000352 0.000004001
8 0.000004001 0.000005441
16 0.000006241 0.00000464
32 0.00000752 0.00000448
64 0.000008481 0.000005281
128 0.000009281 0.000005921
256 0.000011201 0.000007041
512 0.000014402 0.000010401
1024 0.000022563 0.000016962
2048 0.000039205 0.000030724
4096 0.000072809 0.000057768
8192 0.000153459 0.000132793
16384 0.000297157 0.000244992
32768 0.000784416 0.000735298
65536 0.005005252 0.004987382
131072 0.011286821 0.011256855
262144 0.023295169 0.022932165
524288 0.04647724 0.046084839
1048576 0.094114058 0.0932383
--------------------------------------------------------------------------------
Due to the lack of a chip that supports vector extension, I conducted a performance comparison test of memset
using C language and vector implementation on the Spike simulator, which has certain reference value.
It can be clearly seen that vector implementation is more efficient than C language implementation,
with an average performance improvement of over 200%.
--------------------------------------------------------------------------------
length(byte) C language implementation(s) Vector instruction implementation(s)
--------------------------------------------------------------------------------
4 0.000002839 0.000002939
8 0.000003239 0.000002939
16 0.000005239 0.000002939
32 0.000007039 0.000002939
64 0.000008039 0.000002939
128 0.000009239 0.000002939
256 0.000011639 0.000003539
512 0.000016439 0.000004739
1024 0.000026039 0.000007139
2048 0.000045239 0.000011939
4096 0.000083639 0.000021539
8192 0.000162298 0.000042598
16384 0.000317757 0.000082857
32768 0.000628675 0.000163375
65536 0.001250511 0.000324411
131072 0.002494183 0.000646483
262144 0.004981527 0.001290627
524288 0.009956215 0.002578915
1048576 0.019905591 0.005155491
--------------------------------------------------------------------------------
So I hope that a more efficient assembly implementation of riscv64 memset functions can be
integrated into musl and compatible with different riscv architectures' CPUs.
Fei Zhang
> -----原始邮件-----
> 发件人: "Pedro Falcato" <pedro.falcato@gmail.com>
> 发送时间: 2023-04-11 17:48:31 (星期二)
> 收件人: musl@lists.openwall.com
> 抄送:
> 主题: Re: [musl] memset_riscv64
>
> On Tue, Apr 11, 2023 at 3:18 AM 张飞 <zhangfei@nj.iscas.ac.cn> wrote:
> >
> > Hello,
> >
> > Currently, there is no assembly implementation of the memset function for riscv64 in Musl.
> > This patch is a riscv64 assembly implementation of the memset function, which is implemented using the basic instruction set and
> > has better performance than the c language implementation in Musl. I hope it can be integrated into Musl.
>
> Hi!
>
> Do you have performance measurements here? What exactly is the difference?
> As far as I know, no one is actively optimizing on riscv yet, only
> some movements in the upstream kernel (to prepare for vector extension
> stuff, unaligned loads/stores) and the corresponding glibc patches.
> Mainly because it's still super unobtanium and in very early stages,
> so optimizing is very hard.
>
> So what hardware did you use? Is there a large gain here? Given that
> your memset looks so simple, wouldn't it just be easier to write this
> in C?
>
> --
> Pedro
</zhangfei@nj.iscas.ac.cn></pedro.falcato@gmail.com>
[-- Attachment #2: memset_riscv64.patch --]
[-- Type: application/octet-stream, Size: 2646 bytes --]
diff -uprN src/string/riscv64/memset.S src/string/riscv64/memset.S
--- src/string/riscv64/memset.S 1970-01-01 08:00:00.000000000 +0800
+++ src/string/riscv64/memset.S 2023-04-18 13:37:22.548056966 +0800
@@ -0,0 +1,125 @@
+.global memset
+.type memset,@function
+
+#ifndef __riscv_vector
+#define SZREG 8
+#define REG_S sd
+#endif
+
+memset:
+#ifdef __riscv_vector
+ mv t0, a0
+ beqz a2, 3f
+
+ csrr t1, vlenb
+ addi t1, t1, -1
+ add a3, t0, t1
+ not t1, t1
+ and a3, a3, t1
+ beq a3, t0, 2f
+ sub a4, a3, t0
+ add a5, t0, a2
+
+1:
+ sb a1, 0(t0)
+ addi t0, t0, 1
+ beq t0, a5, 3f
+ bltu t0, a3, 1b
+ sub a2, a2, a4
+
+2:
+ vsetvli t1, a2, e8, m8, ta, ma
+ vmv.v.x v0, a1
+ sub a2, a2, t1
+ vse8.v v0, (t0)
+ add t0, t0, t1
+ bnez a2, 2b
+3:
+ ret
+
+#else
+ mv t0, a0
+
+ sltiu a3, a2, 16
+ bnez a3, 4f
+
+ addi a3, t0, SZREG-1
+ andi a3, a3, ~(SZREG-1)
+ beq a3, t0, 2f
+ sub a4, a3, t0
+1:
+ sb a1, 0(t0)
+ addi t0, t0, 1
+ bltu t0, a3, 1b
+ sub a2, a2, a4
+
+2:
+ andi a1, a1, 0xff
+ slli a3, a1, 8
+ or a1, a3, a1
+ slli a3, a1, 16
+ or a1, a3, a1
+ slli a3, a1, 32
+ or a1, a3, a1
+
+ andi a4, a2, ~(SZREG-1)
+ add a3, t0, a4
+
+ andi a4, a4, 31*SZREG
+ beqz a4, 3f
+ neg a4, a4
+ addi a4, a4, 32*SZREG
+
+ sub t0, t0, a4
+
+ la a5, 3f
+ srli a4, a4, 1
+ add a5, a5, a4
+ jr a5
+3:
+ REG_S a1, 0(t0)
+ REG_S a1, SZREG(t0)
+ REG_S a1, 2*SZREG(t0)
+ REG_S a1, 3*SZREG(t0)
+ REG_S a1, 4*SZREG(t0)
+ REG_S a1, 5*SZREG(t0)
+ REG_S a1, 6*SZREG(t0)
+ REG_S a1, 7*SZREG(t0)
+ REG_S a1, 8*SZREG(t0)
+ REG_S a1, 9*SZREG(t0)
+ REG_S a1, 10*SZREG(t0)
+ REG_S a1, 11*SZREG(t0)
+ REG_S a1, 12*SZREG(t0)
+ REG_S a1, 13*SZREG(t0)
+ REG_S a1, 14*SZREG(t0)
+ REG_S a1, 15*SZREG(t0)
+ REG_S a1, 16*SZREG(t0)
+ REG_S a1, 17*SZREG(t0)
+ REG_S a1, 18*SZREG(t0)
+ REG_S a1, 19*SZREG(t0)
+ REG_S a1, 20*SZREG(t0)
+ REG_S a1, 21*SZREG(t0)
+ REG_S a1, 22*SZREG(t0)
+ REG_S a1, 23*SZREG(t0)
+ REG_S a1, 24*SZREG(t0)
+ REG_S a1, 25*SZREG(t0)
+ REG_S a1, 26*SZREG(t0)
+ REG_S a1, 27*SZREG(t0)
+ REG_S a1, 28*SZREG(t0)
+ REG_S a1, 29*SZREG(t0)
+ REG_S a1, 30*SZREG(t0)
+ REG_S a1, 31*SZREG(t0)
+ addi t0, t0, 32*SZREG
+ bltu t0, a3, 3b
+ andi a2, a2, SZREG-1
+
+4:
+ beqz a2, 6f
+ add a3, t0, a2
+5:
+ sb a1, 0(t0)
+ addi t0, t0, 1
+ bltu t0, a3, 5b
+6:
+ ret
+#endif
[-- Attachment #3: test_memset.c --]
[-- Type: text/plain, Size: 929 bytes --]
#include <stdio.h>
#include <sys/mman.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#define DATA_SIZE 5*1024*1024
#define MAX_LEN 1*1024*1024
#define OFFSET 0
#define LOOP_TIMES 100
int main(){
char *str1,*src1;
str1 = (char *)mmap(NULL, DATA_SIZE, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0);
printf("function test start\n");
src1 = str1+OFFSET;
struct timespec tv0,tv;
for(int len=2; len<=MAX_LEN; len*=2){
clock_gettime(CLOCK_REALTIME, &tv0);
for(int k=0; k<LOOP_TIMES; k++){
memset(src1, 'a', len);
}
clock_gettime(CLOCK_REALTIME, &tv);
tv.tv_sec -= tv0.tv_sec;
if ((tv.tv_nsec -= tv0.tv_nsec) < 0) {
tv.tv_nsec += 1000000000;
tv.tv_sec--;
}
printf("len: %d time: %ld.%.9ld\n",len, (long)tv.tv_sec, (long)tv.tv_nsec);
}
printf("function test end\n");
munmap(str1,DATA_SIZE);
return 0;
}
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: Re: [musl] memset_riscv64
2023-04-19 5:33 ` 张飞
@ 2023-04-19 9:02 ` Szabolcs Nagy
2023-04-20 8:17 ` 张飞
0 siblings, 1 reply; 10+ messages in thread
From: Szabolcs Nagy @ 2023-04-19 9:02 UTC (permalink / raw)
To: 张飞; +Cc: musl
* 张飞 <zhangfei@nj.iscas.ac.cn> [2023-04-19 13:33:08 +0800]:
> --------------------------------------------------------------------------------
> length(byte) C language implementation(s) Basic instruction implementation(s)
> --------------------------------------------------------------------------------
> 4 0.00000352 0.000004001
> 8 0.000004001 0.000005441
> 16 0.000006241 0.00000464
> 32 0.00000752 0.00000448
> 64 0.000008481 0.000005281
> 128 0.000009281 0.000005921
> 256 0.000011201 0.000007041
i don't think these numbers can be trusted.
> #include <stdio.h>
> #include <sys/mman.h>
> #include <string.h>
> #include <stdlib.h>
> #include <time.h>
>
> #define DATA_SIZE 5*1024*1024
> #define MAX_LEN 1*1024*1024
> #define OFFSET 0
> #define LOOP_TIMES 100
> int main(){
> char *str1,*src1;
> str1 = (char *)mmap(NULL, DATA_SIZE, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0);
>
> printf("function test start\n");
>
> src1 = str1+OFFSET;
> struct timespec tv0,tv;
> for(int len=2; len<=MAX_LEN; len*=2){
> clock_gettime(CLOCK_REALTIME, &tv0);
> for(int k=0; k<LOOP_TIMES; k++){
> memset(src1, 'a', len);
> }
> clock_gettime(CLOCK_REALTIME, &tv);
> tv.tv_sec -= tv0.tv_sec;
> if ((tv.tv_nsec -= tv0.tv_nsec) < 0) {
> tv.tv_nsec += 1000000000;
> tv.tv_sec--;
> }
> printf("len: %d time: %ld.%.9ld\n",len, (long)tv.tv_sec, (long)tv.tv_nsec);
this repeatedly calls memset with exact same len, alignment and value.
so it favours branch heavy code since those are correctly predicted.
but even if you care about a branch-predicted microbenchmark, you
made a single measurement per size so you cannot tell how much the
time varies, you should do several measurements and take the min
so noise from system effects and cpu internal state are reduced
(also that state needs to be warmed up). and likely the LOOP_TIMES
should be bigger too for small sizes for reliable timing.
benchmarking string functions is tricky especially for a target arch
with many implementations.
> }
>
> printf("function test end\n");
> munmap(str1,DATA_SIZE);
> return 0;
> }
>
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: Re: Re: [musl] memset_riscv64
2023-04-19 9:02 ` Szabolcs Nagy
@ 2023-04-20 8:17 ` 张飞
2023-04-21 13:30 ` Szabolcs Nagy
0 siblings, 1 reply; 10+ messages in thread
From: 张飞 @ 2023-04-20 8:17 UTC (permalink / raw)
To: Szabolcs Nagy; +Cc: musl
[-- Attachment #1: Type: text/plain, Size: 7671 bytes --]
Hi!
I listened to your suggestions and referred to string.c in Musl's test set(libc-bench),
and then modified the test cases. Since BUFLEN is a fixed value in strlen.c, I modified
it to a variable as a parameter in my own test case and passed it to the memset function.
I adjusted the LOOP_TIMES has been counted up to 500 times and the running time has been
sorted, only recording the running time of the middle 300 times.
I took turns executing two programs on the SiFive chip three times each, and the results
are shown below.
First run result
--------------------------------------------------------------------------------
length(byte) C language implementation(s) Basic instruction implementation(s)
--------------------------------------------------------------------------------
100 0.002208102 0.002304056
200 0.005053208 0.004629598
400 0.008666684 0.007739176
800 0.014065196 0.012372702
1600 0.023377685 0.020090966
3200 0.040221849 0.034059631
6400 0.072095377 0.060028906
12800 0.134040475 0.110039387
25600 0.257426806 0.210710952
51200 1.173755160 1.121833227
102400 3.693170402 3.637194098
204800 8.919975455 8.865504460
409600 19.410922418 19.360956493
--------------------------------------------------------------------------------
Second run result
--------------------------------------------------------------------------------
length(byte) C language implementation(s) Basic instruction implementation(s)
--------------------------------------------------------------------------------
100 0.002208109 0.002293857
200 0.005057374 0.004640669
400 0.008674218 0.007760795
800 0.014068582 0.012417084
1600 0.023381095 0.020124496
3200 0.040225138 0.034093181
6400 0.072098744 0.060069574
12800 0.134043954 0.110088141
25600 0.256453187 0.208578633
51200 1.166602505 1.118972796
102400 3.684957231 3.635116808
204800 8.916302592 8.861590734
409600 19.411057216 19.358777670
--------------------------------------------------------------------------------
Third run result
--------------------------------------------------------------------------------
length(byte) C language implementation(s) Basic instruction implementation(s)
--------------------------------------------------------------------------------
100 0.002208111 0.002293227
200 0.005056101 0.004628539
400 0.008677756 0.007748687
800 0.014085242 0.012404443
1600 0.023397782 0.020115710
3200 0.040242985 0.034084435
6400 0.072116665 0.060063767
12800 0.134060262 0.110082427
25600 0.257865186 0.209101754
51200 1.174257177 1.117753408
102400 3.696518162 3.635417503
204800 8.929357747 8.858765915
409600 19.426520562 19.356515671
--------------------------------------------------------------------------------
From the test results, it can be seen that the runtime of memset implemented using the basic
instruction set assembly is basically shorter than that implemented using the C language.
May I ask if the test results are convincing?
> -----原始邮件-----
> 发件人: "Szabolcs Nagy" <nsz@port70.net>
> 发送时间: 2023-04-19 17:02:10 (星期三)
> 收件人: "张飞" <zhangfei@nj.iscas.ac.cn>
> 抄送: musl@lists.openwall.com
> 主题: Re: Re: [musl] memset_riscv64
>
> * 张飞 <zhangfei@nj.iscas.ac.cn> [2023-04-19 13:33:08 +0800]:
> > --------------------------------------------------------------------------------
> > length(byte) C language implementation(s) Basic instruction implementation(s)
> > --------------------------------------------------------------------------------
> > 4 0.00000352 0.000004001
> > 8 0.000004001 0.000005441
> > 16 0.000006241 0.00000464
> > 32 0.00000752 0.00000448
> > 64 0.000008481 0.000005281
> > 128 0.000009281 0.000005921
> > 256 0.000011201 0.000007041
>
> i don't think these numbers can be trusted.
>
> > #include <stdio.h>
> > #include <sys mman.h="">
> > #include <string.h>
> > #include <stdlib.h>
> > #include <time.h>
> >
> > #define DATA_SIZE 5*1024*1024
> > #define MAX_LEN 1*1024*1024
> > #define OFFSET 0
> > #define LOOP_TIMES 100
> > int main(){
> > char *str1,*src1;
> > str1 = (char *)mmap(NULL, DATA_SIZE, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0);
> >
> > printf("function test start\n");
> >
> > src1 = str1+OFFSET;
> > struct timespec tv0,tv;
> > for(int len=2; len<=MAX_LEN; len*=2){
> > clock_gettime(CLOCK_REALTIME, &tv0);
> > for(int k=0; k<loop_times; k++){=""> > memset(src1, 'a', len);
> > }
> > clock_gettime(CLOCK_REALTIME, &tv);
> > tv.tv_sec -= tv0.tv_sec;
> > if ((tv.tv_nsec -= tv0.tv_nsec) < 0) {
> > tv.tv_nsec += 1000000000;
> > tv.tv_sec--;
> > }
> > printf("len: %d time: %ld.%.9ld\n",len, (long)tv.tv_sec, (long)tv.tv_nsec);
>
>
> this repeatedly calls memset with exact same len, alignment and value.
> so it favours branch heavy code since those are correctly predicted.
>
> but even if you care about a branch-predicted microbenchmark, you
> made a single measurement per size so you cannot tell how much the
> time varies, you should do several measurements and take the min
> so noise from system effects and cpu internal state are reduced
> (also that state needs to be warmed up). and likely the LOOP_TIMES
> should be bigger too for small sizes for reliable timing.
>
> benchmarking string functions is tricky especially for a target arch
> with many implementations.
>
> > }
> >
> > printf("function test end\n");
> > munmap(str1,DATA_SIZE);
> > return 0;
> > }
> >
</loop_times;></time.h></stdlib.h></string.h></sys></stdio.h></zhangfei@nj.iscas.ac.cn></zhangfei@nj.iscas.ac.cn></nsz@port70.net>
[-- Attachment #2: test_memset2.c --]
[-- Type: text/plain, Size: 1364 bytes --]
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define BUFLEN 500000
#define LOOP_TIMES 500
int cmp(const void *a, const void *b) {
double x = *(double *)a;
double y = *(double *)b;
if (x < y) return -1;
if (x > y) return 1;
return 0;
}
int main(){
char *buf = malloc(BUFLEN);
double *arr = malloc(sizeof(double) * LOOP_TIMES);
size_t i,j,k;
struct timespec tv0,tv;
double times;
for(j=100; j<BUFLEN; j*=2){
for(k=0; k<LOOP_TIMES; k++){
for (i=0; i<100; i++)
memset(buf+i, i, j-i);
}
}
for(j=100; j<BUFLEN; j*=2){
for(k=0; k<LOOP_TIMES; k++){
clock_gettime(CLOCK_REALTIME, &tv0);
for (i=0; i<100; i++)
memset(buf+i, i, j-i);
clock_gettime(CLOCK_REALTIME, &tv);
tv.tv_sec -= tv0.tv_sec;
if ((tv.tv_nsec -= tv0.tv_nsec) < 0) {
tv.tv_nsec += 1000000000;
tv.tv_sec--;
}
arr[k] = tv.tv_sec + (double)tv.tv_nsec/1000000000;
}
qsort(arr, 500, sizeof(double), cmp);
for (int m = 100; m < LOOP_TIMES - 100; m++) {
times += arr[m];
}
printf("len: %ld time: %.9lf\n",j, times);
}
free(buf);
return 0;
}
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: Re: Re: [musl] memset_riscv64
2023-04-20 8:17 ` 张飞
@ 2023-04-21 13:30 ` Szabolcs Nagy
2023-04-21 14:50 ` Pedro Falcato
2023-04-26 7:25 ` 张飞
0 siblings, 2 replies; 10+ messages in thread
From: Szabolcs Nagy @ 2023-04-21 13:30 UTC (permalink / raw)
To: 张飞; +Cc: musl
* 张飞 <zhangfei@nj.iscas.ac.cn> [2023-04-20 16:17:10 +0800]:
> Hi!
> I listened to your suggestions and referred to string.c in Musl's test set(libc-bench),
> and then modified the test cases. Since BUFLEN is a fixed value in strlen.c, I modified
> it to a variable as a parameter in my own test case and passed it to the memset function.
> I adjusted the LOOP_TIMES has been counted up to 500 times and the running time has been
> sorted, only recording the running time of the middle 300 times.
>
> I took turns executing two programs on the SiFive chip three times each, and the results
> are shown below.
> First run result
> --------------------------------------------------------------------------------
> length(byte) C language implementation(s) Basic instruction implementation(s)
> --------------------------------------------------------------------------------
> 100 0.002208102 0.002304056
> 200 0.005053208 0.004629598
> 400 0.008666684 0.007739176
> 800 0.014065196 0.012372702
> 1600 0.023377685 0.020090966
> 3200 0.040221849 0.034059631
> 6400 0.072095377 0.060028906
> 12800 0.134040475 0.110039387
> 25600 0.257426806 0.210710952
> 51200 1.173755160 1.121833227
> 102400 3.693170402 3.637194098
> 204800 8.919975455 8.865504460
> 409600 19.410922418 19.360956493
> --------------------------------------------------------------------------------
>
> Second run result
> --------------------------------------------------------------------------------
> length(byte) C language implementation(s) Basic instruction implementation(s)
> --------------------------------------------------------------------------------
> 100 0.002208109 0.002293857
> 200 0.005057374 0.004640669
> 400 0.008674218 0.007760795
> 800 0.014068582 0.012417084
> 1600 0.023381095 0.020124496
> 3200 0.040225138 0.034093181
> 6400 0.072098744 0.060069574
> 12800 0.134043954 0.110088141
> 25600 0.256453187 0.208578633
> 51200 1.166602505 1.118972796
> 102400 3.684957231 3.635116808
> 204800 8.916302592 8.861590734
> 409600 19.411057216 19.358777670
> --------------------------------------------------------------------------------
>
> Third run result
> --------------------------------------------------------------------------------
> length(byte) C language implementation(s) Basic instruction implementation(s)
> --------------------------------------------------------------------------------
> 100 0.002208111 0.002293227
> 200 0.005056101 0.004628539
> 400 0.008677756 0.007748687
> 800 0.014085242 0.012404443
> 1600 0.023397782 0.020115710
> 3200 0.040242985 0.034084435
> 6400 0.072116665 0.060063767
> 12800 0.134060262 0.110082427
> 25600 0.257865186 0.209101754
> 51200 1.174257177 1.117753408
> 102400 3.696518162 3.635417503
> 204800 8.929357747 8.858765915
> 409600 19.426520562 19.356515671
> --------------------------------------------------------------------------------
>
> From the test results, it can be seen that the runtime of memset implemented using the basic
> instruction set assembly is basically shorter than that implemented using the C language.
> May I ask if the test results are convincing?
small sizes are much more common than large sizes, memsets can be
distributed such that sizes [0,100), [100,1000), [1000,inf) are
used for 1/3 of all memsets each (not the call count, but the
amount of bytes memset using such sizes), i.e. if you speed up
the size = [100,1000) and [1000,inf) cases by 10% but regress the
[0,100) case by 20% then the overall performance roughly stays
the same. (of course this is very workload dependent, but across
a system this is what i'd expect, probably even more skewed to
smaller sizes).
so we need to know what happens in the [0,100) range. what i see
is a ~4% regression there while there is a ~10% improvement in
the [100,1000) case and ~15% improvement in the [1000,inf) case
(it would be nice to know why the 25k case is so much faster and
why that speed up only applies to that size, we don't want to
optimize for some obscure cpu bug that will go away next year)
on practical workloads i would expect < 10% speedup overall from
the asm code (but we need more data in the [0,100) range to tell).
this may not be enough to justify the asm code.
rich already said he prefers a different style of implementation
(where the body of the function is in c but the inner loop is in
asm if that helps e.g. via simd).
here is an example of a benchmark that takes input distribution
into account from a workload:
https://github.com/ARM-software/optimized-routines/blob/master/string/bench/memset.c#L53
> #include <stdio.h>
> #include <stdlib.h>
> #include <string.h>
> #include <time.h>
>
> #define BUFLEN 500000
> #define LOOP_TIMES 500
>
> int cmp(const void *a, const void *b) {
> double x = *(double *)a;
> double y = *(double *)b;
> if (x < y) return -1;
> if (x > y) return 1;
> return 0;
> }
>
> int main(){
> char *buf = malloc(BUFLEN);
> double *arr = malloc(sizeof(double) * LOOP_TIMES);
> size_t i,j,k;
> struct timespec tv0,tv;
> double times;
>
> for(j=100; j<BUFLEN; j*=2){
> for(k=0; k<LOOP_TIMES; k++){
> for (i=0; i<100; i++)
> memset(buf+i, i, j-i);
> }
> }
>
> for(j=100; j<BUFLEN; j*=2){
> for(k=0; k<LOOP_TIMES; k++){
> clock_gettime(CLOCK_REALTIME, &tv0);
> for (i=0; i<100; i++)
> memset(buf+i, i, j-i);
alignment only matters up to 64 byte alignment and usually inputs
are at least 8byte aligned.
value is almost always 0. (we probably don't even need to test
non-0 case: a 0 check is correctly predicted in practice.)
i think length should have a small variation, just enough to add
penalty to small size checks where implementations may use many
branches.
so something like this may be better (madeup off,al numbers):
buf = malloc((1<<16)+32);
size_t sz[] = {16, 32, 48, 64, 96, 200, 300, 400, 600, 1<<10, 1<<11, 1<<12, 1<<13, 1<<14, 1<<15, 1<<16, 0};
size_t off[16] = {0, 0, 0, -8, 8, 16, 0, 0, -16, -12, 0, 4, -4, 0, 0, 12};
size_t al[16] = {0, 0, 8, 4, 8, 0, 8, 16, 8, 16, 4, 2, 1, 8, 16, 1};
for (j=0; sz[j]; j++)
for (k=0; k<20; k++) {
t0 = tic();
// large loop count is important for small sizes
for (i=0; i<256; i++)
memset(buf + al[i%16], 0, sz[j] + off[i%16]);
t1 = tic();
tmin = min(tmin,t1-t0);
}
large memset (>=1k) can be tested separately (no.need to add off,al
variaion then, less inner loop is enough, but it should not hurt to
include them here).
> clock_gettime(CLOCK_REALTIME, &tv);
> tv.tv_sec -= tv0.tv_sec;
> if ((tv.tv_nsec -= tv0.tv_nsec) < 0) {
> tv.tv_nsec += 1000000000;
> tv.tv_sec--;
> }
> arr[k] = tv.tv_sec + (double)tv.tv_nsec/1000000000;
> }
> qsort(arr, 500, sizeof(double), cmp);
just take the minimum. we want to know the fastest execution.
>
> for (int m = 100; m < LOOP_TIMES - 100; m++) {
> times += arr[m];
> }
> printf("len: %ld time: %.9lf\n",j, times);
you can also print GB/s which is 256*sz[j]/tmin in my example.
> }
> free(buf);
> return 0;
> }
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: Re: Re: [musl] memset_riscv64
2023-04-21 13:30 ` Szabolcs Nagy
@ 2023-04-21 14:50 ` Pedro Falcato
2023-04-21 16:54 ` Rich Felker
2023-04-26 7:25 ` 张飞
1 sibling, 1 reply; 10+ messages in thread
From: Pedro Falcato @ 2023-04-21 14:50 UTC (permalink / raw)
To: musl, 张飞; +Cc: nsz
On Fri, Apr 21, 2023 at 2:37 PM Szabolcs Nagy <nsz@port70.net> wrote:
>
> * 张飞 <zhangfei@nj.iscas.ac.cn> [2023-04-20 16:17:10 +0800]:
> > Hi!
> > I listened to your suggestions and referred to string.c in Musl's test set(libc-bench),
> > and then modified the test cases. Since BUFLEN is a fixed value in strlen.c, I modified
> > it to a variable as a parameter in my own test case and passed it to the memset function.
> > I adjusted the LOOP_TIMES has been counted up to 500 times and the running time has been
> > sorted, only recording the running time of the middle 300 times.
> >
> > I took turns executing two programs on the SiFive chip three times each, and the results
> > are shown below.
> > First run result
> > --------------------------------------------------------------------------------
> > length(byte) C language implementation(s) Basic instruction implementation(s)
> > --------------------------------------------------------------------------------
> > 100 0.002208102 0.002304056
> > 200 0.005053208 0.004629598
> > 400 0.008666684 0.007739176
> > 800 0.014065196 0.012372702
> > 1600 0.023377685 0.020090966
> > 3200 0.040221849 0.034059631
> > 6400 0.072095377 0.060028906
> > 12800 0.134040475 0.110039387
> > 25600 0.257426806 0.210710952
> > 51200 1.173755160 1.121833227
> > 102400 3.693170402 3.637194098
> > 204800 8.919975455 8.865504460
> > 409600 19.410922418 19.360956493
> > --------------------------------------------------------------------------------
> >
> > Second run result
> > --------------------------------------------------------------------------------
> > length(byte) C language implementation(s) Basic instruction implementation(s)
> > --------------------------------------------------------------------------------
> > 100 0.002208109 0.002293857
> > 200 0.005057374 0.004640669
> > 400 0.008674218 0.007760795
> > 800 0.014068582 0.012417084
> > 1600 0.023381095 0.020124496
> > 3200 0.040225138 0.034093181
> > 6400 0.072098744 0.060069574
> > 12800 0.134043954 0.110088141
> > 25600 0.256453187 0.208578633
> > 51200 1.166602505 1.118972796
> > 102400 3.684957231 3.635116808
> > 204800 8.916302592 8.861590734
> > 409600 19.411057216 19.358777670
> > --------------------------------------------------------------------------------
> >
> > Third run result
> > --------------------------------------------------------------------------------
> > length(byte) C language implementation(s) Basic instruction implementation(s)
> > --------------------------------------------------------------------------------
> > 100 0.002208111 0.002293227
> > 200 0.005056101 0.004628539
> > 400 0.008677756 0.007748687
> > 800 0.014085242 0.012404443
> > 1600 0.023397782 0.020115710
> > 3200 0.040242985 0.034084435
> > 6400 0.072116665 0.060063767
> > 12800 0.134060262 0.110082427
> > 25600 0.257865186 0.209101754
> > 51200 1.174257177 1.117753408
> > 102400 3.696518162 3.635417503
> > 204800 8.929357747 8.858765915
> > 409600 19.426520562 19.356515671
> > --------------------------------------------------------------------------------
> >
> > From the test results, it can be seen that the runtime of memset implemented using the basic
> > instruction set assembly is basically shorter than that implemented using the C language.
> > May I ask if the test results are convincing?
>
> small sizes are much more common than large sizes, memsets can be
> distributed such that sizes [0,100), [100,1000), [1000,inf) are
> used for 1/3 of all memsets each (not the call count, but the
> amount of bytes memset using such sizes), i.e. if you speed up
> the size = [100,1000) and [1000,inf) cases by 10% but regress the
> [0,100) case by 20% then the overall performance roughly stays
> the same. (of course this is very workload dependent, but across
> a system this is what i'd expect, probably even more skewed to
> smaller sizes).
>
> so we need to know what happens in the [0,100) range. what i see
> is a ~4% regression there while there is a ~10% improvement in
> the [100,1000) case and ~15% improvement in the [1000,inf) case
> (it would be nice to know why the 25k case is so much faster and
> why that speed up only applies to that size, we don't want to
> optimize for some obscure cpu bug that will go away next year)
>
> on practical workloads i would expect < 10% speedup overall from
> the asm code (but we need more data in the [0,100) range to tell).
> this may not be enough to justify the asm code.
>
> rich already said he prefers a different style of implementation
> (where the body of the function is in c but the inner loop is in
> asm if that helps e.g. via simd).
I don't think writing it all in C is viable, at least if you want to
squeeze every last bit of performance out of it (while avoiding
idiotic codegen that sometimes pops up).
Even with inline asm, I severely question its effectiveness. As I see
it, we have two major roadblocks for fast stringops support (and one
more for riscv):
1) Support GNU_IFUNC (as glibc, FreeBSD, etc do) to automatically
dispatch stringops functions to the best implementation according to
the CPU feature set. I have no good solution for static linking folks.
2) (Optional) Play around with C codegen that could add SIMD, inline
asm to try to make it fast-ish. LLVM folks have played around with
string ops written entirely in C++ through
__builtin_memcpy_inline (which does smart choices wrt overlapping
loads/stores, SIMD, etc depending on the size). Sadly,
__builtin_memcpy_inline is/was not available in GCC.
Testing the performance of C+inline asm vs pure asm would be interesting.
3) Write riscv stringops code in assembly once CPUs get more advanced
and we finally get a good idea on how the things perform. I still
think it's too new to optimize specifically for.
Extensions are popping up left and right, vector extensions aren't yet
properly supported in the kernel, and (most importantly) we don't have
a proper way to detect riscv features just yet.
For instance, doing unaligned accesses may either have little to no
performance penalty, they may have a big performance penalty (trapped
to M mode and emulated), or they may just not be supported at all.
AFAIK, atm Linux userspace has no way of finding this out (patchset
for this is still pending I think?), and things like the existence of
cheap unaligned accesses are a make-or-break for stringops as you get
to avoid *soooo* many branches.
In the RISCV case, you probably want to end up with at least 3 mem*
variants (no-unaligned, unaligned, vector).
Anyway, this was just a general brain-dump of my thoughts. The lack of
fast stringops is, AIUI, a problem in most architectures musl
supports.
> here is an example of a benchmark that takes input distribution
> into account from a workload:
> https://github.com/ARM-software/optimized-routines/blob/master/string/bench/memset.c#L53
For some more data, here's the distribution on a workload (kernel
compiling I think?) on a FreeBSD kernel:
https://people.freebsd.org/~mjg/bufsizes.txt. The sizes will ofc vary
between software, but this is just a cute datapoint on kernel stuff.
Userspace probably has lots of bigger copies/memsets.
>
> > #include <stdio.h>
> > #include <stdlib.h>
> > #include <string.h>
> > #include <time.h>
> >
> > #define BUFLEN 500000
> > #define LOOP_TIMES 500
> >
> > int cmp(const void *a, const void *b) {
> > double x = *(double *)a;
> > double y = *(double *)b;
> > if (x < y) return -1;
> > if (x > y) return 1;
> > return 0;
> > }
> >
> > int main(){
> > char *buf = malloc(BUFLEN);
> > double *arr = malloc(sizeof(double) * LOOP_TIMES);
> > size_t i,j,k;
> > struct timespec tv0,tv;
> > double times;
> >
> > for(j=100; j<BUFLEN; j*=2){
> > for(k=0; k<LOOP_TIMES; k++){
> > for (i=0; i<100; i++)
> > memset(buf+i, i, j-i);
> > }
> > }
> >
> > for(j=100; j<BUFLEN; j*=2){
> > for(k=0; k<LOOP_TIMES; k++){
> > clock_gettime(CLOCK_REALTIME, &tv0);
> > for (i=0; i<100; i++)
> > memset(buf+i, i, j-i);
>
> alignment only matters up to 64 byte alignment and usually inputs
> are at least 8byte aligned.
>
> value is almost always 0. (we probably don't even need to test
> non-0 case: a 0 check is correctly predicted in practice.)
>
> i think length should have a small variation, just enough to add
> penalty to small size checks where implementations may use many
> branches.
>
> so something like this may be better (madeup off,al numbers):
>
> buf = malloc((1<<16)+32);
> size_t sz[] = {16, 32, 48, 64, 96, 200, 300, 400, 600, 1<<10, 1<<11, 1<<12, 1<<13, 1<<14, 1<<15, 1<<16, 0};
> size_t off[16] = {0, 0, 0, -8, 8, 16, 0, 0, -16, -12, 0, 4, -4, 0, 0, 12};
> size_t al[16] = {0, 0, 8, 4, 8, 0, 8, 16, 8, 16, 4, 2, 1, 8, 16, 1};
> for (j=0; sz[j]; j++)
> for (k=0; k<20; k++) {
> t0 = tic();
> // large loop count is important for small sizes
> for (i=0; i<256; i++)
> memset(buf + al[i%16], 0, sz[j] + off[i%16]);
> t1 = tic();
> tmin = min(tmin,t1-t0);
> }
>
> large memset (>=1k) can be tested separately (no.need to add off,al
> variaion then, less inner loop is enough, but it should not hurt to
> include them here).
>
> > clock_gettime(CLOCK_REALTIME, &tv);
> > tv.tv_sec -= tv0.tv_sec;
> > if ((tv.tv_nsec -= tv0.tv_nsec) < 0) {
> > tv.tv_nsec += 1000000000;
> > tv.tv_sec--;
> > }
> > arr[k] = tv.tv_sec + (double)tv.tv_nsec/1000000000;
> > }
> > qsort(arr, 500, sizeof(double), cmp);
>
> just take the minimum. we want to know the fastest execution.
>
> >
> > for (int m = 100; m < LOOP_TIMES - 100; m++) {
> > times += arr[m];
> > }
> > printf("len: %ld time: %.9lf\n",j, times);
>
> you can also print GB/s which is 256*sz[j]/tmin in my example.
>
> > }
> > free(buf);
> > return 0;
> > }
>
I know folks are somewhat allergic to C++ here, but I wholeheartedly
recommend Google Benchmark for microbenchmarking needs.
See https://gist.github.com/heatd/165b70a4e0b75e815b82d723c01637dc for
something I used to benchmark my memcpy (partially taken from
AOSP/bionic).
--
Pedro
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: Re: Re: [musl] memset_riscv64
2023-04-21 14:50 ` Pedro Falcato
@ 2023-04-21 16:54 ` Rich Felker
2023-04-21 17:01 ` enh
0 siblings, 1 reply; 10+ messages in thread
From: Rich Felker @ 2023-04-21 16:54 UTC (permalink / raw)
To: Pedro Falcato; +Cc: musl, 张飞, nsz
On Fri, Apr 21, 2023 at 03:50:45PM +0100, Pedro Falcato wrote:
> On Fri, Apr 21, 2023 at 2:37 PM Szabolcs Nagy <nsz@port70.net> wrote:
> >
> > * 张飞 <zhangfei@nj.iscas.ac.cn> [2023-04-20 16:17:10 +0800]:
> > > Hi!
> > > I listened to your suggestions and referred to string.c in Musl's test set(libc-bench),
> > > and then modified the test cases. Since BUFLEN is a fixed value in strlen.c, I modified
> > > it to a variable as a parameter in my own test case and passed it to the memset function.
> > > I adjusted the LOOP_TIMES has been counted up to 500 times and the running time has been
> > > sorted, only recording the running time of the middle 300 times.
> > >
> > > I took turns executing two programs on the SiFive chip three times each, and the results
> > > are shown below.
> > > First run result
> > > --------------------------------------------------------------------------------
> > > length(byte) C language implementation(s) Basic instruction implementation(s)
> > > --------------------------------------------------------------------------------
> > > 100 0.002208102 0.002304056
> > > 200 0.005053208 0.004629598
> > > 400 0.008666684 0.007739176
> > > 800 0.014065196 0.012372702
> > > 1600 0.023377685 0.020090966
> > > 3200 0.040221849 0.034059631
> > > 6400 0.072095377 0.060028906
> > > 12800 0.134040475 0.110039387
> > > 25600 0.257426806 0.210710952
> > > 51200 1.173755160 1.121833227
> > > 102400 3.693170402 3.637194098
> > > 204800 8.919975455 8.865504460
> > > 409600 19.410922418 19.360956493
> > > --------------------------------------------------------------------------------
> > >
> > > Second run result
> > > --------------------------------------------------------------------------------
> > > length(byte) C language implementation(s) Basic instruction implementation(s)
> > > --------------------------------------------------------------------------------
> > > 100 0.002208109 0.002293857
> > > 200 0.005057374 0.004640669
> > > 400 0.008674218 0.007760795
> > > 800 0.014068582 0.012417084
> > > 1600 0.023381095 0.020124496
> > > 3200 0.040225138 0.034093181
> > > 6400 0.072098744 0.060069574
> > > 12800 0.134043954 0.110088141
> > > 25600 0.256453187 0.208578633
> > > 51200 1.166602505 1.118972796
> > > 102400 3.684957231 3.635116808
> > > 204800 8.916302592 8.861590734
> > > 409600 19.411057216 19.358777670
> > > --------------------------------------------------------------------------------
> > >
> > > Third run result
> > > --------------------------------------------------------------------------------
> > > length(byte) C language implementation(s) Basic instruction implementation(s)
> > > --------------------------------------------------------------------------------
> > > 100 0.002208111 0.002293227
> > > 200 0.005056101 0.004628539
> > > 400 0.008677756 0.007748687
> > > 800 0.014085242 0.012404443
> > > 1600 0.023397782 0.020115710
> > > 3200 0.040242985 0.034084435
> > > 6400 0.072116665 0.060063767
> > > 12800 0.134060262 0.110082427
> > > 25600 0.257865186 0.209101754
> > > 51200 1.174257177 1.117753408
> > > 102400 3.696518162 3.635417503
> > > 204800 8.929357747 8.858765915
> > > 409600 19.426520562 19.356515671
> > > --------------------------------------------------------------------------------
> > >
> > > From the test results, it can be seen that the runtime of memset implemented using the basic
> > > instruction set assembly is basically shorter than that implemented using the C language.
> > > May I ask if the test results are convincing?
> >
> > small sizes are much more common than large sizes, memsets can be
> > distributed such that sizes [0,100), [100,1000), [1000,inf) are
> > used for 1/3 of all memsets each (not the call count, but the
> > amount of bytes memset using such sizes), i.e. if you speed up
> > the size = [100,1000) and [1000,inf) cases by 10% but regress the
> > [0,100) case by 20% then the overall performance roughly stays
> > the same. (of course this is very workload dependent, but across
> > a system this is what i'd expect, probably even more skewed to
> > smaller sizes).
> >
> > so we need to know what happens in the [0,100) range. what i see
> > is a ~4% regression there while there is a ~10% improvement in
> > the [100,1000) case and ~15% improvement in the [1000,inf) case
> > (it would be nice to know why the 25k case is so much faster and
> > why that speed up only applies to that size, we don't want to
> > optimize for some obscure cpu bug that will go away next year)
> >
> > on practical workloads i would expect < 10% speedup overall from
> > the asm code (but we need more data in the [0,100) range to tell).
> > this may not be enough to justify the asm code.
> >
> > rich already said he prefers a different style of implementation
> > (where the body of the function is in c but the inner loop is in
> > asm if that helps e.g. via simd).
>
> I don't think writing it all in C is viable, at least if you want to
> squeeze every last bit of performance out of it (while avoiding
> idiotic codegen that sometimes pops up).
> Even with inline asm, I severely question its effectiveness. As I see
I don't see any good reason for this doubt. If you claim it's not
viable, you should show cases where you really can't get the compiler
to do something reasonable with this type of code.
If the loop body were tiny and the loop control were a significant
portion of the loop execution overhead, then I could see this
potentially being a problem. But the main/only interesting case for
asm is where you're operating on largeish blocks.
> it, we have two major roadblocks for fast stringops support (and one
> more for riscv):
>
> 1) Support GNU_IFUNC (as glibc, FreeBSD, etc do) to automatically
> dispatch stringops functions to the best implementation according to
> the CPU feature set. I have no good solution for static linking folks.
Of course this is not an option, but it's also not needed. There is
only relevant dispatch cost when size is small, but you don't want or
need to dispatch to asm variants when size is small, so the dispatch
goes in the branch for large sizes, and the cost is effectively zero.
> 2) (Optional) Play around with C codegen that could add SIMD, inline
> asm to try to make it fast-ish. LLVM folks have played around with
> string ops written entirely in C++ through
> __builtin_memcpy_inline (which does smart choices wrt overlapping
> loads/stores, SIMD, etc depending on the size). Sadly,
> __builtin_memcpy_inline is/was not available in GCC.
The basic strategy here is to do head/tail of the operation with plain
portable C, in a minimal-length, minimal-branch fast path. Then, if
any middle that wasn't covered by the head/tail remains, either use an
arch-provided block operation primitive that's (for example; subject
to tuning) allowed to assume alignment of size and either src or dest,
or dispatch to a hwcap-specific bulk operation in asm that can make
similar assumptions.
> Testing the performance of C+inline asm vs pure asm would be interesting.
Yes but I don't think we'll find anything unexpected. In theory you
can probaby shave a couple cycles writing the asm by hand, but that
has a lot of costs that aren't sustainable, and pessimizes things like
LTO (for example, in LTO, the short-size fast paths may be able to be
inlined when the exact size isn't known but value range analysis
determines it's always in the small range).
> 3) Write riscv stringops code in assembly once CPUs get more advanced
> and we finally get a good idea on how the things perform. I still
> think it's too new to optimize specifically for.
> Extensions are popping up left and right, vector extensions aren't yet
> properly supported in the kernel, and (most importantly) we don't have
> a proper way to detect riscv features just yet.
> For instance, doing unaligned accesses may either have little to no
> performance penalty, they may have a big performance penalty (trapped
> to M mode and emulated), or they may just not be supported at all.
> AFAIK, atm Linux userspace has no way of finding this out (patchset
> for this is still pending I think?), and things like the existence of
> cheap unaligned accesses are a make-or-break for stringops as you get
> to avoid *soooo* many branches.
Yes, for RISC-V there is no way forward on vector or other ISA
extensions until the specs are firmed up and the framework for
detecting their presence is in place.
> In the RISCV case, you probably want to end up with at least 3 mem*
> variants (no-unaligned, unaligned, vector).
For memset, there's hardly a reason to waste effort on unaligned
versions. The middle is always aligned. For memcpy/memmove, where you
have src and dest misaligned modulo each other, the ability to do
unaligned loads or stores is valuable, and something the general
framework (in C) should allow us to take advantage of. I hadn't really
considered the possibility that we might want to support
unaligned-access support that's only known at runtime, rather than
part of the ISA level you're building for, so perhaps this is
something we should consider.
Rich
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: Re: Re: [musl] memset_riscv64
2023-04-21 16:54 ` Rich Felker
@ 2023-04-21 17:01 ` enh
0 siblings, 0 replies; 10+ messages in thread
From: enh @ 2023-04-21 17:01 UTC (permalink / raw)
To: musl; +Cc: Pedro Falcato, 张飞, nsz
[-- Attachment #1: Type: text/plain, Size: 11477 bytes --]
On Fri, Apr 21, 2023 at 9:54 AM Rich Felker <dalias@libc.org> wrote:
> On Fri, Apr 21, 2023 at 03:50:45PM +0100, Pedro Falcato wrote:
> > On Fri, Apr 21, 2023 at 2:37 PM Szabolcs Nagy <nsz@port70.net> wrote:
> > >
> > > * 张飞 <zhangfei@nj.iscas.ac.cn> [2023-04-20 16:17:10 +0800]:
> > > > Hi!
> > > > I listened to your suggestions and referred to string.c in Musl's
> test set(libc-bench),
> > > > and then modified the test cases. Since BUFLEN is a fixed value in
> strlen.c, I modified
> > > > it to a variable as a parameter in my own test case and passed it to
> the memset function.
> > > > I adjusted the LOOP_TIMES has been counted up to 500 times and the
> running time has been
> > > > sorted, only recording the running time of the middle 300 times.
> > > >
> > > > I took turns executing two programs on the SiFive chip three times
> each, and the results
> > > > are shown below.
> > > > First run result
> > > >
> --------------------------------------------------------------------------------
> > > > length(byte) C language implementation(s) Basic instruction
> implementation(s)
> > > >
> --------------------------------------------------------------------------------
> > > > 100 0.002208102 0.002304056
> > > > 200 0.005053208 0.004629598
> > > > 400 0.008666684 0.007739176
> > > > 800 0.014065196 0.012372702
> > > > 1600 0.023377685 0.020090966
> > > > 3200 0.040221849 0.034059631
> > > > 6400 0.072095377 0.060028906
> > > > 12800 0.134040475 0.110039387
> > > > 25600 0.257426806 0.210710952
> > > > 51200 1.173755160 1.121833227
> > > > 102400 3.693170402 3.637194098
> > > > 204800 8.919975455 8.865504460
> > > > 409600 19.410922418 19.360956493
> > > >
> --------------------------------------------------------------------------------
> > > >
> > > > Second run result
> > > >
> --------------------------------------------------------------------------------
> > > > length(byte) C language implementation(s) Basic instruction
> implementation(s)
> > > >
> --------------------------------------------------------------------------------
> > > > 100 0.002208109 0.002293857
> > > > 200 0.005057374 0.004640669
> > > > 400 0.008674218 0.007760795
> > > > 800 0.014068582 0.012417084
> > > > 1600 0.023381095 0.020124496
> > > > 3200 0.040225138 0.034093181
> > > > 6400 0.072098744 0.060069574
> > > > 12800 0.134043954 0.110088141
> > > > 25600 0.256453187 0.208578633
> > > > 51200 1.166602505 1.118972796
> > > > 102400 3.684957231 3.635116808
> > > > 204800 8.916302592 8.861590734
> > > > 409600 19.411057216 19.358777670
> > > >
> --------------------------------------------------------------------------------
> > > >
> > > > Third run result
> > > >
> --------------------------------------------------------------------------------
> > > > length(byte) C language implementation(s) Basic instruction
> implementation(s)
> > > >
> --------------------------------------------------------------------------------
> > > > 100 0.002208111 0.002293227
> > > > 200 0.005056101 0.004628539
> > > > 400 0.008677756 0.007748687
> > > > 800 0.014085242 0.012404443
> > > > 1600 0.023397782 0.020115710
> > > > 3200 0.040242985 0.034084435
> > > > 6400 0.072116665 0.060063767
> > > > 12800 0.134060262 0.110082427
> > > > 25600 0.257865186 0.209101754
> > > > 51200 1.174257177 1.117753408
> > > > 102400 3.696518162 3.635417503
> > > > 204800 8.929357747 8.858765915
> > > > 409600 19.426520562 19.356515671
> > > >
> --------------------------------------------------------------------------------
> > > >
> > > > From the test results, it can be seen that the runtime of memset
> implemented using the basic
> > > > instruction set assembly is basically shorter than that implemented
> using the C language.
> > > > May I ask if the test results are convincing?
> > >
> > > small sizes are much more common than large sizes, memsets can be
> > > distributed such that sizes [0,100), [100,1000), [1000,inf) are
> > > used for 1/3 of all memsets each (not the call count, but the
> > > amount of bytes memset using such sizes), i.e. if you speed up
> > > the size = [100,1000) and [1000,inf) cases by 10% but regress the
> > > [0,100) case by 20% then the overall performance roughly stays
> > > the same. (of course this is very workload dependent, but across
> > > a system this is what i'd expect, probably even more skewed to
> > > smaller sizes).
> > >
> > > so we need to know what happens in the [0,100) range. what i see
> > > is a ~4% regression there while there is a ~10% improvement in
> > > the [100,1000) case and ~15% improvement in the [1000,inf) case
> > > (it would be nice to know why the 25k case is so much faster and
> > > why that speed up only applies to that size, we don't want to
> > > optimize for some obscure cpu bug that will go away next year)
> > >
> > > on practical workloads i would expect < 10% speedup overall from
> > > the asm code (but we need more data in the [0,100) range to tell).
> > > this may not be enough to justify the asm code.
> > >
> > > rich already said he prefers a different style of implementation
> > > (where the body of the function is in c but the inner loop is in
> > > asm if that helps e.g. via simd).
> >
> > I don't think writing it all in C is viable, at least if you want to
> > squeeze every last bit of performance out of it (while avoiding
> > idiotic codegen that sometimes pops up).
> > Even with inline asm, I severely question its effectiveness. As I see
>
> I don't see any good reason for this doubt. If you claim it's not
> viable, you should show cases where you really can't get the compiler
> to do something reasonable with this type of code.
>
> If the loop body were tiny and the loop control were a significant
> portion of the loop execution overhead, then I could see this
> potentially being a problem. But the main/only interesting case for
> asm is where you're operating on largeish blocks.
>
> > it, we have two major roadblocks for fast stringops support (and one
> > more for riscv):
> >
> > 1) Support GNU_IFUNC (as glibc, FreeBSD, etc do) to automatically
> > dispatch stringops functions to the best implementation according to
> > the CPU feature set. I have no good solution for static linking folks.
>
> Of course this is not an option, but it's also not needed. There is
> only relevant dispatch cost when size is small, but you don't want or
> need to dispatch to asm variants when size is small, so the dispatch
> goes in the branch for large sizes, and the cost is effectively zero.
>
> > 2) (Optional) Play around with C codegen that could add SIMD, inline
> > asm to try to make it fast-ish. LLVM folks have played around with
> > string ops written entirely in C++ through
> > __builtin_memcpy_inline (which does smart choices wrt overlapping
> > loads/stores, SIMD, etc depending on the size). Sadly,
> > __builtin_memcpy_inline is/was not available in GCC.
>
> The basic strategy here is to do head/tail of the operation with plain
> portable C, in a minimal-length, minimal-branch fast path. Then, if
> any middle that wasn't covered by the head/tail remains, either use an
> arch-provided block operation primitive that's (for example; subject
> to tuning) allowed to assume alignment of size and either src or dest,
> or dispatch to a hwcap-specific bulk operation in asm that can make
> similar assumptions.
>
> > Testing the performance of C+inline asm vs pure asm would be interesting.
>
> Yes but I don't think we'll find anything unexpected. In theory you
> can probaby shave a couple cycles writing the asm by hand, but that
> has a lot of costs that aren't sustainable, and pessimizes things like
> LTO (for example, in LTO, the short-size fast paths may be able to be
> inlined when the exact size isn't known but value range analysis
> determines it's always in the small range).
>
> > 3) Write riscv stringops code in assembly once CPUs get more advanced
> > and we finally get a good idea on how the things perform. I still
> > think it's too new to optimize specifically for.
> > Extensions are popping up left and right, vector extensions aren't yet
> > properly supported in the kernel, and (most importantly) we don't have
> > a proper way to detect riscv features just yet.
> > For instance, doing unaligned accesses may either have little to no
> > performance penalty, they may have a big performance penalty (trapped
> > to M mode and emulated), or they may just not be supported at all.
> > AFAIK, atm Linux userspace has no way of finding this out (patchset
> > for this is still pending I think?), and things like the existence of
> > cheap unaligned accesses are a make-or-break for stringops as you get
> > to avoid *soooo* many branches.
>
> Yes, for RISC-V there is no way forward on vector or other ISA
> extensions until the specs are firmed up and the framework for
> detecting their presence is in place.
>
(the vector state save/restore stuff still isn't in yet, which is making me
worry it won't make linux 6.4, but fwiw the risc-v hwprobe patches went
into linux-next earlier this week, so there's some progress there at
least...)
> > In the RISCV case, you probably want to end up with at least 3 mem*
> > variants (no-unaligned, unaligned, vector).
>
> For memset, there's hardly a reason to waste effort on unaligned
> versions. The middle is always aligned. For memcpy/memmove, where you
> have src and dest misaligned modulo each other, the ability to do
> unaligned loads or stores is valuable, and something the general
> framework (in C) should allow us to take advantage of. I hadn't really
> considered the possibility that we might want to support
> unaligned-access support that's only known at runtime, rather than
> part of the ISA level you're building for, so perhaps this is
> something we should consider.
>
> Rich
>
[-- Attachment #2: Type: text/html, Size: 14167 bytes --]
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: Re: Re: Re: [musl] memset_riscv64
2023-04-21 13:30 ` Szabolcs Nagy
2023-04-21 14:50 ` Pedro Falcato
@ 2023-04-26 7:25 ` 张飞
1 sibling, 0 replies; 10+ messages in thread
From: 张飞 @ 2023-04-26 7:25 UTC (permalink / raw)
To: musl
[-- Attachment #1: Type: text/plain, Size: 17550 bytes --]
Hi！
I used your test example and modified the code for the link you provided to enable it to
run on the riscv platform, just like test_memset1.c and test_memset2.c.
Here are the test results for test_memset1.c：
First run result
------------------------------------------------------------------------------------
| C language implementation | Basic instruction implementation
------------------------------------------------------------------------------------
size(bytes) | min_time(s) speed(GB/s) | min_time(s) speed(GB/s)
------------------------------------------------------------------------------------
16 | 0.000022152 0.18 | 0.000020818 0.20
32 | 0.000026968 0.30 | 0.000023380 0.35
48 | 0.000027450 0.45 | 0.000023860 0.52
64 | 0.000029215 0.56 | 0.000024341 0.67
96 | 0.000030178 0.81 | 0.000025302 0.97
200 | 0.000033228 1.54 | 0.000027864 1.84
300 | 0.000036279 2.12 | 0.000031227 2.46
400 | 0.000039810 2.57 | 0.000033949 3.02
600 | 0.000047836 3.21 | 0.000040515 3.79
1024 | 0.000064531 4.06 | 0.000054127 4.84
2048 | 0.000106910 4.90 | 0.000089998 5.83
4096 | 0.000191828 5.47 | 0.000155656 6.74
8192 | 0.000356046 5.89 | 0.000286811 7.31
16384 | 0.000685124 6.12 | 0.000549441 7.63
32768 | 0.001460304 5.74 | 0.001222189 6.86
65536 | 0.012082280 1.39 | 0.012054872 1.39
------------------------------------------------------------------------------------
Second run result
------------------------------------------------------------------------------------
| C language implementation | Basic instruction implementation
------------------------------------------------------------------------------------
size(bytes) | min_time(s) speed(GB/s) | min_time(s) speed(GB/s)
------------------------------------------------------------------------------------
16 | 0.000021755 0.19 | 0.000020750 0.20
32 | 0.000026484 0.31 | 0.000022810 0.36
48 | 0.000026957 0.46 | 0.000023601 0.52
64 | 0.000028692 0.57 | 0.000023918 0.69
96 | 0.000029638 0.83 | 0.000024868 0.99
200 | 0.000032633 1.57 | 0.000027403 1.87
300 | 0.000035628 2.16 | 0.000030887 2.49
400 | 0.000038781 2.64 | 0.000033580 3.05
600 | 0.000046979 3.27 | 0.000040233 3.82
1024 | 0.000063532 4.13 | 0.000053538 4.90
2048 | 0.000104993 4.99 | 0.000088861 5.90
4096 | 0.000188389 5.57 | 0.000153804 6.82
8192 | 0.000349664 6.00 | 0.000283691 7.39
16384 | 0.000673000 6.23 | 0.000543464 7.72
32768 | 0.001433181 5.85 | 0.001217448 6.89
65536 | 0.011850111 1.42 | 0.011945281 1.40
------------------------------------------------------------------------------------
Third run result
------------------------------------------------------------------------------------
| C language implementation | Basic instruction implementation
------------------------------------------------------------------------------------
size(bytes) | min_time(s) speed(GB/s) | min_time(s) speed(GB/s)
------------------------------------------------------------------------------------
16 | 0.000021885 0.19 | 0.000020816 0.20
32 | 0.000026642 0.31 | 0.000023040 0.36
48 | 0.000027118 0.45 | 0.000023676 0.52
64 | 0.000028863 0.57 | 0.000024311 0.67
96 | 0.000029814 0.82 | 0.000024947 0.99
200 | 0.000034413 1.49 | 0.000027648 1.85
300 | 0.000035841 2.14 | 0.000031144 2.47
400 | 0.000039329 2.60 | 0.000034005 3.01
600 | 0.000047259 3.25 | 0.000040360 3.81
1024 | 0.000063752 4.11 | 0.000053867 4.87
2048 | 0.000105620 4.96 | 0.000089302 5.87
4096 | 0.000189513 5.53 | 0.000154610 6.78
8192 | 0.000351749 5.96 | 0.000284591 7.37
16384 | 0.000676855 6.20 | 0.000545187 7.69
32768 | 0.001440141 5.82 | 0.001208756 6.94
65536 | 0.011974218 1.40 | 0.011976172 1.40
------------------------------------------------------------------------------------
Here are the test results for test_memset2.c：
C language implementation
Random memset (bytes/ns):
memset_call 32K: 0.36 64K: 0.29 128K: 0.25 256K: 0.23 512K: 0.22 1024K: 0.21 avg 0.25
Medium memset (bytes/ns):
memset_call 8B: 0.28 16B: 0.30 32B: 0.48 64B: 0.86 128B: 1.55 256B: 2.60 512B: 3.86
Large memset (bytes/ns):
memset_call 1K: 4.82 2K: 5.40 4K: 5.83 8K: 6.09 16K: 6.22 32K: 6.14 64K: 1.39
Basic instruction implementation
Random memset (bytes/ns):
memset_call 32K: 0.45 64K: 0.35 128K: 0.30 256K: 0.28 512K: 0.27 1024K: 0.25 avg 0.30
Medium memset (bytes/ns):
memset_call 8B: 0.18 16B: 0.48 32B: 0.91 64B: 1.63 128B: 2.71 256B: 4.40 512B: 5.67
Large memset (bytes/ns):
memset_call 1K: 6.62 2K: 7.03 4K: 7.47 8K: 7.71 16K: 7.83 32K: 7.64 64K: 1.40
From the test results, it can be seen that the memset implemented in C language performs better
at around 8 bytes, while in other cases, the assembly implementation will perform better.
Fei Zhang
> -----原始邮件-----
> 发件人: "Szabolcs Nagy" <nsz@port70.net>
> 发送时间: 2023-04-21 21:30:34 (星期五)
> 收件人: "张飞" <zhangfei@nj.iscas.ac.cn>
> 抄送: musl@lists.openwall.com
> 主题: Re: Re: Re: [musl] memset_riscv64
>
> * 张飞 <zhangfei@nj.iscas.ac.cn> [2023-04-20 16:17:10 +0800]:
> > Hi!
> > I listened to your suggestions and referred to string.c in Musl's test set(libc-bench),
> > and then modified the test cases. Since BUFLEN is a fixed value in strlen.c, I modified
> > it to a variable as a parameter in my own test case and passed it to the memset function.
> > I adjusted the LOOP_TIMES has been counted up to 500 times and the running time has been
> > sorted, only recording the running time of the middle 300 times.
> >
> > I took turns executing two programs on the SiFive chip three times each, and the results
> > are shown below.
> > First run result
> > --------------------------------------------------------------------------------
> > length(byte) C language implementation(s) Basic instruction implementation(s)
> > --------------------------------------------------------------------------------
> > 100 0.002208102 0.002304056
> > 200 0.005053208 0.004629598
> > 400 0.008666684 0.007739176
> > 800 0.014065196 0.012372702
> > 1600 0.023377685 0.020090966
> > 3200 0.040221849 0.034059631
> > 6400 0.072095377 0.060028906
> > 12800 0.134040475 0.110039387
> > 25600 0.257426806 0.210710952
> > 51200 1.173755160 1.121833227
> > 102400 3.693170402 3.637194098
> > 204800 8.919975455 8.865504460
> > 409600 19.410922418 19.360956493
> > --------------------------------------------------------------------------------
> >
> > Second run result
> > --------------------------------------------------------------------------------
> > length(byte) C language implementation(s) Basic instruction implementation(s)
> > --------------------------------------------------------------------------------
> > 100 0.002208109 0.002293857
> > 200 0.005057374 0.004640669
> > 400 0.008674218 0.007760795
> > 800 0.014068582 0.012417084
> > 1600 0.023381095 0.020124496
> > 3200 0.040225138 0.034093181
> > 6400 0.072098744 0.060069574
> > 12800 0.134043954 0.110088141
> > 25600 0.256453187 0.208578633
> > 51200 1.166602505 1.118972796
> > 102400 3.684957231 3.635116808
> > 204800 8.916302592 8.861590734
> > 409600 19.411057216 19.358777670
> > --------------------------------------------------------------------------------
> >
> > Third run result
> > --------------------------------------------------------------------------------
> > length(byte) C language implementation(s) Basic instruction implementation(s)
> > --------------------------------------------------------------------------------
> > 100 0.002208111 0.002293227
> > 200 0.005056101 0.004628539
> > 400 0.008677756 0.007748687
> > 800 0.014085242 0.012404443
> > 1600 0.023397782 0.020115710
> > 3200 0.040242985 0.034084435
> > 6400 0.072116665 0.060063767
> > 12800 0.134060262 0.110082427
> > 25600 0.257865186 0.209101754
> > 51200 1.174257177 1.117753408
> > 102400 3.696518162 3.635417503
> > 204800 8.929357747 8.858765915
> > 409600 19.426520562 19.356515671
> > --------------------------------------------------------------------------------
> >
> > From the test results, it can be seen that the runtime of memset implemented using the basic
> > instruction set assembly is basically shorter than that implemented using the C language.
> > May I ask if the test results are convincing?
>
> small sizes are much more common than large sizes, memsets can be
> distributed such that sizes [0,100), [100,1000), [1000,inf) are
> used for 1/3 of all memsets each (not the call count, but the
> amount of bytes memset using such sizes), i.e. if you speed up
> the size = [100,1000) and [1000,inf) cases by 10% but regress the
> [0,100) case by 20% then the overall performance roughly stays
> the same. (of course this is very workload dependent, but across
> a system this is what i'd expect, probably even more skewed to
> smaller sizes).
>
> so we need to know what happens in the [0,100) range. what i see
> is a ~4% regression there while there is a ~10% improvement in
> the [100,1000) case and ~15% improvement in the [1000,inf) case
> (it would be nice to know why the 25k case is so much faster and
> why that speed up only applies to that size, we don't want to
> optimize for some obscure cpu bug that will go away next year)
>
> on practical workloads i would expect < 10% speedup overall from
> the asm code (but we need more data in the [0,100) range to tell).
> this may not be enough to justify the asm code.
>
> rich already said he prefers a different style of implementation
> (where the body of the function is in c but the inner loop is in
> asm if that helps e.g. via simd).
>
> here is an example of a benchmark that takes input distribution
> into account from a workload:
> https://github.com/ARM-software/optimized-routines/blob/master/string/bench/memset.c#L53
>
> > #include <stdio.h>
> > #include <stdlib.h>
> > #include <string.h>
> > #include <time.h>
> >
> > #define BUFLEN 500000
> > #define LOOP_TIMES 500
> >
> > int cmp(const void *a, const void *b) {
> > double x = *(double *)a;
> > double y = *(double *)b;
> > if (x < y) return -1;
> > if (x > y) return 1;
> > return 0;
> > }
> >
> > int main(){
> > char *buf = malloc(BUFLEN);
> > double *arr = malloc(sizeof(double) * LOOP_TIMES);
> > size_t i,j,k;
> > struct timespec tv0,tv;
> > double times;
> >
> > for(j=100; j<buflen; j*="2){"> > for(k=0; k<loop_times; k++){=""> > for (i=0; i<100; i++)
> > memset(buf+i, i, j-i);
> > }
> > }
> >
> > for(j=100; j<buflen; j*="2){"> > for(k=0; k<loop_times; k++){=""> > clock_gettime(CLOCK_REALTIME, &tv0);
> > for (i=0; i<100; i++)
> > memset(buf+i, i, j-i);
>
> alignment only matters up to 64 byte alignment and usually inputs
> are at least 8byte aligned.
>
> value is almost always 0. (we probably don't even need to test
> non-0 case: a 0 check is correctly predicted in practice.)
>
> i think length should have a small variation, just enough to add
> penalty to small size checks where implementations may use many
> branches.
>
> so something like this may be better (madeup off,al numbers):
>
> buf = malloc((1<<16)+32);
> size_t sz[] = {16, 32, 48, 64, 96, 200, 300, 400, 600, 1<<10, 1<<11, 1<<12, 1<<13, 1<<14, 1<<15, 1<<16, 0};
> size_t off[16] = {0, 0, 0, -8, 8, 16, 0, 0, -16, -12, 0, 4, -4, 0, 0, 12};
> size_t al[16] = {0, 0, 8, 4, 8, 0, 8, 16, 8, 16, 4, 2, 1, 8, 16, 1};
> for (j=0; sz[j]; j++)
> for (k=0; k<20; k++) {
> t0 = tic();
> // large loop count is important for small sizes
> for (i=0; i<256; i++)
> memset(buf + al[i%16], 0, sz[j] + off[i%16]);
> t1 = tic();
> tmin = min(tmin,t1-t0);
> }
>
> large memset (>=1k) can be tested separately (no.need to add off,al
> variaion then, less inner loop is enough, but it should not hurt to
> include them here).
>
> > clock_gettime(CLOCK_REALTIME, &tv);
> > tv.tv_sec -= tv0.tv_sec;
> > if ((tv.tv_nsec -= tv0.tv_nsec) < 0) {
> > tv.tv_nsec += 1000000000;
> > tv.tv_sec--;
> > }
> > arr[k] = tv.tv_sec + (double)tv.tv_nsec/1000000000;
> > }
> > qsort(arr, 500, sizeof(double), cmp);
>
> just take the minimum. we want to know the fastest execution.
>
> >
> > for (int m = 100; m < LOOP_TIMES - 100; m++) {
> > times += arr[m];
> > }
> > printf("len: %ld time: %.9lf\n",j, times);
>
> you can also print GB/s which is 256*sz[j]/tmin in my example.
>
> > }
> > free(buf);
> > return 0;
> > }
</loop_times;></buflen;></loop_times;></buflen;></time.h></string.h></stdlib.h></stdio.h></zhangfei@nj.iscas.ac.cn></zhangfei@nj.iscas.ac.cn></nsz@port70.net>
[-- Attachment #2: test_memset1.c --]
[-- Type: text/plain, Size: 1395 bytes --]
#include <float.h>
#include <stdio.h>
#include <string.h>
#include <time.h>
#include <stdlib.h>
int main(){
int j,k,i;
double times;
struct timespec tv0,tv;
int sz[] = {16, 32, 48, 64, 96, 200, 300, 400, 600, 1<<10, 1<<11, 1<<12, 1<<13, 1<<14, 1<<15, 1<<16, 0};
int off[16] = {0, 0, 0, -8, 8, 16, 0, 0, -16, -12, 0, 4, -4, 0, 0, 12};
int al[16] = {0, 0, 8, 4, 8, 0, 8, 16, 8, 16, 4, 2, 1, 8, 16, 1};
char *buf = malloc((1<<16)+32);
if (buf == NULL) {
printf("malloc failed\n");
exit(1);
}
// warm up
for (j=0; sz[j]; j++)
for (k=0; k<20; k++)
for (i=0; i<256; i++)
memset(buf + al[i%16], 0, sz[j] + off[i%16]);
printf("%-15s %-20s %-20s\n", "size(bytes)", "min_time(s)", "speed(GB/s)");
for (j=0; sz[j]; j++) {
double min_time = DBL_MAX;
for (k=0; k<20; k++) {
clock_gettime(CLOCK_REALTIME, &tv0);
// large loop count is important for small sizes
for (i=0; i<256; i++)
memset(buf + al[i%16], 0, sz[j] + off[i%16]);
clock_gettime(CLOCK_REALTIME, &tv);
tv.tv_sec -= tv0.tv_sec;
if ((tv.tv_nsec -= tv0.tv_nsec) < 0) {
tv.tv_nsec += 1000000000;
tv.tv_sec--;
}
times = tv.tv_sec + (double)tv.tv_nsec/1e9;
min_time = min_time < times ? min_time : times;
}
printf("%-15d %-20.9lf %-20.2lf\n",sz[j], min_time, 256*sz[j] / (min_time * 1e9));
}
return 0;
}
[-- Attachment #3: test_memset2.c --]
[-- Type: text/plain, Size: 7461 bytes --]
/*
* memset benchmark.
*
* Copyright (c) 2021, Arm Limited.
* SPDX-License-Identifier: MIT OR Apache-2.0 WITH LLVM-exception
*/
#define _GNU_SOURCE
#include <stdint.h>
#include <stdio.h>
#include <string.h>
#include <assert.h>
//#include "stringlib.h"
#include "benchlib.h"
#define ITERS 5000
#define ITERS2 20000000
#define ITERS3 1000000
#define NUM_TESTS 16384
#define MIN_SIZE 32768
#define MAX_SIZE (1024 * 1024)
static uint8_t a[MAX_SIZE + 4096] __attribute__((__aligned__(64)));
/*
#define F(x) {#x, x},
static const struct fun
{
const char *name;
void *(*fun)(void *, int, size_t);
} funtab[] =
{
#if __aarch64__
F(__memset_aarch64)
#elif __arm__
F(__memset_arm)
#endif
F(memset)
#undef F
{0, 0}
};
*/
typedef struct { uint32_t offset : 20, len : 12; } memset_test_t;
static memset_test_t test_arr[NUM_TESTS];
typedef struct { uint16_t size; uint16_t freq; } freq_data_t;
typedef struct { uint8_t align; uint16_t freq; } align_data_t;
#define SIZE_NUM 65536
#define SIZE_MASK (SIZE_NUM-1)
static uint8_t len_arr[SIZE_NUM];
/* Frequency data for memset sizes up to 4096 based on SPEC2017. */
static freq_data_t memset_len_freq[] =
{
{40,28817}, {32,15336}, { 16,3823}, {296,3545}, { 24,3454}, { 8,1412},
{292,1202}, { 48, 927}, { 12, 613}, { 11, 539}, {284, 493}, {108, 414},
{ 88, 380}, { 20, 295}, {312, 271}, { 72, 233}, { 2, 200}, { 4, 192},
{ 15, 180}, { 14, 174}, { 13, 160}, { 56, 151}, { 36, 144}, { 64, 140},
{4095,133}, { 10, 130}, { 9, 124}, { 3, 124}, { 28, 120}, { 0, 118},
{288, 110}, {1152, 96}, {104, 90}, { 1, 86}, {832, 76}, {248, 74},
{1024, 69}, {120, 64}, {512, 63}, {384, 60}, { 6, 59}, { 80, 54},
{ 17, 50}, { 7, 49}, {520, 47}, {2048, 39}, {256, 37}, {864, 33},
{1440, 28}, { 22, 27}, {2056, 24}, {260, 23}, { 68, 23}, { 5, 22},
{ 18, 21}, {200, 18}, {2120, 18}, { 60, 17}, { 52, 16}, {336, 15},
{ 44, 13}, {192, 13}, {160, 12}, {2064, 12}, {128, 12}, { 76, 11},
{164, 11}, {152, 10}, {136, 9}, {488, 7}, { 96, 6}, {560, 6},
{1016, 6}, {112, 5}, {232, 5}, {168, 5}, {952, 5}, {184, 5},
{144, 4}, {252, 4}, { 84, 3}, {960, 3}, {3808, 3}, {244, 3},
{280, 3}, {224, 3}, {156, 3}, {1088, 3}, {440, 3}, {216, 2},
{304, 2}, { 23, 2}, { 25, 2}, { 26, 2}, {264, 2}, {328, 2},
{1096, 2}, {240, 2}, {1104, 2}, {704, 2}, {1664, 2}, {360, 2},
{808, 1}, {544, 1}, {236, 1}, {720, 1}, {368, 1}, {424, 1},
{640, 1}, {1112, 1}, {552, 1}, {272, 1}, {776, 1}, {376, 1},
{ 92, 1}, {536, 1}, {824, 1}, {496, 1}, {760, 1}, {792, 1},
{504, 1}, {344, 1}, {1816, 1}, {880, 1}, {176, 1}, {320, 1},
{352, 1}, {2008, 1}, {208, 1}, {408, 1}, {228, 1}, {2072, 1},
{568, 1}, {220, 1}, {616, 1}, {600, 1}, {392, 1}, {696, 1},
{2144, 1}, {1280, 1}, {2136, 1}, {632, 1}, {584, 1}, {456, 1},
{472, 1}, {3440, 1}, {2088, 1}, {680, 1}, {2928, 1}, {212, 1},
{648, 1}, {1752, 1}, {664, 1}, {3512, 1}, {1032, 1}, {528, 1},
{4072, 1}, {204, 1}, {2880, 1}, {3392, 1}, {712, 1}, { 59, 1},
{736, 1}, {592, 1}, {2520, 1}, {744, 1}, {196, 1}, {172, 1},
{728, 1}, {2040, 1}, {1192, 1}, {3600, 1}, {0, 0}
};
#define ALIGN_NUM 1024
#define ALIGN_MASK (ALIGN_NUM-1)
static uint8_t align_arr[ALIGN_NUM];
/* Alignment data for memset based on SPEC2017. */
static align_data_t memset_align_freq[] =
{
{16, 338}, {8, 307}, {32, 148}, {64, 131}, {4, 72}, {1, 23}, {2, 5}, {0, 0}
};
static void
init_memset_distribution (void)
{
int i, j, freq, size, n;
for (n = i = 0; (freq = memset_len_freq[i].freq) != 0; i++)
for (j = 0, size = memset_len_freq[i].size; j < freq; j++)
len_arr[n++] = size;
assert (n == SIZE_NUM);
for (n = i = 0; (freq = memset_align_freq[i].freq) != 0; i++)
for (j = 0, size = memset_align_freq[i].align; j < freq; j++)
align_arr[n++] = size - 1;
assert (n == ALIGN_NUM);
}
static size_t
init_memset (size_t max_size)
{
size_t total = 0;
/* Create a random set of memsets with the given size and alignment
distributions. */
for (int i = 0; i < NUM_TESTS; i++)
{
test_arr[i].offset = (rand32 (0) & (max_size - 1));
test_arr[i].offset &= ~align_arr[rand32 (0) & ALIGN_MASK];
test_arr[i].len = len_arr[rand32 (0) & SIZE_MASK];
total += test_arr[i].len;
}
return total;
}
int main (void)
{
init_memset_distribution ();
memset (a, 1, sizeof (a));
printf("Random memset (bytes/ns):\n");
/*
for (int f = 0; funtab[f].name != 0; f++)
{
size_t total_size = 0;
uint64_t tsum = 0;
printf ("%22s ", funtab[f].name);
rand32 (0x12345678);
for (int size = MIN_SIZE; size <= MAX_SIZE; size *= 2)
{
size_t memset_size = init_memset (size) * ITERS;
for (int c = 0; c < NUM_TESTS; c++)
funtab[f].fun (a + test_arr[c].offset, 0, test_arr[c].len);
uint64_t t = clock_get_ns ();
for (int i = 0; i < ITERS; i++)
for (int c = 0; c < NUM_TESTS; c++)
funtab[f].fun (a + test_arr[c].offset, 0, test_arr[c].len);
t = clock_get_ns () - t;
total_size += memset_size;
tsum += t;
printf ("%dK: %.2f ", size / 1024, (double)memset_size / t);
}
printf( "avg %.2f\n", (double)total_size / tsum);
}
*/
size_t total_size = 0;
uint64_t tsum = 0;
printf ("%22s ", "memset_call");
rand32 (0x12345678);
for (int size = MIN_SIZE; size <= MAX_SIZE; size *= 2)
{
size_t memset_size = init_memset (size) * ITERS;
for (int c = 0; c < NUM_TESTS; c++)
memset (a + test_arr[c].offset, 0, test_arr[c].len);
uint64_t t = clock_get_ns ();
for (int i = 0; i < ITERS; i++)
for (int c = 0; c < NUM_TESTS; c++)
memset (a + test_arr[c].offset, 0, test_arr[c].len);
t = clock_get_ns () - t;
total_size += memset_size;
tsum += t;
printf ("%dK: %.2f ", size / 1024, (double)memset_size / t);
}
printf( "avg %.2f\n", (double)total_size / tsum);
printf ("\nMedium memset (bytes/ns):\n");
/*
for (int f = 0; funtab[f].name != 0; f++)
{
printf ("%22s ", funtab[f].name);
for (int size = 8; size <= 512; size *= 2)
{
uint64_t t = clock_get_ns ();
for (int i = 0; i < ITERS2; i++)
funtab[f].fun (a, 0, size);
t = clock_get_ns () - t;
printf ("%dB: %.2f ", size, (double)size * ITERS2 / t);
}
printf ("\n");
}
*/
printf ("%22s ", "memset_call");
for (int size = 8; size <= 512; size *= 2)
{
uint64_t t = clock_get_ns ();
for (int i = 0; i < ITERS2; i++)
memset (a, 0, size);
t = clock_get_ns () - t;
printf ("%dB: %.2f ", size, (double)size * ITERS2 / t);
}
printf ("\nLarge memset (bytes/ns):\n");
/*
for (int f = 0; funtab[f].name != 0; f++)
{
printf ("%22s ", funtab[f].name);
for (int size = 1024; size <= 65536; size *= 2)
{
uint64_t t = clock_get_ns ();
for (int i = 0; i < ITERS3; i++)
funtab[f].fun (a, 0, size);
t = clock_get_ns () - t;
printf ("%dK: %.2f ", size / 1024, (double)size * ITERS3 / t);
}
printf ("\n");
}
*/
printf ("%22s ", "memset_call");
for (int size = 1024; size <= 65536; size *= 2)
{
uint64_t t = clock_get_ns ();
for (int i = 0; i < ITERS3; i++)
memset (a, 0, size);
t = clock_get_ns () - t;
printf ("%dK: %.2f ", size / 1024, (double)size * ITERS3 / t);
}
printf ("\n\n");
return 0;
}
^ permalink raw reply [flat|nested] 10+ messages in thread
end of thread, other threads:[~2023-04-26 7:25 UTC | newest]
Thread overview: 10+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2023-04-11 2:17 [musl] memset_riscv64 张飞
2023-04-11 9:48 ` Pedro Falcato
2023-04-19 5:33 ` 张飞
2023-04-19 9:02 ` Szabolcs Nagy
2023-04-20 8:17 ` 张飞
2023-04-21 13:30 ` Szabolcs Nagy
2023-04-21 14:50 ` Pedro Falcato
2023-04-21 16:54 ` Rich Felker
2023-04-21 17:01 ` enh
2023-04-26 7:25 ` 张飞
Code repositories for project(s) associated with this public inbox
https://git.vuxu.org/mirror/musl/
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).