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

Groups > comp.lang.c > #15264

Re: Memory management and custom allocator

Show all headers | View raw

On 1/1/2012 7:54 AM, BartC wrote:
> "Markus Wichmann" <nullplan@gmx.net> wrote in message
> news:f7s5t8-jo5.ln1@voyager.wichi.de.vu...
>> On 31.12.2011 18:52, FtM wrote:
>
>>> Simply because it can't know if I'm going to do 200 little allocations
>>> or 1 big one.
>
>> For one, it _never_ uses brk(). That syscall is just plain old and does
>> nothing mmap() couldn't do better. Then it has linked lists prepared for
>> objects of sizes of powers of two, starting at 16 and stopping at 2048.
>
> That exactly what I do in my own allocator! Except I stop at 1024.
> Although I probably manage them very differently, for example once a
> small block size is allocated, say 64 bytes, it always stays that size.

     Sounds like a recipe for internal fragmentation, but YMMV.

> And one thing about malloc() I don't like, are the overheads in having
> to remember the block sizes; if I allocate 16 bytes, malloc() seems to
> reserve either 20 or, more often, 24 bytes on the few compilers I've
> tried. That's a 50% overhead!

     It's only significant if you have many such small allocations.
Even if so, a malloc() implementation can find other ways to remember
the size than by storing it explicitly.  For example, malloc() might
set aside regions of memory dedicated to "small" allocations: If an
pointer aims at an address anyhere in [A1,A1+N1), [A2,A2+N2), ... it
could simply be "known" to point at a 32-byte block.  (The test can't
be done efficiently in portable C, but a malloc() implementation need
not be portable, nor written in C.)

> Also if you're being sensible and trying to keep to power-of-two
> allocations, this 4- or 8-byte overhead is going to screw that up.

     What's "sensible" about allocating in powers of two?  Why should
you allocate 128 bytes to hold a line of input, rather than 100 or
80 or 250?  Programmers are numerologically superstitious.

> My allocators have never stored a block size, and it has never really
> been a problem. Either you will know the size (a struct for example), or
> you need to keep track of it yourself, in which case it is very handy
> when you have an allocation that can grow in never having to keep
> running back to realloc().

     If your allocators never store block sizes, it follows that free()
cannot recycle a released block for re-use by a subsequent malloc(),
because it does not know whether the freed block is big enough to
satisfy the malloc() request.  (Re-computing the size by examining the
addresses of nearby busy and free blocks counts as "storing the size"
in my book, just encoding it deviously.)

     An allocator with a different API -- one whose free()-substitute
takes the block size as a parameter -- could recycle blocks.  But now
you're no longer talking about the O.P.'s drop-in replacement for the
API as it stands.

> As an illustration, take this simple example of a string growing from
> one to ten million characters:
>
> #include <stdio.h>
> #include <stdlib.h>
> #include <string.h>
>
> int main(void)
> {
> char *p;
> int i,len;
>
> p=malloc(1);
> *p=0;
> len=0;
>
> for (i=1; i<=10000000; ++i) {
> ++len;
> p=realloc(p,len+1);

     Side note: Never call realloc() this way in real code, because if
it returns NULL you'll have lost your only pointer to the original
block; you won't even be able to free() it any more.

> p[len-1]='*';
> p[len]=0;
> // puts(p);
> }

     With an allocator that does not store the block size, this will
necessarily take a long time, for several reasons:

     - Since realloc() does not know how long the block at `p' is, it
       cannot tell whether there's any slop at the end that the block
       could grow into without moving.  Therefore, every realloc() call
       must allocate a new block and copy the old contents into it.

     - Since realloc() does not know how long the old block is, it
       must copy `len+1' bytes from the old block to the new, even
       though that's more than the old block holds.  (We'll assume a
       non-portable implementation can get away with copying the non-
       existent bytes.)  Total amount copied: 2+...+10000001 bytes;
       that's fifty terabytes.

     - Since realloc() does not know how long the old block was, it
       cannot re-use that memory to satisfy subsequent requests.  Thus,
       every call allocates a brand-new block and makes the old block
       unavailable.  Total memory allocated: 1+2+...+10000001 bytes.
       50TB to store a 10MB string is an overhead of fifty million
       percent -- and you groused about a mere fifty???!

-- 
Eric Sosman
esosman@ieee-dot-org.invalid

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

Thread

[Slightly OT] Memory management and custom allocator FtM <fmassei@gmail.com> - 2011-12-31 06:56 -0800
  Re: [Slightly OT] Memory management and custom allocator Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-12-31 11:08 -0500
    Re: Memory management and custom allocator FtM <fmassei@gmail.com> - 2011-12-31 08:28 -0800
  Re: [Slightly OT] Memory management and custom allocator Johann Klammer <klammerr@NOSPAM.aon.at> - 2011-12-31 17:39 +0100
    Re: Memory management and custom allocator FtM <fmassei@gmail.com> - 2011-12-31 08:55 -0800
      Re: Memory management and custom allocator Johann Klammer <klammerr@NOSPAM.aon.at> - 2011-12-31 19:01 +0100
        Re: Memory management and custom allocator Kaz Kylheku <kaz@kylheku.com> - 2011-12-31 18:31 +0000
  Re: [Slightly OT] Memory management and custom allocator Kaz Kylheku <kaz@kylheku.com> - 2011-12-31 17:24 +0000
    Re: Memory management and custom allocator FtM <fmassei@gmail.com> - 2011-12-31 09:52 -0800
      Re: Memory management and custom allocator Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-12-31 14:30 -0500
      Re: Memory management and custom allocator Markus Wichmann <nullplan@gmx.net> - 2012-01-01 12:21 +0100
        Re: Memory management and custom allocator "BartC" <bc@freeuk.com> - 2012-01-01 12:54 +0000
          Re: Memory management and custom allocator Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-01-01 09:03 -0500
            Re: Memory management and custom allocator "BartC" <bc@freeuk.com> - 2012-01-01 16:23 +0000
            Re: Memory management and custom allocator jgk@panix.com (Joe keane) - 2012-01-01 21:41 +0000
              Re: Memory management and custom allocator Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-01-02 08:10 -0500
                Re: Memory management and custom allocator "BartC" <bc@freeuk.com> - 2012-01-02 14:07 +0000
                Re: Memory management and custom allocator Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-01-02 09:47 -0500
                Re: Memory management and custom allocator FtM <fmassei@gmail.com> - 2012-01-02 08:36 -0800
                Re: Memory management and custom allocator Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-01-02 13:43 -0500
                Re: Memory management and custom allocator FtM <fmassei@gmail.com> - 2012-01-02 11:38 -0800
                Re: Memory management and custom allocator jgk@panix.com (Joe keane) - 2012-01-03 13:14 +0000
                Re: Memory management and custom allocator 88888 Dihedral <dihedral88888@googlemail.com> - 2012-01-03 06:07 -0800
                Re: Memory management and custom allocator 88888 Dihedral <dihedral88888@googlemail.com> - 2012-01-05 17:06 -0800
                Re: Memory management and custom allocator "BartC" <bc@freeuk.com> - 2012-01-02 21:36 +0000
                Re: Memory management and custom allocator Kaz Kylheku <kaz@kylheku.com> - 2012-01-02 21:44 +0000
                Re: Memory management and custom allocator 88888 Dihedral <dihedral88888@googlemail.com> - 2012-01-02 23:10 -0800
                Re: Memory management and custom allocator Keith Thompson <kst-u@mib.org> - 2012-01-02 13:42 -0800
                Re: Memory management and custom allocator Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-01-02 17:38 -0500
                Re: Memory management and custom allocator jgk@panix.com (Joe keane) - 2012-01-02 21:45 +0000
                Re: Memory management and custom allocator Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-01-02 18:19 -0500
                Re: Memory management and custom allocator Keith Thompson <kst-u@mib.org> - 2012-01-02 15:42 -0800
                Re: Memory management and custom allocator "BartC" <bc@freeuk.com> - 2012-01-02 23:59 +0000
                Re: Memory management and custom allocator Kleuske <kleuske@nowhere.net> - 2012-01-03 11:38 +0000
                Re: Memory management and custom allocator "BartC" <bc@freeuk.com> - 2012-01-03 12:49 +0000
                Re: Memory management and custom allocator jgk@panix.com (Joe keane) - 2012-01-04 23:42 +0000
                Re: Memory management and custom allocator Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-01-04 20:23 -0500
                Re: Memory management and custom allocator Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2012-01-05 23:31 +0200
                Re: Memory management and custom allocator jgk@panix.com (Joe keane) - 2012-01-04 21:52 +0000
                Re: Memory management and custom allocator Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-01-04 20:31 -0500
                Re: Memory management and custom allocator "BartC" <bc@freeuk.com> - 2012-01-05 01:45 +0000
                Re: Memory management and custom allocator Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2012-01-07 05:55 +0200
                Re: Memory management and custom allocator "BartC" <bc@freeuk.com> - 2012-01-07 12:02 +0000
          Re: Memory management and custom allocator Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-01-01 09:08 -0500
            Re: Memory management and custom allocator FtM <fmassei@gmail.com> - 2012-01-01 10:08 -0800
              Re: Memory management and custom allocator "BartC" <bc@freeuk.com> - 2012-01-01 23:34 +0000
                Re: Memory management and custom allocator FtM <fmassei@gmail.com> - 2012-01-02 02:18 -0800
                Re: Memory management and custom allocator 88888 Dihedral <dihedral88888@googlemail.com> - 2012-01-02 02:34 -0800
                Re: Memory management and custom allocator FtM <fmassei@gmail.com> - 2012-01-02 02:43 -0800
                Re: Memory management and custom allocator 88888 Dihedral <dihedral88888@googlemail.com> - 2012-01-02 03:11 -0800
                Re: Memory management and custom allocator FtM <fmassei@gmail.com> - 2012-01-02 08:17 -0800
                Re: Memory management and custom allocator "BartC" <bc@freeuk.com> - 2012-01-02 11:40 +0000
                Re: Memory management and custom allocator FtM <fmassei@gmail.com> - 2012-01-02 08:27 -0800
          Re: Memory management and custom allocator "BartC" <bc@freeuk.com> - 2012-01-01 23:26 +0000
            Re: Memory management and custom allocator Ben Bacarisse <ben.usenet@bsb.me.uk> - 2012-01-01 23:54 +0000
              Re: Memory management and custom allocator "BartC" <bc@freeuk.com> - 2012-01-02 00:32 +0000
          Re: Memory management and custom allocator Kaz Kylheku <kaz@kylheku.com> - 2012-01-02 02:46 +0000
            Re: Memory management and custom allocator "BartC" <bc@freeuk.com> - 2012-01-02 11:53 +0000
              Re: Memory management and custom allocator Ben Bacarisse <ben.usenet@bsb.me.uk> - 2012-01-02 15:18 +0000
          Re: Memory management and custom allocator jgk@panix.com (Joe keane) - 2012-01-03 12:21 +0000
          Re: Memory management and custom allocator Karl Malbrain <malbrain@yahoo.com> - 2012-01-04 16:48 -0800
            Re: Memory management and custom allocator "BartC" <bc@freeuk.com> - 2012-01-05 01:36 +0000
  Re: [Slightly OT] Memory management and custom allocator "io_x" <a@b.c.invalid> - 2012-01-01 17:02 +0100
  Re: [Slightly OT] Memory management and custom allocator jgk@panix.com (Joe keane) - 2012-01-01 21:21 +0000
  Re: [Slightly OT] Memory management and custom allocator 88888 Dihedral <dihedral88888@googlemail.com> - 2012-01-01 21:01 -0800
  Re: [Slightly OT] Memory management and custom allocator 88888 Dihedral <dihedral88888@googlemail.com> - 2012-01-07 05:20 -0800

csiph-web