Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.forth > #44782 > unrolled thread
| Started by | Chris Curl <ccurl609@gmail.com> |
|---|---|
| First post | 2016-01-12 07:47 -0800 |
| Last post | 2016-02-11 07:39 -0800 |
| Articles | 20 on this page of 127 — 28 participants |
Back to article view | Back to comp.lang.forth
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
Page 2 of 7 — ← Prev page 1 [2] 3 4 5 6 7 Next page →
| From | peter.m.falth@gmail.com |
|---|---|
| Date | 2016-01-12 15:00 -0800 |
| Message-ID | <6e01edb6-e936-4418-bb77-e2ef9369a339@googlegroups.com> |
| In reply to | #44792 |
On Tuesday, 12 January 2016 21:43:54 UTC+1, Chris Curl wrote: > The same code in SP-Forth takes under 2 seconds: > > : .inc. DUP @ 1+ SWAP ! ; > 1024 DUP * 256 * CONSTANT memSz > VARIABLE (memory) > memSz ALLOCATE DROP (memory) ! > > CREATE stats 256 CELLS ALLOT > : clr-stats stats 256 CELLS 0 FILL ; > : all-stats > stats CELL (memory) @ DUP memSz 1- + SWAP > DO OVER OVER I C@ * + .inc. LOOP > 2DROP ; > : .stats 256 0 DO stats I DUP . CELLS + @ . CR LOOP ; > : do-test all-stats .stats ; > clr-stats > do-test with my 64 bit token threaded forth I get 3092 ms on a 2 GHz i5 laptop with my 32 bit native code generating forth I get 983 ms on the same laptop BR Peter Fälth
[toc] | [prev] | [next] | [standalone]
| From | Paul Rubin <no.email@nospam.invalid> |
|---|---|
| Date | 2016-01-12 16:13 -0800 |
| Message-ID | <87si22mj3x.fsf@jester.gateway.pace.com> |
| In reply to | #44801 |
peter.m.falth@gmail.com writes: > with my 64 bit token threaded forth I get 3092 ms on a 2 GHz i5 laptop > with my 32 bit native code generating forth I get 983 ms on the same laptop Interestingly, your 32 bit Forth is beating 64 bit C++ by a wide margin, even with C++ running on a considerably faster machine (i7-3770). That's using the std::array container straightforwardly: I'll see if I can fool with it to make it faster.
[toc] | [prev] | [next] | [standalone]
| From | mhx@iae.nl |
|---|---|
| Date | 2016-01-12 16:22 -0800 |
| Message-ID | <4158e334-f6a7-4d1f-a3ec-326adf43e2cd@googlegroups.com> |
| In reply to | #44806 |
On Wednesday, January 13, 2016 at 1:13:55 AM UTC+1, Paul Rubin wrote: > peter.m.falth@gmail.com writes: > > with my 64 bit token threaded forth I get 3092 ms on a 2 GHz i5 laptop > > with my 32 bit native code generating forth I get 983 ms on the same laptop > > Interestingly, your 32 bit Forth is beating 64 bit C++ by a wide margin, > even with C++ running on a considerably faster machine (i7-3770). > That's using the std::array container straightforwardly: I'll see if > I can fool with it to make it faster. Using ancient idioms: iForth version 4.0.1782, generated 21:06:07, March 6, 2014. x86_64 binary, native floating-point, extended precision. Copyright 1996 - 2014 Marcel Hendrix. #28 2^x =: memSz memSz ALLOCATE ?ALLOCATE =: memory HERE #256 CELLS ALLOT =: stats : reset ( -- ) stats #256 CELLS ERASE ; : do-test ( -- ) memory memSz BOUNDS DO 1 stats I C@ CELL[] +! LOOP ; : .stats ( -- ) stats #256 CELLS BOUNDS DO I ? CELL +LOOP ; TIMER-RESET reset do-test CR .stats .ELAPSED \ 0.492 seconds elapsed. ok -marcel
[toc] | [prev] | [next] | [standalone]
| From | Paul Rubin <no.email@nospam.invalid> |
|---|---|
| Date | 2016-01-12 16:24 -0800 |
| Message-ID | <87oacqmilx.fsf@jester.gateway.pace.com> |
| In reply to | #44806 |
Paul Rubin <no.email@nospam.invalid> writes:
>> with my 32 bit native code generating forth I get 983 ms on the same laptop
> Interestingly, your 32 bit Forth is beating 64 bit C++ by a wide margin,
> even with C++ running on a considerably faster machine (i7-3770).
Oh never mind, with optimization off and subscript checking on, I was
getting about 1 sec (GCC 4.7.2). With optimization -O3 and unsafe
subscripts, I get 141 ms. This is just for the counting part, not the
random initialization, which depends considerably on which PRNG you use.
The subscript checking actually only makes a tiny difference.
================================================================
#include <iostream>
#include <random>
#include <array>
#include <cstdint>
#include <chrono>
const int Bufsize = 1<<28;
std::array<std::uint8_t, Bufsize+3> buf;
void init_array()
{
std::minstd_rand rd;
for (int i = 0; i < buf.size(); i += 3)
{
int r = rd();
buf[i] = r&0xff;
r >>= 8;
buf[i+1] = r&0xff;
r >>= 8;
buf[i+2] = r&0xff;
}
}
int main(int argc, char **argv) {
auto t0 = std::chrono::high_resolution_clock::now();
init_array();
auto t1 = std::chrono::high_resolution_clock::now();
static std::array<std::uint32_t, 256> counts;
for (uint8_t b: buf) {
++counts[b];
}
auto t2 = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> d1 = t1 - t0;
std::chrono::duration<double> d2 = t2 - t1;
std::cout << d1.count () << " " << d2.count() << std::endl;
return 0;
}
[toc] | [prev] | [next] | [standalone]
| From | mhx@iae.nl |
|---|---|
| Date | 2016-01-12 17:46 -0800 |
| Message-ID | <2a5759c0-2109-4bd5-bc31-8a87aaebecc0@googlegroups.com> |
| In reply to | #44808 |
On Wednesday, January 13, 2016 at 1:24:47 AM UTC+1, Paul Rubin wrote:
> Paul Rubin <no.email@nospam.invalid> writes:
> >> with my 32 bit native code generating forth I get 983 ms on the same laptop
> > Interestingly, your 32 bit Forth is beating 64 bit C++ by a wide margin,
> > even with C++ running on a considerably faster machine (i7-3770).
>
> Oh never mind, with optimization off and subscript checking on, I was
> getting about 1 sec (GCC 4.7.2). With optimization -O3 and unsafe
> subscripts, I get 141 ms. This is just for the counting part, not the
> random initialization, which depends considerably on which PRNG you use.
> The subscript checking actually only makes a tiny difference.
>
> ================================================================
>
> #include <iostream>
> #include <random>
> #include <array>
> #include <cstdint>
> #include <chrono>
>
> const int Bufsize = 1<<28;
> std::array<std::uint8_t, Bufsize+3> buf;
>
> void init_array()
> {
> std::minstd_rand rd;
> for (int i = 0; i < buf.size(); i += 3)
> {
> int r = rd();
> buf[i] = r&0xff;
> r >>= 8;
> buf[i+1] = r&0xff;
> r >>= 8;
> buf[i+2] = r&0xff;
> }
> }
>
> int main(int argc, char **argv) {
> auto t0 = std::chrono::high_resolution_clock::now();
> init_array();
> auto t1 = std::chrono::high_resolution_clock::now();
>
> static std::array<std::uint32_t, 256> counts;
> for (uint8_t b: buf) {
> ++counts[b];
> }
> auto t2 = std::chrono::high_resolution_clock::now();
> std::chrono::duration<double> d1 = t1 - t0;
> std::chrono::duration<double> d2 = t2 - t1;
> std::cout << d1.count () << " " << d2.count() << std::endl;
> return 0;
> }
The compiler should have noticed that you aren't doing anything
with the contents of buf. I can get 122 ms in Forth by not
storing the counts in stats.
-marcel
[toc] | [prev] | [next] | [standalone]
| From | Paul Rubin <no.email@nospam.invalid> |
|---|---|
| Date | 2016-01-12 18:39 -0800 |
| Message-ID | <87a8oaurrx.fsf@nightsong.com> |
| In reply to | #44810 |
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.
[toc] | [prev] | [next] | [standalone]
| From | mhx@iae.nl |
|---|---|
| Date | 2016-01-13 13:05 -0800 |
| Message-ID | <45f4d146-8690-42b2-90eb-78b24d103e93@googlegroups.com> |
| In reply to | #44811 |
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 \ <--
There must be something very special about these
two instructions.
-- 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
-- ----------------------------------------------------
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 only possible reason is that the newest CPUs are
extremely serious about data/code separation.
-marcel
[toc] | [prev] | [next] | [standalone]
| From | Bernd Paysan <bernd.paysan@gmx.de> |
|---|---|
| Date | 2016-01-14 04:33 +0100 |
| Message-ID | <n774pc$gvn$1@dont-email.me> |
| In reply to | #44839 |
mhx@iae.nl wrote: > The only possible reason is that the newest CPUs are > extremely serious about data/code separation. They have been for quite some time, but at least it's no longer a read/read conflict (as with the Pentium). You should put your code somewhere else, not into the normal dictionary; the second best way is to put your variables and buffers somewhere else, and keep the constant data together with the code. Think of code memory on x86 like of Flash on a microcontroller: write once, read often. Writing is (in terms of performance) prohibitively expensive. -- Bernd Paysan "If you want it done right, you have to do it yourself" net2o ID: kQusJzA;7*?t=uy@X}1GWr!+0qqp_Cn176t4(dQ* http://bernd-paysan.de/
[toc] | [prev] | [next] | [standalone]
| From | m.a.m.hendrix@tue.nl |
|---|---|
| Date | 2016-01-14 03:27 -0800 |
| Message-ID | <54c04c7c-3d3f-462f-94e7-f602e5ed8301@googlegroups.com> |
| In reply to | #44857 |
On Thursday, January 14, 2016 at 4:33:36 AM UTC+1, Bernd Paysan wrote: > mhx@iae.nl wrote: > > > The only possible reason is that the newest CPUs are > > extremely serious about data/code separation. > > They have been for quite some time, but at least it's no longer a read/read > conflict (as with the Pentium). You should put your code somewhere else, > not into the normal dictionary; the second best way is to put your variables > and buffers somewhere else, and keep the constant data together with the > code. > > Think of code memory on x86 like of Flash on a microcontroller: write once, > read often. Writing is (in terms of performance) prohibitively expensive. In the fragment under discussion the variable is tens of megabytes away from the code: the code is at HERE and the variable is in the Forth stack. Therefore, quantifying "somewhere" is critical. How does the processor verify that code and data are "near?" I was always assuming that being in the same cacheline or some small multiple thereof would be seriously wrong. The current iForth uses the fact that a few kB distance is good enough (found by experiment). If current processors look at all of the data and code cache, iForth must be rewritten. However, if that were true, it should currently be much slower than other languages for any program (which is definitely not the case, and certainly not by a factor of four, like here :-) Is there something with memory pages being marked read, write, or execute that could be at play? The iForth stack is executable memory (not that it uses that, but the stacks are setup with malloc). -marcel
[toc] | [prev] | [next] | [standalone]
| From | peter.m.falth@gmail.com |
|---|---|
| Date | 2016-01-14 04:42 -0800 |
| Message-ID | <47d7a39e-1b71-4bde-93e1-7e54355f73e7@googlegroups.com> |
| In reply to | #44864 |
On Thursday, 14 January 2016 12:27:06 UTC+1, m.a.m....@tue.nl wrote: > On Thursday, January 14, 2016 at 4:33:36 AM UTC+1, Bernd Paysan wrote: > > mhx@iae.nl wrote: > > > > > The only possible reason is that the newest CPUs are > > > extremely serious about data/code separation. > > > > They have been for quite some time, but at least it's no longer a read/read > > conflict (as with the Pentium). You should put your code somewhere else, > > not into the normal dictionary; the second best way is to put your variables > > and buffers somewhere else, and keep the constant data together with the > > code. > > > > Think of code memory on x86 like of Flash on a microcontroller: write once, > > read often. Writing is (in terms of performance) prohibitively expensive. > > In the fragment under discussion the variable is tens > of megabytes away from the code: the code is at HERE > and the variable is in the Forth stack. Therefore, > quantifying "somewhere" is critical. > > How does the processor verify that code and data > are "near?" I was always assuming that being in the > same cacheline or some small multiple thereof would > be seriously wrong. The current iForth uses the fact > that a few kB distance is good enough (found by > experiment). > > If current processors look at all of the data and > code cache, iForth must be rewritten. However, if > that were true, it should currently be much slower > than other languages for any program (which is > definitely not the case, and certainly not by a > factor of four, like here :-) > > Is there something with memory pages being marked > read, write, or execute that could be at play? The > iForth stack is executable memory (not that it uses > that, but the stacks are setup with malloc). > > -marcel I have been trying out several code variants to see the effect. I then discovered that if I fill the memory with data before doing the stats then the code runs significantly , in the best case from 670 ms to 281 ms. This is on Windows. BR Peter Fälth
[toc] | [prev] | [next] | [standalone]
| From | anton@mips.complang.tuwien.ac.at (Anton Ertl) |
|---|---|
| Date | 2016-01-14 13:03 +0000 |
| Message-ID | <2016Jan14.140340@mips.complang.tuwien.ac.at> |
| In reply to | #44864 |
m.a.m.hendrix@tue.nl writes:
>How does the processor verify that code and data
>are "near?" I was always assuming that being in the
>same cacheline or some small multiple thereof would
>be seriously wrong. The current iForth uses the fact
>that a few kB distance is good enough (found by
>experiment).
Right. I have seen prefetch effects on the Pentium (code in one cache
line close to the end with data accessed by that code in the next
cache line resulted in slowdowns), and on the Pentium 4 with its trace
cache there was a 1KB granularity, and they recommended to not keep
code and data in the same page (4KB) to be future-proof, but that's
it.
The problem in your case is not mixing code and data; see my other
posting.
- 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/
[toc] | [prev] | [next] | [standalone]
| From | Paul Rubin <no.email@nospam.invalid> |
|---|---|
| Date | 2016-01-13 21:17 -0800 |
| Message-ID | <87si20u4cx.fsf@nightsong.com> |
| In reply to | #44839 |
mhx@iae.nl writes: > than even an *empty loop* in iForth: > $012249A8 sub [rbp 0 +] qword, 1 b# \ <-- > $012249AD jae $012249A8 offset NEAR \ <-- I don't understand that syntax, but (as you say) if it means you're decrementing from some memory cell that's very near the code, then yeah you could be causing pipeline conflicts. Can you move that variable far away from the code? Is there a reason you don't use a register for the loop index?
[toc] | [prev] | [next] | [standalone]
| From | hughaguilar96@gmail.com |
|---|---|
| Date | 2016-01-13 21:44 -0800 |
| Message-ID | <8393de2a-6a53-4f62-bc0a-eb7f075e0f93@googlegroups.com> |
| In reply to | #44859 |
On Wednesday, January 13, 2016 at 10:17:36 PM UTC-7, Paul Rubin wrote: > mhx@iae.nl writes: > > than even an *empty loop* in iForth: > > $012249A8 sub [rbp 0 +] qword, 1 b# \ <-- > > $012249AD jae $012249A8 offset NEAR \ <-- > > I don't understand that syntax, but (as you say) if it means you're > decrementing from some memory cell that's very near the code, then yeah > you could be causing pipeline conflicts. Can you move that variable far > away from the code? Is there a reason you don't use a register for the > loop index? I don't know what the term "pipeline conflict" means. In the old days of the Pentium, the term "pipeline" referred to the U and V pipes, but that doesn't exist anymore. I've never heard of any other use of the term. The modern x86 processors have separate code and data caches. Maybe when the same memory is cached in both code and data caches, and the data cache-line gets written to, the data cache-line has to be written back to memory and the code cache-line has to be read back in from memory in order to ensure that the code being executed hasn't been modified --- that could really drag down the speed --- the question has never come up on comp.lang.asm.x86 because nobody has juxtaposed code and data in over 30 years, so I don't know what the term is to describe this (I would be embarrassed to ask on CLAX because doing so would require me to admit how dumb ANS-Forth is to mix code and data, which would make me look dumb because I'm a known ANS-Forth programmer). I have said many times that ANS-Forth failed to require that code and data be separate, with a CHERE and HERE for the code dictionary pointer and the data dictionary pointer respectively. The need to separate code and data was well known in 1994 --- the PDP-11 was in the 1970s --- it is a bad idea to keep that ancient code going forever and never learn anything new. AFAIK, PolyForth was just Charles Moore's old PDP-11 MicroForth ported to new processors with little or no modification --- first the 8086 then the 80386 --- now SwiftForth is just PolyForth converted from ITC to STC, but still with most of the PolyForth features such as intermixed code and data. FIG-Forth was also derived directly from MicroForth.
[toc] | [prev] | [next] | [standalone]
| From | anton@mips.complang.tuwien.ac.at (Anton Ertl) |
|---|---|
| Date | 2016-01-14 10:57 +0000 |
| Message-ID | <2016Jan14.115741@mips.complang.tuwien.ac.at> |
| In reply to | #44839 |
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/
[toc] | [prev] | [next] | [standalone]
| From | mhx@iae.nl |
|---|---|
| Date | 2016-01-14 12:20 -0800 |
| Message-ID | <1bbf42e1-9a64-45c3-9820-aabde317ceb3@googlegroups.com> |
| In reply to | #44865 |
On Thursday, January 14, 2016 at 1:28:24 PM UTC+1, Anton Ertl wrote:
> 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.
Thanks a lot for the analysis, I really appreciate it.
However, the tests say it is still not working.
I patched from
$01224600 : do-test
$0122460A mov rcx, $1B350050 d#
$01224611 mov rbx, $0FFFFFFF d#
$01224618 call (FOR) offset NEAR
$01224622 nop
$01224623 lea rax, [rax 0 +] qword
$01224628 movzx rdi, [rbx] byte
$0122462C add [rdi*8 $01220F30 +] qword, 1 b#
$01224635 lea rbx, [rbx 1 +] qword
$01224639 sub [rbp 0 +] qword, 1 b#
$0122463E jae $01224628 offset NEAR
$01224644 add rbp, #24 b#
$01224648 ;
to
$01224600 : do-test
$0122460A mov rcx, $1B350050 d#
$01224611 mov rbx, $0FFFFFFF d#
$01224618 call (FOR) offset NEAR
$01224622 nop
$01224623 nop
$01224624 mov rcx, [rbp 0 +] qword
$01224628 movzx rdi, [rbx] byte
$0122462C add [rdi*8 $01220F30 +] qword, 1 b#
$01224635 lea rbx, [rbx 1 +] qword
$01224639 sub rcx, 1 b#
$0122463D nop
$0122463E jae $01224628 offset NEAR
$01224644 add rbp, #24 b#
$01224648 ;
Both do-tests need the same amount of time,
although the "sub [rbp 0 +] qword, 1 b#" instruction is
avoided. (I should've stuck to the tight loop, for
comparison, sorry about that).
I tried pre-filling "memory" with '1': no change.
I allotted 256MB at HERE instead of ALLOCATE: no change.
-marcel
[toc] | [prev] | [next] | [standalone]
| From | mhx@iae.nl |
|---|---|
| Date | 2016-01-14 13:57 -0800 |
| Message-ID | <689e95b2-af8b-42c0-bce2-977d9472381b@googlegroups.com> |
| In reply to | #44878 |
On Thursday, January 14, 2016 at 9:20:55 PM UTC+1, m...@iae.nl wrote:
> On Thursday, January 14, 2016 at 1:28:24 PM UTC+1, Anton Ertl wrote:
> > 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.
>
> Thanks a lot for the analysis, I really appreciate it.
>
> However, the tests say it is still not working.
>
> I patched from
>
> $01224600 : do-test
> $0122460A mov rcx, $1B350050 d#
> $01224611 mov rbx, $0FFFFFFF d#
> $01224618 call (FOR) offset NEAR
> $01224622 nop
> $01224623 lea rax, [rax 0 +] qword
> $01224628 movzx rdi, [rbx] byte
> $0122462C add [rdi*8 $01220F30 +] qword, 1 b#
> $01224635 lea rbx, [rbx 1 +] qword
> $01224639 sub [rbp 0 +] qword, 1 b#
> $0122463E jae $01224628 offset NEAR
> $01224644 add rbp, #24 b#
> $01224648 ;
>
> to
>
> $01224600 : do-test
> $0122460A mov rcx, $1B350050 d#
> $01224611 mov rbx, $0FFFFFFF d#
> $01224618 call (FOR) offset NEAR
> $01224622 nop
> $01224623 nop
> $01224624 mov rcx, [rbp 0 +] qword
> $01224628 movzx rdi, [rbx] byte
> $0122462C add [rdi*8 $01220F30 +] qword, 1 b#
> $01224635 lea rbx, [rbx 1 +] qword
> $01224639 sub rcx, 1 b#
> $0122463D nop
> $0122463E jae $01224628 offset NEAR
> $01224644 add rbp, #24 b#
> $01224648 ;
>
> Both do-tests need the same amount of time,
> although the "sub [rbp 0 +] qword, 1 b#" instruction is
> avoided. (I should've stuck to the tight loop, for
> comparison, sorry about that).
>
> I tried pre-filling "memory" with '1': no change.
> I allotted 256MB at HERE instead of ALLOCATE: no change.
>
> -marcel
Forget it.
Running the original code (translated to C, but
resulting in nearly the same machine code as shown
for the C++ original) gives 470ms! I didn't
know the difference in Intel CPU could be that
large (using a i7-4930 @3.4 GHz myself), or that
this code could be vectorized.
-marcel
-- random.c --------------
#include <stdio.h>
#define Bufsize (1<<28)
uint8_t buf[Bufsize]; int counts[256];
int main(void) { int ix; for (ix = 0; ix < Bufsize; ix++) ++counts[buf[ix]]; return 0; }
marcel@me-tarzan ~
$ gcc -O3 random.c
$ time ./a.exe
real 0m0.470s
user 0m0.436s
sys 0m0.031s
[toc] | [prev] | [next] | [standalone]
| From | Paul Rubin <no.email@nospam.invalid> |
|---|---|
| Date | 2016-01-14 14:22 -0800 |
| Message-ID | <87mvs7u7gz.fsf@nightsong.com> |
| In reply to | #44879 |
mhx@iae.nl writes: > Running the original code (translated to C, but resulting in nearly > the same machine code as shown for the C++ original) gives 470ms! I > didn't know the difference in Intel CPU could be that large (using a > i7-4930 @3.4 GHz myself), or that this code could be vectorized. Your C program takes 416 ms on the i7-3770 that I timed the C++ program on. Output of the C++ program is 0.386345 0.140901 which makes me wonder if something is off about the timing routine. When I comment out the call to init_array, the output is "1e-06 0.442457". Another idea is that the initial 0.386 sec is used in allocating or paging the 256MB buffer. But I find that running the loop in your program twice doubles the cpu time, to 852 msec. I'll test more stuff.
[toc] | [prev] | [next] | [standalone]
| From | mhx@iae.nl |
|---|---|
| Date | 2016-01-14 16:14 -0800 |
| Message-ID | <320eda79-0524-4898-a332-34870f00a9c3@googlegroups.com> |
| In reply to | #44880 |
On Thursday, January 14, 2016 at 11:22:40 PM UTC+1, Paul Rubin wrote:
> mhx@iae.nl writes:
> > Running the original code (translated to C, but resulting in nearly
> > the same machine code as shown for the C++ original) gives 470ms! I
> > didn't know the difference in Intel CPU could be that large (using a
> > i7-4930 @3.4 GHz myself), or that this code could be vectorized.
>
> Your C program takes 416 ms on the i7-3770 that I timed the C++ program
> on. Output of the C++ program is 0.386345 0.140901 which makes me
> wonder if something is off about the timing routine. When I comment out
> the call to init_array, the output is "1e-06 0.442457". Another idea is
> that the initial 0.386 sec is used in allocating or paging the 256MB
> buffer. But I find that running the loop in your program twice doubles
> the cpu time, to 852 msec. I'll test more stuff.
I can get 0.19 seconds for the C code if I use openmp:
#include <stdio.h>
#define Bufsize (1<<28)
uint8_t buf[Bufsize];
int counts[256];
int main(void) {
int ix;
#pragma omp parallel for
for (ix = 0; ix < Bufsize; ix++)
++counts[buf[ix]];
return 0;
}
marcel@me-tarzan ~
$ gcc -O6 -fopenmp random.c
marcel@me-tarzan ~
$ set OMP_NUM_THREADS = 8
marcel@me-tarzan ~
$ time ./a.exe
real 0m0.190s
user 0m0.951s
sys 0m0.062s
[toc] | [prev] | [next] | [standalone]
| From | Melzzzzz <mel@zzzzz.com> |
|---|---|
| Date | 2016-01-15 03:05 +0100 |
| Message-ID | <20160115030520.37cfb202@maxa-pc> |
| In reply to | #44880 |
On Thu, 14 Jan 2016 14:22:36 -0800 Paul Rubin <no.email@nospam.invalid> wrote: > mhx@iae.nl writes: > > Running the original code (translated to C, but resulting in nearly > > the same machine code as shown for the C++ original) gives 470ms! I > > didn't know the difference in Intel CPU could be that large (using a > > i7-4930 @3.4 GHz myself), or that this code could be vectorized. > > Your C program takes 416 ms on the i7-3770 that I timed the C++ > program on. Output of the C++ program is 0.386345 0.140901 which > makes me wonder if something is off about the timing routine. When I > comment out the call to init_array, the output is "1e-06 0.442457". > Another idea is that the initial 0.386 sec is used in allocating or > paging the 256MB buffer. But I find that running the loop in your > program twice doubles the cpu time, to 852 msec. I'll test more > stuff. > This is same problem I met when constantly updating same memory cell vs initializing whole array (in assembly). Seems that cache trashing happens when updating same memory cell constantly.
[toc] | [prev] | [next] | [standalone]
| From | Waldek Hebisch <hebisch@antispam.uni.wroc.pl> |
|---|---|
| Date | 2016-01-15 00:41 +0000 |
| Message-ID | <n79f8k$bph$1@z-news.wcss.wroc.pl> |
| In reply to | #44879 |
mhx@iae.nl wrote:
> On Thursday, January 14, 2016 at 9:20:55 PM UTC+1, m...@iae.nl wrote:
>
> Forget it.
>
> Running the original code (translated to C, but
> resulting in nearly the same machine code as shown
> for the C++ original) gives 470ms! I didn't
> know the difference in Intel CPU could be that
> large (using a i7-4930 @3.4 GHz myself), or that
> this code could be vectorized.
>
> -marcel
>
> -- random.c --------------
> #include <stdio.h>
> #define Bufsize (1<<28)
> uint8_t buf[Bufsize]; int counts[256];
> int main(void) { int ix; for (ix = 0; ix < Bufsize; ix++) ++counts[buf[ix]]; return 0; }
>
> marcel@me-tarzan ~
> $ gcc -O3 random.c
> $ time ./a.exe
>
> real 0m0.470s
> user 0m0.436s
> sys 0m0.031s
>
Your buf is initialized to 0. This means that you are always bumping
count[0] -- this is the same problem that your empty loop had.
On my machine (2.4GHz Core 2), a slightly modified version of
the program takes a bit more than 0.7s (timing are unstable
changing from run to run from 0.704 up to 0.764). Initializing
buf with linear sequence bring time down to a bit more than 0.3
(low 0.299 high 0.332). The initialization with linear sequence
means that following iteration of the loop uses different counter
than the previous one.
Clearly, performance of this program greatly depends on tiny
details of cache interface and actual access pattern to counts
array. Hence performance can change a lot between CPU models.
--
Waldek Hebisch
[toc] | [prev] | [next] | [standalone]
Page 2 of 7 — ← Prev page 1 [2] 3 4 5 6 7 Next page →
Back to top | Article view | comp.lang.forth
csiph-web