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

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

heap implementation

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

Contents

  heap implementation Hugh Aguilar <hughaguilar96@nospicedham.yahoo.com> - 2012-08-02 00:25 -0700
    Re: heap implementation Alex McDonald <blog@nospicedham.rivadpm.com> - 2012-08-02 02:51 -0700
      Re: heap implementation Andrew Haley <andrew29@littlepinkcloud.invalid> - 2012-08-02 05:23 -0500
        Re: heap implementation Alex McDonald <blog@rivadpm.com> - 2012-08-02 13:57 -0700
    Re: heap implementation "Rod Pemberton" <do_not_have@notemailnot.cmm> - 2012-08-02 18:45 -0400
      Re: heap implementation vandys@vsta.org - 2012-08-02 22:53 +0000
        Re: heap implementation Hugh Aguilar <hughaguilar96@yahoo.com> - 2012-08-02 21:53 -0700
          Re: heap implementation "Rod Pemberton" <do_not_have@notemailnot.cmm> - 2012-08-03 07:23 -0400
            Re: heap implementation anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-08-03 12:12 +0000
              Re: heap implementation Hugh Aguilar <hughaguilar96@yahoo.com> - 2012-08-05 23:08 -0700
          Re: heap implementation Alex McDonald <blog@rivadpm.com> - 2012-08-03 08:41 -0700
        Re: heap implementation "Rod Pemberton" <do_not_have@notemailnot.cmm> - 2012-08-03 06:58 -0400
          Re: heap implementation Alex McDonald <blog@rivadpm.com> - 2012-08-03 05:36 -0700
            Re: heap implementation Hugh Aguilar <hughaguilar96@yahoo.com> - 2012-08-05 23:28 -0700
        Re: heap implementation Aleksej Saushev <asau@inbox.ru> - 2012-08-06 01:43 +0400
    Re: heap implementation "wolfgang kern" <nowhere@never.at> - 2012-08-17 19:57 +0200

#14655 — heap implementation

Does anybody know how to implement a heap on the modern x86
processors?

This question came up on comp.lang.forth:
https://groups.google.com/group/comp.lang.forth/browse_thread/thread/f7cb467ec9d95ce5#
I cross-posted to c.l.f. for this reason.

The problem is that the ANS-Forth standard, and the upcoming
Forth-200x standard, both require that the heap be exactly compatible
with the heap in GLIBC. This is because nobody on the standards
committee knows how to implement a heap, and so they plan on
continuing to rely on GLIBC forever. Unfortunately, the heap in GLIBC
isn't very good. It doesn't have ALLOCATION for one thing (a function
that returns the amount of memory in a node given the node's address).
Also, as described in the thread mentioned above, FREE doesn't
specifically tell you if it has been given an address that isn't a
node. There are other problems. All in all, I would like to get rid of
Forth's dependence on GLIBC altogether --- if people want to use GLIBC
they should program in C.

I can implement a working heap, and I likely will for my next novice-
package release.
http://www.forth.org/novice.html
The problem is that I don't understand how the caches work on the
modern x86 processors, and this is necessary for an efficient
implementation. My novice package has linked lists and self-balancing
trees, so an efficient heap is important.

[toc] | [next] | [standalone]

#14659

On Aug 2, 8:25 am, Hugh Aguilar <hughaguila...@nospicedham.yahoo.com>
wrote:
> Does anybody know how to implement a heap on the modern x86
> processors?
>
> This question came up on comp.lang.forth:https://groups.google.com/group/comp.lang.forth/browse_thread/thread/...
> I cross-posted to c.l.f. for this reason.
>
> The problem is that the ANS-Forth standard, and the upcoming
> Forth-200x standard, both require that the heap be exactly compatible
> with the heap in GLIBC. This is because nobody on the standards
> committee knows how to implement a heap, and so they plan on
> continuing to rely on GLIBC forever. Unfortunately, the heap in GLIBC
> isn't very good. It doesn't have ALLOCATION for one thing (a function
> that returns the amount of memory in a node given the node's address).

We've discussed that one before. I still maintain that the problem is
not in the language. If you need the length, store it on allocation.
Win32Forth does this.

> Also, as described in the thread mentioned above, FREE doesn't
> specifically tell you if it has been given an address that isn't a
> node. There are other problems.

If code is written to FREE stuff which it didn't ALLOCATE, an
ALLOCATION to get the length of some random address is going to have
serious issues. If you can't FREE it, you can't ALLOCATION it.

> All in all, I would like to get rid of
> Forth's dependence on GLIBC altogether --- if people want to use GLIBC
> they should program in C.

What Forth dependance? Many Forths use the underlying OS allocator,
not a library. Some don't have support for dynamic memory.

>
> I can implement a working heap, and I likely will for my next novice-
> package release.http://www.forth.org/novice.html
> The problem is that I don't understand how the caches work on the
> modern x86 processors, and this is necessary for an efficient
> implementation. My novice package has linked lists and self-balancing
> trees, so an efficient heap is important.

Avoiding fragmentation and getting the locking right should be your
focus; cache performance issues will pale into insignificance if you
chose a poor algorithm. There are lots of resources on the web that
cover this.

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

#14660

In comp.lang.forth Alex McDonald <blog@nospicedham.rivadpm.com> wrote:
> Avoiding fragmentation and getting the locking right should be your
> focus; cache performance issues will pale into insignificance if you
> chose a poor algorithm. There are lots of resources on the web that
> cover this.

As usual, it's in Knuth.  (Sorry :-)

I agree with most of what you wrote, but these days one of the most
important factors is cache locality, and for big boxes some sort of
thread-local allocator is a big win.  Now, NUMA-aware allocators are
starting to gain traction, and simple heap allocators are unlikely to
get near the performance of the system's library.  There's a paper on
a NUMA-aware allocator at
http://developer.amd.com/Assets/NUMA_aware_heap_memory_manager_article_final.pdf

Andrew.

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

#14671

On Aug 2, 11:23 am, Andrew Haley <andre...@littlepinkcloud.invalid>
wrote:
> In comp.lang.forth Alex McDonald <b...@nospicedham.rivadpm.com> wrote:
>
> > Avoiding fragmentation and getting the locking right should be your
> > focus; cache performance issues will pale into insignificance if you
> > chose a poor algorithm. There are lots of resources on the web that
> > cover this.
>
> As usual, it's in Knuth.  (Sorry :-)

Why apologize? I swear by the books, and they're a constant joy to
read.

>
> I agree with most of what you wrote, but these days one of the most
> important factors is cache locality, and for big boxes some sort of
> thread-local allocator is a big win.  Now, NUMA-aware allocators are
> starting to gain traction, and simple heap allocators are unlikely to
> get near the performance of the system's library.  There's a paper on
> a NUMA-aware allocator athttp://developer.amd.com/Assets/NUMA_aware_heap_memory_manager_articl...

Interesting article.

>
> Andrew.

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

#14676

"Hugh Aguilar" <hughaguilar96@nospicedham.yahoo.com> wrote in message
news:32efd358-5119-44a2-83fd-2a2967d81d32@y1g2000vbx.googlegroups.com...

[dropped c.l.a.x.]

> The problem is that the ANS-Forth standard, and the upcoming
> Forth-200x standard, both require that the heap be exactly compatible
> with the heap in GLIBC.

Really?  Where exactly...  ;-)

Seriously, I'd like to know where.  :-)

I.e., I doubt anything remotely close to that is stated, even if the
specifications did encourage it indirectly, which they probably don't.
They do probably allow for it to be compatible or supportible.

You know I'd support that though, right?

> It doesn't have ALLOCATION for one thing (a function
> that returns the amount of memory in a node given the
> node's address).

That sounds _alot_ like C's sizeof()... on a node... at least to me.  So,
why don't you just implement C's SIZEOF for Forth?  ;-)

So, you dislike Forth-200x for it's "C dependence" and have argued with
Anton over the necessity or usefulness of your ALLOCATION word.  But, if
ALLOCATION is just a variant of C's sizeof() for Forth, it seems to me that
you're promoting another dependence on C also ...

Ironic?

> Also, as described in the thread mentioned above, FREE doesn't
> specifically tell you if it has been given an address that isn't a
> node.

So?

> There are other problems.

Wait.  Before you proceed to "other" problems, why was the one issue you
stated a problem?

[Um, why is the infomercial phrase "Wait, there's more!" popping into my
head... ?]

> All in all, I would like to get rid of Forth's dependence on GLIBC
> altogether --- if people want to use GLIBC they should program in C.

People might've taken this more seriously if you didn't automatically equate
GLIBC with whatever memory allocation method is being used for a specific
platform.

GLIBC might provide the memory allocation via it's own memory allocator and
the OS (operating system) might use that, but that's no longer the norm.
Today, most OSes implement their own allocator and the C library calls its.
If you're not implementing a free-standing Forth, i.e., Forth is the OS,
then implementing a memory allocator which is incompatible with all other
memory allocation schemes is perfectly acceptable.  However, when
implementing a Forth on an existing OS, which is most of them today, such a
Forth is most likely going to use the host's memory allocator.


Rod Pemberton

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

#14677

Rod Pemberton <do_not_have@notemailnot.cmm> wrote:
>> It doesn't have ALLOCATION for one thing (a function
>> that returns the amount of memory in a node given the
>> node's address).
> That sounds _alot_ like C's sizeof()... on a node... at least to me.  So,
> why don't you just implement C's SIZEOF for Forth?  ;-)

No, sizeof() is an operator which compiles to a constant based on looking at
the (compile time) types.  This sounds more like a runtime thing.  malloc()
records the size of the allocated object, so that free() can return its
storage.  I don't think there's ever been an API to find out an allocated
node's size--if you care, you have to keep it somewhere (usually in the
allocate memory) for yourself.

-- 
Andy Valencia
Home page: http://www.vsta.org/andy/
To contact me: http://www.vsta.org/contact/andy.html

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

#14681

On Aug 2, 3:53 pm, van...@vsta.org wrote:
> Rod Pemberton <do_not_h...@notemailnot.cmm> wrote:
> >> It doesn't have ALLOCATION for one thing (a function
> >> that returns the amount of memory in a node given the
> >> node's address).
> > That sounds _alot_ like C's sizeof()... on a node... at least to me.  So,
> > why don't you just implement C's SIZEOF for Forth?  ;-)
>
> No, sizeof() is an operator which compiles to a constant based on looking at
> the (compile time) types.  This sounds more like a runtime thing.  malloc()
> records the size of the allocated object, so that free() can return its
> storage.  I don't think there's ever been an API to find out an allocated
> node's size--if you care, you have to keep it somewhere (usually in the
> allocate memory) for yourself.
>
> --
> Andy Valencia
> Home page:http://www.vsta.org/andy/
> To contact me:http://www.vsta.org/contact/andy.html

SIZEOF() is a compile-time function --- it examines the *name* of the
variable, not the address of the variable. You can't do that in Forth
because Forth is untyped. In Forth we just have cells on the stack,
which may be addresses or numbers or codes that represent anything
else that the programmer says that they represent, but they don't have
inherent types. It is possible to treat a cell as a code (zero
indicating error), then treat it as a number (by adding another number
to it), and then treat it as an address (by fetching through it) ---
the type of the cell depends upon how the programmer is treating it,
and is not inherent in the cell. This is a pretty fundamental aspect
of Forth --- you should know this, Rod.

In my novice package I do keep the allocated size in the allocated
block myself. I had to rewrite ALLOCATE, RESIZE and FREE (and write
ALLOCATION and some other words) to accomplish this. Considering how
low-level these words are, and how often they are used, they should be
written in assembly-language rather than in Forth. This is necessary
for speed. Also, to save memory, it is important to not duplicate this
information for every node (the size is obviously stored internally
because FREE and RESIZE use the information). For an assembly-language
implementation to be possible though, ALLOCATION needs to be in the
standard --- hence the RfD.

It is very important to have this information. If you want to clone a
list, and the list contains nodes of different types, then you have to
be able to find out what size the nodes are in order to clone them.
See CLONE-NODE in my novice package. All of this is discussed here:
http://www.forth.org/novice.pdf

Leon Wagner rejected my RfD saying that it had nothing to do with
lists, and yet this was my only example. It is obvious to me that he
rejected the RfD without bothering to read it. I think that the
Forth-200x committee rejects *every* RfD that is not submitted by a
committee member. Allowing RfDs to be written by non-members is just a
charade to make it appear that Forth-200x was created by the entire
Forth community including myself --- but Forth-200x is really just
what Forth Inc. says that it is --- no RfD that I write will ever be
accepted or even read. The committee's standard procedure is to tell
me that my RfD needs to be considered by the "Forth community" on
comp.lang.forth, then Passaniti and the other trolls say that it
"sucks," then the committee says that the "Forth community" rejected
it --- this way they avoid explicitly rejecting it themselves, which
would require them to give a reason for why it is rejected ---
although in the case of my ALLOCATION RfD Leon Wagner did just go
ahead and personally kill it without giving any reason.

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

#14684

"Hugh Aguilar" <hughaguilar96@yahoo.com> wrote in message
news:0eb23bbb-3804-46a1-b49c-0371da0d65b1@w8g2000vbx.googlegroups.com...

> SIZEOF() is a compile-time function --- it examines the *name* of the
> variable, not the address of the variable. You can't do that in Forth
> because Forth is untyped.

You can't?  Shouldn't a VARIABLE in Forth be in the dictionary, have a name,
have an address, have space for the variable, and be FINDable ... ?   I
guess
I must've misunderstood something about Forth yet again.  ;-)

> In Forth we just have cells on the stack,
> which may be addresses or numbers or codes that represent anything
> else that the programmer says that they represent, but they don't have
> inherent types.

Wait, Forth only has cells on the stack ... ?  So, your Forth has no
dictionary?  Odd.  ;-)  Yes, it's true that Forth is typeless.

> It is possible to treat a cell as a code (zero
> indicating error), then treat it as a number (by adding another number
> to it), and then treat it as an address (by fetching through it) ---
> the type of the cell depends upon how the programmer is treating it,
> and is not inherent in the cell. This is a pretty fundamental aspect
> of Forth --- you should know this, Rod.

I do.  That - typeless - is one of the issues with implementing Forth in C,
and interpreters in C too.

> In my novice package I do keep the allocated size in the allocated
> block myself. I had to rewrite ALLOCATE, RESIZE and FREE (and write
> ALLOCATION and some other words) to accomplish this. Considering how
> low-level these words are, and how often they are used, they should be
> written in assembly-language rather than in Forth. This is necessary
> for speed. Also, to save memory, it is important to not duplicate this
> information for every node (the size is obviously stored internally
> because FREE and RESIZE use the information). For an assembly-language
> implementation to be possible though, ALLOCATION needs to be in the
> standard --- hence the RfD.

Can you post a very simple example of usage for me?  Then, can you post the
same example without ALLOCATION?  That way, I can compare the two.

> It is very important to have this information. If you want to clone a
> list, and the list contains nodes of different types, then you have to
> be able to find out what size the nodes are in order to clone them.

True, but I thought you just said Forth doesn't have types.  Now, you're
saying the nodes have types.  ;-)  Yes, I understood what you meant.

> See CLONE-NODE in my novice package.

No.

> Leon Wagner rejected my RfD saying that it had nothing to do with
> lists, and yet this was my only example. It is obvious to me that he
> rejected the RfD without bothering to read it. I think that the
> Forth-200x committee rejects *every* RfD that is not submitted by a
> committee member. Allowing RfDs to be written by non-members is
> just a charade to make it appear that Forth-200x was created by the
> entire Forth community including myself --- but Forth-200x is really
> just what Forth Inc. says that it is --- no RfD that I write will ever be
> accepted or even read.

So, widespread use of a Forth word or lack of is unimportant?  I.e.,
shouldn't you wait to RfD until nearly every Forth uses ALLOCATION?


No offense, but I vote that this was one of the least clear posts by you...


Rod Pemberton

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

#14686

"Rod Pemberton" <do_not_have@notemailnot.cmm> writes:
>"Hugh Aguilar" <hughaguilar96@yahoo.com> wrote in message
>news:0eb23bbb-3804-46a1-b49c-0371da0d65b1@w8g2000vbx.googlegroups.com...
>> Leon Wagner rejected my RfD saying that it had nothing to do with
>> lists, and yet this was my only example. It is obvious to me that he
>> rejected the RfD without bothering to read it. I think that the
>> Forth-200x committee rejects *every* RfD that is not submitted by a
>> committee member.

Your SIZE proposal was not rejected, you just did not pursue it any
further after the feedback (which was pretty sympathetic, but also
indicated that the proposal was unlikely to reach standardization in
the foreseeable future).

>So, widespread use of a Forth word or lack of is unimportant?  I.e.,
>shouldn't you wait to RfD until nearly every Forth uses ALLOCATION?

That's not necessary, although it helps.  E.g., X:xchar and X:synonym
were not in many Forth systems when the RfD was initially written.

- 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]

#14757

On Aug 3, 5:12 am, an...@mips.complang.tuwien.ac.at (Anton Ertl)
wrote:
> "Rod Pemberton" <do_not_h...@notemailnot.cmm> writes:
> >"Hugh Aguilar" <hughaguila...@yahoo.com> wrote in message
> >news:0eb23bbb-3804-46a1-b49c-0371da0d65b1@w8g2000vbx.googlegroups.com...
> >> Leon Wagner rejected my RfD saying that it had nothing to do with
> >> lists, and yet this was my only example. It is obvious to me that he
> >> rejected the RfD without bothering to read it. I think that the
> >> Forth-200x committee rejects *every* RfD that is not submitted by a
> >> committee member.
>
> Your SIZE proposal was not rejected, you just did not pursue it any
> further after the feedback (which was pretty sympathetic, but also
> indicated that the proposal was unlikely to reach standardization in
> the foreseeable future).

This is what Leon Wagner said:
"I don't support this feature and would likely not implement it. Other
than the nice discussion of what to name it, I
see no compelling reason for its actual use."

That killed it. There was some discussion after this, but it mostly
involved everybody scrambling to agree with Leon Wagner so that any
earlier statements they may have made in agreement with me would be
forgotten --- just like in that book "1984," they felt obliged to
agree with Leon not only in the present and future, but in the past as
well.

You yourself brought up the issue of GLIBC not supporting ALLOCATION,
and Gforth being dependent upon GLIBC, which you claim makes
ALLOCATION impossible for the Forth-200x standard to support.

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

#14698

On Aug 3, 5:53 am, Hugh Aguilar <hughaguila...@yahoo.com> wrote:
> On Aug 2, 3:53 pm, van...@vsta.org wrote:
>
>
>
>
>
>
>
>
>
> > Rod Pemberton <do_not_h...@notemailnot.cmm> wrote:
> > >> It doesn't have ALLOCATION for one thing (a function
> > >> that returns the amount of memory in a node given the
> > >> node's address).
> > > That sounds _alot_ like C's sizeof()... on a node... at least to me.  So,
> > > why don't you just implement C's SIZEOF for Forth?  ;-)
>
> > No, sizeof() is an operator which compiles to a constant based on looking at
> > the (compile time) types.  This sounds more like a runtime thing.  malloc()
> > records the size of the allocated object, so that free() can return its
> > storage.  I don't think there's ever been an API to find out an allocated
> > node's size--if you care, you have to keep it somewhere (usually in the
> > allocate memory) for yourself.
>
> > --
> > Andy Valencia
> > Home page:http://www.vsta.org/andy/
> > To contact me:http://www.vsta.org/contact/andy.html
[snip]
>
> In my novice package I do keep the allocated size in the allocated
> block myself. I had to rewrite ALLOCATE, RESIZE and FREE (and write
> ALLOCATION and some other words) to accomplish this. Considering how
> low-level these words are, and how often they are used, they should be
> written in assembly-language rather than in Forth. This is necessary
> for speed. Also, to save memory, it is important to not duplicate this
> information for every node (the size is obviously stored internally
> because FREE and RESIZE use the information). For an assembly-language
> implementation to be possible though, ALLOCATION needs to be in the
> standard --- hence the RfD.
>
> It is very important to have this information. If you want to clone a
> list, and the list contains nodes of different types, then you have to
> be able to find out what size the nodes are in order to clone them.
> See CLONE-NODE in my novice package. All of this is discussed here:http://www.forth.org/novice.pdf

Your requirements are more akin to garbage collection and you might
want to consider pursuing that approach.

>
> Leon Wagner rejected my RfD saying that it had nothing to do with
> lists, and yet this was my only example. It is obvious to me that he
> rejected the RfD without bothering to read it. I think that the
> Forth-200x committee rejects *every* RfD that is not submitted by a
> committee member. Allowing RfDs to be written by non-members is just a
> charade to make it appear that Forth-200x was created by the entire
> Forth community including myself --- but Forth-200x is really just
> what Forth Inc. says that it is --- no RfD that I write will ever be
> accepted or even read. The committee's standard procedure is to tell
> me that my RfD needs to be considered by the "Forth community" on
> comp.lang.forth, then Passaniti and the other trolls say that it
> "sucks," then the committee says that the "Forth community" rejected
> it --- this way they avoid explicitly rejecting it themselves, which
> would require them to give a reason for why it is rejected ---
> although in the case of my ALLOCATION RfD Leon Wagner did just go
> ahead and personally kill it without giving any reason.

But don't propose GC to the TC, since proposing a full blown GC
language feature would be akin to the task of Sisyphus, and your
emails on the subject would be too tedious for words.

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

#14682

<vandys@vsta.org> wrote in message news:a80emiF5f6U1@mid.individual.net...
...

> This sounds more like a runtime thing.  malloc()
> records the size of the allocated object, so that free() can return its
> storage.  I don't think there's ever been an API to find out an allocated
> node's size--if you care, you have to keep it somewhere (usually in the
> allocate memory) for yourself.
>

So, why do those who program Forth need ALLOCATION ... ?
[The question is really directed to Hugh, not you...]


RP

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

#14687

On Aug 3, 11:58 am, "Rod Pemberton" <do_not_h...@notemailnot.cmm>
wrote:
> <van...@vsta.org> wrote in messagenews:a80emiF5f6U1@mid.individual.net...
>
> ...
>
> > This sounds more like a runtime thing.  malloc()
> > records the size of the allocated object, so that free() can return its
> > storage.  I don't think there's ever been an API to find out an allocated
> > node's size--if you care, you have to keep it somewhere (usually in the
> > allocate memory) for yourself.
>
> So, why do those who program Forth need ALLOCATION ... ?
> [The question is really directed to Hugh, not you...]
>
> RP

It's a proposal that would support something similar to Pascal's
variant record type. From Hugh's description, his lists are composed
of varying node types. He would like the heap to support a length
query on the node without the node requiring to know its type and
hence length. That limits the proposal to allocation of memory from
the heap in discrete record-sized chunks, since asking for lengths
from non-heap memory, or asking for a size from n nodes allocated with
a single call, would get erroneous results.

If that's not what was being proposed, perhaps Hugh could clarify.

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

#14758

On Aug 3, 5:36 am, Alex McDonald <b...@rivadpm.com> wrote:
> On Aug 3, 11:58 am, "Rod Pemberton" <do_not_h...@notemailnot.cmm>
> wrote:
>
> > <van...@vsta.org> wrote in messagenews:a80emiF5f6U1@mid.individual.net...
>
> > ...
>
> > > This sounds more like a runtime thing.  malloc()
> > > records the size of the allocated object, so that free() can return its
> > > storage.  I don't think there's ever been an API to find out an allocated
> > > node's size--if you care, you have to keep it somewhere (usually in the
> > > allocate memory) for yourself.
>
> > So, why do those who program Forth need ALLOCATION ... ?
> > [The question is really directed to Hugh, not you...]
>
> > RP
>
> It's a proposal that would support something similar to Pascal's
> variant record type. From Hugh's description, his lists are composed
> of varying node types. He would like the heap to support a length
> query on the node without the node requiring to know its type and
> hence length. That limits the proposal to allocation of memory from
> the heap in discrete record-sized chunks, since asking for lengths
> from non-heap memory, or asking for a size from n nodes allocated with
> a single call, would get erroneous results.
>
> If that's not what was being proposed, perhaps Hugh could clarify.

Actually, in my novice package ALLOCATION works for both nodes in the
heap and nodes in the dictionary --- the nodes in the dictionary have
to have been defined with CONCRETE-ALLOCATE though, as CREATE doesn't
install the size cell in front of the node as ALLOCATION needs.

At the time of that RfD, I didn't have CONCRETE-ALLOCATE yet. I
thought that up later on. It doesn't matter anyway though, as the RfD
was going to get rejected no matter what.

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

#14750

vandys@vsta.org writes:

> Rod Pemberton <do_not_have@notemailnot.cmm> wrote:
>>> It doesn't have ALLOCATION for one thing (a function
>>> that returns the amount of memory in a node given the
>>> node's address).
>> That sounds _alot_ like C's sizeof()... on a node... at least to me.  So,
>> why don't you just implement C's SIZEOF for Forth?  ;-)
>
> No, sizeof() is an operator which compiles to a constant based on looking at
> the (compile time) types.  This sounds more like a runtime thing.  malloc()
> records the size of the allocated object, so that free() can return its
> storage.  I don't think there's ever been an API to find out an allocated
> node's size--if you care, you have to keep it somewhere (usually in the
> allocate memory) for yourself.

In some cases there exists API to find it, the only problem is that it
isn't exported for "hysterical raisins." "You have to keep it somewhere"
not because it is hard or it is impossible, it is due to the long
standing tradition of using lowest common denominator in C and records
of fixed size in other languages of Algol family. Some allocators may
require some refactoring, but at least if you look at jemalloc source,
you can easily find the relevant function. It is not hard to remove one
word ("static") and introduce function prototype. The only problem here
is change resistance.


-- 
HE CE3OH...

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

#15014

Hugh Aguilar asked:

> Does anybody know how to implement a heap on the modern x86
> processors?

A heap would look in my world as nothing else than allocated memory.
It now depends on the OS and required heap-size vs. available-size.

if its a hiding paged memory model:
you may not know if its in RAM or paged out on disk.

some slow applications could live with such virtual hideaway ...,
but speed aware code shouldn't accept swapped to disk memory anyway.

So your question may be more related to the OS involved rather than
to x86-CPUs, the latter (OS independant) allows everything desired.

My own OS (KESYS) never used nor needed any virtual RAM-space on disk.
As any application got its own data-space on disk anyway, I couldn't
find a reason to make a copy of this somewhere else on the disk ... :)

__
wolfgang

[toc] | [prev] | [standalone]

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

csiph-web