Velocity Reviews

Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   C Programming (http://www.velocityreviews.com/forums/f42-c-programming.html)
-   -   [Slightly OT] Memory management and custom allocator (http://www.velocityreviews.com/forums/t807532-slightly-ot-memory-management-and-custom-allocator.html)

FtM 12-31-2011 02:56 PM

[Slightly OT] Memory management and custom allocator
 
[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 ;-)

Eric Sosman 12-31-2011 04:08 PM

Re: [Slightly OT] Memory management and custom allocator
 
On 12/31/2011 9:56 AM, FtM wrote:
> [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).


This is frequently done, usually either to use an alternate memory
manager with extra debugging features or to substitute a manager whose
performance characteristics better match the needs of the program at
hand. However, the C language does not guarantee that it's possible to
do such substitution; "the library" is regarded as monolithic, and not
as something that can be replaced piecemeal. This allows the library
implementor to use internal and unadvertised features, "back doors" if
you like. (For example, exit() needs a "back door" to find and close
all the still-open FILE* streams.) It is at least possible that some
implementation's internals involve "back doors" to the memory manager,
so if you substituted a memory manager that implemented only the public
operations you'd break the library in strange ways.

That's mostly a "theoretical" consideration, though, perhaps since
replacing the memory manager is such an incredibly useful thing to want
to do. Still, keep in mind that it's not guaranteed to work.

> 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? :-)


Not much, unless you are fond of re-inventing well-rounded wheels
for your own amusement. The things you mention are already common
practice in many Unixoid allocators; I have no specific knowledge of
Windows' allocators but there's no reason to think Redmond is unaware
of the state(s) of the art(s).

> 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 ;-)


For a "general low-level" library I think you'll be hard-pressed
just to match the performance of the O/S' own allocators, much less
improve on them. Things would be different for a library tuned to
the specific needs of a particular program and making use of program-
specific knowledge: Which allocations will be short- or long-lived,
which will be used together and would benefit from sharing a single
page, which data items are allocated and freed so frequently that they
merit their own cache, ... Large gains can (sometimes) be had by
exploiting knowledge of this kind, but a "general low-level" library
really can't have that kind of knowledge.

If you stay on the "general low-level" plane, you're just matching
wits with people who are paid to devote a lot of thought to aspects of
this particular problem -- which is why I say you're unlikely even to
do as well as they've already done. More engineer-decades have gone
into the existing allocators than you're likely to be able to devote
to replacing them. There are probably better targets for your effort.

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

FtM 12-31-2011 04:28 PM

Re: Memory management and custom allocator
 
On Dec 31, 5:08*pm, Eric Sosman <esos...@ieee-dot-org.invalid> wrote:
> On 12/31/2011 9:56 AM, FtM wrote:
>
> > [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).

>
> * * *This is frequently done, usually either to use an alternate memory
> manager with extra debugging features or to substitute a manager whose
> performance characteristics better match the needs of the program at
> hand. *However, the C language does not guarantee that it's possible to
> do such substitution; "the library" is regarded as monolithic, and not
> as something that can be replaced piecemeal. *This allows the library
> implementor to use internal and unadvertised features, "back doors" if
> you like. *(For example, exit() needs a "back door" to find and close
> all the still-open FILE* streams.) *It is at least possible that some
> implementation's internals involve "back doors" to the memory manager,
> so if you substituted a memory manager that implemented only the public
> operations you'd break the library in strange ways.
>
> * * *That's mostly a "theoretical" consideration, though, perhaps since
> replacing the memory manager is such an incredibly useful thing to want
> to do. *Still, keep in mind that it's not guaranteed to work.
>


You are perfectly right, I optimistically hope that if something like
the memory allocation functions are broken I'll notice it in a short
time and fix it (replacing my allocator with the wrapper) :-) Anyway
the "custom" allocator is written for those simple systems that don't
have a dynamic memory allocator at all (and they are probably
disappearing from the market).

> > 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? :-)

>
> * * *Not much, unless you are fond of re-inventing well-rounded wheels
> for your own amusement. *The things you mention are already common
> practice in many Unixoid allocators; I have no specific knowledge of
> Windows' allocators but there's no reason to think Redmond is unaware
> of the state(s) of the art(s).
>
> > 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 ;-)

>
> * * *For a "general low-level" library I think you'll be hard-pressed
> just to match the performance of the O/S' own allocators, much less
> improve on them. *Things would be different for a library tuned to
> the specific needs of a particular program and making use of program-
> specific knowledge: Which allocations will be short- or long-lived,
> which will be used together and would benefit from sharing a single
> page, which data items are allocated and freed so frequently that they
> merit their own cache, ... *Large gains can (sometimes) be had by
> exploiting knowledge of this kind, but a "general low-level" library
> really can't have that kind of knowledge.
>
> * * *If you stay on the "general low-level" plane, you're just matching
> wits with people who are paid to devote a lot of thought to aspects of
> this particular problem -- which is why I say you're unlikely even to
> do as well as they've already done. *More engineer-decades have gone
> into the existing allocators than you're likely to be able to devote
> to replacing them. *There are probably better targets for your effort.
>


You exactly identified the origin of my doubts: if I go the way I
described, I'd like to give the library user the possibility to switch/
reuse more than one allocator just like the way you can switch
allocators in C++. I know that I can't beat the general standard one,
but using an optimized (maybe third-party?) one only in some occasions
and the system's one otherwise seems reasonable to me.. isn't it?
I'm asking here because I know that it's a common problem that many of
you have faced and solved ;-)
Ciao!

Johann Klammer 12-31-2011 04:39 PM

Re: [Slightly OT] Memory management and custom allocator
 
FtM wrote:
> [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:


AFAIK the allocator of GNU/Linux libc already does this.
man mallopt will give you some information about it's behavior.
Or read the source code.
No need to reinvent the wheel.

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


linux libc uses sbrk and mmap... and possibly other syscalls

regards,
JK

FtM 12-31-2011 04:55 PM

Re: Memory management and custom allocator
 
On Dec 31, 5:39*pm, Johann Klammer <klamm...@NOSPAM.aon.at> wrote:
> FtM 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
> > I've some questions:

>
> AFAIK the allocator of GNU/Linux libc already does this.
> man mallopt will give you some information about it's behavior.


I've already looked into mallopt but it doesn't seem enough fine-
grained for my needs... Do you know some code or a project that uses
it so I can take a look?

> Or read the source code.
> No need to reinvent the wheel.
>


That's the reason of asking before coding ;)

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

>
> linux libc uses sbrk and mmap... and possibly other syscalls
>


sure, sbrk() is the way to go for a low-level allocator, but the
question of how I can take a page-aligned segment remains: you can't
be sure of the OS's VA masking mechanism (or maybe yes?). Anyway, I
could proceed by reading the code of a specific kernel, but it would
be totally useless if there isn't a general enough-shared "philosophy"
underneath (read as: "a specific syscall").
I already use mmap() for persistent b-trees, but does it make sense to
use it without an underlying physical file?
Ciao!

Kaz Kylheku 12-31-2011 05:24 PM

Re: [Slightly OT] Memory management and custom allocator
 
On 2011-12-31, FtM <fmassei@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?

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?

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

FtM 12-31-2011 05:52 PM

Re: Memory management and custom allocator
 
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.

> 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? :-)

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

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, 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!) :-)

Johann Klammer 12-31-2011 06:01 PM

Re: Memory management and custom allocator
 
FtM wrote:
....
> I already use mmap() for persistent b-trees, but does it make sense to
> use it without an underlying physical file?

....
RTFM: MAP_ANONYMOUS

However, the number of mmaps per process is limited on linux.

JK

Kaz Kylheku 12-31-2011 06:31 PM

Re: Memory management and custom allocator
 
On 2011-12-31, Johann Klammer <klammerr@NOSPAM.aon.at> wrote:
> FtM wrote:
> ...
>> I already use mmap() for persistent b-trees, but does it make sense to
>> use it without an underlying physical file?

> ...
> RTFM: MAP_ANONYMOUS
>
> However, the number of mmaps per process is limited on linux.


That is true, but now for some qualifying cluesticks:

- malloc uses mmap when sbrk runs into a collision, and also for
thread arenas and large allocations. So you don't avoid mmap by using
malloc (though you avoid making lots of little mmap requests).

- brk/sbrk are based on mmmap! so there is no escaping from mmap that way.
So if you make lots of little page-sized brk increments, can you hit
the limit? It would seems to, but ...

- ... luckily, mmap will coalesce adjacent anonymous mappings which have
compatible flags so you will only run into the limit if you make a large
number of maps which do not touch or that do touch but have incompatible
properties.

- The default limit is only 65536 but in the light of the above, it's
maybe not so terrible.

- If you still have a problem, you can easily tweak the maximum count. become
root and then:

sysctl -w vm.max_map_count=<your-desired-number>

better yet, record it in /etc/sysctl.conf and run sysctl -p.

Eric Sosman 12-31-2011 07:30 PM

Re: Memory management and custom allocator
 
On 12/31/2011 12:52 PM, 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.


Why do you think the kernel predicts your program's future behavior
better than malloc() does?

> I already said that I don't want to "beat malloc", just to find a
> (probably platform-specific) way to facilitate its job.


Both the kernel and malloc() have a hard time predicting your
program's behavior, but I'll risk a prediction for the New Year:

You will not invent a "general low-level" replacement that
outperforms malloc() et al.

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


Easy: Use malloc() et al., right out of the box. Platform
specifics are already masked, system-specific dodges and tricks are
already employed, code is already tested and debugged to a degree
that you cannot possibly replicate.

There! Wasn't that easy?

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


All times are GMT. The time now is 01:14 AM.

Powered by vBulletin®. Copyright ©2000 - 2014, vBulletin Solutions, Inc.
SEO by vBSEO ©2010, Crawlability, Inc.