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

Groups > comp.lang.forth > #39659

Re: Extendable structure with inspection

Show all headers | View raw

on 08/06/2015 22:24:14, Bernd Paysan wrote:
> 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. 

Exactly. It looked like an application aide memoire rather than a useful
feature of the language.

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

On Windows that doesn't work (but you probably knew 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.
> 

This assumes a set of well ordered and user definable allocators. Windows
supports multiple heaps, uses different allocators for the same heap
dependant on the size of the request, supports reservation vs commit. A
Windows application that reserves but doesn't commit a huge chunk of
memory would be considered badly behaved. It requires backing storage,
builds page tables that are pinned but never referred to, and increases
TLB costs. To commit large areas would cause significant amounts of work,
since pages are zeroed for reasons of security; zeroing say 4GB is a non-
trivial start up cost. 

One could argue that Windows could use malloc. That adds a library (the
CRT or C runtime) and a layer of obfuscation over the underlying Windows
allocators. Windows does not have system wide user definable allocators;
at bottom the Windows allocators are used by the CRT.

The language does not need to accomodate any of this beyond ALLOCATE and
FREE. A Forth library that works directly with ALLOCATE and FREE leaves
the implementor complete freedom as to how and what facility to use.
malloc for you, a SLAB allocator for him, HeapAlloc for me.

A suitable Windows implementation is left as an exercise for the reader.
Here's mine.

\ Windows heap function calls
1 import: GetProcessHeap
3 import: HeapAlloc
3 import: HeapFree
4 import: HeapReAlloc

\ The memory allocation code uses HEAP_GENERATE_EXCEPTIONS rather than
returning \ false on the stack. The reason is simple; crashing on a known
exception is \ easier than a crash further down the line on some other
exception. Early & \ informative is best. But if you want ANS behavior,
call ANS-MEMORY

create process-heap           \ process heap address
    0 ,                      \  heap address
    HEAP_GENERATE_EXCEPTIONS ,  \ flag should be zero to pass ANS test

: ans-memory   ( -- )          [ process-heap cell+ ] literal off ;
: heap&flag@   ( -- fl heap )  process-heap 2@ ;
: allocate     ( n -- a f )    heap&flag@ call HeapAlloc dup 0= ;
: malloc       ( n -- a )      allocate throw_memallocfail ?throw ;
: free         ( a -- f )      heap&flag@ call HeapFree 0= ;
: release      ( a -- )        free throw_memrelfail ?throw ;
: realloc      ( n a -- a' f ) dup>r heap&flag@ call HeapReAlloc
                               ?dup if r>drop 0 else r> -1 then ;
: resize       ( a n -- a' f ) swap ?dup if realloc else allocate then ;
: init-malloc  ( -- )          call GetProcessHeap process-heap ! ;

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