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 4 of 4 — ← Prev page 1 2 3 [4]

#15434 — Re: Memory management and custom allocator

On Jan 1, 4:54 am, "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.
>
> 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!
>
> 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.
>
> 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().
>
> 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);
>  p[len-1]='*';
>  p[len]=0;
> // puts(p);}
>
> printf("Length= %d\n",strlen(p));
>
> }
>
> 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).
>
> Using my strategy, of avoiding any calls to malloc or realloc unless
> absolutely necessary, and using that inside an interpreter, this bit of
> script took about 0.1 seconds:
>
> string a
>
> a:=""
> to 10 million do
>  a+:="*"
> od
> println "Length=",a.len
>
> Of course, real C code wouldn't use such a naive strategy; it would also
> seek to minimise malloc()/realloc() calls, but that's also an admission that
> these calls have some overheads which it would be desirable to avoid. Hence
> I can understand the OP's attempt to experiment with his own versions.
>
> --
> Bartc

You can take a look at my bit-mapped memory allocator: code.google.com/
p/arena-memory-allocation
for an example of out-of-band storage of the block sizes.

Karl m

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

#15441 — Re: Memory management and custom allocator

"Karl Malbrain" <malbrain@yahoo.com> wrote in message 
news:0f8561ea-8775-4527-bb2d-da5fb5e0c5da@a17g2000yqj.googlegroups.com...


> You can take a look at my bit-mapped memory allocator: code.google.com/
> p/arena-memory-allocation
> for an example of out-of-band storage of the block sizes.

Thanks, I'll take a closer look later.

But a few things struck me immediately:

(1) It had a comment block at the beginning that actually said what the code 
was and gave a brief description, instead of the usual GPL waffle.

(2) It's vfree() function requires the size to be supplied, just like mine 
does! So I'm not alone in thinking the way C does it is not the only way.

(3) It has plenty of powers-of-two sprinkled about. With the comments in 
this thread I was starting to feel like some sort of dinosaur.

-- 
Bartc 

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

#15266

"FtM" <fmassei@gmail.com> ha scritto nel messaggio
news:911c685c-3bf9-4079-bf61-66342d8a8c2c@u6g2000vbc.googlegroups.com...
> [xpost comp.lang.c, comp.unix.programmer, comp.os.ms-
> windows.programmer.win32]
> Hello NG,
> I have a very specific question, but first of all I describe you what
> I'm facing as I'm open to alternative general solutions..
> I'm refactoring some old C code that deals with very basilar data
> structures (like lists, priority queues, hashtables and so on) that
> pretends to be very portable. Regarding the memory management, I have
> an internal wrapper that, on *nix and windows systems, maps the malloc/
> calloc/realloc/free functions one-to-one to the default ones, but it's
> possibile to switch to another custom allocator that works pretty much
> as a standard allocator (a big chunk of memory splitted/joined, tought
> for embedded systems).
> I would like to implement my custom allocator for the *nix and windows
> systems too (of course loosing some portability for performance gain),
> and maybe implement something like the C++ allocators to improve the
> memory management of the different algorithms (like rare large
> allocations on vectors / frequent small allocations on lists), but
> I've some questions:

i'm just an hobby programmer... my vew is
the point of start is the the malloc-free functions in
the K&R2 book; and think about them

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

#15281

In article <911c685c-3bf9-4079-bf61-66342d8a8c2c@u6g2000vbc.googlegroups.com>,
FtM  <fmassei@gmail.com> wrote:
>- Does all of this make any sense? :-)

IMHE this come up when

a) you are not pleased with the default functions' time or space
overhead
b) you like to control things
c) you want the 'memory' in memory-mapped files
d) you want to use shared memory

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

#15297

FtM於 2011年12月31日星期六UTC+8下午10時56分53秒寫道：
> [xpost comp.lang.c, comp.unix.programmer, comp.os.ms-
> windows.programmer.win32]
> Hello NG,
> I have a very specific question, but first of all I describe you what
> I'm facing as I'm open to alternative general solutions..
> I'm refactoring some old C code that deals with very basilar data
> structures (like lists, priority queues, hashtables and so on) that
> pretends to be very portable. Regarding the memory management, I have
> an internal wrapper that, on *nix and windows systems, maps the malloc/
> calloc/realloc/free functions one-to-one to the default ones, but it's
> possibile to switch to another custom allocator that works pretty much
> as a standard allocator (a big chunk of memory splitted/joined, tought
> for embedded systems).
> I would like to implement my custom allocator for the *nix and windows
> systems too (of course loosing some portability for performance gain),
> and maybe implement something like the C++ allocators to improve the
> memory management of the different algorithms (like rare large
> allocations on vectors / frequent small allocations on lists), but
> I've some questions:
> - In these systems, to have decent performances, I was thinking to
> allocate page-sized (and page-aligned) chunks to have small
> allocations in the same page, but how is it possible to request some
> memory with this characteristics? Will it help the OS memory manager?
> - Does all of this make any sense? :-)
> Thanks for any suggestion!
> Ciao!
> 
> P.S. I don't really have the necessity of a "performance boost", but
> I'm dealing with a general, low-level and already used library, and as
> long as I'm refactoring the code I'd like to do it the better possible
> way ;-)

Kind of interesting here. I thought you were  describing a customized 
heap manager that can support page swapping to some file in the hard disk. 

A graph of nodes of buffers is required. 

If you don't have to page out to the secondary storage system, then 
the malloc, memcpy, memset and  free in the GCC source code are available.  

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

#15539

FtM於 2011年12月31日星期六UTC+8下午10時56分53秒寫道：
> [xpost comp.lang.c, comp.unix.programmer, comp.os.ms-
> windows.programmer.win32]
> Hello NG,
> I have a very specific question, but first of all I describe you what
> I'm facing as I'm open to alternative general solutions..
> I'm refactoring some old C code that deals with very basilar data
> structures (like lists, priority queues, hashtables and so on) that
> pretends to be very portable. Regarding the memory management, I have
> an internal wrapper that, on *nix and windows systems, maps the malloc/
> calloc/realloc/free functions one-to-one to the default ones, but it's
> possibile to switch to another custom allocator that works pretty much
> as a standard allocator (a big chunk of memory splitted/joined, tought
> for embedded systems).
> I would like to implement my custom allocator for the *nix and windows
> systems too (of course loosing some portability for performance gain),
> and maybe implement something like the C++ allocators to improve the
> memory management of the different algorithms (like rare large
> allocations on vectors / frequent small allocations on lists), but
> I've some questions:
> - In these systems, to have decent performances, I was thinking to
> allocate page-sized (and page-aligned) chunks to have small
> allocations in the same page, but how is it possible to request some
> memory with this characteristics? Will it help the OS memory manager?
> - Does all of this make any sense? :-)
> Thanks for any suggestion!
> Ciao!
> 
> P.S. I don't really have the necessity of a "performance boost", but
> I'm dealing with a general, low-level and already used library, and as
> long as I'm refactoring the code I'd like to do it the better possible
> way ;-)

I mean the allocation requests for the heap space can be modeled 
as a discrete random process X[n] for n=0,1,2,3... in an application 
and so is the free process Y[m] for m=0, 1,2,3 .... 

Therefore the amount of memory  used can be counted as 

for(i=0, s1=0;i<n;i++) s1+=X[i];
for(i=0, s2=0;i<m;i++) s2+=Y[i]; 

The number s1-s2 is the amount of space used is another random process, too. 

The OS part does not know the two random processes better than the programmer 
who is the author of the application. Thus a customized heap manager 
can beat the OS as proved in the above. 
  

[toc] | [prev] | [standalone]

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

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

csiph-web