Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > boost alternative to realloc

Reply
Thread Tools

boost alternative to realloc

 
 
Aaron Graham
Guest
Posts: n/a
 
      04-16-2010
I was wondering if there is a boost wrapper or alternative that
essentially provided malloc/realloc/free in a RAII wrapper. Any ideas?
 
Reply With Quote
 
 
 
 
Aaron Graham
Guest
Posts: n/a
 
      04-16-2010
On Apr 16, 12:37*pm, "Leigh Johnston" <(E-Mail Removed)> wrote:
> "Aaron Graham" <(E-Mail Removed)> wrote in message
>
> news:(E-Mail Removed)...
>
> > I was wondering if there is a boost wrapper or alternative that
> > essentially provided malloc/realloc/free in a RAII wrapper. Any ideas?

>
> Why don't you just use std::vector instead of trying to mix C and C++
> techniques?
>
> /Leigh


For several reasons:
- std::vector initializes the entire buffer. This is bad, not only
because of the time it takes to initialize the buffer, but also
because it requires the OS to map all pages into physical memory even
if they never end up being used.
- You can't shrink the memory footprint of a std::vector without
copying the data.

I'm aware of std::vector, I love it and I use it all the time, but
it's not appropriate for this situation. It's a video application on
an embedded system, and it's one of those areas of the code that I've
profiled and determined that I need maximum performance with minimal
memory overhead. With a few minor changes, std::vector could fit the
bill. But it doesn't.

This has taken more time than it would have taken to write my own RAII
wrapper, so I guess I'll do that. Thanks anyway.
 
Reply With Quote
 
 
 
 
Alf P. Steinbach
Guest
Posts: n/a
 
      04-17-2010
* Leigh Johnston:
>
>
> "Juha Nieminen" <(E-Mail Removed)> wrote in message
> news:hqbo7n$14h$(E-Mail Removed)...
>> On 04/16/2010 11:20 PM, Leigh Johnston wrote:
>>> A combination of reserve() and a custom allocator whose construct is a
>>> no-op might work although std::vector will probably still emit a
>>> construct loop.

>>
>> That's not how std::vector works.
>>
>> reserve() (including the implicit reserving which happens when the
>> vector grows) allocates *uninitialized* memory. Even if you do a
>> reserve(100000000) (on an empty vector), no constructors will be called
>> *at all* (and consequently no loop is performed). Only those elements
>> will be constructed which are actually added to the vector.
>>

>
> Yes I know how reserve() works thanks. I meant so say resize() but said
> reserve() as I was thinking about malloc/realloc. It is UB to access
> the allocated but uninitialized parts of a std::vector.


If understand you correctly you meant resize + no-construction-op because you
thought just doing a reseve would have to yield UB when accessing the elements.

Happily that's not the case for POD elements. C++03 guaranteed a contiguous
buffer for std::vector, and C++0x will additionally do so for std::string (in
practice you already have also that). Using uninitialized values is UB, as ever,
but you can store data into those elements, and then read from them.

For a std::vector v, v[i] is defined to have the same semantics as
*(v.begin()+i). This can theoretically be troublesome with some pedantically
correct C++ implementation, and if used with i >= v.size() it may well be UB or
implementation defined, I haven't checked (e.g. think range checking). But since
it's a contiguous buffer you can do (&v[0])[i], with [i] here being the built-in
indexing operator, which is well-defined for the complete raw array.


Cheers,

- Alf
 
Reply With Quote
 
Alf P. Steinbach
Guest
Posts: n/a
 
      04-17-2010
* Leigh Johnston:
>
>
> "Juha Nieminen" <(E-Mail Removed)> wrote in message
> news:hqboe9$1er$(E-Mail Removed)...
>> On 04/16/2010 10:54 PM, Aaron Graham wrote:
>>> For several reasons:
>>> - std::vector initializes the entire buffer.

>>
>> No, it doesn't. It initializes only the elements you explicitly add to
>> the vector. Even if/when std::vector preallocates more memory than the
>> amount of inserted elements, that memory will be *uninitialized* (in
>> other words, no constructor calls, nothing).
>>
>> If you want to make std::vector be prepared for a certain amount of
>> elements, you call reserve(). It will internally preallocate
>> uninitialized memory for that many elements.

>
> That doesn't help as it is UB to access the uninitialized memory so the
> memory still needs to be initialized before you can use it hence
> std::vector is not suitable for the OP.


See my reply to you else-thread, but in short: that's overly pessimistic.


Cheers & hth.,

- Alf
 
Reply With Quote
 
Gert-Jan de Vos
Guest
Posts: n/a
 
      04-17-2010
On Apr 17, 12:25*pm, "Alf P. Steinbach" <(E-Mail Removed)> wrote:

> For a std::vector v, v[i] is defined to have the same semantics as
> *(v.begin()+i). This can theoretically be troublesome with some pedantically
> correct C++ implementation, and if used with i >= v.size() it may well be UB or
> implementation defined, I haven't checked (e.g. think range checking). But since
> it's a contiguous buffer you can do (&v[0])[i], with [i] here being the built-in
> indexing operator, which is well-defined for the complete raw array.


I use such an implementation (MSVC2005 and _SECURE_SCL). resize()
initializes the
entire vector<T> with T(). I often need large arrays of POD, that's
why I made a
dynamic_array<T> class with an interface very close to std::vector but
not using
allocators. I don't think an allocator can support uninitialized POD
allocation
like new T[] does. The nice thing of new T[] is that it does not
initialize PODs
while it does default construct true classes.

G-J
 
Reply With Quote
 
Alf P. Steinbach
Guest
Posts: n/a
 
      04-17-2010
* Leigh Johnston:
>
>
> "Alf P. Steinbach" <(E-Mail Removed)> wrote in message
> news:hqc2bm$poj$(E-Mail Removed)-september.org...
>> * Leigh Johnston:
>>>
>>>
>>> "Juha Nieminen" <(E-Mail Removed)> wrote in message
>>> news:hqbo7n$14h$(E-Mail Removed)...
>>>> On 04/16/2010 11:20 PM, Leigh Johnston wrote:
>>>>> A combination of reserve() and a custom allocator whose construct is a
>>>>> no-op might work although std::vector will probably still emit a
>>>>> construct loop.
>>>>
>>>> That's not how std::vector works.
>>>>
>>>> reserve() (including the implicit reserving which happens when the
>>>> vector grows) allocates *uninitialized* memory. Even if you do a
>>>> reserve(100000000) (on an empty vector), no constructors will be called
>>>> *at all* (and consequently no loop is performed). Only those elements
>>>> will be constructed which are actually added to the vector.
>>>>
>>>
>>> Yes I know how reserve() works thanks. I meant so say resize() but
>>> said reserve() as I was thinking about malloc/realloc. It is UB to
>>> access
>>> the allocated but uninitialized parts of a std::vector.

>>
>> If understand you correctly you meant resize + no-construction-op
>> because you thought just doing a reseve would have to yield UB when
>> accessing the elements.
>>
>> Happily that's not the case for POD elements. C++03 guaranteed a
>> contiguous buffer for std::vector, and C++0x will additionally do so
>> for std::string (in practice you already have also that). Using
>> uninitialized values is UB, as ever, but you can store data into those
>> elements, and then read from them.
>>
>> For a std::vector v, v[i] is defined to have the same semantics as
>> *(v.begin()+i). This can theoretically be troublesome with some
>> pedantically correct C++ implementation, and if used with i >=
>> v.size() it may well be UB or implementation defined, I haven't
>> checked (e.g. think range checking). But since it's a contiguous
>> buffer you can do (&v[0])[i], with [i] here being the built-in
>> indexing operator, which is well-defined for the complete raw array.
>>

>
> std::vector<T>:perator[](i) is UB if i >= std::vector<T>::size()


It may be.

If you were thinking of backing me up on that possibility you'd better cite
chapter and verse from the standard instead of plain asserting.

Anyway, it isn't relevant to what you're replying to; did you read it?


> - do
> not even think about writing such crap code, this is about the correct
> use of containers of any element type not just POD so POD is a red
> herring


I can't comment on the details of whatever it is you're imagining here; did you
read what you responded to?


> (and I believe the only valid operation on an uninitialized POD
> is it initialize it via assignment).


Or by other means such as placement new or memcpy, but in the end they all
reduce to machine code level assignments, so with a sufficiently abstract notion
of "assignment" you're right about that.

Did you read what you responded to?


Cheers & hth.,

- Alf
 
Reply With Quote
 
Öö Tiib
Guest
Posts: n/a
 
      04-17-2010
On 16 apr, 22:31, Aaron Graham <(E-Mail Removed)> wrote:
> I was wondering if there is a boost wrapper or alternative that
> essentially provided malloc/realloc/free in a RAII wrapper. Any ideas?


Lightest might be to use boost::shared_ptr. Then you achieve RAII with
your malloc'ed pointer since shared_ptr can be set to call custom
deleter in destructor (free on your case).
 
Reply With Quote
 
Alf P. Steinbach
Guest
Posts: n/a
 
      04-17-2010
* Leigh Johnston:
> "Alf P. Steinbach" <(E-Mail Removed)> wrote in message
> news:hqc4bf$3qg$(E-Mail Removed)-september.org...
>> If you were thinking of backing me up on that possibility you'd better
>> cite chapter and verse from the standard instead of plain asserting.
>>

>
> I cannot find an explicit reference to it being UB in the draft
> standard, it might be covered by description of iterators, i.e. creating
> an iterator past end() or dereferencing end() being UB (it equates
> operator[]() semantics to being equivalent to *(a.begin() + n)).


Yes, I think that's where you'd have to look.


> From MSDN std::vector reference:
>
> "If the position specified is greater than the size of the container,
> the result is undefined."


MSDN needs to be consulted very carefully. It's more of an implementation's
documentation than a language reference.


> SGI website asserts that 0 <= n < a.size() is a precondition for a[n].
> Violating a precondition would be UB in my book.
>
> Writing such code would still be an extremely retarded thing to do even
> if the standard didn't explicitly state that it was UB.


"retarded" is probably too strong. It all depends.

But since you are stating this POV in reply to me I'm wondering how the idea of
using std::vector:perator[i] with i > size popped into your mind?

Are you next going to very heatedly warn me about the dangers of dereferencing
null pointers (outside of typeid expressions), if I causally mention that that
might not be a good idea, or e.g. reply to me stating that integer division by
zero is "retarded", if I should ever say that it may be UB, or what?


Cheers & hth.,

- Alf
 
Reply With Quote
 
Alf P. Steinbach
Guest
Posts: n/a
 
      04-17-2010
* Leigh Johnston:
> * Alf P. Steinbach:
>>
>> "retarded" is probably too strong. It all depends.
>>
>> But since you are stating this POV in reply to me I'm wondering how
>> the idea of using std::vector:perator[i] with i > size popped into
>> your mind?
>>
>> Are you next going to very heatedly warn me about the dangers of
>> dereferencing null pointers (outside of typeid expressions), if I
>> causally mention that that might not be a good idea, or e.g. reply to
>> me stating that integer division by zero is "retarded", if I should
>> ever say that it may be UB, or what?
>>

>
> You said:
>
> "If understand you correctly you meant resize + no-construction-op
> because you
> thought just doing a reseve would have to yield UB when accessing the
> elements.
>
> Happily that's not the case for POD elements."


Yes. And I added more detailed discussion. See that discussion for practical
details, see below for less informal reasoning.


> This is incorrect


Happily that's incorrect.


> and retarded.


I'm sorry, that's empty name calling.


> Only accessing the first size()
> elements of a std::vector is well defined and correct.


Happily that's incorrect, see below.


> The fact that
> you can access the "raw array" allocated by std::vector does not make it
> a correct thing to do


That's right, in the sense that the fact that you can jump up and down doesn't
always make it the correct thing to do.


>, even if it works on all known implementations.


I'm sorry, but that's very misleading: it's guaranteed to work with a conforming
compiler. This was much of the point of the C++03 change in wording to require a
contiguous buffer, namely to support direct access of the buffer as a raw array.

The standard could have been more clear, though: with the wording in e.g. the
2008 draft (n200 the only /explicit/ guarantee for direct buffer access is
that it's well-defined for the range 0 through size-1 (not capacity-1) -- this
is almost a defect in the draft, if it's still that way, since it's less of a
guarantee than the one provided implicitly by the behavior discussed below.

The wording that lets you go on to capacity (i.e. that says that there's only
one buffer, and that that buffer is at &v[0]) is in n2800 §23.2.4.2/5, namely
that (1) after reserve you have at least the requested capacity, (2)
reallocation invalidates all iterators, pointers & references, and (3) that an
insert can only cause reallocation when it would make the size of the vector
exceed the current capacity.

This means that reserve() can't allocate a buffer on the side deferring the
replacement of the current buffer, because such later buffer replacement would
invalidate pointers and references at a time when that isn't allowed.

Hence, after any reallocation you have that >=capacity-size buffer at &v[0].

In passing, about "less than clear": also §23.2.4.2/5 has a direct defect, at
least in n2800, namely, it refers to "the size specified in the most recent call
to reserve()" when it should say "the capacity established by the most recent
call to reserve". For it's possible to specify a capacity less than the current,
in which case reserve is guaranteed to not reduce the capacity. I.e. the n2800
wording allows insert() to reallocate after a call to reserve(0), which is
unintended and incorrect.

I don't know whether it's wise to mention such defects here, but it might help
you to understand that the standard is an evolving document, not 100% prefect.


> Only std::vector is "allowed" to access the unused allocated memory it
> owns.


Happily that's also incorrect. But there is a subtle issue once discussed in
great detail, about whether the buffer starting at &v[0] necessarily is
zero-terminated after a .c_str() call; it was Andrei who raised the issue. I
can't recall the conclusion, sorry again.


> UB can "silently work" but it is still UB.


That's right.


Cheers, & hth.,

- Alf
 
Reply With Quote
 
Alf P. Steinbach
Guest
Posts: n/a
 
      04-17-2010
* Leigh Johnston:
> * Alf P. Steinbach:
> <snip>
>
> Unless I am mistaken you are basically advocating that the following
> code is correct according to the standard:
>
> void foo()
> {
> std::vector<int> v;
> v.reserve(2);
> v.push_back(41);
> *(&v[0]+1) = 42;
> }
>
> The above code is plain wrong.


No, it's meaningless, but it's not wrong.

After the reserve(2) you are guaranteed a contiguous buffer of at least 2 ints,
and you're guaranteed that that buffer is the one accessible via &v[0]; see the
posting you replied to for the formal details.

If I understand this correctly what you're reacting to is that you've been
proven wrong.


> If I you disagree then your position is untenable.


On the contrary, your only argument for your position is that you maintain that
you're right, reasserting that again and again as you've done with other issues,
and as before you disregard and snip all facts and arguments to the contrary.

It's now clear that that is a habit you have.

I already regret wasting time providing you with references and reasoning, only
to have that snipped and replaced, as now usual, with childish assertions.


- Alf
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
#include <boost/shared_ptr.hpp> or #include "boost/shared_ptr.hpp"? Colin Caughie C++ 1 08-29-2006 02:19 PM
Problems mixing boost::lambda::bind and boost::shared_ptr.. Toby Bradshaw C++ 6 06-02-2006 04:12 PM
Any Boost Experts out there for Boost.Regex? Richard Latter C++ 2 05-17-2004 03:12 PM
What is the best alternative for realloc in C++ Kumar C++ 9 04-07-2004 05:28 PM
Boost + Python C/API: Mixing python return types with boost return types Steve Knight Python 2 10-10-2003 10:11 AM



Advertisments