Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.forth > #52718 > unrolled thread

Data Stack of Just Pointers?

Back to article view | Back to comp.lang.forth

Contents

  Data Stack of Just Pointers? trans <transfire@gmail.com> - 2016-11-18 10:10 -0800
    Re: Data Stack of Just Pointers? Paul Rubin <no.email@nospam.invalid> - 2016-11-18 10:45 -0800
    Re: Data Stack of Just Pointers? Rod Pemberton <NeedNotReplyHere@xrsevnneqk.cem> - 2016-11-18 20:39 -0500
      Re: Data Stack of Just Pointers? minforth@arcor.de - 2016-11-19 03:14 -0800
        Re: Data Stack of Just Pointers? hughaguilar96@gmail.com - 2016-11-19 18:26 -0800
          Re: Data Stack of Just Pointers? trans <transfire@gmail.com> - 2016-11-19 18:50 -0800
            Re: Data Stack of Just Pointers? hughaguilar96@gmail.com - 2016-11-19 19:54 -0800
        Re: Data Stack of Just Pointers? trans <transfire@gmail.com> - 2016-11-19 18:52 -0800
          Re: Data Stack of Just Pointers? minforth@arcor.de - 2016-11-21 11:46 -0800
      Re: Data Stack of Just Pointers? trans <transfire@gmail.com> - 2016-11-19 13:57 -0800
    Re: Data Stack of Just Pointers? Jan Coombs <jenfhaomndgfwutc@murmic.plus.com> - 2016-11-19 11:27 +0000
    Re: Data Stack of Just Pointers? Ron Aaron <rambamist@gmail.com> - 2016-11-19 18:05 +0200
    Re: Data Stack of Just Pointers? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-11-20 13:29 +0000
      Re: Data Stack of Just Pointers? Spiros Bousbouras <spibou@gmail.com> - 2016-11-20 15:43 +0000
      Re: Data Stack of Just Pointers? Ron Aaron <rambamist@gmail.com> - 2016-11-20 19:06 +0200
        Re: Data Stack of Just Pointers? Ron Aaron <rambamist@gmail.com> - 2016-11-21 09:09 +0200
          Re: Data Stack of Just Pointers? Paul Rubin <no.email@nospam.invalid> - 2016-11-20 23:17 -0800
            Re: Data Stack of Just Pointers? Ron Aaron <rambamist@gmail.com> - 2016-11-21 09:22 +0200
          Re: Data Stack of Just Pointers? albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) - 2016-11-21 11:12 +0100
            Re: Data Stack of Just Pointers? Ron Aaron <rambamist@gmail.com> - 2016-11-21 12:17 +0200
              Re: Data Stack of Just Pointers? Paul Rubin <no.email@nospam.invalid> - 2016-11-21 10:45 -0800
                Re: Data Stack of Just Pointers? Ron Aaron <rambamist@gmail.com> - 2016-11-21 21:22 +0200
                  Re: Data Stack of Just Pointers? Paul Rubin <no.email@nospam.invalid> - 2016-11-21 17:28 -0800
                    Re: Data Stack of Just Pointers? Ron Aaron <rambamist@gmail.com> - 2016-11-22 06:49 +0200
                      Re: Data Stack of Just Pointers? Paul Rubin <no.email@nospam.invalid> - 2016-11-21 21:13 -0800
                        Re: Data Stack of Just Pointers? franck.bensusan@gmail.com - 2016-12-21 13:48 -0800
          Re: Data Stack of Just Pointers? Cecil Bayona <cbayona@cbayona.com> - 2016-11-21 13:22 -0600
            Re: Data Stack of Just Pointers? "Robert L." <No_spamming@noWhere_7073.org> - 2016-11-22 01:53 +0000
              Re: Data Stack of Just Pointers? Cecil Bayona <cbayona@cbayona.com> - 2016-11-21 21:16 -0600
            Re: Data Stack of Just Pointers? Ron Aaron <rambamist@gmail.com> - 2016-11-22 07:01 +0200
          Re: Data Stack of Just Pointers? "Robert L." <No_spamming@noWhere_7073.org> - 2016-11-22 11:37 +0000

Page 2 of 2 — ← Prev page 1 [2]

#52790

Ron Aaron <rambamist@gmail.com> writes:
> The 2.36 was g++ -O2, that's the fastest it did.  This was relying on
> the std library, so possibly using boost etc. might be faster.

What version of gcc was that?  I got > 30+% speedup going from 4.8.3 to
6.1 (haven't tried 6.2).  I also got about 20% by changing

        string key = record.substr(0, pos2);
        string val = record.substr(pos2+1, record.length());
        retval[key] = val;

to

        retval.emplace(record.substr(0, pos2),                        
                       record.substr(pos2+1, record.length()));   

in the inner loop, which gets rid of some unnecessary string copying.
And I got a few more percent from changing std::map (which uses a
balanced tree of some sort) to std::unordered_map, which uses hashing.

gcc 6.1's C++ library doesn't seem to support C++17 string views (I
think 6.2 supports them) but using a string view for "record" should
eliminate some more small object allocation and copying.  (A string view
is a pointer to a segment of another string).

That's still pretty impressive about 8th!  I wonder if your memory
allocator is more efficient than C++'s (I remember your saying you use
mark/sweep gc).  I wonder how a stop-and-copy gc would do against either
of them.  The Boost intrusive containers (you mentioned Boost) might be
another possibility.

[toc] | [prev] | [next] | [standalone]

#52791

On 21/11/2016 20:45, Paul Rubin wrote:
> Ron Aaron <rambamist@gmail.com> writes:
>> The 2.36 was g++ -O2, that's the fastest it did.  This was relying on
>> the std library, so possibly using boost etc. might be faster.
> 
> What version of gcc was that?  I got > 30+% speedup going from 4.8.3 to
> 6.1 (haven't tried 6.2). 

It was 4.8.4.

> I also got about 20% by changing ...

Yes, I'm sure there are more than a few optimizations which could be
wrought on the C++ code.  Though I've used C++ daily for many years, I
never actually got too familiar with the std libs (every project I
worked on had their own special libs).

Thanks for the pointers (so to speak).

> That's still pretty impressive about 8th!  I wonder if your memory
> allocator is more efficient than C++'s (I remember your saying you use
> mark/sweep gc).  I wonder how a stop-and-copy gc would do against either
> of them.  The Boost intrusive containers (you mentioned Boost) might be
> another possibility.

Right; no, our GC is incremental (we do reference-counting, items are
GCed when the refcnt is 0).  On macOS and Linux we use 'tcmalloc' which
we've found to be better for our usage than the standard allocators.  We
also do "pooling" of like items so we try to eliminate a lot of small
allocations (and string allocation is quantized to try to avoid
fragmenting the heap).

[toc] | [prev] | [next] | [standalone]

#52797

Ron Aaron <rambamist@gmail.com> writes:
> Though I've used C++ daily for many years, I never actually got too
> familiar with the std libs... Thanks for the pointers (so to speak).

unordered_map is new (C++11) but could have been added earlier without
issues afaict.  .emplace, though, depends on move semantics that were
added to the language in C++11, so it couldn't have been done (at least
the same way) before that.

C++11 had a lot of significant changes compared with earlier versions.
If you're used to C++99, then "Effective Modern C++" by Scott Meyers is
worth a read.  It discusses the new stuff and why you'd want to use it.

This is also good:
https://isocpp.org/blog/2015/09/bjarne-stroustrup-announces-cpp-core-guidelines

[toc] | [prev] | [next] | [standalone]

#52802

On 22/11/2016 3:28, Paul Rubin wrote:
> Ron Aaron <rambamist@gmail.com> writes:
>> Though I've used C++ daily for many years, I never actually got too
>> familiar with the std libs... Thanks for the pointers (so to speak).
> 
> unordered_map is new (C++11) but could have been added earlier without
> issues afaict.  .emplace, though, depends on move semantics that were
> added to the language in C++11, so it couldn't have been done (at least
> the same way) before that.

I tried 'unordered_map', but it was actually slower (on macOS; didn't
try it on my Linux box yet).

I'll make a few modifications to show C++11 vs earlier versions, just
for grins.


> C++11 had a lot of significant changes compared with earlier versions.
> If you're used to C++99, then "Effective Modern C++" by Scott Meyers is
> worth a read.  It discusses the new stuff and why you'd want to use it.
> 
> This is also good:
> https://isocpp.org/blog/2015/09/bjarne-stroustrup-announces-cpp-core-guidelines

Thanks, I'll be looking at those.  I'm familiar with some of the C++11
stuff, but there were a *lot* of changes (as you said).

[toc] | [prev] | [next] | [standalone]

#52804

Ron Aaron <rambamist@gmail.com> writes:
> I tried 'unordered_map', but it was actually slower (on macOS; didn't
> try it on my Linux box yet).

I was surprised to not get a significant speedup, but I guess the map is
pretty small (the same one being built up over and over) and so the tree
is not very deep.

> I'll make a few modifications to show C++11 vs earlier versions, just
> for grins.

Cool.  I suspect mostly that your storage allocator is beating glibc's.
If I get industrious I might try using a do-nothing allocator (one that
keeps expanding storage) since the 400k iterations of that loop allocate
a GB or two tops, and my development box has enough ram to run that
test.

[toc] | [prev] | [next] | [standalone]

#53476

Le mardi 22 novembre 2016 06:13:46 UTC+1, Paul Rubin a écrit :
> Ron Aaron <rambamist@gmail.com> writes:
> > I tried 'unordered_map', but it was actually slower (on macOS; didn't
> > try it on my Linux box yet).
> 
> I was surprised to not get a significant speedup, but I guess the map is
> pretty small (the same one being built up over and over) and so the tree
> is not very deep.
> 
> > I'll make a few modifications to show C++11 vs earlier versions, just
> > for grins.
> 
> Cool.  I suspect mostly that your storage allocator is beating glibc's.
> If I get industrious I might try using a do-nothing allocator (one that
> keeps expanding storage) since the 400k iterations of that loop allocate
> a GB or two tops, and my development box has enough ram to run that
> test.

C++ performances has always been a big mystery for me.

Perhap's I don't use the right compiler (or the right version), but I have 
always found thoses performances a bit disappointing, especially when using 
the standard libraries.

On my system (Windows 10, Core i7 2,6 Ghz) 
with g++ compiler (4.6.2), this code runs in
6,5 seconds with no optimizations
4,3 seconds with -O2
Probably better performances with an higher version...

In Oforth V0.9.26, on the same system, generating a hash takes 3,5 seconds. 

"8=FIX.4.2
9=153
35=D
49=BLP
56=SCHB
34=1
50=30737
97=Y
52=20000809-20:20:50
11=90001008
1=10030003
21=2
55=TESTA
54=1
38=4000
40=2
59=0
44=30
47=I
60=20000809-18:20:32
10=061
" const: fixrec

import: collect

: dofix     \ s -- [ [ key, value ] ]
| s h | 
   Hash new ->h
   split( 0x01 ) forEach: s [ '=' s split dup first swap second h insert ] h
;

#[ 400000 #[ fixrec dofix drop ] times ] bench
3522653



If an array is generated instead of a Hash, time is 2,8 seconds

"8=FIX.4.2
9=153
35=D
49=BLP
56=SCHB
34=1
50=30737
97=Y
52=20000809-20:20:50
11=90001008
1=10030003
21=2
55=TESTA
54=1
38=4000
40=2
59=0
44=30
47=I
60=20000809-18:20:32
10=061
" const: fixrec

: dofix     \ s -- [ [ key, value ] ]
    0x01 swap split map( #[ '=' swap split ] ) ;

#[ 400000 #[ fixrec dofix drop ] times ] bench
2829273


And those versions split the string by '0x01', which creates 
intermediary substrings.
Parsing the string by manually searching '0x01' gives 2,1 seconds for a hash :  

"8=FIX.4.2
9=153
35=D
49=BLP
56=SCHB
34=1
50=30737
97=Y
52=20000809-20:20:50
11=90001008
1=10030003
21=2
55=TESTA
54=1
38=4000
40=2
59=0
44=30
47=I
60=20000809-18:20:32
10=061
" const: fixrec

import: collect

: dofix2( s -- hash )
| c h |
   Hash new ->h
   StringBuffer new
   s forEach: c [
      c  '=' if=: [ dup freeze StringBuffer new continue ]
      c 0x01 if=: [ dup freeze  h insert  StringBuffer new continue ]
      c over add
      ]
   drop h
;

#[ 400000 #[ fixrec dofix2 drop ] times ] bench
2106547


And, at last, parsing the string and creating an array of pairs instead 
of a hash gives 1,6 seconds

"8=FIX.4.2
9=153
35=D
49=BLP
56=SCHB
34=1
50=30737
97=Y
52=20000809-20:20:50
11=90001008
1=10030003
21=2
55=TESTA
54=1
38=4000
40=2
59=0
44=30
47=I
60=20000809-18:20:32
10=061
" const: fixrec

: dofix2( s -- hash )
| c a |
   32 ArrayBuffer newSize ->a
   StringBuffer new
   s forEach: c [
      c  '=' if=: [ dup freeze StringBuffer new continue ]
      c 0x01 if=: [ dup freeze Pair new a add  StringBuffer new continue ]
      c over add
      ]
   drop a
;
      
#[ 400000 #[ fixrec dofix2 drop ] times ] bench
1590844


Franck

[toc] | [prev] | [next] | [standalone]

#52792

On 11/21/2016 1:09 AM, Ron Aaron wrote:
>
>
> On 11/20/2016 19:06, Ron Aaron wrote:
>>
>>
>> On 20/11/2016 15:29, Anton Ertl wrote:
>>
>>> Given that it's a very common approach in many language
>>> implementations (e.g., Lisp, or the object part of Java), and for good
>>> reasons, it's not a stupid idea.  It has significant performance cost,
>>
>> Indeed, and yes; in particular, it makes optimizing in the manner of
>> native C compilers (for example) very difficult.
>
> Though as a curiosity, I created a C++ version of my "FIX parsing"
> benchmark using the std C++ libraries.
>
> To my surprise, 8th outperformed unoptimized C++ by quite a lot, and was
> pretty competitive even with "-O2" optimized C++ (for reference, the 8th
> version took 2.67 sec while the optimized C++ took 2.36, and unoptimized
> C++ took 4.14).
>
That is nice to see. Benchmarks unfortunately are really no clear 
indication of what software will do as they are generally don't do the 
things that user programs do but instead test certain features of a 
language.

I use to be quite a fanatic for benchmarks and squeezing every bit of 
speed from an application even when it was not necessary, one pays for 
that with longer development time. I'm older and hopefully wiser now and 
over the years I seen too many benchmarks where there was a big 
difference between two CPUs or two compilers and in the end when one 
wrote a complex application the huge difference was just not there in 
the real world. It is still a habit that is hard to control but I'm 
better at it. Instead of squeezing every millisecond out of an 
application, I now look to increase my productivity, here 8th and Forth 
like languages reign supreme.

It's good that 8th did well in that benchmark, you would not want it to 
do badly but the thing about 8th, and its parent Forth is how they help 
the programmer to get a program done. The interactivity so one can test 
modules in a bottom up approach, to easily setup the environment to test 
a module is where no matter the benchmarks they come out the winner. As 
one proceeds to create the application one is making much better 
progress having tested the modules beforehand so the application gets 
together smoothly is the huge advantage that 8th and other Forth like 
languages have over C and C++.

-- 
Cecil - k5nwa

[toc] | [prev] | [next] | [standalone]

#52798

On 11/21/2016, Cecil Bayona wrote:

> interactivity so one can test modules in a bottom up approach,

OCaml is interactive, Scheme is interactive, Racket is interactive,
Lisp is interactive, Julia is interactive, ML is interactive.

-- 
Goyim were born only to serve us....  They will work, they will plow, they will
reap. We will sit like an effendi and eat. --- Rabbi Ovadia Yosef
web.archive.org/web/20101020044210/http://www.jpost.com/JewishWorld/JewishNews/Article.aspx?id=191782
archive.org/download/DavidDuke_videos/TopRabbiExposesJewishRacism-cybsdwjezqi.ogv

[toc] | [prev] | [next] | [standalone]

#52800

On 11/21/2016 7:53 PM, Robert L. wrote:
> On 11/21/2016, Cecil Bayona wrote:
>
>> interactivity so one can test modules in a bottom up approach,
>
> OCaml is interactive, Scheme is interactive, Racket is interactive,
> Lisp is interactive, Julia is interactive, ML is interactive.
>
There are many interactive languages but for the most part they lack the 
ability to get close to the hardware like Forth can, can you write fast 
efficient device drivers with most of these languages?

-- 
Cecil - k5nwa

[toc] | [prev] | [next] | [standalone]

#52803

On 21/11/2016 21:22, Cecil Bayona wrote:

> That is nice to see. Benchmarks unfortunately are really no clear
> indication of what software will do as they are generally don't do the
> things that user programs do but instead test certain features of a
> language.

Obviously true, though the 'benchmark' I chose for this example was
something I've had to do in my "real job life", e.g. parsing FIX records
(for a low-latency financial feed).

...
> It's good that 8th did well in that benchmark, you would not want it to
> do badly but the thing about 8th, and its parent Forth is how they help
> the programmer to get a program done.

Yes, that's true.  Unlike (most) Forths, however, 8th comes with a lot
of the infrastructure code (arrays, maps, database, crypto, GUI, etc)
which makes creating real-world applications easier.

So to restate what you said, 8th's performance is secondary to many
other considerations.  Nevertheless, I keep getting asked about
performance by potential users, so it's nice to have a pleasing answer.

[toc] | [prev] | [next] | [standalone]

#52812

On 11/20/2016, Ron Aaron wrote:

> Though as a curiosity, I created a C++ version of my "FIX parsing"
> benchmark using the std C++ libraries.
> 
> To my surprise, 8th outperformed unoptimized C++ by quite a lot, and was
> pretty competitive even with "-O2" optimized C++ (for reference, the 8th
> version took 2.67 sec while the optimized C++ took 2.36, and unoptimized
> C++ took 4.14).

OCaml:


(* Compile with
ocamlopt parse_fix.ml
*)

let fixrec = "8=FIX.4.2\x019=153\x0135=D\x0149=BLP\x0156=SCHB\x0134=1\x01" ^
 "50=30737\x0197=Y\x0152=20000809-20:20:50\x0111=90001008\x011=10030003\x01" ^
 "21=2\x0155=TESTA\x0154=1\x0138=4000\x0140=2\x0159=0\x0144=30\x0147=I\x01" ^
 "60=20000809-18:20:32\x0110=061\x01"

open String

let parse_fix string =
  let result = Hashtbl.create 32 in
    let rec  loop i =
      try
        let middle = index_from string i '=' in
        let right = index_from string (middle+1) '\x01' in
          Hashtbl.add result
            (sub string i (middle - i))
            (sub string (middle+1) (right - middle - 1)) ;
          loop (right + 1)
      with Not_found | Invalid_argument _ -> ()
    in loop 0 ;
    result ;;

let start = Sys.time () in
  for _ = 1 to 400_000 do  ignore (parse_fix fixrec)  done ;
  Printf.printf "%.2f sec.\n" (Sys.time () -. start)




On an old winXP laptop the output is

1.97 sec.


-- 
Goyim were born only to serve us....  They will work, they will plow, they will
reap. We will sit like an effendi and eat. --- Rabbi Ovadia Yosef
web.archive.org/web/20101020044210/http://www.jpost.com/JewishWorld/JewishNews/Article.aspx?id=191782
archive.org/download/DavidDuke_videos/TopRabbiExposesJewishRacism-cybsdwjezqi.ogv

[toc] | [prev] | [standalone]

Page 2 of 2 — ← Prev page 1 [2]

Back to top | Article view | comp.lang.forth

csiph-web