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

Groups > comp.lang.forth > #39643

Re: Extendable structure with inspection

Show all headers | View raw

Anton Ertl wrote:

>>But the above means that it will not be standardised as say a controlled
>>word because those systems would have to admit that they can't implement
>>it. "We implement the total of the Forth language" would no longer be
>>true. So SIZE is kept out of the standard, and although you and I
>>implement the same word, its name would be different.
> 
> Why would it be different?  If you and Hugh cannot agree on a name
> (and probably not on a common specification, either), that's certainly
> not the fault of the standardization process; on the contrary, it
> would explain why there is no progress in standardizing this feature.

One of the problem of the SIZE proposal is that it's not well specified, 
which size.  Aparently, Hugh just wants to know how much memory the 
allocater actually used, to allow cloning of lists without knowing what kind 
of data is inside the list.  The other possible reason is to get what was 
actually allocated, which can be used to allocate strings and query the 
string length.  The second usage is not possible if you just return the size 
of the actual memory chunk, but it's more useful.

In current GLIBC, it's fairly easy to implement SIZE:

: SIZE ( addr -- len )  1 cells - @ -2 cells and ;

This hasn't changed since last time I looked at that, and that was when Hugh 
proposed his RfD.  We could run an automated test which checks if this 
works, and if not, do a fallback on a solution which stores another cell.  
So I don't agree that it is prohibitive to implement that.

A memory allocater which works like the one of GLIBC could as well store the 
actual size, and not the padded one, as doing the padding is a simple 
operation, and it's not really harmful to do that on free() as well.

However, I could think of a very different way on allocating small blocks, 
especially on a 64 bit machine: I'd use mmap to grab a pretty large chunk of 
memory, and then subdivide it into e.g. 256 regions, each of which is 
responsible for 1..256*16 bytes objects.  All objects greater 4k (one page) 
can use a different allocater, with more overhead per object.

Computing the size of the smaller ones is easy, just subtract the start 
address of the big mmap area, and then extract the part of the address which 
indicates the size.  One mmap on 64 bit Linux is limited to ~4GB, so if you 
run out of space and need another map, try to map it fixed on an address 
related to the previous map (that way, obtaining the size still works).

malloc() would first check the free list for that size, to give you the last 
freed block of that size (that's good for cache locality to always re-
allocate the last freed block; it has been touched recently); if the free-
list of that size is empty, return the first-unused pointer for that size, 
and increment that pointer.  free() just inserts the block into the free 
list for that size.

In this scheme, it's not reasonable to store the actual requested size, i.e. 
you only get the size with padding.  But the allocate/free operation could 
be really fast, and you don't waste any memory for storing the size.  The 
implementation is trivial, size effectivity is very high (only the alignment 
padding overhead), and LIFO reuse is cache friendly and makes use-after-free 
bugs obvious.

-- 
Bernd Paysan
"If you want it done right, you have to do it yourself"
net2o ID: kQusJzA;7*?t=uy@X}1GWr!+0qqp_Cn176t4(dQ*
http://bernd-paysan.de/

Back to comp.lang.forth | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Extendable structure with inspection humptydumpty <ouatubi@gmail.com> - 2015-06-02 13:29 -0700
  Re: Extendable structure with inspection anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-06-03 06:02 +0000
    Re: Extendable structure with inspection humptydumpty <ouatubi@gmail.com> - 2015-06-03 08:27 -0700
  Re: Extendable structure with inspection humptydumpty <ouatubi@gmail.com> - 2015-06-03 11:30 -0700
    Re: Extendable structure with inspection Raimond Dragomir <raimond.dragomir@gmail.com> - 2015-06-03 20:54 -0700
      Re: Extendable structure with inspection "Alex McDonald" <blog@rivadpm.com> - 2015-06-04 09:11 +0100
        Re: Extendable structure with inspection Raimond Dragomir <raimond.dragomir@gmail.com> - 2015-06-04 04:43 -0700
          Re: Extendable structure with inspection "Alex McDonald" <blog@rivadpm.com> - 2015-06-04 20:21 +0100
            Re: Extendable structure with inspection Raimond Dragomir <raimond.dragomir@gmail.com> - 2015-06-04 23:23 -0700
              Re: Extendable structure with inspection "Rod Pemberton" <boo@fasdfrewar.cdm> - 2015-06-05 03:40 -0400
              Re: Extendable structure with inspection "Alex McDonald" <blog@rivadpm.com> - 2015-06-05 15:31 +0100
                Re: Extendable structure with inspection Raimond Dragomir <raimond.dragomir@gmail.com> - 2015-06-05 08:48 -0700
                Re: Extendable structure with inspection "Alex McDonald" <blog@rivadpm.com> - 2015-06-05 18:10 +0100
                Re: Extendable structure with inspection albert@spenarnc.xs4all.nl (Albert van der Horst) - 2015-06-06 10:46 +0000
                Re: Extendable structure with inspection hughaguilar96@gmail.com - 2015-06-05 17:53 -0700
                Re: Extendable structure with inspection albert@spenarnc.xs4all.nl (Albert van der Horst) - 2015-06-06 10:56 +0000
                Re: Extendable structure with inspection anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-06-06 16:00 +0000
                Re: Extendable structure with inspection hughaguilar96@gmail.com - 2015-06-06 19:35 -0700
                Re: Extendable structure with inspection "Alex McDonald" <blog@rivadpm.com> - 2015-06-07 10:51 +0100
                Re: Extendable structure with inspection Bernd Paysan <bernd.paysan@gmx.de> - 2015-06-08 23:24 +0200
                SIZE RfD: Re: Extendable structure with inspection anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2015-06-09 07:56 +0000
                Re: Extendable structure with inspection "Alex McDonald" <blog@rivadpm.com> - 2015-06-09 12:09 +0100
                Re: Extendable structure with inspection Bernd Paysan <bernd.paysan@gmx.de> - 2015-06-09 23:25 +0200
              Re: Extendable structure with inspection "Elizabeth D. Rather" <erather@forth.com> - 2015-06-05 07:53 -1000
                Re: Extendable structure with inspection hughaguilar96@gmail.com - 2015-06-05 17:34 -0700
      Re: Extendable structure with inspection humptydumpty <ouatubi@gmail.com> - 2015-06-05 00:40 -0700
  Re: Extendable structure with inspection humptydumpty <ouatubi@gmail.com> - 2015-06-10 12:16 -0700

csiph-web