Re: heap implementation

From	Paul Rubin <no.email@nospam.invalid>
Newsgroups	comp.lang.forth
Subject	Re: heap implementation
References	(5 earlier) <2012Aug1.170907@mips.complang.tuwien.ac.at> <7xy5lymwrl.fsf@ruckus.brouhaha.com> <2012Aug1.183425@mips.complang.tuwien.ac.at> <7xy5ly355t.fsf@ruckus.brouhaha.com> <2012Aug2.164829@mips.complang.tuwien.ac.at>
Date	2012-08-02 14:37 -0700
Message-ID	<7xfw85otzy.fsf@ruckus.brouhaha.com> (permalink)
Organization	Nightsong/Fort GNOX

Show all headers | View raw

anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
> I would not use a tree for the table, just a big block; then the check
> for validity can be performed in constant time. 

You mean a preallocated big block that could hold all the pointers
that might potentially be allocated all at once?  You might have
to reserve 100's of MB, or even GB.  Even though it might not allocate
real pages, it still seems awful.

A tree isn't needed: I think a linked list of blocks is good enough.
Just prepend new blocks to the linked list and remember where the newest
one is.  When you delete a pointer from the middle of some block, pop
and copy the most recent pointer from the newest block, into the
now-freed slot.  If that makes the block become empty, release it after
following its link to get to the previous block.  All these operations
are constant time (you do need a way to allocate these blocks...).

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

Of course that is also probabilistic (the definition of a conservative
gc).

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