Re: Memory management and custom allocator

From	Markus Wichmann <nullplan@gmx.net>
Newsgroups	comp.lang.c
Subject	Re: Memory management and custom allocator
Date	2012-01-01 12:21 +0100
Organization	Aioe.org NNTP Server
Message-ID	<f7s5t8-jo5.ln1@voyager.wichi.de.vu> (permalink)
References	<911c685c-3bf9-4079-bf61-66342d8a8c2c@u6g2000vbc.googlegroups.com> <20111231091520.131@kylheku.com> <67cb95d9-a8ef-4e34-9def-a5163e008862@n6g2000vbg.googlegroups.com>

Show all headers | View raw

On 31.12.2011 18:52, FtM wrote:
> On Dec 31, 6:24 pm, Kaz Kylheku <k...@kylheku.com> wrote:
>> On 2011-12-31, FtM <fmas...@gmail.com> wrote:
>>
>>> 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
>>
>> What makes you think that your malloc doesn't already handle
>> such cases?
>>
> 
> Simply because it can't know if I'm going to do 200 little allocations
> or 1 big one. Even if it has the most neat heuristic ever, the libc
> (or the kernel) exposing a simple specific function/syscall would do
> its job way better. Part of the question was about this hypothetical
> function.
> 

malloc() is already optimized to exactly those cases, as these are the
by far most common ones: Either you want a storage area, the size of
which is determined at run time, then you will probably have one big
allocation, or you are using fancy data structures other than dynamic
arrays (that includes, but is not limited to, linked lists, trees and
hashes), then chances are you are allocating each node separately so you
get your n+1 little allocations.

Having seen the glibc, eglibc, dietlibc and uclibc allocators, I already
saw that those are the preferred modes of operation. The dietlibc
allocator is especially easy to describe:

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.
It rounds the sum of the object header size and the object size to the
next power of two (using some nifty eye-watering bit-mangling) and puts
it in such a linked list. If the list is too small, it is expanded using
mmap() or mremap().

If the object is bigger than 2048 bytes it gets it's own page(s)!

>> Say, have you profiled the code to see what fraction of the time is actually
>> spent executing the allocator code?
>>
>> Can you answer the question: how much faster will the program be if
>> a magic allocator is substituted which requires zero cycles to execute?
>>
> 
> Let's see... So why do the C++ STLs (or boost, for another example) do
> exactly what I'm asking here? :-)
> 

Hmmm... I just had a look at the libstdc++ deployed with g++ 4.5.0 and I
saw that at least there, operator new calls malloc(). I also looked at
STLport and saw the same.

Also, you didn't answer the questions. Those are actually pretty good ones!

>>> 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?
>>
>> Not knowing these basics is an indicator that you need to study more if you
>> want to write memory allocators that beat malloc.
> 
> I already said that I don't want to "beat malloc", just to find a
> (probably platform-specific) way to facilitate its job.
> Ciao!
> 

You are not making sense. You don't want to beat malloc but you still
want to write a malloc replacement? You'd willingly choose the inferior
implementation?

> P.S. I'm sorry if I'm looking so.. childish(?).. to you but, believe
> me, I've written some physical/virtual memory allocators for many
> simpler system,

That's an entirely different can of worms. Believe me, the memory
management that just uses an OS is far easier than the one the OS has to
maintain.

> I know how systems work behind the scenes, and I
> really don't want to start writing something like that: I'm just
> asking how to deal with the two specific environments above while
> masking the differences between the two and maintaining a standard
> interface. I know that it's hard and that someone already did it: I'm
> asking *how* he did that (and maybe where!) :-)

You could look at the libc source codes. glibc, eglibc, dietlibc and
uclibc are a good place to start for Linux. For Windows I'd recommend
cygwin.

If you are interested in the syscalls that allocate memory: For *nix
that's mmap() with MAP_ANONYMOUS or, failing that, /dev/zero. Failing
_that_, you could try to map a newly created and truncated file. Try to
stay away from brk(), it's marked obsolete.

For Windows, have a look at HeapAlloc(), VirtualAlloc() and
LocalAlloc(). BTW: The MSVC implementation somehow manages to make
access to _one_ byte after the allocated buffer fail with a crash. Good
job, as it makes finding off-by-one errors easier.

But I still don't see your point. malloc() is meant to be portable! The
only thing you might want to tweak against is malloc(0), as that's
unspecified. Several allocators return NULL on that, but several others
do not. They just present you an object you can't even access the first
byte of.

HTH,
Markus

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