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

Groups > comp.lang.c > #15245 > unrolled thread

[Slightly OT] Memory management and custom allocator

Back to article view | Back to comp.lang.c

Contents

  [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

Page 3 of 4 — ← Prev page 1 2 [3] 4  Next page →

#15442 — Re: Memory management and custom allocator

"Eric Sosman" <esosman@ieee-dot-org.invalid> wrote in message
news:je2uhu$6s5$1@dont-email.me...
> On 1/4/2012 4:52 PM, Joe keane wrote:
>> In article<jdsact$nr6$1@dont-email.me>,
>> Eric Sosman<esosman@ieee-dot-org.invalid>  wrote:
>>>      If you have a forty-four-byte struct and allocate sixty-four
>>> bytes to hold it, how have you avoided *either* sort of "waste?"
>>
>> If the cache line is 16 bytes, we know that each object will take only
>> three lines; the fourth is never used [it may be worse with the VM].
>> For this case 48 would work just as well (the compiler will do that for
>> you if it thinks 8-byte alignment is a good idea).  But then if the
>> cache line is 32 bytes, same argument applies.
>
>     All I can say is that you and I have divergent notions of
> efficiency.  I'm thinking "I can run over the entire array with
> just N*44/C cache misses; Joe would prefer N*64/C."  That is, I
> think you'll incur 46% more cache misses than I will.  Tell me
> again, please, what I have wasted by using 31% fewer cache line
> loads than you would?

I think he means that the last 16-bytes of the 64 might never be accessed,
so will never be fetched from memory in the first place; there is no cache
miss.

(That does depend on how the 64-bytes are used; if the whole struct is
copied, the compiler might access all 64-bytes anyway.)

And if the cache blocks are 32-bytes, then it doesn't matter.

>     I'm also thinking "I need N*44/P pages for my array; Joe would
> rather use N*64/P."  That is, I think your working set size will
> be 46% larger than mine, your likelihood of taking a page fault
> will be 46% greater than mine.  Tell me again, please, what have
> I wasted by using 31% fewer memory pages?

No one was advocating wasting 20 bytes, but finding a use for them, perhaps
moving data there that would have been stored elsewhere.

>     It's an odd sort of "waste" that spends fewer resources.

If you had a heavily used struct, and it turned out it had 65 bytes, that
wouldn't bother you any? You wouldn't try and get it down to 64?

-- 
Bartc 

[toc] | [prev] | [next] | [standalone]

#15519 — Re: Memory management and custom allocator

"BartC" <bc@freeuk.com> writes:
> "Eric Sosman" <esosman@ieee-dot-org.invalid> wrote in message
> news:je2uhu$6s5$1@dont-email.me...
> > On 1/4/2012 4:52 PM, Joe keane wrote:
> >> In article<jdsact$nr6$1@dont-email.me>,
> >> Eric Sosman<esosman@ieee-dot-org.invalid>  wrote:
> >>>      If you have a forty-four-byte struct and allocate sixty-four
> >>> bytes to hold it, how have you avoided *either* sort of "waste?"
> >>
> >> If the cache line is 16 bytes, we know that each object will take only
> >> three lines; the fourth is never used [it may be worse with the VM].
> >> For this case 48 would work just as well (the compiler will do that for
> >> you if it thinks 8-byte alignment is a good idea).  But then if the
> >> cache line is 32 bytes, same argument applies.
> >
> >     All I can say is that you and I have divergent notions of
> > efficiency.  I'm thinking "I can run over the entire array with
> > just N*44/C cache misses; Joe would prefer N*64/C."  That is, I
> > think you'll incur 46% more cache misses than I will.  Tell me
> > again, please, what I have wasted by using 31% fewer cache line
> > loads than you would?
> 
> I think he means that the last 16-bytes of the 64 might never be accessed,
> so will never be fetched from memory in the first place; there is no cache
> miss.

Were there to be no hits on google for "64 bytes (one cache line)", then 
you might have a point. The fact that most of such hits refer to the single
most popular general purpose computer architecture in the world diminishes
your point significantly. Those bytes are being pulled into the cache whether
you access them or not.
 
> (That does depend on how the 64-bytes are used; if the whole struct is
> copied, the compiler might access all 64-bytes anyway.)
> 
> And if the cache blocks are 32-bytes, then it doesn't matter.

Nonsense. An adjacent bunch of Eric's structures being pulled into the 
working set will displace fewer cache lines than the same number of your
structs. It's only if the cache lines are 16 bytes (i.e. not any of the
half dozen architectures I've worked with in recent years) that both
will cause 48 bytes to be churned.

> >     I'm also thinking "I need N*44/P pages for my array; Joe would
> > rather use N*64/P."  That is, I think your working set size will
> > be 46% larger than mine, your likelihood of taking a page fault
> > will be 46% greater than mine.  Tell me again, please, what have
> > I wasted by using 31% fewer memory pages?
> 
> No one was advocating wasting 20 bytes, but finding a use for them, perhaps
> moving data there that would have been stored elsewhere.

How about the "use" of "still being available for subsequent allocations"?

> >     It's an odd sort of "waste" that spends fewer resources.
> 
> If you had a heavily used struct, and it turned out it had 65 bytes, that
> wouldn't bother you any? You wouldn't try and get it down to 64?

Straw man.

Phil
-- 
Unix is simple. It just takes a genius to understand its simplicity
-- Dennis Ritchie (1941-2011), Unix Co-Creator

[toc] | [prev] | [next] | [standalone]

#15538 — Re: Memory management and custom allocator

"Phil Carmody" <thefatphil_demunged@yahoo.co.uk> wrote in message 
news:87obugw4i7.fsf@bazspaz.fatphil.org...
> "BartC" <bc@freeuk.com> writes:

>> I think he means that the last 16-bytes of the 64 might never be 
>> accessed,
>> so will never be fetched from memory in the first place; there is no 
>> cache
>> miss.
>
> Were there to be no hits on google for "64 bytes (one cache line)", then
> you might have a point. The fact that most of such hits refer to the 
> single
> most popular general purpose computer architecture in the world diminishes
> your point significantly. Those bytes are being pulled into the cache 
> whether
> you access them or not.

I've no idea what cache-line sizes are being used these days. If it's 64 
instead of 16 then perhaps we'd be talking about a 176-byte versus a 
256-byte struct instead.

>> And if the cache blocks are 32-bytes, then it doesn't matter.
>
> Nonsense. An adjacent bunch of Eric's structures being pulled into the
> working set will displace fewer cache lines than the same number of your
> structs.

That's true, if you touch any element of a 64-byte struct, and the cache 
lines are 64-bytes, and the struct is aligned on 64-bytes, then a set of, 
say, 1000 serial accesses will require 1000 memory fetches, instead of 688 
if they were only 44 bytes. That's why I advocated not wasting that extra 20 
bytes per struct. (In fact I suggested making do with 32 in the first 
place.)

The problem with 44-bytes in this case, is that if you're touching two parts 
of the struct at a time, and you're doing random access (which is what 
arrays are for), you'll frequently be fetching two cache lines instead of 
one, as the structs will straddle a 64-byte boundary.

And if you are only touching one member of the struct at a time, and are 
doing serial accesses, then perhaps you'd be better off using a set of 
parallel arrays, for at least some of the struct members. If a field is 
4-bytes wide, then that would require only about 1/11 of the memory fetches 
as the 44-byte struct.

You're quite likely to find these narrower array elements happen to have 
power-of-two widths..

Anyway, look at this struct (compiled with default padding):

struct record{
 char c1;
 double d1;
 char c2;
 double d2;
 char c3;
 double d3;
 char c4;
} x;

On my machine, these 28 bytes end up occupying 56, exactly double!

Rearrange these fields so all the small ones are at the end, and still you 
get 32, not 28!

Wasting bytes is obviously OK when the compiler does it...

(BTW I put that struct into another language, and it consistently gave a 
size of 28 bytes no matter how the fields are ordered.)

-- 
Bartc 

[toc] | [prev] | [next] | [standalone]

#15265 — Re: Memory management and custom allocator

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

[toc] | [prev] | [next] | [standalone]

#15268 — Re: Memory management and custom allocator

On Jan 2, 1:54 pm, "BartC" <b...@freeuk.com> wrote:
> "Markus Wichmann" <nullp...@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.
>

Ok, thank you all for the suggestions (that basically are "use malloc
and don't bother"). I know that the allocation functions are great as
they are: I'm using them right now and I have no problems at all! I
was only trying to expand the code from the embedded part that
contains some code that I already have, that's it. More on, I already
have some handlers that help me debugging the algorithms..

Anyway, regarding the allocator descriptions that Markus and BartC
gave, that's what I was thinking and partially already doing, let's
see if this makes more sense to you:
- first of all, I'm dealing with the memory allocation only *inside*
my library, so I don't need to build a general purpose allocator.
- inside, I'll have three different "objects": the first one is for
little allocations, the second one for the others, the third one for
the medium/big allocations that possibly will need to realloc(). The
third allocator follows the "normal" strategy (and could simply use
the system calls for that matter), while the first and the second one
could simply have some preallocated blocks and a vector to mark if
they are used or not, skipping the natural overhead needed by the
general purpose allocator.

What do you think about this approach (despite the fact that in the
end it probably gives no noticeable advantages)?
Ciao!

[toc] | [prev] | [next] | [standalone]

#15291 — Re: Memory management and custom allocator

"FtM" <fmassei@gmail.com> wrote in message
news:433dd1ba-34f5-47d5-a7db-d4dbcda01939@cs7g2000vbb.googlegroups.com...

> - inside, I'll have three different "objects": the first one is for
> little allocations, the second one for the others, the third one for
> the medium/big allocations that possibly will need to realloc(). The
> third allocator follows the "normal" strategy (and could simply use
> the system calls for that matter), while the first and the second one
> could simply have some preallocated blocks and a vector to mark if
> they are used or not, skipping the natural overhead needed by the
> general purpose allocator.
>
> What do you think about this approach (despite the fact that in the
> end it probably gives no noticeable advantages)?

I don't think there's enough information here; what sort of sizes are the
three classes of allocator handling?

Will any of them always be a fixed size? Will they need deallocating? (As
sometimes this isn't necessary, or the pool of memory from which they're
drawn will be freed as one block.) What strategy will be used to grow the 
heap from which the the blocks will come; in fact does this heap need to 
grow? Where does the memory come from in the first place? Etc..

-- 
Bartc 

[toc] | [prev] | [next] | [standalone]

#15310 — Re: Memory management and custom allocator

On Jan 2, 12:34 am, "BartC" <b...@freeuk.com> wrote:
> "FtM" <fmas...@gmail.com> wrote in message
>
> news:433dd1ba-34f5-47d5-a7db-d4dbcda01939@cs7g2000vbb.googlegroups.com...
>
> > - inside, I'll have three different "objects": the first one is for
> > little allocations, the second one for the others, the third one for
> > the medium/big allocations that possibly will need to realloc(). The
> > third allocator follows the "normal" strategy (and could simply use
> > the system calls for that matter), while the first and the second one
> > could simply have some preallocated blocks and a vector to mark if
> > they are used or not, skipping the natural overhead needed by the
> > general purpose allocator.
>
> > What do you think about this approach (despite the fact that in the
> > end it probably gives no noticeable advantages)?
>
> I don't think there's enough information here; what sort of sizes are the
> three classes of allocator handling?
>

16<=x<=128 (little structures, one-shot char buffers, etc.)
128<x<=2048 (array of pointers, bigger structures, etc.)
x>2048 (realloc()atable memory)


> Will any of them always be a fixed size?

Yes, the first two types. (Of course, if a realloc() is requested for
a first or second type memory it should be switched to the third one,
but this is not likely to happen as the user (me) is aware of that
behaviour!). I didn't write it, but obviously I will have the
possibility to call the objects directly, choosing the preferred
allocation strategy.

> Will they need deallocating?

Sure they will. The first two by marking on their own map-vector, the
third by the usual way of joining adiacent free blocks.

> What strategy will be used to grow the
> heap from which the the blocks will come; in fact does this heap need to
> grow?

Each "object" will have some pages to start with; when one of them
fills its pages completely will ask the system for some more
(increasing its allocation vector on the fly too). I don't know the
"some" quantity, but I think no one do before runtime.. Making it a
compile-(or maybe run-)time parameter will help monitoring and testing
the overall performances, but this is just an idea.
Naturally, speaking of the first two "objects", the space of the
allocation vector should be taken into account, but as it is a bit-
masked vector it will occupy a very little space.

> Where does the memory come from in the first place?

mmap (thus even leaving the possibility to swap to persistent storage
or share the memory between processes).

Ciao!

[toc] | [prev] | [next] | [standalone]

#15311 — Re: Memory management and custom allocator

FtM於 2012年1月2日星期一UTC+8下午6時18分45秒寫道：
> On Jan 2, 12:34 am, "BartC" <b....@freeuk.com> wrote:
> > "FtM" <fma...@gmail.com> wrote in message
> >
> > news:433dd1ba-34f5-47d5-a7db-d4dbcda01939@cs7g2000vbb.googlegroups.com...
> >
> > > - inside, I'll have three different "objects": the first one is for
> > > little allocations, the second one for the others, the third one for
> > > the medium/big allocations that possibly will need to realloc(). The
> > > third allocator follows the "normal" strategy (and could simply use
> > > the system calls for that matter), while the first and the second one
> > > could simply have some preallocated blocks and a vector to mark if
> > > they are used or not, skipping the natural overhead needed by the
> > > general purpose allocator.
> >
> > > What do you think about this approach (despite the fact that in the
> > > end it probably gives no noticeable advantages)?
> >
> > I don't think there's enough information here; what sort of sizes are the
> > three classes of allocator handling?
> >
> 
> 16<=x<=128 (little structures, one-shot char buffers, etc.)
> 128<x<=2048 (array of pointers, bigger structures, etc.)
> x>2048 (realloc()atable memory)
> 
> 
> > Will any of them always be a fixed size?
> 
> Yes, the first two types. (Of course, if a realloc() is requested for
> a first or second type memory it should be switched to the third one,
> but this is not likely to happen as the user (me) is aware of that
> behaviour!). I didn't write it, but obviously I will have the
> possibility to call the objects directly, choosing the preferred
> allocation strategy.
> 
> > Will they need deallocating?
> 
> Sure they will. The first two by marking on their own map-vector, the
> third by the usual way of joining adiacent free blocks.
> 
> > What strategy will be used to grow the
> > heap from which the the blocks will come; in fact does this heap need to
> > grow?
> 
> Each "object" will have some pages to start with; when one of them
> fills its pages completely will ask the system for some more
> (increasing its allocation vector on the fly too). I don't know the
> "some" quantity, but I think no one do before runtime.. Making it a
> compile-(or maybe run-)time parameter will help monitoring and testing
> the overall performances, but this is just an idea.
> Naturally, speaking of the first two "objects", the space of the
> allocation vector should be taken into account, but as it is a bit-
> masked vector it will occupy a very little space.
> 
> > Where does the memory come from in the first place?
> 
> mmap (thus even leaving the possibility to swap to persistent storage
> or share the memory between processes).

This requires customized data compression modules not just the heap manager. 

If a program only uses 20 to 30 percent of the total heap space in a typical 
platform, then a lot people won't bother to write a new heap manager at all.   

> 
> Ciao!

[toc] | [prev] | [next] | [standalone]

#15312 — Re: Memory management and custom allocator

On Jan 2, 11:34 am, 88888 Dihedral <dihedral88...@googlemail.com>
wrote:
> FtM於 2012年1月2日星期一UTC+8下午6時18分45秒寫道：
>
> > > Where does the memory come from in the first place?
>
> > mmap (thus even leaving the possibility to swap to persistent storage
> > or share the memory between processes).
>
> This requires customized data compression modules not just the heap manager.
>

Maybe. Or maybe more disk space? :-) I don't think it's relevant
here..

> If a program only uses 20 to 30 percent of the total heap space in a typical
> platform, then a lot people won't bother to write a new heap manager at all.
>

I don't see your point.. In the OSes we were speaking about there's no
fixed "heap-space", the physical memory is "recycled" based on the
current needs.. Or you were thinking something different?

Ciao!

[toc] | [prev] | [next] | [standalone]

#15316 — Re: Memory management and custom allocator

FtM於 2012年1月2日星期一UTC+8下午6時43分33秒寫道：
> On Jan 2, 11:34 am, 88888 Dihedral <dihedr...@googlemail.com>
> wrote:
> > FtM於 2012年1月2日星期一UTC+8下午6時18分45秒寫道：
> >
> > > > Where does the memory come from in the first place?
> >
> > > mmap (thus even leaving the possibility to swap to persistent storage
> > > or share the memory between processes).
> >
> > This requires customized data compression modules not just the heap manager.
> >
> 
> Maybe. Or maybe more disk space? :-) I don't think it's relevant
> here..
> 
> > If a program only uses 20 to 30 percent of the total heap space in a typical
> > platform, then a lot people won't bother to write a new heap manager at all.
> >
> 
> I don't see your point.. In the OSes we were speaking about there's no
> fixed "heap-space", the physical memory is "recycled" based on the
> current needs.. Or you were thinking something different?
> 
> Ciao!

I think the heap space in a 32 bit platform is somewhat limited. 
Of course in the 64 bit OS a lot things will be different. 

But as long as the hard disk  and the dram  are both  of some finite sizes, 
I just model the heap space to be of a finite size  in my programs. 

I am not interested in trivial programs. 

[toc] | [prev] | [next] | [standalone]

#15325 — Re: Memory management and custom allocator

On Jan 2, 12:11 pm, 88888 Dihedral <dihedral88...@googlemail.com>
wrote:
> FtM於 2012年1月2日星期一UTC+8下午6時43分33秒寫道：
>
> > On Jan 2, 11:34 am, 88888 Dihedral <dihedr...@googlemail.com>
> > wrote:
> > > FtM於 2012年1月2日星期一UTC+8下午6時18分45秒寫道：
>
> > > > > Where does the memory come from in the first place?
>
> > > > mmap (thus even leaving the possibility to swap to persistent storage
> > > > or share the memory between processes).
>
> > > This requires customized data compression modules not just the heap manager.
>
> > Maybe. Or maybe more disk space? :-) I don't think it's relevant
> > here..
>
> > > If a program only uses 20 to 30 percent of the total heap space in a typical
> > > platform, then a lot people won't bother to write a new heap manager at all.
>
> > I don't see your point.. In the OSes we were speaking about there's no
> > fixed "heap-space", the physical memory is "recycled" based on the
> > current needs.. Or you were thinking something different?
>
> > Ciao!
>
> I think the heap space in a 32 bit platform is somewhat limited.
> Of course in the 64 bit OS a lot things will be different.
>

More bits == More space. So?

> But as long as the hard disk  and the dram  are both  of some finite sizes,
> I just model the heap space to be of a finite size  in my programs.
>

I don't think anyone deals with infinite spaces.

Ciao!

[toc] | [prev] | [next] | [standalone]

#15317 — Re: Memory management and custom allocator

"FtM" <fmassei@gmail.com> wrote in message 
news:8c4b9ed3-8f9f-47ae-a70f-cc803aa6cc79@d9g2000yqg.googlegroups.com...
> On Jan 2, 12:34 am, "BartC" <b...@freeuk.com> wrote:


>> What strategy will be used to grow the
>> heap from which the the blocks will come; in fact does this heap need to
>> grow?
>
> Each "object" will have some pages to start with; when one of them
> fills its pages completely will ask the system for some more
> (increasing its allocation vector on the fly too). I don't know the
> "some" quantity, but I think no one do before runtime.. Making it a
> compile-(or maybe run-)time parameter will help monitoring and testing
> the overall performances, but this is just an idea.
> Naturally, speaking of the first two "objects", the space of the
> allocation vector should be taken into account, but as it is a bit-
> masked vector it will occupy a very little space.
>
>> Where does the memory come from in the first place?
>
> mmap (thus even leaving the possibility to swap to persistent storage
> or share the memory between processes).

It sounds like you are more interesting in playing with the virtual memory 
side of things and doing your own paging.

Be aware that the OS tends to be take care of this, and does it rather well 
in conjunction with the hardware! (If you look in particular at the memory 
management routines on the msdn website, it can do it rather comprehensively 
too. I usually take one look then go back to the friendly little malloc, 
realloc and free functions of C.)

Also, if you just want to experiment, then possibly malloc() can provide the 
initial memory within which you can do your own allocations. Just ask for 
the largest block of memory you want to work with, and look for the first 
address within it where the bottom 12 bits are zero; that will likely be on 
a page boundary. (In a real program, malloc()ed memory may not grow in the 
way you might like, so your mmap() method might be needed.)

-- 
Bartc 

[toc] | [prev] | [next] | [standalone]

#15326 — Re: Memory management and custom allocator

On Jan 2, 12:40 pm, "BartC" <b...@freeuk.com> wrote:
> "FtM" <fmas...@gmail.com> wrote in message
>
> news:8c4b9ed3-8f9f-47ae-a70f-cc803aa6cc79@d9g2000yqg.googlegroups.com...
>
>
> > On Jan 2, 12:34 am, "BartC" <b...@freeuk.com> wrote:
> >> What strategy will be used to grow the
> >> heap from which the the blocks will come; in fact does this heap need to
> >> grow?
>
> > Each "object" will have some pages to start with; when one of them
> > fills its pages completely will ask the system for some more
> > (increasing its allocation vector on the fly too). I don't know the
> > "some" quantity, but I think no one do before runtime.. Making it a
> > compile-(or maybe run-)time parameter will help monitoring and testing
> > the overall performances, but this is just an idea.
> > Naturally, speaking of the first two "objects", the space of the
> > allocation vector should be taken into account, but as it is a bit-
> > masked vector it will occupy a very little space.
>
> >> Where does the memory come from in the first place?
>
> > mmap (thus even leaving the possibility to swap to persistent storage
> > or share the memory between processes).
>
> It sounds like you are more interesting in playing with the virtual memory
> side of things and doing your own paging.
>
> Be aware that the OS tends to be take care of this, and does it rather well
> in conjunction with the hardware! (If you look in particular at the memory
> management routines on the msdn website, it can do it rather comprehensively
> too. I usually take one look then go back to the friendly little malloc,
> realloc and free functions of C.)
>

Yeah, I know.. I have a strange intrinsic vision of the memory
management that is more low-level than the c-level, probably due to my
previous works.. I don't know if it's a "fortune" or not, but that's
why I start by directly asking for low-level facilities instead of
abstracting the real problems. Anyway, I think that porting some of
this logic one level up could help somehow..

> Also, if you just want to experiment, then possibly malloc() can provide the
> initial memory within which you can do your own allocations. Just ask for
> the largest block of memory you want to work with, and look for the first
> address within it where the bottom 12 bits are zero; that will likely be on
> a page boundary. (In a real program, malloc()ed memory may not grow in the
> way you might like, so your mmap() method might be needed.)
>

You made the right example: I didn't know if that was true or not!
Technically, a virtual page base address doesn't have to match the
physical page boundary..

Ciao!

[toc] | [prev] | [next] | [standalone]

#15290 — Re: Memory management and custom allocator

"BartC" <bc@freeuk.com> wrote in message 
news:LPYLq.355$EO5.173@newsfe26.ams2...

[growing a string from empty, to 10 million chars]
> char *p;
> int i,len;
>
> p=malloc(1);
> *p=0;
> len=0;
>
> for (i=1; i<=10000000; ++i) {
> ++len;
> p=realloc(p,len+1);
> p[len-1]='*';
> p[len]=0;
> }

> On three C compilers, this took about 12 seconds (on DMC, any length of 
> string resulted in a runtime of 0.4 seconds; a bit odd).

Measuring the number of times the value of p changes, with the slow 
compilers, this was respectively 2335, 2336, and 2337. With DMC, it was just 
46.

Clearly DMC overallocates more than the others (growing allocations by 
sqrt(2) apparently).

(My own code, which just uses doubling, will call a memory allocator only 
about 20 times, so doesn't have the overheads of calling a function like 
realloc() ten million times, hence it was quite quick even though it was 
interpreted (but heavily optimised too..))

So with an application with certain memory usage patterns, one 
implementation can dramatically outperform another. Another reason, even if 
not writing your own allocators, at least to not just use what's provided 
without question.

-- 
Bartc 

[toc] | [prev] | [next] | [standalone]

#15292 — Re: Memory management and custom allocator

"BartC" <bc@freeuk.com> writes:

> "BartC" <bc@freeuk.com> wrote in message
> news:LPYLq.355$EO5.173@newsfe26.ams2...
>
> [growing a string from empty, to 10 million chars]
>> char *p;
>> int i,len;
>>
>> p=malloc(1);
>> *p=0;
>> len=0;
>>
>> for (i=1; i<=10000000; ++i) {
>> ++len;
>> p=realloc(p,len+1);
>> p[len-1]='*';
>> p[len]=0;
>> }
>
>> On three C compilers, this took about 12 seconds (on DMC, any length
>> of string resulted in a runtime of 0.4 seconds; a bit odd).

On my system is takes, .15 seconds

> Measuring the number of times the value of p changes, with the slow
> compilers, this was respectively 2335, 2336, and 2337. With DMC, it
> was just 46.

and changes p 156 times.  (Off-topic extra: a C++ program using s += '*'
on a std::string takes 0.07s on the same machine.)

> Clearly DMC overallocates more than the others (growing allocations by
> sqrt(2) apparently).

I don't see how you can conclude that.  The allocated storage might be
able to grown (i.e. it is not initially over-allocated) without changing
the address.

<snip>
-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#15294 — Re: Memory management and custom allocator

"Ben Bacarisse" <ben.usenet@bsb.me.uk> wrote in message
news:0.0749b13cccb174981f23.20120101235442GMT.87ipkv7zct.fsf@bsb.me.uk...
> "BartC" <bc@freeuk.com> writes:

>>> for (i=1; i<=10000000; ++i) {
>>> p=realloc(p,len+1);

>>> On three C compilers, this took about 12 seconds (on DMC, any length
>>> of string resulted in a runtime of 0.4 seconds; a bit odd).
>
> On my system is takes, .15 seconds

>> Measuring the number of times the value of p changes, with the slow
>> compilers, this was respectively 2335, 2336, and 2337. With DMC, it
>> was just 46.
>
> and changes p 156 times.

Your implementation must be pretty good then, or maybe it's optimised a few
realloc() calls out.

Running the test by calling realloc() with the same argument (so no new
allocations are needed) still takes about 1 second on those three slow
compilers (gcc, lccwin-32 and Pelles C). Seems like two of them have ripped
off the other's inefficient realloc() implementation!

>  (Off-topic extra: a C++ program using s += '*'
> on a std::string takes 0.07s on the same machine.)

Sounds about right when calls to realloc() are minimised. The question I
suppose is how much buffering/allocation logic should be done outside of
malloc()/realloc(), or do you just let those functions do most of the work;
you can afford to do that with fast implementations like yours.

>> Clearly DMC overallocates more than the others (growing allocations by
>> sqrt(2) apparently).
>
> I don't see how you can conclude that.

Just a guess. The 46th root of ten million is around 1.42.

> The allocated storage might be
> able to grown (i.e. it is not initially over-allocated) without changing
> the address.

That's true; with nothing else going on memory-wise, even an over-allocated
block could be further expanded at the same location, depending on how
allocator works.

-- 
Bartc  

[toc] | [prev] | [next] | [standalone]

#15296 — Re: Memory management and custom allocator

On 2012-01-01, BartC <bc@freeuk.com> wrote:
> for (i=1; i<=10000000; ++i) {
>  ++len;
>  p=realloc(p,len+1);

Growing linearly, and, by one character, is silly.

You have O(N*N) behavior here.

If you grow exponentially (e.g. doubling the buffer), you get amortized O(N)
behavior.

I.e. this is a poor algorithm. It's the O(N*N) time that's killing this,
not malloc.

[toc] | [prev] | [next] | [standalone]

#15318 — Re: Memory management and custom allocator

"Kaz Kylheku" <kaz@kylheku.com> wrote in message
news:20120101184335.99@kylheku.com...
> On 2012-01-01, BartC <bc@freeuk.com> wrote:
>> for (i=1; i<=10000000; ++i) {
>>  ++len;
>>  p=realloc(p,len+1);
>
> Growing linearly, and, by one character, is silly.

Nevertheless, that's what the program wants to do. (As it happens I quite
often have to build strings this way, and without knowing the final size.)


> You have O(N*N) behavior here.
>
> If you grow exponentially (e.g. doubling the buffer), you get amortized
> O(N)
> behavior.

But do you worry about this stuff directly in your code, or let the
language's runtime take care of it, or have some intermediate functions deal
with these details?

(And in the case of a simple C string, there is nowhere to put any extra
information about what the current allocated size is; it doesn't even know
it's length!)

> I.e. this is a poor algorithm. It's the O(N*N) time that's killing this,
> not malloc.

Yet some C implementations coped reasonably enough:

"Ben Bacarisse" <ben.usenet@bsb.me.uk> wrote in message

> On my system is takes, .15 seconds

-- 
Bartc 

[toc] | [prev] | [next] | [standalone]

#15323 — Re: Memory management and custom allocator

"BartC" <bc@freeuk.com> writes:

> "Kaz Kylheku" <kaz@kylheku.com> wrote in message
<snip>
>> You have O(N*N) behavior here.
>>
>> If you grow exponentially (e.g. doubling the buffer), you get amortized
>> O(N)
>> behavior.
<snip>
>> I.e. this is a poor algorithm. It's the O(N*N) time that's killing this,
>> not malloc.
>
> Yet some C implementations coped reasonably enough:
>
> "Ben Bacarisse" <ben.usenet@bsb.me.uk> wrote in message
>
>> On my system is takes, .15 seconds

Though I made no attempt to determine the growth rate of the time.  It
may still have been quadratic, but fast quadratic.

However, it is in fact linear.  Judging by the number of times the
pointer is changed by realloc it is doing some kind of internal doubling
of the requested space.

The trouble is that you can't rely on this, so to get amortised linear
performance in portable C you have to do the exponential growth
yourself.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#15366 — Re: Memory management and custom allocator

In article <LPYLq.355$EO5.173@newsfe26.ams2>, BartC <bc@freeuk.com> wrote:
>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!

Agreed.  When i was doing memory allocation, if you ask for 16 bytes it
really was 16 bytes, plus some per-page control structures stage left.

Trick is all the objects on the same 'page' (not the same as a VM page,
you can make it what size seems to work best) are the same size!  So you
just need the page number, look it up in a hash table (don't worry, this
is very fast).

[toc] | [prev] | [next] | [standalone]

Page 3 of 4 — ← Prev page 1 2 [3] 4  Next page →

Back to top | Article view | comp.lang.c

csiph-web