extended realloc

[Martin Sedlak]

Hi all,

I propose a simple extended realloc, let's say realloc_ext as an extension to the standard C library:

/*

 * ptr - pointer to reallocate

 * size - requested (new) size

 * skip_free - flag to tell whether or not to skip free

 */

void *realloc_ext( void *ptr, size_t size, int skip_free );

It's only purpose would be to control whether or not to free the old pointer in the case that reallocation failed.

The reasoning behind this is that it would enable implementations of important stl containers (i.e. std::vector)

to do in-place reallocation if possible. In such cases, memory fragmentation and expensive copying could be avoided.

If this is a duplicate of another request (or if something similar already exists and I'm not aware of it), I apologize.

Best regards

Martin Sedlak

[Fabio Fracassi]

There has been a similar proposal back in 2006 (http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2045.html#Problem%203)

It goes a bit further in allowing to request a minimum needed, and a prefered size and allow realloc to resize the memory approproately.

 

The main problem with those proposals seems to be that it would need support of the C-committee and all C-library vendors, which is difficult to achieve,

and it seems not clear if the performance win is big enough to warrant this cost.

 

best regards

 

Fabio Fracassi

 

--

---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposal...@isocpp.org.
To post to this group, send email to std-pr...@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/.

[Ion Gaztañaga]

El 17/04/2014 9:27, Fabio Fracassi wrote:
> There has been a similar proposal back in 2006
> (http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2045.html#Problem%203)
>
> It goes a bit further in allowing to request a minimum needed, and a
> prefered size and allow realloc to resize the memory approproately.
>
> The main problem with those proposals seems to be that it would need
> support of the C-committee and all C-library vendors, which is difficult
> to achieve,
>
> and it seems not clear if the performance win is big enough to warrant
> this cost.

A modified version of the proposal has been implemented in
Boost.Container and it will ship in Boost 1.56 (it's in both master and
develop branches). A new allocator type has been developed that can
offer realloc-like capabilities. If anyone want to measure performance
wins in its plaform there are some benchmarks in the Boost.Container
"bench" subfolder.

Best,

Ion

[Fabio Fracassi]

> From: Ion Gaztañaga [mailto:igazt...@gmail.com]

> El 17/04/2014 9:27, Fabio Fracassi wrote:
> > and it seems not clear if the performance win is big enough to
> warrant
> > this cost.
>
> A modified version of the proposal has been implemented in
> Boost.Container and it will ship in Boost 1.56 (it's in both master and
> develop branches). A new allocator type has been developed that can
> offer realloc-like capabilities.

+1
Do you have to have support form the runtime, or can you work around this issue?
are you going to submit a Paper on this?

best regards

Fabio

[Ion Gaztañaga]

The latest version of DLMalloc (2.8.6) has been extended to implement
all needed functions. That code is wrapped in a Boost.Container DLL. It
should work on all Windows and Unixes.

Obviously is not a replacement for an optimized multithreaded allocator,
but at least in my tests, reallocation is quite effective, even in the
presence of move semantics. Burst allocation is also quite effective in
node containers when inserting ranges. The idea of making it part of
Boost is to obtain user reports and improvements.

I don't have a plan to submit a paper (yet). The interface is quite
complicated and the committee does not seem interested in this type of
extensions. The idea is to have a working implementation so that we can
measure real improvements in our programs. If the performance is good
enough, we could have another proposal backed by existing practice.

I would like to use also system allocators, at least to implement part
of the proposal, but that would require some kind of runtime support.
Another idea is to try to convince C memory allocator writers
(nedmalloc, jemalloc,tcmalloc) to implement some extensions, this could
be tried once we've established we appropriate C interface.

Now it's time to try and measure. I'd be glad to receive any feedback
from the community in this mailing list or in any Boost mailing lists.

Best,

Ion

[Martin Sedlak]

After some thinking, I figured out that my proposal is useless.

Standard realloc will do (objects holding pointers will be copied by realloc anyway, I can't think of a case where it would break).

Plus standard realloc has one important advantage over what I proposed:

it can do reallocation by moving overlapping region if previous block is free and combined with the one to be reallocated fits the new size.

So I take my proposal back. Still, it should be possible to reduce fragmentation of vector by using realloc in some cases.

In fact my primary concern was fragmentation, not performance.

My apologies :)

Best regards

Martin

[Martin Sedlak]

On the second thought C realloc won't work if move/copy is non-trivial (but in that case storing pointers in the container instead would be the right thing to do).

Plus overlapping reallocation is still possible but requires the caller to detect the overlap and not call free in that case.

I think I went too deep in low-level thinking...

Thanks for your replies.

Best regards

Martin

[Thiago Macieira]

Em qui 17 abr 2014, às 09:26:06, Martin Sedlak escreveu:
> On the second thought C realloc won't work if move/copy is non-trivial (but
> in that case storing pointers in the container instead would be the right
> thing to do).
> Plus overlapping reallocation is still possible but requires the caller to
> detect the overlap and not call free in that case.
> I think I went too deep in low-level thinking...

What we need in containers is "realloc by extending if you can", which means
non-trivial contained objects will stay in place.

What has occurred to me when you posted your proposal is that the next thing
that any container will do after getting a "failed to extend" return code is
allocate a new memory block. So a realloc function that extends if possible,
allocating a brand new block if not, would also be welcome.

--
Thiago Macieira - thiago (AT) macieira.info - thiago (AT) kde.org
Software Architect - Intel Open Source Technology Center
PGP/GPG: 0x6EF45358; fingerprint:
E067 918B B660 DBD1 105C 966C 33F5 F005 6EF4 5358

[Ion Gaztañaga]

El 17/04/2014 18:56, Thiago Macieira escribió:
> Em qui 17 abr 2014, às 09:26:06, Martin Sedlak escreveu:
>> On the second thought C realloc won't work if move/copy is non-trivial (but
>> in that case storing pointers in the container instead would be the right
>> thing to do).
>> Plus overlapping reallocation is still possible but requires the caller to
>> detect the overlap and not call free in that case.
>> I think I went too deep in low-level thinking...
>
> What we need in containers is "realloc by extending if you can", which means
> non-trivial contained objects will stay in place.
>
> What has occurred to me when you posted your proposal is that the next thing
> that any container will do after getting a "failed to extend" return code is
> allocate a new memory block. So a realloc function that extends if possible,
> allocating a brand new block if not, would also be welcome.

N2045 covered this case and also proposed atomically checking for
extensions and allocate on failure. The steps are:

-> Check if memory can be expanded forward. Usually this means (e.g.
vector) that stored objects won't be copied or moved after expansion.

-> Otherwise, check if memory can be expanded backwards + forward. This
obtains a memory region that will have the stored objects in the middle
of the region. This lowers fragmentation and usually it's faster because
several allocators can check in O(1) if the previous and next blocks are
free.

-> Otherwise, allocate a new block.

Once memory has been expanded/allocated, the user copies/moves elements
if needed and in case a new buffer was allocated, frees the old buffer.

The downside of the forward+backwards expansion is that you can lose
strong safety guarantees in some vector operations.

Best,

Ion