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

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

Compiled Forth

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

Contents

  Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-04 12:02 -0700
    Re: Compiled Forth "Elizabeth D. Rather" <erather@forth.com> - 2015-04-04 14:43 -1000
      Re: Compiled Forth hughaguilar96@gmail.com - 2015-04-04 18:16 -0700
        Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-05 10:58 -0700
      Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-05 10:52 -0700
        Re: Compiled Forth anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-04-06 15:35 +0000
          Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-06 08:51 -0700
            Re: Compiled Forth mhx@iae.nl - 2015-04-06 15:32 -0700
              Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-06 16:28 -0700
                Re: Compiled Forth mhx@iae.nl - 2015-04-08 13:58 -0700
                  Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-08 14:41 -0700
                    Re: Compiled Forth "Elizabeth D. Rather" <erather@forth.com> - 2015-04-08 14:01 -1000
                      Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-09 00:06 -0700
                      Re: Compiled Forth albert@spenarnc.xs4all.nl (Albert van der Horst) - 2015-04-10 16:48 +0000
                        Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-10 10:23 -0700
                          Re: Compiled Forth albert@spenarnc.xs4all.nl (Albert van der Horst) - 2015-04-10 18:04 +0000
                  Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-09 10:31 -0700
                    Re: Compiled Forth albert@spenarnc.xs4all.nl (Albert van der Horst) - 2015-04-09 17:57 +0000
                      Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-09 11:06 -0700
                      Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-22 09:17 -0700
          Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-06 09:01 -0700
    Re: Compiled Forth anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-04-05 09:32 +0000
      Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-05 11:02 -0700
        Re: Compiled Forth "HAA" <someone@microsoft.com> - 2015-04-06 18:35 +1000
    Re: Compiled Forth albert@spenarnc.xs4all.nl (Albert van der Horst) - 2015-04-05 09:52 +0000
      Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-05 11:20 -0700
      Re: Compiled Forth Paul Rubin <no.email@nospam.invalid> - 2015-04-05 11:57 -0700
        Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-05 12:05 -0700
          Re: Compiled Forth Paul Rubin <no.email@nospam.invalid> - 2015-04-05 12:47 -0700
            Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-05 13:36 -0700
              Re: Compiled Forth Paul Rubin <no.email@nospam.invalid> - 2015-04-05 13:57 -0700
                Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-05 14:37 -0700
                  Re: Compiled Forth Paul Rubin <no.email@nospam.invalid> - 2015-04-05 15:10 -0700
                    Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-05 15:23 -0700
        Re: Compiled Forth Ron Aaron <rambamist@gmail.com> - 2015-04-06 08:52 +0300
          Re: Compiled Forth Paul Rubin <no.email@nospam.invalid> - 2015-04-05 23:09 -0700
            Re: Compiled Forth Ron Aaron <rambamist@gmail.com> - 2015-04-06 10:12 +0300
            Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-06 00:15 -0700
              Re: Compiled Forth Paul Rubin <no.email@nospam.invalid> - 2015-04-06 01:05 -0700
                Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-06 01:27 -0700
              Re: Compiled Forth anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-04-06 12:20 +0000
            Re: Compiled Forth anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-04-06 12:10 +0000
              Re: Compiled Forth Paul Rubin <no.email@nospam.invalid> - 2015-04-06 11:45 -0700
                Re: Compiled Forth Melzzzzz <mel@zzzzz.com> - 2015-04-06 21:16 +0200
                  Re: Compiled Forth Paul Rubin <no.email@nospam.invalid> - 2015-04-06 12:55 -0700
          Re: Compiled Forth Jan Coombs <Jan-54 <jenfhaomndgfwutc@murmic.plus.com>> - 2015-04-06 09:01 +0100
            Re: Compiled Forth Ron Aaron <rambamist@gmail.com> - 2015-04-06 11:27 +0300
        Re: Compiled Forth Jan Coombs <Jan-54 <jenfhaomndgfwutc@murmic.plus.com>> - 2015-04-06 08:06 +0100
        Re: Compiled Forth albert@spenarnc.xs4all.nl (Albert van der Horst) - 2015-04-06 14:15 +0000
    Re: Compiled Forth stephen@mpeforth.com (Stephen Pelc) - 2015-04-06 11:32 +0000
    Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-06 08:01 -0700
      Re: Compiled Forth Paul Rubin <no.email@nospam.invalid> - 2015-04-06 12:04 -0700
        Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-06 12:58 -0700
          Re: Compiled Forth Paul Rubin <no.email@nospam.invalid> - 2015-04-06 13:29 -0700
            Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-06 16:44 -0700
              Re: Compiled Forth Paul Rubin <no.email@nospam.invalid> - 2015-04-06 19:59 -0700
                Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-07 01:31 -0700
                  Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-07 01:36 -0700
                  Re: Compiled Forth Jan Coombs <Jan-54 <jenfhaomndgfwutc@murmic.plus.com>> - 2015-04-07 12:00 +0100
                    Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-07 04:25 -0700
                      Proposal for ALLOCATEd bignum's Re: Compiled Forth albert@spenarnc.xs4all.nl (Albert van der Horst) - 2015-04-07 12:41 +0000
                      Re: Compiled Forth Paul Rubin <no.email@nospam.invalid> - 2015-04-08 21:40 -0700
                        Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-09 00:18 -0700
                  Re: Compiled Forth Paul Rubin <no.email@nospam.invalid> - 2015-04-09 23:43 -0700
                    Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-10 04:07 -0700
                      Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-10 04:37 -0700
                    Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-10 04:45 -0700
                      Re: Compiled Forth albert@spenarnc.xs4all.nl (Albert van der Horst) - 2015-04-10 12:02 +0000
                        Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-10 07:21 -0700
                          Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-10 07:53 -0700
                            Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-10 09:43 -0700
                            Re: Compiled Forth albert@spenarnc.xs4all.nl (Albert van der Horst) - 2015-04-10 16:43 +0000
                              Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-10 11:03 -0700
                                Re: Compiled Forth albert@spenarnc.xs4all.nl (Albert van der Horst) - 2015-04-10 18:26 +0000
                                Re: Compiled Forth mhx@iae.nl - 2015-04-10 11:27 -0700
                                  Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-10 11:36 -0700
                                    Re: Compiled Forth mhx@iae.nl - 2015-04-10 11:56 -0700
                                    Re: Compiled Forth Paul Rubin <no.email@nospam.invalid> - 2015-04-10 12:20 -0700
                                      Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-10 13:00 -0700
                                        Re: Compiled Forth Paul Rubin <no.email@nospam.invalid> - 2015-04-10 13:14 -0700
                                          Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-10 13:29 -0700
                                            Re: Compiled Forth Paul Rubin <no.email@nospam.invalid> - 2015-04-10 16:08 -0700
                                              Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-10 23:08 -0700
                                        Re: Compiled Forth mhx@iae.nl - 2015-04-11 01:59 -0700
                                          Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-11 02:20 -0700
                                          Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-11 02:44 -0700
                                            Re: Compiled Forth mhx@iae.nl - 2015-04-11 11:21 -0700
                                        Re: Compiled Forth Paul Rubin <no.email@nospam.invalid> - 2015-04-11 11:43 -0700
                                          Re: Compiled Forth albert@spenarnc.xs4all.nl (Albert van der Horst) - 2015-04-11 19:44 +0000
                                            Re: Compiled Forth Paul Rubin <no.email@nospam.invalid> - 2015-04-11 12:51 -0700
                                              Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-11 15:26 -0700
                    Re: Compiled Forth lehs <skydda.barnen@gmail.com> - 2015-04-10 04:50 -0700

Page 3 of 5 — ← Prev page 1 2 [3] 4 5  Next page →

#38007

lehs <skydda.barnen@gmail.com> writes:
>Why don't use "typed stacks", special stacks for references that replaces parameter stacks and local variables for bignums? So that every ref to a bignum must be stored in a bignum stack.

That is certainly something some string packages have used.  However,
both bignums and strings do not just live on stacks, you also want to
store them in variables or data structures, and you also need an
answer for 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 2014: http://www.euroforth.org/ef14/

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

#38006

Paul Rubin <no.email@nospam.invalid> writes:
>Ron Aaron <rambamist@gmail.com> writes:
>>>> ciforth has a small ALLOCATE
>>> I don't see a reasonable way to do this without garbage collection.
>>> How are you going to free the bignums?
>> That's why 8th uses reference-counted GC.  Items (strings, numbers,
>> etc) are allocated from pools of that kind of item....
>
>Ok, but that is basically Lisp in the sense that you can know the type
>of every object at runtime.  I don't see how to do integrated bignums
>sanely with reference counting in a regular Forth which uses untyped
>data and pointers everywhere, and whose low level interpreter has words
>like DUP or DROP which do a few simple machine instructions and would
>take a speed and complexity hit if they also messed with ref counts.

The Forth way to do this is, of course, to have typed operations.  B@
B! BDUP BDROP etc.  Reference counting is relatively easy for data
types that don't contain pointers, such as bignums or strings.  The
main disadvantage is that you have to deal with all references to
bignums using these words.  E.g., no bulk copying or erasing of memory
that may contain such references.  Another disadvantage is that it
costs some overhead.

Reference counting has not caught on in Forth yet.  Not sure if this
is due to the disadvantages, or because most Forthers prefer
lower-level storage management anyway.

- 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 2014: http://www.euroforth.org/ef14/

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

#38016

anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
> have typed operations.  B@ B! BDUP BDROP etc.  ...  The main
> disadvantage is that you have to deal with all references to bignums
> using these words.  E.g., no bulk copying or erasing of memory that
> may contain such references.

What happens if you want to allocate an object that contains bignums,
strings, and other stuff, and free it later?  Would you use something
like OOP with destructors that you'd have to set up to decrement the
refcounted variables?

> Reference counting has not caught on in Forth yet.  Not sure if this
> is due to the disadvantages, or because most Forthers prefer
> lower-level storage management anyway.

Is anyone using your gc?  Tracing seems preferable to refcounts in most
ways I can think of.

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

#38018

On Mon, 06 Apr 2015 11:45:42 -0700
Paul Rubin <no.email@nospam.invalid> wrote:

> anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
> > have typed operations.  B@ B! BDUP BDROP etc.  ...  The main
> > disadvantage is that you have to deal with all references to bignums
> > using these words.  E.g., no bulk copying or erasing of memory that
> > may contain such references.
> 
> What happens if you want to allocate an object that contains bignums,
> strings, and other stuff, and free it later?  Would you use something
> like OOP with destructors that you'd have to set up to decrement the
> refcounted variables?
> 
> > Reference counting has not caught on in Forth yet.  Not sure if this
> > is due to the disadvantages, or because most Forthers prefer
> > lower-level storage management anyway.
> 
> Is anyone using your gc?  Tracing seems preferable to refcounts in
> most ways I can think of.

Except that tracing is awfully slow when using large container
with data structure that has pointers.
This is large problem with every GC-ed language. 

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

#38019

Melzzzzz <mel@zzzzz.com> writes:
> Except that tracing is awfully slow when using large container
> with data structure that has pointers.

Something similar happens with refcounting if you free a structure
containing a lot of refcounted objects.  Is there better than a constant
factor difference between them?

> This is large problem with every GC-ed language. 

Generational gc apparently can get the cpu time overhead of gc to be
quite small, at the cost of using extra memory.  And there are real-time
gc schemes that can bound the maximum pause time, at the cost of higher
amortized overhead.  I guess if you're only refcounting large objects
like bignums, and they're on a separate stack, the overhead of adjusting
the refcounts on every DUP or DROP might not be too bad compared to
full-width arithmetic.  

I've implemented one interpreter (not for Forth) with refcounts and
another with tracing, and generally found that maintaining the refcounts
everywhere was tedious and seemed bug-prone.  CPython also uses them and
gets some ugliness from them.  The main benefit people keep mentioning
is deterministic release time.  I'm not sure how big a deal that is.

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

#37997

On Mon, 06 Apr 2015 08:52:48 +0300
Ron Aaron <rambamist@gmail.com> wrote:

> On 4/5/15 21:57, Paul Rubin wrote:
>
> > albert@spenarnc.xs4all.nl (Albert van der Horst) writes:
> > > By the way, I would be interested to have your bignums integrated
> > > in ciforth. That would mean replacing the lowest layer with
> > > transparant allocation ... ciforth has a small ALLOCATE
> >
> > I don't see a reasonable way to do this without garbage collection.
> > How are you going to free the bignums?
> 
> That's why 8th uses reference-counted GC.  Items (strings, numbers, etc) 
> are allocated from pools of that kind of item.  When an item's reference 
> count returns to 0, it is cleaned-up (deallocated, resources released, 
> etc).  The items inside the pools themselves are not deallocated until 
> the program quits, though.

In Python (2.x), stack items are all object pointers, but the objects 
are small, containing only the ref count and a pointer to the data. 
Because of the extra level of indirection the ref counts are bunched, 
and likely to get a cache hit.  Ref count adjustment is only needed 
for stack operations like DUP or DROP which create or remove data refs. 

Also, as in 8th, Python pools the data for small objects, so accessing 
integers is also likely to get a cache hit.  Not sure how much this 
might apply to bignums. 

In a hardware stack engine, with tagged bignum data, the object 
reference count maintenance would be automatic.  Also, the tagging 
would allow bignums to be natural stack items, and remove the need 
for indirection and garbage management for these. 

Although having more data types as objects has a clear cost, this 
can be minimised in both soft and hard bignum implementations. 

Jan Coombs
-- 
email valid, else fix dots and hyphen
jan4clf2014@murrayhyphenmicroftdotcodotuk

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

#38000

On 4/6/15 11:01, Jan Coombs <Jan-54 wrote:
> On Mon, 06 Apr 2015 08:52:48 +0300

> In Python (2.x), stack items are all object pointers, but the objects
> are small, containing only the ref count and a pointer to the data.
> Because of the extra level of indirection the ref counts are bunched,
> and likely to get a cache hit.  Ref count adjustment is only needed
> for stack operations like DUP or DROP which create or remove data refs.

Right.  So in 8th the objects are in the pool, so there is only one 
level of indirection.  But thus they may not get a cache hit.  However, 
I wanted to avoid extra memory allocations; I suppose a 
double-allocation could work just as nicely, but not sure if it would 
make a big difference in practice.  I may try it on an experimental 
branch, as one of my lesser goals is to improve performance.

> Also, as in 8th, Python pools the data for small objects, so accessing
> integers is also likely to get a cache hit.  Not sure how much this
> might apply to bignums.

Good question.  Depends on the bignum engine they use.

>
> In a hardware stack engine, with tagged bignum data, the object
> reference count maintenance would be automatic.  Also, the tagging
> would allow bignums to be natural stack items, and remove the need
> for indirection and garbage management for these.

That's interesting.  Though not too helpful for 8th, as its targets are 
the standard commercial OS platforms on commodity hardware.

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

#37993

On Sun, 05 Apr 2015 11:57:47 -0700
Paul Rubin <no.email@nospam.invalid> wrote:

> albert@spenarnc.xs4all.nl (Albert van der Horst) writes:
> > By the way, I would be interested to have your bignums integrated
> > in ciforth. That would mean replacing the lowest layer with
> > transparant allocation ... ciforth has a small ALLOCATE
> 
> I don't see a reasonable way to do this without garbage collection.
> How are you going to free the bignums?

If you are happy with just simple stack manipulation, then 
only the top three stack items need to be cached.  The rest 
can be pushed onto a stack.  I do this in hardware.

If the bignum stack cache size is limited, then both this 
and the total stack size impose a limit on the maximum size 
of bignum that can be handled. 

Jan Coombs
-- 
email valid, else fix dots and hyphen
jan4clf2014@murrayhyphenmicroftdotcodotuk

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

#38008

In article <87y4m64d3o.fsf@jester.gateway.sonic.net>,
Paul Rubin  <no.email@nospam.invalid> wrote:
>albert@spenarnc.xs4all.nl (Albert van der Horst) writes:
>> By the way, I would be interested to have your bignums integrated
>> in ciforth. That would mean replacing the lowest layer with
>> transparant allocation ... ciforth has a small ALLOCATE
>
>I don't see a reasonable way to do this without garbage collection.
>How are you going to free the bignums?

Of course there is garbage collection.

My idea is as follows:
   let's coin great numbers, they are handles
   great numbers may reside on the return stack, on the stack,
     or in GVARIABLE's or fields in structs that are build using
     BUILD-G  (those are linked among themselves).

With this convention, the usual Forth discipline and a dedicated
ALLOCATE it is easy to find out which numbers can be free-ed. My
ALLOCATE could be made to do this in a number of ways:
   1 just load an instance of the ALLOCATE package separately for
       great numbers (easiest).
   2 make the ALLOCATE use a separate area from regular allocations
       within the normal allocation area.
   3 turn it into an allocation class, with more instances
   4 adorn the ALLOCATE with an extra link, to separate the great
     numbers from other allocations

Setting aside a part of the heap for great numbers looks the most
promising for the ALLOCATE I have in ciforth. This could be
repartitioned.

(If your ALLOCATE is based on malloc/free from a c-library you're
out of luck probably.)

Option 3 is just the political correct way to do 1.
Option 4 is safest, but I count that I end up with 4 cells overhead
for each great constant, plus an extra header and a cell for
great variables.

Bottom line. Probably I'm just going to use an ALLOCATE that is
integrated in the great number package. Not much different from the
dedicated area lehs uses.

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]

#38004

On Sat, 4 Apr 2015 12:02:42 -0700 (PDT), lehs
<skydda.barnen@gmail.com> wrote:

>I'm using an old laptop with a simple Celeron processor and SP-Forth from t=
>he Russian Forth Interest Group. In SP-Forth there are words SET-OPT and DI=
>S-OPT that optionally compile the Forth code to machine code. Using this op=
>timization method the code normally become 20 times faster.=20
>
>I wonder, is this normal for a processor like mine? It's a rather big gap i=
>n my opinion...

You'll have to show the benchmark source code for us to comment.

On modern CPUs, a typical ratio between ITC code and native code
compilers is about 12:1. The MPE web site contains a downloadable
file called benchmrk.fth which contains a range of compiler
benchmarks.

Stephen

-- 
Stephen Pelc, stephenXXX@mpeforth.com
MicroProcessor Engineering Ltd - More Real, Less Time
133 Hill Lane, Southampton SO15 5AF, England
tel: +44 (0)23 8063 1441, fax: +44 (0)23 8033 9691
web: http://www.mpeforth.com - free VFX Forth downloads

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

#38011

I have been thinking, is it really that good to use references to bignum on the parameter stack? Of course it's faster to execute OVER than a BOVER which makes CMOVE of about 10 to 100 bytes, but what after that word it will typically follow a word that change the top value, say B1+, and then a new copy must be created and the OVER was utterly useless as such.

I'm not so sure that my "pure Forth" way of bignum is remarkably slower than other implementations. 

On http://wrap.warwick.ac.uk/54707/1/WRAP_Hart_S1446788712000146a.pdf (20119 a simple factorization routine OLF is presented with: 

"n = nextprime(10ˆ29+5342347)*nextprime(10ˆ31+2232788)OLF(n) which will instantly produce the factors of n"

and also my old Celeron with my bignum make this calculation instantly.

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

#38017

lehs <skydda.barnen@gmail.com> writes:
> Of course it's faster to execute OVER than a BOVER which makes CMOVE
> of about 10 to 100 bytes,

Even further, in cryptography one often uses 2k or 4k bit numbers,
i.e. 256 or 512 bytes.  If you do a modular multiplication the naive way
you also deal with intermediate results 2x as large as that.

> but what after that word it will typically follow a word that change
> the top value, say B1+, and then a new copy must be created and the
> OVER was utterly useless as such.

You mean a B1+ that does an in-place destructive increment?  Seems
like an optimization of limited value.
>
> On http://wrap.warwick.ac.uk/54707/1/WRAP_Hart_S1446788712000146a.pdf

Looks interesting and I'll try to examine it more later.  

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

#38020

Den måndag 6 april 2015 kl. 21:05:04 UTC+2 skrev Paul Rubin:
> lehs <skydda.barnen@gmail.com> writes:
> > Of course it's faster to execute OVER than a BOVER which makes CMOVE
> > of about 10 to 100 bytes,
> 
> Even further, in cryptography one often uses 2k or 4k bit numbers,
> i.e. 256 or 512 bytes.  If you do a modular multiplication the naive way
> you also deal with intermediate results 2x as large as that.
> 
> > but what after that word it will typically follow a word that change
> > the top value, say B1+, and then a new copy must be created and the
> > OVER was utterly useless as such.
> 
> You mean a B1+ that does an in-place destructive increment?  Seems
> like an optimization of limited value.
> >
> > On http://wrap.warwick.ac.uk/54707/1/WRAP_Hart_S1446788712000146a.pdf
> 
> Looks interesting and I'll try to examine it more later.

I was trying to visualize that it perhaps is better to use big-number stacks instead of references to big-number. Since a stack manipulation normally is followed by a arithmetic manipulation, when a new allocation is needed and data must be moved to that area anyway. BOVER does that in the first place.

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

#38022

lehs <skydda.barnen@gmail.com> writes:
> Since a stack manipulation normally is followed by a arithmetic
> manipulation, when a new allocation is needed and data must be moved
> to that area anyway. BOVER does that in the first place.

I wonder to what extent the running time of typical bignum calculations
are dominated by multiplication and division, since they are usually
implemented with quadratic-time algorithms.  Multiplication also
produces a result that uses more memory than its operands, so you can't
do it in place.  For addition/subtraction, you may have to reallocate if
the result overflows the highest cell, but that's infrequent.

Idioms like   ( a b ) 2DUP > IF something THEN 
would be pretty wasteful though, if they are actually copying the
bignums just to compare them and drop them.

Maybe you are on to something though, at least for modest size numbers,
up to a few kilobits (enough for cryptography).

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

#38026

Den måndag 6 april 2015 kl. 22:29:22 UTC+2 skrev Paul Rubin:
> lehs <skydda.barnen@gmail.com> writes:
> > Since a stack manipulation normally is followed by a arithmetic
> > manipulation, when a new allocation is needed and data must be moved
> > to that area anyway. BOVER does that in the first place.
> 
> I wonder to what extent the running time of typical bignum calculations
> are dominated by multiplication and division, since they are usually
> implemented with quadratic-time algorithms.  Multiplication also
> produces a result that uses more memory than its operands, so you can't
> do it in place.  For addition/subtraction, you may have to reallocate if
> the result overflows the highest cell, but that's infrequent.
> 
> Idioms like   ( a b ) 2DUP > IF something THEN 
> would be pretty wasteful though, if they are actually copying the
> bignums just to compare them and drop them.
> 
> Maybe you are on to something though, at least for modest size numbers,
> up to a few kilobits (enough for cryptography).

It works like this: in highmem in a big buffer there is a stack with references to bignum-data in a stack in lowmem. There is no explicit limit for a number, the buffer is the limit. The top of the reference stack refers to the bignumber at the top of the big-num-data stack, where all results are built up and can grow towards highmem. So there is no need for reallocating. 

Words like B= doesn't change the stack so the values can be reused.

There are better algorithms for B* and B/MOD (probably all the idioms can be enhanced) but I'm testing the system first. When I have fixed some bugs I will try to make it work on SwiftForth and might learn something from that. After that I will extend the documentation.

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

#38032

lehs <skydda.barnen@gmail.com> writes:
> It works like this: in highmem in a big buffer there is a stack with
> references to bignum-data in a stack in lowmem.

How do you implement bignum variables?  What if you want an array of
them?  With regular numbers I often say:

    : make-array ( n "name" ) CREATE cells allot  compiled
    DOES> ( n addr -- addr ) swap cells + ;

to make a simple array that can be accessed with @ and !

> Words like B= doesn't change the stack so the values can be reused.

That's different from the usual = operation in Forth and could get
confusing.

> There are better algorithms for B* and B/MOD (probably all the idioms
> can be enhanced) but I'm testing the system first. 

Sure, that's reasonable.  

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

#38037

Den tisdag 7 april 2015 kl. 04:59:15 UTC+2 skrev Paul Rubin:
> lehs <skydda.barnen@gmail.com> writes:
> > It works like this: in highmem in a big buffer there is a stack with
> > references to bignum-data in a stack in lowmem.
> 
> How do you implement bignum variables?  What if you want an array of
> them?  With regular numbers I often say:
> 
>     : make-array ( n "name" ) CREATE cells allot  compiled
>     DOES> ( n addr -- addr ) swap cells + ;
> 
> to make a simple array that can be accessed with @ and !
> 
> > Words like B= doesn't change the stack so the values can be reused.
> 
> That's different from the usual = operation in Forth and could get
> confusing.
> 
> > There are better algorithms for B* and B/MOD (probably all the idioms
> > can be enhanced) but I'm testing the system first. 
> 
> Sure, that's reasonable.

I use two stacks for big numbers because it makes programming easier and because I haven't any acceptable solution to global arrays. Instead of a global variable it's possible to pre-load bignumbers in the X-stack were the rapidly can be read and changed by their address in the X-stack.

My goal is to make a simple and efficient system, as much as possible in Forth-style. I think some minor deviations from the norm is necessary, like B= and B. BDROP is just a change of references, but BOVER BOVER (to make temporary copies to be eaten by a comparison routine) does two CMOVE.

The word

: BSQRT \ w -- v        \ not included yet
  B0= IF BDROP BZERO EXIT THEN        \ B0= is much faster than B= and B<
  BLOG~ 2/              \ BLOG~ gives the number of binary digits
  BONE BLEFT 10 0       \ bone = 1; put a start value bigger than v on the stack
  DO BOVER BOVER B/ B=  \ put flag on parameter stack
     B+ B2/
     IF LEAVE THEN      \ read the flag
  LOOP BNIP ;

shows that programming in bigforth differs a little from normal.

Programming bignum is more difficult, there is an absolute need of adequate algorithms and one have to be aware of the different speed of different words.

The word B**MOD ( a b c -- a^b[mod c] ) is fast:

B 80247824076802476804276248067204876240876024876280476024876420867420867420687
B 7962597629562495642756767746579264926597426592465924765972465924569274659
B 16357961957638769631974563151376597136591375613975613 B**MOD

instantly (with my system in 4/100 second) gives 

6639276191969705355236646500004312964523609080804143

but misused in a loop it could be a disaster.

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

#38038

Den tisdag 7 april 2015 kl. 10:31:12 UTC+2 skrev lehs:
> Den tisdag 7 april 2015 kl. 04:59:15 UTC+2 skrev Paul Rubin:
> > lehs <skydda.barnen@gmail.com> writes:
> > > It works like this: in highmem in a big buffer there is a stack with
> > > references to bignum-data in a stack in lowmem.
> > 
> > How do you implement bignum variables?  What if you want an array of
> > them?  With regular numbers I often say:
> > 
> >     : make-array ( n "name" ) CREATE cells allot  compiled
> >     DOES> ( n addr -- addr ) swap cells + ;
> > 
> > to make a simple array that can be accessed with @ and !
> > 
> > > Words like B= doesn't change the stack so the values can be reused.
> > 
> > That's different from the usual = operation in Forth and could get
> > confusing.
> > 
> > > There are better algorithms for B* and B/MOD (probably all the idioms
> > > can be enhanced) but I'm testing the system first. 
> > 
> > Sure, that's reasonable.
> 
> I use two stacks for big numbers because it makes programming easier and because I haven't any acceptable solution to global arrays. Instead of a global variable it's possible to pre-load bignumbers in the X-stack were the rapidly can be read and changed by their address in the X-stack.
> 
> My goal is to make a simple and efficient system, as much as possible in Forth-style. I think some minor deviations from the norm is necessary, like B= and B. BDROP is just a change of references, but BOVER BOVER (to make temporary copies to be eaten by a comparison routine) does two CMOVE.
> 
> The word
> 
> : BSQRT \ w -- v        \ not included yet
>   B0= IF BDROP BZERO EXIT THEN        \ B0= is much faster than B= and B<
>   BLOG~ 2/              \ BLOG~ gives the number of binary digits
>   BONE BLEFT 10 0       \ bone = 1; put a start value bigger than v on the stack
>   DO BOVER BOVER B/ B=  \ put flag on parameter stack
>      B+ B2/
>      IF LEAVE THEN      \ read the flag
>   LOOP BNIP ;
> 
> shows that programming in bigforth differs a little from normal.
> 
> Programming bignum is more difficult, there is an absolute need of adequate algorithms and one have to be aware of the different speed of different words.
> 
> The word B**MOD ( a b c -- a^b[mod c] ) is fast:
> 
> B 80247824076802476804276248067204876240876024876280476024876420867420867420687
> B 7962597629562495642756767746579264926597426592465924765972465924569274659
> B 16357961957638769631974563151376597136591375613975613 B**MOD
> 
> instantly (with my system in 4/100 second) gives 
> 
> 6639276191969705355236646500004312964523609080804143
> 
> but misused in a loop it could be a disaster.

Of course it shouldn't be

B0= IF BDROP BZERO EXIT THEN

but 

B0= IF EXIT THEN

in the BSQRT routine above.

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

#38039

On Tue, 7 Apr 2015 01:31:11 -0700 (PDT)
lehs <skydda.barnen@gmail.com> wrote:

> My goal is to make a simple and efficient system, as much 
> as possible in Forth-style. I think some minor deviations 
> from the norm is necessary, like B= and B. BDROP is just 
> a change of references, but BOVER BOVER (to make temporary 
> copies to be eaten by a comparison routine) does two CMOVE.

With some extra tagging you can just copy the pointer to do 
BOVER.  The tag (reference count +?) lets you know when the 
bignum storage is free, and warns you to not over-write it 
if it has more than one reference. 

Interesingly, increment-in-place should work for loop counters 
where the loop termination detection is sign change, because 
the number size is only reducing. 

If you really need  B= ( b1 b2 -- b1 b2 flag ) then, to keep 
sympathy, call it 2DUP_B= or something similar. 

If you do just copy pointers, and manage data refs, then the
code

  B2DUP B= 

is quick to execute, no data copying, and looks standard. 

Jan Coombs. 
-- 
email valid, else fix dots and hyphen
jan4clf2014@murrayhyphenmicroftdotcodotuk

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

#38041

Den tisdag 7 april 2015 kl. 13:00:23 UTC+2 skrev Jan Coombs:
> On Tue, 7 Apr 2015 01:31:11 -0700 (PDT)
> lehs <skydda.barnen@gmail.com> wrote:
> 
> > My goal is to make a simple and efficient system, as much 
> > as possible in Forth-style. I think some minor deviations 
> > from the norm is necessary, like B= and B. BDROP is just 
> > a change of references, but BOVER BOVER (to make temporary 
> > copies to be eaten by a comparison routine) does two CMOVE.
> 
> With some extra tagging you can just copy the pointer to do 
> BOVER.  The tag (reference count +?) lets you know when the 
> bignum storage is free, and warns you to not over-write it 
> if it has more than one reference. 
> 
> Interesingly, increment-in-place should work for loop counters 
> where the loop termination detection is sign change, because 
> the number size is only reducing. 
> 
> If you really need  B= ( b1 b2 -- b1 b2 flag ) then, to keep 
> sympathy, call it 2DUP_B= or something similar. 
> 
> If you do just copy pointers, and manage data refs, then the
> code
> 
>   B2DUP B= 
> 
> is quick to execute, no data copying, and looks standard. 
> 
> Jan Coombs. 
> -- 
> email valid, else fix dots and hyphen
> jan4clf2014@murrayhyphenmicroftdotcodotuk

Yes, you are right, I should point out when comparing don't eat numbers somehow,  perhaps B|= or B^=

Since I do believe that copying isn't that bad I will finish what I'm doing and then perhaps try to make a fourth reorganization with pointers and GC - and compare.

To make it possible to write faster code when needed, I will try to make some words that acts on given addresses, as a complement.

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

Page 3 of 5 — ← Prev page 1 2 [3] 4 5  Next page →

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

csiph-web