Re: heap implementation

From	anton@mips.complang.tuwien.ac.at (Anton Ertl)
Newsgroups	comp.lang.forth
Subject	Re: heap implementation
Date	2012-08-03 13:58 +0000
Organization	Institut fuer Computersprachen, Technische Universitaet Wien
Message-ID	<2012Aug3.155806@mips.complang.tuwien.ac.at> (permalink)
References	(5 earlier) <7xy5lymwrl.fsf@ruckus.brouhaha.com> <2012Aug1.183425@mips.complang.tuwien.ac.at> <7xy5ly355t.fsf@ruckus.brouhaha.com> <2012Aug2.164829@mips.complang.tuwien.ac.at> <7xfw85otzy.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:
>> 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?

Yes, but some variations are possible:

1) Start small, and double the size when it becomes too small; this
may incur the costs of relocation, though (either redo the pointers
when the size is doubled, or store offsets into the table instead of
pointers).

2) Use an expandable memory area (e.g., sbrk() in Unix, and mmap for
the data blocks).

>You might have
>to reserve 100's of MB, or even GB.  Even though it might not allocate
>real pages, it still seems awful.

Why?

Unused virtual memory costs very little.  Let's see what 1TB costs:

[~:77867] time gforth -e bye

real    0m0.007s
user    0m0.008s
sys     0m0.004s
[~:77868] time gforth -m 1T -e bye

real    0m0.007s
user    0m0.004s
sys     0m0.004s

I.e., time difference in the noise.

USER       PID %CPU %MEM    VSZ   RSS TTY      STAT START   TIME COMMAND
anton     6119  0.0  0.0 1073755196 1544 pts/0 S+   16:17   0:00 gforth -m 1T
anton     6142  0.0  0.0  21564  1532 pts/0    S+   16:18   0:00 gforth

And a whopping 12KB difference in resident set size.

The strategy is admittedly limited in the platforms it works on, but
on those platforms it's a good strategy.

>A tree isn't needed: I think a linked list of blocks is good enough.

In order to perform the check we need to determine if the validation
pointer points to an address in one of the blocks (otherwise you can
get false positives).  If we keep the extra data in one block, we can
do this with a simple WITHIN.  If we keep it in a tree, we need a tree
search (no longer constant time); if we keep it in a list, we need a
linear search (linear cost).

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

The check is reliable.  Of course success still does not guarantee
that the value is a pointer, so I could have just as well used a
probabilistic method that may produce false positives (but must not
produce false negatives), but I didn't; there would be no advantage.

- 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