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 1 of 2  [1] 2  Next page →

#52718 — Data Stack of Just Pointers?

Would a Forth implementation with a data stack that just contains reference pointers have really bad performance? Is that just a stupid idea?

I've been working on the design for a typed Forth language, and one idea I've had is to keep things very uniform by having the data stack just be pointers to data in the heap. I know it would effect performance so I was thinking there could also be a kind of "cache stack" to pre-fetch the data that the data stack points to. But maybe that would still be really slow, and not worth it?

[toc] | [next] | [standalone]

#52722

trans <transfire@gmail.com> writes:
> Would a Forth implementation with a data stack that just contains
> reference pointers have really bad performance? Is that just a stupid
> idea?

It's not a stupid idea but I wouldn't really think of it as being Forth.
It's basically how Lisp, Python, Ruby, and maybe 8th and Oforth work.

> I was thinking there could also be a kind of "cache stack" ... But
> maybe that would still be really slow, and not worth it?

I'd say get the simple implementation working before worrying about
optimization.  If you do the simplest possible thing there will be a big
slowdown compared to traditional Forth, but it will still be fast enough
to be useful.

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

#52725

On Fri, 18 Nov 2016 10:10:57 -0800 (PST)
trans <transfire@gmail.com> wrote:

> Would a Forth implementation with a data stack that just contains
> reference pointers have really bad performance?

Each access of an item on the stack would have an extra pointer
indirection.  This isn't much time in and of itself, but since a Forth
interpreter can execute millions of stack operations even for simple
things, this will be slower.  However, the slowness may still be within
acceptable limits.  This doesn't take into account the effect of
processor caching, which is mentioned below.

If the stack data can be of different sizes, your idea would eliminate
the need for a linked list or stack frames or contiguous memory for
the stack, but this offers no advantage in terms of executing fewer
instructions.  However, if the processor manages to store some of the
pointer stack in the processor's cache, this could be significantly
faster than linked lists or stack frames.  Having data in cache may be
fast enough that the slow-down from the extra pointer indirection is
irrelevant too.

If the stack data is of a consistent size, like for Forth, I see no
point in using pointers.


Rod Pemberton

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

#52732

> If the stack data is of a consistent size, like for Forth, I see no
> point in using pointers.
> 

A very long time ago I experimented with fixed 32 byte long unions as stack elements, so that I could also hold bignums or 32 chars as strings (Forth dictionary names among them). It ran pretty neat.

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

#52745

On Saturday, November 19, 2016 at 4:14:26 AM UTC-7, minf...@arcor.de wrote:
> > If the stack data is of a consistent size, like for Forth, I see no
> > point in using pointers.
> > 
> 
> A very long time ago I experimented with fixed 32 byte long unions as stack elements, so that I could also hold bignums or 32 chars as strings (Forth dictionary names among them). It ran pretty neat.

Well, I'm doing something similar with Straight Forth. I have an 8-byte cell. Pointers are only 4-byte however. So, I can use the cell as a struct to hold two 32-bit values. For example, an xt has a pointer to the cfa and a pointer to the parent function's local-frame (this part is zero if the xt is of a simple word rather than a quotation). Also, a string has a pointer to the string and count. A number is 64-bit with an assumed unity of 2^32.

I don't really know what bignums are for. As for strings, I have my string-stack. 

I don't think it is a good idea to have a cell size that is wider than the register size of the processor --- the modern x86 has a 64-bit register though.

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

#52746

On Saturday, November 19, 2016 at 9:26:03 PM UTC-5, hughag...@gmail.com wrote:

> Well, I'm doing something similar with Straight Forth. I have an 8-byte cell. Pointers are only 4-byte however. So, I can use the cell as a struct to hold two 32-bit values. For example, an xt has a pointer to the cfa and a pointer to the parent function's local-frame (this part is zero if the xt is of a simple word rather than a quotation). Also, a string has a pointer to the string and count. A number is 64-bit with an assumed unity of 2^32.

That's an interesting approach. So your quotations have scope?

I've been leaning toward 64-bit pointers (on 64 bit chips), even though 32-bit would suffice, just to be future proof. Eventually our computers will have multiple TBs of RAM.

> I don't really know what bignums are for. As for strings, I have my string-stack. 

Bignums are just for arbitrary precision. They can get as big as necessary (e.g. 2^100).

> I don't think it is a good idea to have a cell size that is wider than the register size of the processor --- the modern x86 has a 64-bit register though.

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

#52749

On Saturday, November 19, 2016 at 7:50:46 PM UTC-7, trans wrote:
> On Saturday, November 19, 2016 at 9:26:03 PM UTC-5, hughag...@gmail.com wrote:
> 
> > Well, I'm doing something similar with Straight Forth. I have an 8-byte cell. Pointers are only 4-byte however. So, I can use the cell as a struct to hold two 32-bit values. For example, an xt has a pointer to the cfa and a pointer to the parent function's local-frame (this part is zero if the xt is of a simple word rather than a quotation). Also, a string has a pointer to the string and count. A number is 64-bit with an assumed unity of 2^32.
> 
> That's an interesting approach. So your quotations have scope?

Quotations can only execute so long as the parent function remains in scope --- if you execute them after the parent function has exited, the system aborts with a helpful error-message.

They are mostly provided to support general-purpose data-structures. You have a HOF that traverses the data-structure and executes the quotation (it is given the xt of the quotation as a parameter by the parent function) for every node in the data-structure.

What I have here is a "fat xt" system. This doesn't have the limitations that my rquotations had (only one HOF between the parent function and the quotation, and it must have local variables of its own). So it is a more robust system. As a practical matter though, I can't think of any circumstance in which my rquotations would be inadequate.

I don't think that it is useful to have quotations continue to be executable after the parent function has exited. This is done in Scheme etc. --- they have the local variables in the heap and they have GC to get rid of the local variables eventually --- I think this is better done with OOP.

> I've been leaning toward 64-bit pointers (on 64 bit chips), even though 32-bit would suffice, just to be future proof. Eventually our computers will have multiple TBs of RAM.

Well, Straight Forth is limited to accessing 4GB of RAM (2GB for the heap which are negative pointers and 2GB for the dictionary which are positive pointers). This seems like a lot to me. You could hold a file in virtual memory. You would access it like a file, but you would pretty high speed --- that should be adequate for most applications --- I can't think of anything that needs 64-bit pointers.

I suppose games need more than 4GB of RAM --- they have a lot of graphical images --- this is a subject that I have no interest in.

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

#52747

On Saturday, November 19, 2016 at 6:14:26 AM UTC-5, minf...@arcor.de wrote:

> A very long time ago I experimented with fixed 32 byte long unions as stack elements, so that I could also hold bignums or 32 chars as strings (Forth dictionary names among them). It ran pretty neat.

That's crazy! What is that, a 256-bit stack machine? ;)

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

#52794

Am Sonntag, 20. November 2016 03:52:59 UTC+1 schrieb trans:
> On Saturday, November 19, 2016 at 6:14:26 AM UTC-5, minf...@arcor.de wrote:
> 
> > A very long time ago I experimented with fixed 32 byte long unions as stack elements, so that I could also hold bignums or 32 chars as strings (Forth dictionary names among them). It ran pretty neat.
> 
> That's crazy! What is that, a 256-bit stack machine? ;)

Actually not so crazy. We had many string "atoms" (service commands arriving over teleservice modems) which could be handled easily this way. Forth is not just for number crunching but ideal for DSLs.  ;-)

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

#52739

On Friday, November 18, 2016 at 8:38:40 PM UTC-5, Rod Pemberton wrote:
>
> Each access of an item on the stack would have an extra pointer
> indirection.  This isn't much time in and of itself, but since a Forth
> interpreter can execute millions of stack operations even for simple
> things, this will be slower.  However, the slowness may still be within
> acceptable limits.  This doesn't take into account the effect of
> processor caching, which is mentioned below.
> 
> If the stack data can be of different sizes, your idea would eliminate
> the need for a linked list or stack frames or contiguous memory for
> the stack, but this offers no advantage in terms of executing fewer
> instructions.  However, if the processor manages to store some of the
> pointer stack in the processor's cache, this could be significantly
> faster than linked lists or stack frames.  Having data in cache may be
> fast enough that the slow-down from the extra pointer indirection is
> irrelevant too.
> 
> If the stack data is of a consistent size, like for Forth, I see no
> point in using pointers.

It wouldn't be too much different from regular Forth. If I don't use a pointer-based stack then the data stack would consist of 1 byte, 2 byte, 4 byte and 8 byte cell sizes (on a 64-bit CPU) and everything else would be pointers (e.g. Array, BigInt, etc.). So that's basically the same as Forth but with two extra cell sizes. I think putting anything bigger than a CPU word on the data stack would be useless (memory management might be easier, but I don't expect that to be much of an issue in my design).

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

#52733

On Fri, 18 Nov 2016 10:10:57 -0800 (PST)
trans <transfire@gmail.com> wrote:

> Would a Forth implementation with a data stack that just
> contains reference pointers have really bad performance? Is
> that just a stupid idea?

For software implementation most likely yes.  If the indirection
is build in hardware then maybe not. 

Jan Coombs

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

#52735

On 18/11/2016 20:10, trans wrote:
> Would a Forth implementation with a data stack that just contains reference pointers have really bad performance? Is that just a stupid idea?

Not necessarily.  8th uses just this model, and the performance is decent.

> I've been working on the design for a typed Forth language, and one idea I've had is to keep things very uniform by having the data stack just be pointers to data in the heap. I know it would effect performance so I was thinking there could also be a kind of "cache stack" to pre-fetch the data that the data stack points to. But maybe that would still be really slow, and not worth it?

That's the thought process I went through designing 8th.  The stack just
contains pointers to items. 8th does do reference-counting, which pretty
much requires this model.

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

#52761

trans <transfire@gmail.com> writes:
>Would a Forth implementation with a data stack that just contains reference=
> pointers have really bad performance? Is that just a stupid idea?

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,
but despite that cost, the designers and implementors of these
languages have chosen this approach for the general case.  They then
try to reduce the cost in various common cases, with mixed success;
the cost is known as boxing and unboxing, and searching for these
terms should give you some literature on the performance effects of
this approach and how to reduce the cost.

> I was think=
>ing there could also be a kind of "cache stack" to pre-fetch the data that =
>the data stack points to.

I expect that the data on the stack is in the data cache of the CPU,
because it was accessed recently (otherwise, how does it get on the
stack); so I don't expect prefetching to help for these cases.  If you
mean something else, it's unclear what you mean.

- 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 2016: http://www.euroforth.org/ef16/

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

#52763

On Sun, 20 Nov 2016 13:29:21 GMT
anton@mips.complang.tuwien.ac.at (Anton Ertl) wrote:
> trans <transfire@gmail.com> writes:
> >Would a Forth implementation with a data stack that just contains reference
> > pointers have really bad performance? Is that just a stupid idea?
> 
> 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,
> but despite that cost, the designers and implementors of these
> languages have chosen this approach for the general case.  They then
> try to reduce the cost in various common cases, with mixed success;
> the cost is known as boxing and unboxing, and searching for these
> terms should give you some literature on the performance effects of
> this approach and how to reduce the cost.

Two such references are
blogs.janestreet.com/what-is-gained-and-lost-with-63-bit-integers
and  ocaml.org/learn/tutorials/performance_and_profiling.html
especially the part starting with
"The representation of integers, tag bits, heap-allocated values" .

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

#52767

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.

> but despite that cost, the designers and implementors of these
> languages have chosen this approach for the general case.  They then
> try to reduce the cost in various common cases, with mixed success;
> the cost is known as boxing and unboxing, and searching for these
> terms should give you some literature on the performance effects of
> this approach and how to reduce the cost.

Hmm.  I don't do boxing and unboxing in 8th (at least, not as I
understand those terms).  That's because in general, the values are not
primitives.  Case in point: numbers in 8th can be integers, floating
point, big-integers or big-floating-point.  That's convenient for the
user, not so much for me as the implementor.

> I expect that the data on the stack is in the data cache of the CPU,
> because it was accessed recently (otherwise, how does it get on the
> stack); so I don't expect prefetching to help for these cases.  If you
> mean something else, it's unclear what you mean.

The stack is mostly in the data-cache (as far as 8th goes, that is).
But the items pointed to in the stack are allocated from their
respective pools.  However, that gives some locality of reference in
many common cases, which makes the performance reasonably good.

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

#52784

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).

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

#52786

Ron Aaron <rambamist@gmail.com> writes:
> To my surprise, 8th outperformed unoptimized C++ by quite a lot

Can you post the code?

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

#52787

On 11/21/2016 09:17, Paul Rubin wrote:
> Ron Aaron <rambamist@gmail.com> writes:
>> To my surprise, 8th outperformed unoptimized C++ by quite a lot
> 
> Can you post the code?

Both the C++ and the 8th code are here:

http://8th-dev.com/forum/index.php?topic=1093.msg5965#msg5965

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

#52788

In article <o0u6jf$ppr$1@dont-email.me>,
Ron Aaron  <rambamist@gmail.com> 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).

I presume that some form of optimisation was done in 8th?
What was the fastest C++ could do?

Groetjes Albert
-- 
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst

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

#52789

On 11/21/2016 12:12, Albert van der Horst wrote:

> I presume that some form of optimisation was done in 8th?
> What was the fastest C++ could do?

The 8th code was just simple code, nothing optimized.

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.

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

Page 1 of 2  [1] 2  Next page →

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

csiph-web