heap implementation (was: Appending definition to another definition)

From	anton@mips.complang.tuwien.ac.at (Anton Ertl)
Newsgroups	comp.lang.forth
Subject	heap implementation (was: Appending definition to another definition)
Date	2012-08-02 14:48 +0000
Organization	Institut fuer Computersprachen, Technische Universitaet Wien
Message-ID	<2012Aug2.164829@mips.complang.tuwien.ac.at> (permalink)
References	(4 earlier) <2aeb4f5b-2266-485a-8845-a77051849ca2@googlegroups.com> <2012Aug1.170907@mips.complang.tuwien.ac.at> <7xy5lymwrl.fsf@ruckus.brouhaha.com> <2012Aug1.183425@mips.complang.tuwien.ac.at> <7xy5ly355t.fsf@ruckus.brouhaha.com>

Show all headers | View raw

Paul Rubin <no.email@nospam.invalid> writes:
>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.

Two or three cells extra for just this purpose is not what I consider
efficient.  And it would still be probabilistic.

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

That's better: It still costs two cells per ALLOCATEd block, but at
least it's not probabilistic.

I would not use a tree for the table, just a big block; then the check
for validity can be performed in constant time.  Getting the big block
may be a problem in some environments, but with a large address space
(64 bits) and an OS that supports memory overcommitment it's a
non-issue.  In smaller environments one might grow that block towards
bigger addresses and grow the ALLOCATEd memory towards smaller
addresses.

Still, the space overhead of that approach is considerable for small
ALLOCATEd blocks, which are frequent.

I thought a little more about this problem and remembered that I have
already solved it, in the allocator used in my garbage collector.  The
garbage collector is conservative, so I need a way to check if a value
X can be the address of an allocated block.

I solved the problem as follows: for each grain (of, say, 8 bytes),
there are two bits (stored elsewhere): One says if the grain is at the
start of a block (this provides information about the length of the
block), the other says whether the block starting at the grain is
occupied or free.  These bits are stored in separate areas, which has
similar issues as the table discussed above.

The check whether an address points to an ALLOCATEd block can be
performed in constant time.  The space overhead is 3% for 8-byte
granularity.  To achieve the same space efficiency with a system that
needs three cells per block (one for the block size and two for the
two pointers mentioned above), the average block size would have to be
96 cells.

One could also combine the two systems: Have an allocator for blocks
up to 96 cells that uses my approach and one for larger blocks that
uses your approach; put the small blocks in one area of the address
space that does not contain any big blocks, then the address check can
just decide which check to use with a simple WITHIN check.

Implementing all that is left as an exercise to the reader:-)

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

Thread

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

csiph-web