Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.forth > #44865
| From | anton@mips.complang.tuwien.ac.at (Anton Ertl) |
|---|---|
| Newsgroups | comp.lang.forth |
| Subject | Re: Ruby/Forth challenge for WJ |
| Date | 2016-01-14 10:57 +0000 |
| Organization | Institut fuer Computersprachen, Technische Universitaet Wien |
| Message-ID | <2016Jan14.115741@mips.complang.tuwien.ac.at> (permalink) |
| References | (3 earlier) <87si22mj3x.fsf@jester.gateway.pace.com> <87oacqmilx.fsf@jester.gateway.pace.com> <2a5759c0-2109-4bd5-bc31-8a87aaebecc0@googlegroups.com> <87a8oaurrx.fsf@nightsong.com> <45f4d146-8690-42b2-90eb-78b24d103e93@googlegroups.com> |
mhx@iae.nl writes:
>On Wednesday, January 13, 2016 at 3:39:37 AM UTC+1, Paul Rubin wrote:
>> mhx@iae.nl writes:
>> >> for (uint8_t b: buf) {
>> >> ++counts[b];
>> >> } ...
>> >
>> > The compiler should have noticed that you aren't doing anything
>> > with the contents of buf.
>>
>> In C++11, the "for (uint_t b: buf) ..." syntax means that b iterates
>> through the contents of buf. OTOH it's true that I didn't do anything
>> with the contents of counts. But I had tested with smaller bufs earlier
>> and the runtime scaled linearly.
>
>Hi Paul,
>
>This is really very strange. The code generated by gcc with -O3
>does not look very spectacular, but is about 4 times faster
>than even an *empty loop* in iForth:
>
>$012249A8 sub [rbp 0 +] qword, 1 b# \ <--
>$012249AD jae $012249A8 offset NEAR \ <--
This empty loop has a recurrence (loop-carried dependency) through
memory. So in every iteration you load from the L1 cache or store
buffer (4 cycle latency in recent intel chips), perform the sub (1
cycle), and store it into the store buffer and later the L1 cache (not
sure what the latency is until you can read that value again). The
takeaway message is that you should keep the loop counter in a
register, then you have one cycle per iteration.
As others have mentioned, if the data is close to the code, you get
cache misses from cache consistency, but I guess that this data is on
the return stack and far away from the code.
>-- C++ -O3 -------------------------------------------
> static std::array<std::uint32_t, 256> counts;
> for (uint8_t b: buf) {
> ++counts[b];
> }
> auto t2 = std::chrono::high_resolution_clock::now();
>-- ---------------------------------------------------
> call _ZNSt6chrono3_V212system_clock3nowEv
> leaq 268435459(%rdi), %r8
> leaq _ZZ4mainE6counts(%rip), %rcx
> movq %rax, %rbp
> .p2align 4,,10
>.L7:
> movzbl (%rbx), %edx
> addq $1, %rbx
> addl $1, (%rcx,%rdx,4)
> cmpq %r8, %rbx
> jne .L7
> call _ZNSt6chrono3_V212system_clock3nowEv
>-- ----------------------------------------------------
While the loop does a read-modify-write of memory here, too, most of
the reads do not depend on the immediately preceding writes, and are
thus independent. In the best case a current Intel CPU can achieve a
throughput of 0.8-1 iteration per cycle for such code.
You might see false sharing (reads from a cell waiting for the write
to a nearby cell to complete), because they are in the same cache
line, but I don't know the granularity of sharing in the write buffer
of current Intel CPUs.
>FORTH> see do-test ( do-test takes 490 ms.)
>Flags: TOKENIZE, ANSI
>: do-test [trashed] [trashed] BOUNDS DO 1 [trashed] I C@ CELL[] +! LOOP ; ok
>FORTH> ' do-test idis ( OK, this doesn't look too good )
>$01221C00 : do-test
>...
>$01221C28 mov rdi, [rbp 0 +] qword
>$01221C2C movzx rdi, [rdi] byte
>$01221C30 add [rdi*8 $01220F30 +] qword, 1 b#
>$01221C39 add [rbp 0 +] qword, 1 b#
>$01221C3E add [rbp 8 +] qword, 1 b#
>$01221C43 jno $01221C28 offset NEAR
>...
>
>But even when shortened to do nothing at all (in principle):
>
>: do-test ( -- ) memory memSz 1- FOR ( C@+ stats []CELL 1 SWAP +! ) NEXT DROP ;
>
>$01224980 : do-test
>$0122498A mov rcx, $1A960050 d#
>$01224991 mov rbx, $0FFFFFFF d#
>$01224998 call (FOR) offset NEAR
>$012249A2 nop
>$012249A3 lea rax, [rax 0 +] qword
>$012249A8 sub [rbp 0 +] qword, 1 b# \ <--
>$012249AD jae $012249A8 offset NEAR \ <--
>
>It still takes 490 ms! These Intel CPU's are strange beasts.
>Apparently the above sequence, generated by the C-compiler.
>is 4 times faster than the two iForth lines marked above.
The C++ compiler keeps the loop variable in a register, and iForth
keeps it in memory. This means n>=5 cycles per iteration for iForth,
and, for the loop alone, 1 cycle for the code generated by the C++
compiler. All the other instructions in your Forth program run in
parallel to the add or sub instruction for the loop variable. For the
code generated C++ compiler, the loop runs into the limit of four
instructions per cycle, and it occasionally sees a loop-carried
dependency through the counts array, so it's a little slower than 1
cycle per iteration, but probably not by much.
>The only possible reason is that the newest CPUs are
>extremely serious about data/code separation.
That's not the case for this example, but yes, they are also that.
- anton
--
M. Anton Ertl http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
New standard: http://www.forth200x.org/forth200x.html
EuroForth 2015: http://www.rigwit.co.uk/EuroForth2015/
Back to comp.lang.forth | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
Ruby/Forth challenge for WJ Chris Curl <ccurl609@gmail.com> - 2016-01-12 07:47 -0800
Re: Ruby/Forth challenge for WJ Albert van der Horst <albert@spenarnc.xs4all.nl> - 2016-01-12 16:25 +0000
Re: Ruby/Forth challenge for WJ Andrew Haley <andrew29@littlepinkcloud.invalid> - 2016-01-12 10:45 -0600
Re: Ruby/Forth challenge for WJ Chris Curl <ccurl609@gmail.com> - 2016-01-12 08:46 -0800
Re: Ruby/Forth challenge for WJ rickman <gnuarm@gmail.com> - 2016-01-12 11:57 -0500
Re: Ruby/Forth challenge for WJ Chris Curl <ccurl609@gmail.com> - 2016-01-12 09:22 -0800
Re: Ruby/Forth challenge for WJ hughaguilar96@gmail.com - 2016-01-12 21:04 -0800
Re: Ruby/Forth challenge for WJ Ron Aaron <rambamist@gmail.com> - 2016-01-13 07:59 +0200
Re: Ruby/Forth challenge for WJ Albert van der Horst <albert@spenarnc.xs4all.nl> - 2016-01-12 19:42 +0000
Re: Ruby/Forth challenge for WJ Paul Rubin <no.email@nospam.invalid> - 2016-01-12 12:53 -0800
Re: Ruby/Forth challenge for WJ anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-01-13 15:45 +0000
Re: Ruby/Forth challenge for WJ rickman <gnuarm@gmail.com> - 2016-01-13 13:44 -0500
Re: Ruby/Forth challenge for WJ Paul Rubin <no.email@nospam.invalid> - 2016-01-13 11:39 -0800
Re: Ruby/Forth challenge for WJ Bernd Paysan <bernd.paysan@gmx.de> - 2016-01-14 05:01 +0100
Re: Ruby/Forth challenge for WJ anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-01-14 12:28 +0000
Re: Ruby/Forth challenge for WJ Chris Curl <ccurl609@gmail.com> - 2016-01-12 09:50 -0800
Re: Ruby/Forth challenge for WJ Pablo Hugo Reda <pabloreda@gmail.com> - 2016-01-12 11:50 -0800
Re: Ruby/Forth challenge for WJ Chris Curl <ccurl609@gmail.com> - 2016-01-12 12:30 -0800
Re: Ruby/Forth challenge for WJ Chris Curl <ccurl609@gmail.com> - 2016-01-12 12:43 -0800
Re: Ruby/Forth challenge for WJ stephen@mpeforth.com (Stephen Pelc) - 2016-01-12 21:01 +0000
Re: Ruby/Forth challenge for WJ peter.m.falth@gmail.com - 2016-01-12 15:00 -0800
Re: Ruby/Forth challenge for WJ Paul Rubin <no.email@nospam.invalid> - 2016-01-12 16:13 -0800
Re: Ruby/Forth challenge for WJ mhx@iae.nl - 2016-01-12 16:22 -0800
Re: Ruby/Forth challenge for WJ Paul Rubin <no.email@nospam.invalid> - 2016-01-12 16:24 -0800
Re: Ruby/Forth challenge for WJ mhx@iae.nl - 2016-01-12 17:46 -0800
Re: Ruby/Forth challenge for WJ Paul Rubin <no.email@nospam.invalid> - 2016-01-12 18:39 -0800
Re: Ruby/Forth challenge for WJ mhx@iae.nl - 2016-01-13 13:05 -0800
Re: Ruby/Forth challenge for WJ Bernd Paysan <bernd.paysan@gmx.de> - 2016-01-14 04:33 +0100
Re: Ruby/Forth challenge for WJ m.a.m.hendrix@tue.nl - 2016-01-14 03:27 -0800
Re: Ruby/Forth challenge for WJ peter.m.falth@gmail.com - 2016-01-14 04:42 -0800
Re: Ruby/Forth challenge for WJ anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-01-14 13:03 +0000
Re: Ruby/Forth challenge for WJ Paul Rubin <no.email@nospam.invalid> - 2016-01-13 21:17 -0800
Re: Ruby/Forth challenge for WJ hughaguilar96@gmail.com - 2016-01-13 21:44 -0800
Re: Ruby/Forth challenge for WJ anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-01-14 10:57 +0000
Re: Ruby/Forth challenge for WJ mhx@iae.nl - 2016-01-14 12:20 -0800
Re: Ruby/Forth challenge for WJ mhx@iae.nl - 2016-01-14 13:57 -0800
Re: Ruby/Forth challenge for WJ Paul Rubin <no.email@nospam.invalid> - 2016-01-14 14:22 -0800
Re: Ruby/Forth challenge for WJ mhx@iae.nl - 2016-01-14 16:14 -0800
Re: Ruby/Forth challenge for WJ Melzzzzz <mel@zzzzz.com> - 2016-01-15 03:05 +0100
Re: Ruby/Forth challenge for WJ Waldek Hebisch <hebisch@antispam.uni.wroc.pl> - 2016-01-15 00:41 +0000
Re: Ruby/Forth challenge for WJ anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-01-15 16:22 +0000
Re: Ruby/Forth challenge for WJ mhx@iae.nl (Marcel Hendrix) - 2016-01-16 11:44 +0200
Re: Ruby/Forth challenge for WJ mhx@iae.nl - 2016-01-16 04:49 -0800
Re: Ruby/Forth challenge for WJ Albert van der Horst <albert@spenarnc.xs4all.nl> - 2016-01-16 15:05 +0000
Re: Ruby/Forth challenge for WJ m.a.m.hendrix@tue.nl - 2016-01-18 03:26 -0800
Re: Ruby/Forth challenge for WJ anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-01-18 12:48 +0000
Re: Ruby/Forth challenge for WJ Bernd Paysan <bernd.paysan@gmx.de> - 2016-01-19 22:26 +0100
Re: Ruby/Forth challenge for WJ mhx@iae.nl - 2016-01-20 03:05 -0800
Re: Ruby/Forth challenge for WJ Bernd Paysan <bernd.paysan@gmx.de> - 2016-01-20 21:00 +0100
Re: Ruby/Forth challenge for WJ mhx@iae.nl - 2016-01-20 15:57 -0800
Re: Ruby/Forth challenge for WJ Bernd Paysan <bernd.paysan@gmx.de> - 2016-01-21 23:02 +0100
Re: Ruby/Forth challenge for WJ Albert van der Horst <albert@spenarnc.xs4all.nl> - 2016-01-22 01:25 +0000
Re: Ruby/Forth challenge for WJ hughaguilar96@gmail.com - 2016-01-21 18:05 -0800
Re: Ruby/Forth challenge for WJ mhx@iae.nl - 2016-01-21 22:03 -0800
Re: Ruby/Forth challenge for WJ anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-01-20 13:40 +0000
Re: Ruby/Forth challenge for WJ m.a.m.hendrix@tue.nl - 2016-01-18 03:55 -0800
Re: Ruby/Forth challenge for WJ Andrew Haley <andrew29@littlepinkcloud.invalid> - 2016-01-23 15:13 -0600
Re: Ruby/Forth challenge for WJ mhx@iae.nl - 2016-01-24 00:55 -0800
Re: Ruby/Forth challenge for WJ Andrew Haley <andrew29@littlepinkcloud.invalid> - 2016-01-25 04:48 -0600
Re: Ruby/Forth challenge for WJ Albert van der Horst <albert@spenarnc.xs4all.nl> - 2016-01-25 12:39 +0000
Re: Ruby/Forth challenge for WJ Andrew Haley <andrew29@littlepinkcloud.invalid> - 2016-01-25 08:05 -0600
Re: Ruby/Forth challenge for WJ Albert van der Horst <albert@spenarnc.xs4all.nl> - 2016-01-25 16:40 +0000
Re: Ruby/Forth challenge for WJ Mark Wills <markwills1970@gmail.com> - 2016-01-25 04:44 -0800
Re: Ruby/Forth challenge for WJ stephen@mpeforth.com (Stephen Pelc) - 2016-01-25 14:01 +0000
Re: Ruby/Forth challenge for WJ Andrew Haley <andrew29@littlepinkcloud.invalid> - 2016-01-25 08:08 -0600
Re: Ruby/Forth challenge for WJ Andrew Haley <andrew29@littlepinkcloud.invalid> - 2016-01-25 11:56 -0600
Re: Ruby/Forth challenge for WJ "Elizabeth D. Rather" <erather@forth.com> - 2016-01-25 11:12 -1000
Re: Ruby/Forth challenge for WJ Andrew Haley <andrew29@littlepinkcloud.invalid> - 2016-01-26 03:33 -0600
Re: Ruby/Forth challenge for WJ stephen@mpeforth.com (Stephen Pelc) - 2016-01-26 11:09 +0000
Re: Ruby/Forth challenge for WJ stephen@mpeforth.com (Stephen Pelc) - 2016-01-26 11:06 +0000
Re: Ruby/Forth challenge for WJ Andrew Haley <andrew29@littlepinkcloud.invalid> - 2016-01-26 07:45 -0600
Re: Ruby/Forth challenge for WJ anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-01-26 16:46 +0000
Re: Ruby/Forth challenge for WJ Andrew Haley <andrew29@littlepinkcloud.invalid> - 2016-01-26 11:16 -0600
Object-oriented Forth (was: Ruby/Forth challenge for WJ) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-01-27 14:13 +0000
Re: Object-oriented Forth Andrew Haley <andrew29@littlepinkcloud.invalid> - 2016-01-27 10:33 -0600
Re: Object-oriented Forth hughaguilar96@gmail.com - 2016-01-27 08:45 -0800
Re: Object-oriented Forth Chris Curl <ccurl609@gmail.com> - 2016-01-27 09:14 -0800
Re: Object-oriented Forth hughaguilar96@gmail.com - 2016-01-29 21:57 -0800
Re: Object-oriented Forth Albert van der Horst <albert@spenarnc.xs4all.nl> - 2016-01-30 10:58 +0000
Re: Object-oriented Forth Chris Curl <ccurl609@gmail.com> - 2016-01-30 09:38 -0800
Re: Object-oriented Forth Coos Haak <chforth@hccnet.nl> - 2016-01-30 20:39 +0100
Re: Ruby/Forth challenge for WJ Bernd Paysan <bernd.paysan@gmx.de> - 2016-01-26 15:56 +0100
Re: Ruby/Forth challenge for WJ stephen@mpeforth.com (Stephen Pelc) - 2016-01-26 20:46 +0000
Re: Ruby/Forth challenge for WJ Bernd Paysan <bernd.paysan@gmx.de> - 2016-01-25 22:27 +0100
Re: Ruby/Forth challenge for WJ Roelf Toxopeus <rt4all@notthis.hetnet.nl> - 2016-01-28 14:20 +0100
Re: Ruby/Forth challenge for WJ Andrew Haley <andrew29@littlepinkcloud.invalid> - 2016-01-28 08:06 -0600
Re: Ruby/Forth challenge for WJ Bernd Paysan <bernd.paysan@gmx.de> - 2016-01-28 16:14 +0100
Re: Ruby/Forth challenge for WJ Andrew Haley <andrew29@littlepinkcloud.invalid> - 2016-01-28 10:32 -0600
Re: Ruby/Forth challenge for WJ anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-01-28 17:26 +0000
Re: Ruby/Forth challenge for WJ Andrew Haley <andrew29@littlepinkcloud.invalid> - 2016-01-28 12:13 -0600
Re: Ruby/Forth challenge for WJ Albert van der Horst <albert@spenarnc.xs4all.nl> - 2016-01-29 11:07 +0000
Re: Ruby/Forth challenge for WJ Bernd Paysan <bernd.paysan@gmx.de> - 2016-01-29 21:18 +0100
Re: Ruby/Forth challenge for WJ Tessa Bonting <tessa.bonting@gmail.com> - 2016-01-16 06:24 -0800
Re: Ruby/Forth challenge for WJ Rod Pemberton <NoHaveNotOne@bcczxcfre.cmm> - 2016-01-13 05:21 -0500
Re: Ruby/Forth challenge for WJ Rod Pemberton <NoHaveNotOne@bcczxcfre.cmm> - 2016-01-13 05:36 -0500
Re: Ruby/Forth challenge for WJ Paul Rubin <no.email@nospam.invalid> - 2016-01-13 10:33 -0800
Re: Ruby/Forth challenge for WJ Rod Pemberton <NoHaveNotOne@bcczxcfre.cmm> - 2016-01-14 01:37 -0500
Re: Ruby/Forth challenge for WJ Chris Curl <ccurl609@gmail.com> - 2016-01-12 13:45 -0800
Re: Ruby/Forth challenge for WJ Chris Curl <ccurl609@gmail.com> - 2016-01-12 13:55 -0800
Re: Ruby/Forth challenge for WJ Paul Rubin <no.email@nospam.invalid> - 2016-01-12 14:34 -0800
Re: Ruby/Forth challenge for WJ rickman <gnuarm@gmail.com> - 2016-01-12 19:00 -0500
Re: Ruby/Forth challenge for WJ Chris Curl <ccurl609@gmail.com> - 2016-01-12 16:49 -0800
Re: Ruby/Forth challenge for WJ rickman <gnuarm@gmail.com> - 2016-01-12 22:18 -0500
Re: Ruby/Forth challenge for WJ hughaguilar96@gmail.com - 2016-01-12 14:31 -0800
Re: Ruby/Forth challenge for WJ Chris Curl <ccurl609@gmail.com> - 2016-01-12 16:05 -0800
Re: Ruby/Forth challenge for WJ "WJ" <w_a_x_man@yahoo.com> - 2016-01-13 07:58 +0000
Re: Ruby/Forth challenge for WJ Rod Pemberton <NoHaveNotOne@bcczxcfre.cmm> - 2016-01-13 05:17 -0500
Re: Ruby/Forth challenge for WJ Paul Rubin <no.email@nospam.invalid> - 2016-01-13 12:36 -0800
Re: Ruby/Forth challenge for WJ Chris Curl <ccurl609@gmail.com> - 2016-01-13 12:53 -0800
Re: Ruby/Forth challenge for WJ Andrew Haley <andrew29@littlepinkcloud.invalid> - 2016-01-14 06:50 -0600
Re: Ruby/Forth challenge for WJ Julian Fondren <julian.fondren@gmail.com> - 2016-01-13 05:36 -0800
Re: Ruby/Forth challenge for WJ lehs <skydda.barnen@gmail.com> - 2016-01-13 11:59 -0800
Re: Ruby/Forth challenge for WJ Chris Curl <ccurl609@gmail.com> - 2016-01-21 21:08 -0800
Re: Ruby/Forth challenge for WJ "WJ" <w_a_x_man@yahoo.com> - 2016-02-09 13:36 +0000
Re: Ruby/Forth challenge for WJ "WJ" <w_a_x_man@yahoo.com> - 2016-02-09 13:48 +0000
Re: Ruby/Forth challenge for WJ hughaguilar96@gmail.com - 2016-02-09 12:02 -0800
Re: Ruby/Forth challenge for WJ "WJ" <w_a_x_man@yahoo.com> - 2016-02-09 13:58 +0000
Re: Ruby/Forth challenge for WJ "WJ" <w_a_x_man@yahoo.com> - 2016-02-09 14:30 +0000
Re: Ruby/Forth challenge for WJ "WJ" <w_a_x_man@yahoo.com> - 2016-02-14 15:35 +0000
Re: Ruby/Forth challenge for WJ franck.bensusan@gmail.com - 2016-02-14 08:50 -0800
Re: Ruby/Forth challenge for WJ Julian Fondren <julian.fondren@gmail.com> - 2016-02-14 20:09 -0800
Re: Ruby/Forth challenge for WJ hughaguilar96@gmail.com - 2016-02-15 08:52 -0800
Re: Ruby/Forth challenge for WJ "WJ" <w_a_x_man@yahoo.com> - 2016-02-14 21:31 +0000
Re: Ruby/Forth challenge for WJ "WJ" <w_a_x_man@yahoo.com> - 2016-01-14 22:49 +0000
Re: Ruby/Forth challenge for WJ Paul Rubin <no.email@nospam.invalid> - 2016-01-14 15:31 -0800
Re: Ruby/Forth challenge for WJ Melzzzzz <mel@zzzzz.com> - 2016-01-15 06:55 +0100
Re: Ruby/Forth challenge for WJ djc <ciesinger@gmx.net> - 2016-02-11 07:39 -0800
csiph-web