[<prev] [next>] [<thread-prev] [day] [month] [year] [list]
Message-ID: <37ca1f0c.1a115.187bc73b1d2.Coremail.zhangfei@nj.iscas.ac.cn>
Date: Wed, 26 Apr 2023 15:25:11 +0800 (GMT+08:00)
From: 张飞 <zhangfei@...iscas.ac.cn>
To: musl@...ts.openwall.com
Subject: Re: Re: Re: Re: memset_riscv64
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@...t70.net>
> 发送时间: 2023-04-21 21:30:34 (星期五)
> 收件人: "张飞" <zhangfei@...iscas.ac.cn>
> 抄送: musl@...ts.openwall.com
> 主题: Re: Re: Re: [musl] memset_riscv64
>
> * 张飞 <zhangfei@...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@...iscas.ac.cn></zhangfei@...iscas.ac.cn></nsz@...t70.net>
View attachment "test_memset1.c" of type "text/plain" (1395 bytes)
View attachment "test_memset2.c" of type "text/plain" (7461 bytes)
Powered by blists - more mailing lists
Confused about mailing lists and their use?
Read about mailing lists on Wikipedia
and check out these
guidelines on proper formatting of your messages.
