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

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

Appending definition to another definition

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

Contents

  Appending definition to another definition programmingkidx@gmail.com - 2012-07-29 11:28 -0700
    Re: Appending definition to another definition Jason Damisch <jasondamisch@yahoo.com> - 2012-07-29 11:39 -0700
      Re: Appending definition to another definition teammember0x01@gmail.com - 2012-07-29 12:16 -0700
        Re: Appending definition to another definition Jason Damisch <jasondamisch@yahoo.com> - 2012-07-29 12:24 -0700
          Re: Appending definition to another definition programmingkidx@gmail.com - 2012-07-29 13:41 -0700
            Re: Appending definition to another definition Jason Damisch <jasondamisch@yahoo.com> - 2012-07-29 13:46 -0700
              Re: Appending definition to another definition programmingkidx@gmail.com - 2012-07-29 14:00 -0700
                Re: Appending definition to another definition Jason Damisch <jasondamisch@yahoo.com> - 2012-07-29 14:03 -0700
                Re: Appending definition to another definition Paul Rubin <no.email@nospam.invalid> - 2012-07-29 14:21 -0700
                Re: Appending definition to another definition "Elizabeth D. Rather" <erather@forth.com> - 2012-07-30 12:43 -0500
                Re: Appending definition to another definition rickman <gnuarm@gmail.com> - 2012-07-31 02:07 -0700
        Re: Appending definition to another definition Mark Wills <markrobertwills@yahoo.co.uk> - 2012-07-30 01:13 -0700
          Re: Appending definition to another definition Hugh Aguilar <hughaguilar96@yahoo.com> - 2012-07-31 00:42 -0700
            Re: Appending definition to another definition Mark Wills <markrobertwills@yahoo.co.uk> - 2012-07-31 01:05 -0700
              Re: Appending definition to another definition Hugh Aguilar <hughaguilar96@yahoo.com> - 2012-07-31 01:55 -0700
                Re: Appending definition to another definition George Hubert <georgeahubert@yahoo.co.uk> - 2012-07-31 09:55 -0700
                  Re: Appending definition to another definition Andrew Haley <andrew29@littlepinkcloud.invalid> - 2012-07-31 12:38 -0500
                    Re: Appending definition to another definition George Hubert <georgeahubert@yahoo.co.uk> - 2012-07-31 13:20 -0700
                      Re: Appending definition to another definition Andrew Haley <andrew29@littlepinkcloud.invalid> - 2012-08-01 04:34 -0500
                        Re: Appending definition to another definition hughaguilar96@yahoo.com - 2012-08-01 03:27 -0700
                          Re: Appending definition to another definition Coos Haak <chforth@hccnet.nl> - 2012-08-01 15:45 +0200
                            Re: Appending definition to another definition Paul Rubin <no.email@nospam.invalid> - 2012-08-01 07:01 -0700
                              Re: Appending definition to another definition Jason Damisch <jasondamisch@yahoo.com> - 2012-08-01 08:02 -0700
                                Re: Appending definition to another definition Mark Wills <markrobertwills@yahoo.co.uk> - 2012-08-01 08:07 -0700
                                  Re: Appending definition to another definition jim@rainbarrel.com - 2012-08-01 14:06 -0700
                            Re: Appending definition to another definition hughaguilar96@yahoo.com - 2012-08-01 16:59 -0700
                      Re: Appending definition to another definition anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-08-01 15:09 +0000
                        Re: Appending definition to another definition Paul Rubin <no.email@nospam.invalid> - 2012-08-01 08:56 -0700
                          Re: Appending definition to another definition anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-08-01 16:34 +0000
                            Re: Appending definition to another definition Paul Rubin <no.email@nospam.invalid> - 2012-08-01 10:15 -0700
                              Re: Appending definition to another definition George Hubert <georgeahubert@yahoo.co.uk> - 2012-08-01 11:04 -0700
                                Re: Appending definition to another definition Paul Rubin <no.email@nospam.invalid> - 2012-08-01 12:02 -0700
                                  Re: Appending definition to another definition George Hubert <georgeahubert@yahoo.co.uk> - 2012-08-01 13:51 -0700
                                  Re: Appending definition to another definition Aleksej Saushev <asau@inbox.ru> - 2012-08-02 05:28 +0400
                                    Re: Appending definition to another definition Paul Rubin <no.email@nospam.invalid> - 2012-08-01 19:04 -0700
                                      Re: Appending definition to another definition Aleksej Saushev <asau@inbox.ru> - 2012-08-02 08:33 +0400
                                        Re: Appending definition to another definition Paul Rubin <no.email@nospam.invalid> - 2012-08-01 22:07 -0700
                                          Re: Appending definition to another definition "A. K." <akk@nospam.org> - 2012-08-02 08:03 +0200
                                            Re: Appending definition to another definition Paul Rubin <no.email@nospam.invalid> - 2012-08-01 23:11 -0700
                                          Re: Appending definition to another definition hughaguilar96@yahoo.com - 2012-08-02 00:05 -0700
                                          Re: Appending definition to another definition Aleksej Saushev <asau@inbox.ru> - 2012-08-06 01:44 +0400
                              Re: Appending definition to another definition hughaguilar96@yahoo.com - 2012-08-01 16:48 -0700
                              heap implementation (was: Appending definition to another definition) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-08-02 14:48 +0000
                                Re: heap implementation Paul Rubin <no.email@nospam.invalid> - 2012-08-02 14:37 -0700
                                  Re: heap implementation anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-08-03 13:58 +0000
                                    Re: heap implementation Alex McDonald <blog@rivadpm.com> - 2012-08-03 08:57 -0700
                                      Re: heap implementation anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-08-03 16:12 +0000
                                        Re: heap implementation Alex McDonald <blog@rivadpm.com> - 2012-08-04 08:29 -0700
                                    Re: heap implementation Paul Rubin <no.email@nospam.invalid> - 2012-08-03 21:22 -0700
                                      Re: heap implementation Andrew Haley <andrew29@littlepinkcloud.invalid> - 2012-08-04 03:11 -0500
                                      Re: heap implementation anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-08-04 11:40 +0000
                                Re: heap implementation (was: Appending definition to another definition) Bernd Paysan <bernd.paysan@gmx.de> - 2012-08-03 00:04 +0200
                        Re: Appending definition to another definition George Hubert <georgeahubert@yahoo.co.uk> - 2012-08-01 11:20 -0700
                        Re: Appending definition to another definition Bernd Paysan <bernd.paysan@gmx.de> - 2012-08-02 01:55 +0200
                          Re: Appending definition to another definition Bernd Paysan <bernd.paysan@gmx.de> - 2012-08-02 02:09 +0200
                            Re: Appending definition to another definition hughaguilar96@yahoo.com - 2012-08-01 18:57 -0700
                          Re: Appending definition to another definition anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-08-02 09:41 +0000
                  Re: Appending definition to another definition hughaguilar96@yahoo.com - 2012-07-31 23:52 -0700
                    Re: Appending definition to another definition Coos Haak <chforth@hccnet.nl> - 2012-08-01 15:46 +0200
              Re: Appending definition to another definition jim@rainbarrel.com - 2012-08-01 14:01 -0700
                Re: Appending definition to another definition Jason Damisch <jasondamisch@yahoo.com> - 2012-08-01 14:39 -0700
          Re: Appending definition to another definition programmingkidx@gmail.com - 2012-08-05 19:35 -0700
    Re: Appending definition to another definition Jason Damisch <jasondamisch@yahoo.com> - 2012-07-29 11:40 -0700
      Re: Appending definition to another definition programmingkidx@gmail.com - 2012-07-29 11:58 -0700
        Re: Appending definition to another definition Jason Damisch <jasondamisch@yahoo.com> - 2012-07-29 12:08 -0700
        Re: Appending definition to another definition Gerry Jackson <gerry@jackson9000.fsnet.co.uk> - 2012-07-29 22:43 +0100
          Re: Appending definition to another definition Arnold Doray <invalid@invalid.com> - 2012-07-30 02:34 +0000
            Re: Appending definition to another definition Gerry Jackson <gerry@jackson9000.fsnet.co.uk> - 2012-07-30 06:59 +0100
        Re: Appending definition to another definition Arnold Doray <invalid@invalid.com> - 2012-07-30 13:42 +0000
    Re: Appending definition to another definition "Rod Pemberton" <do_not_have@notemailnot.cmm> - 2012-07-29 18:23 -0400

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

#14608

Op Wed, 1 Aug 2012 03:27:41 -0700 (PDT) schreef hughaguilar96@yahoo.com:

> In regard to FREE, the standard (14.6.1.1605) says: "If the operation
> fails, the ior is an implementation-defined I/O result code." 
> 
> That is completely useless! If the standard said what code would be
> returned in the event that the address was not originally provided by
> ALLOCATE or RESIZE, then the programmer could do something about it. As
> it is, we don't know what caused the failure, which makes it
> unreasonable to do anything other than just abort the program with an
> unhelpful error message: "FREE has failed, but we don't know why." So it
> doesn't really matter if FREE crashes outright, or if it returns an
> uninformative error-code and the application program has to abort ---
> from the user's perspective, the Forth program has just crashed. 

If the implementation returns a sensible I/O result code, the program could
warn the programmer that she made a mistake to use FREE on an invalid
address. That's where I/O result codes are for. If your implementation
does not do that, throw it away.

-- 
Coos

CHForth, 16 bit DOS applications
http://home.hccnet.nl/j.j.haak/forth.html 

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

#14610

Coos Haak <chforth@hccnet.nl> writes:
> If the implementation returns a sensible I/O result code, the program
> could warn the programmer that she made a mistake to use FREE on an
> invalid address.

I don't see how to determine if the address is invalid without an awful
lot of overhead and hassle, remembering in some auxiliary structure
where all the valid pointers are.  The auxiliary structure would itself
have to be dynamically allocated since its required size can't be known
in advance.  I guess you could mark each allocated region with a magic
random number that the user program isn't allowed to inspect, so the
chance of the user data containing the same number by accident would be
very low.

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

#14612

All of this seems like an incredibly huge pain in the butt, I would solve the problem by not doing that, and totally rethinking the problem.

Jason

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

#14613

On Aug 1, 4:02 pm, Jason Damisch <jasondami...@yahoo.com> wrote:
> All of this seems like an incredibly huge pain in the butt, I would solve the problem by not doing that, and totally rethinking the problem.
>
> Jason

I was very surprised to see that FREE takes an address as its
argument. If I had to design my own, I think ALLOCATE would return a
token (or 0 for fail) and the token is used for FREE. I guess it could
be argued that the address could be considered a token.

What happens if you FREE an address which wasn't ALLOCATEd?

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

#14630

> I was very surprised to see that FREE takes an address as its
> 
> argument. If I had to design my own, I think ALLOCATE would return a
> 
> token (or 0 for fail) and the token is used for FREE. I guess it could
> 
> be argued that the address could be considered a token.
> 
> 
> 
> What happens if you FREE an address which wasn't ALLOCATEd?

Diaperglu Forth doesn't have FREE and ALLOCATE. It instead uses a buffer management system where a token is returned which is actually a 0 based index like you are suggesting. This means Diaperglu can tell when someone tries to free a buffer that doesn't exist. It also keeps track of free buffers.

What about adding a buffer management system to the Forth standard?

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

#14641

On Wednesday, August 1, 2012 6:45:47 AM UTC-7, Coos Haak wrote:
> Op Wed, 1 Aug 2012 03:27:41 -0700 (PDT) schreef hughaguilar96@yahoo.com:
> > In regard to FREE, the standard (14.6.1.1605) says: "If the operation
> > fails, the ior is an implementation-defined I/O result code." 
> > 
> > That is completely useless! 
>
> If the implementation returns a sensible I/O result code, the program could
> warn the programmer that she made a mistake to use FREE on an invalid
> address. That's where I/O result codes are for. If your implementation
> does not do that, throw it away.

The idea is that a program will work the same on any standard-compliant system. That is what the word "standard" means.

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

#14614

George Hubert <georgeahubert@yahoo.co.uk> writes:
>On Tuesday, July 31, 2012 6:38:13 PM UTC+1, Andrew Haley wrote:
>> George Hubert <georgeahubert@yahoo.co.uk> wrote: > The Standard states th=
>at FREE either succeeds and returns zero or > fails returning non-zero: any=
>thing else is clearly a bug. Not exactly. The standard doesn't say anything=
> about what happens if you fail to honour your side of the contract, which =
>is "a-addr shall indicate a region of data space that was previously obtain=
>ed by ALLOCATE or RESIZE." Andrew.
>
>Surely:
>
>14.4.1.2 Ambiguous conditions
>no additional requirements.=20
>
>implies that there aren't any ambiguous conditions

Or not any additional ones.

>which undefined behavio=
>ur in the event of a-addr not coming from ALLOCATE implies. Anyway it doesn=
>'t state it will crash, as Hugh said.

But crash it does, on a number of systems (see below).  And I don't
see a reliable and efficient way to prevent this in all cases.

- anton
-----------------------------------------------------
 VFX Forth for Linux IA32
 © MicroProcessor Engineering Ltd, 1998-2009 

 Version: 4.40 [build 0404]
 Build date: 7 December 2009

 Free dictionary = 7922527 bytes [7736kb]


here free 
 CS=0023 DS=002B ES=002B SS=002B FS=0000 GS=0063
 EAX=0800:0000 EBX=F7FB:4FF4 ECX=0893:4EB1 EDX=0000:0000
 ESI=F7FB:6160 EDI=080B:9CA1 EBP=0893:4F94 ESP=0893:4F7C
 EIP=F7ED:631C EFLAGS=0001:0206
--- RS top ---
 $0000:0009
 $080B:61C9 ADD-HISTORY-LINE 
 $0800:0000
 $0000:0000
 $0894:4FC0
 $0893:4FA0
 $0894:4FB0
 $0804:AADD NXCALL 
Signal number SIGSEGV
at address F7ED:631C, probably in * outside dictionary *  

Press E to exit, R to restart, other to continue: 

----------------------------------------------------------
[c7:~:31707] sf
SwiftForth i386-Linux 3.2.1 28-Dec-2009 
here free *** glibc detected *** sf: free(): invalid pointer: 0x080801b1 ***
Aborted

----------------------------------------------------------
Gforth 0.6.2, Copyright (C) 1995-2003 Free Software Foundation, Inc.
Gforth comes with ABSOLUTELY NO WARRANTY; for details type `license'
Type `bye' to exit
0 free . 0  ok
here free . *** glibc detected *** gforth: free(): invalid pointer: 0x00007f85c1f28898 ***
======= Backtrace: =========
/lib/libc.so.6[0x7f85c2767948]
/lib/libc.so.6(cfree+0x76)[0x7f85c2769a56]
gforth(engine+0x2584)[0x406674]
gforth(go_forth+0x174)[0x40f914]
gforth(main+0x153)[0x4106e3]
/lib/libc.so.6(__libc_start_main+0xe6)[0x7f85c27121a6]
gforth[0x404059]
======= Memory map: ========
...
Aborted.

The Gforth behaviour is wrong.  The Forth system should not terminate
(it normally does not terminate even if it executes an illegal
instruction).

- 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 2012: http://www.euroforth.org/ef12/

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

#14618

anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
> But crash it does, on a number of systems (see below).  And I don't
> see a reliable and efficient way to prevent this in all cases.

If you're using malloc as the underlying manager, to allocate a block of
n cells, get a block of n+1 cells from malloc.  Lightly scramble the
address of this block and store the result in cell 0, then return the
address of block 1.  On free, make sure that the stuff before block 1
has the right contents.  Obviously since forth has no memory protection,
a malicious program could subvert this scheme, but it's not likely to
happen by accident.

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

#14619

Paul Rubin <no.email@nospam.invalid> writes:
>anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>> But crash it does, on a number of systems (see below).  And I don't
>> see a reliable and efficient way to prevent this in all cases.
>
>If you're using malloc as the underlying manager, to allocate a block of
>n cells, get a block of n+1 cells from malloc.  Lightly scramble the
>address of this block and store the result in cell 0, then return the
>address of block 1.  On free, make sure that the stuff before block 1
>has the right contents.  Obviously since forth has no memory protection,
>a malicious program could subvert this scheme, but it's not likely to
>happen by accident.

Not what I consider reliable, especially on 32-bit systems.  Good
enough for debugging purposes (and probably the libc malloc used by
Gforth and SwiftForth used such an approach), but if "not crashing"
was guaranteed, it would not be good enough.

On a 32-bit system I would expect it to fail for one out of 2^32 FREEs
of non-ALLOCATEd addresses.  And if not-crashing was guaranteed, there
would likely be programs that make use of this guarantee and FREE
arbitrary addresses with abandon, and such a program would find the
failing case eventually.  And if you don't expect such programs, why
ask for that guarantee?

- 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 2012: http://www.euroforth.org/ef12/

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

#14620

anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
> On a 32-bit system I would expect it to fail for one out of 2^32 FREEs
> of non-ALLOCATEd addresses.

Using two or three cells would decrease that likelihood exponentially.
The alternative is to remember every pointer ALLOCATE has returned until
it is freed.  I guess that could be tolerable.  Have cell 0 point back
to a table entry owned by the allocator, where the table entry has the
allocated block's address, until it is freed.  The table would have to
expand dynamically, maybe using a tree structure, etc.  Blecch.

> And if not-crashing was guaranteed, there would likely be programs
> that make use of this guarantee and FREE arbitrary addresses with
> abandon,

Yeah, that would be a pretty horrendous way to program, but I suppose
issuing a guarantee would invite it.

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

#14624

On Wednesday, August 1, 2012 6:15:10 PM UTC+1, Paul Rubin wrote:
> anton@mips.complang.tuwien.ac.at (Anton Ertl) writes: > On a 32-bit system I would expect it to fail for one out of 2^32 FREEs > of non-ALLOCATEd addresses. Using two or three cells would decrease that likelihood exponentially. The alternative is to remember every pointer ALLOCATE has returned until it is freed. I guess that could be tolerable. Have cell 0 point back to a table entry owned by the allocator, where the table entry has the allocated block's address, until it is freed. The table would have to expand dynamically, maybe using a tree structure, etc. Blecch. > And if not-crashing was guaranteed, there would likely be programs > that make use of this guarantee and FREE arbitrary addresses with > abandon, Yeah, that would be a pretty horrendous way to program, but I suppose issuing a guarantee would invite it.

Using a linked list where the cell is linked in by ALLOCATE is more sensible. FREE checks if it's in the list and fails if not or unlinks the the block and releases it. RESIZE is similar but relinks the block after resizing. It's actually how w32F does it. It also allows debugging aids like
.MALLOCS 
Link-Addr Rel-Addr         Bytes  HeapAddr  Type
--------- --------      --------  --------  ----
00E50020  00E50030     1,257,472  00150000
0015AFC0  0015AFD0        32,768  00150000
00157090  001570A0           332  00150000
00159DE0  00159DF0           132  00150000
00CC0020  00CC0030     1,048,576  00150000
00159C90  00159CA0           293  00150000
00157228  00157238           260  00150000
00156840  00156850         2,084  00150000
--------- --------      --------  --------  ----
Total allocated    2,341,917
 ok

George Hubert

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

#14625

George Hubert <georgeahubert@yahoo.co.uk> writes:
> Using a linked list where the cell is linked in by ALLOCATE is more
> sensible. FREE checks if it's in the list and fails if not or unlinks

If FREE has to linearly search a list of arbitrary size on every call, I
wouldn't describe that as an efficient solution.

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

#14629

On Wednesday, August 1, 2012 8:02:28 PM UTC+1, Paul Rubin wrote:
> George Hubert <georgeahubert@yahoo.co.uk> writes: > Using a linked list where the cell is linked in by ALLOCATE is more > sensible. FREE checks if it's in the list and fails if not or unlinks If FREE has to linearly search a list of arbitrary size on every call, I wouldn't describe that as an efficient solution.

Then add 2 cells prior to the data and used a binary tree with the memory address itself (rather than a pointer) as the key, then it only costs an extra 2 cells per allocation. Certainly it would be more efficient than 2 pointers and having to expand the allocation table. All the dictionary needs is a pointer to the starting node (VARIABLE or VALUE).

George Hubert 

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

#14643

Paul Rubin <no.email@nospam.invalid> writes:

> George Hubert <georgeahubert@yahoo.co.uk> writes:
>> Using a linked list where the cell is linked in by ALLOCATE is more
>> sensible. FREE checks if it's in the list and fails if not or unlinks
>
> If FREE has to linearly search a list of arbitrary size on every call, I
> wouldn't describe that as an efficient solution.

There's a natural linear order on addresses.


-- 
HE CE3OH...

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

#14645

Aleksej Saushev <asau@inbox.ru> writes:
>> If FREE has to linearly search a list of arbitrary size on every call, 
> There's a natural linear order on addresses.

How do you suggest 1) finding an address in the list, even if they're
in linear order; 2) inserting a new address into the list?

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

#14646

Paul Rubin <no.email@nospam.invalid> writes:

> Aleksej Saushev <asau@inbox.ru> writes:
>>> If FREE has to linearly search a list of arbitrary size on every call, 
>> There's a natural linear order on addresses.
>
> How do you suggest 1) finding an address in the list, even if they're
> in linear order; 2) inserting a new address into the list?

What is the point of maintaining a list when you can maintain at least
balanced tree with faster lookups and insertions?? You can implement
self-balancing tree the way you like with minimal effort.


-- 
HE CE3OH...

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

#14647

Aleksej Saushev <asau@inbox.ru> writes:
> What is the point of maintaining a list when you can maintain at least
> balanced tree with faster lookups and insertions?? You can implement
> self-balancing tree the way you like with minimal effort.

I don't understand what point you were making about the linear ordering
of addresses in this case.  Structures like self-balancing trees are
fancier than what one normally sees in Forth, in my limited knowledge.
The scheme I suggested earlier of a pointer next to each allocated
region, pointing back to a table of allocated addresses, seems a lot
simpler than a self-balancing tree.

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

#14649

On 02.08.2012 07:07, Paul Rubin wrote:
> Aleksej Saushev <asau@inbox.ru> writes:
>> What is the point of maintaining a list when you can maintain at least
>> balanced tree with faster lookups and insertions?? You can implement
>> self-balancing tree the way you like with minimal effort.
>
> I don't understand what point you were making about the linear ordering
> of addresses in this case.  Structures like self-balancing trees are
> fancier than what one normally sees in Forth, in my limited knowledge.
> The scheme I suggested earlier of a pointer next to each allocated
> region, pointing back to a table of allocated addresses, seems a lot
> simpler than a self-balancing tree.
>

Yep. We once had a heap in extra RAM. ALLOCATE was just taking the next 
free space of sufficient size between chained blocks by circular memory 
search. No garbage collection, never ever any problems, blazingly fast.

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

#14650

"A. K." <akk@nospam.org> writes:
> Yep. We once had a heap in extra RAM. ALLOCATE was just taking the
> next free space of sufficient size between chained blocks by circular
> memory search. No garbage collection, never ever any problems,
> blazingly fast.

A classic first-fit allocator from Knuth vol 1, probably just right for
the sorts of 16-bit environments where Forth was historically important,
but not really suitable for modern hardware with potentially millions or
billions of live objects.

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

#14654

On Wednesday, August 1, 2012 10:07:21 PM UTC-7, Paul Rubin wrote:
> Aleksej Saushev <asau@inbox.ru> writes:
> 
> > What is the point of maintaining a list when you can maintain at least
> > balanced tree with faster lookups and insertions?? You can implement
> > self-balancing tree the way you like with minimal effort.
> 
> I don't understand what point you were making about the linear ordering
> of addresses in this case.  Structures like self-balancing trees are
> fancier than what one normally sees in Forth, in my limited knowledge.
> 
> The scheme I suggested earlier of a pointer next to each allocated
> region, pointing back to a table of allocated addresses, seems a lot
> simpler than a self-balancing tree.

I have a self-balancing tree in my novice package.

I don't think that your scheme with the table is all that efficient. If your "table" is an array, then inserting and deleting in the middle is slow, and a binary search isn't any faster than a tree descent.

I haven't given a whole lot of thought to the subject of heap design, although I think that it is fairly easy. Searching for nodes isn't really the time-critical aspect of the code. The difficult part is allocating the nodes so they use the caches efficiently. You guys have immediately begun speculating on algorithms for node searching, which is really the most trivial aspect of the problem.

A little bit of research wouldn't hurt --- heaps have been in use since before I was born --- somebody likely knows something about implementing them. 

A heap is a somewhat interesting problem --- maybe I will implement one for the next novice-package release. :-)

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

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

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

csiph-web