Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > An idea for heap allocation at near stack allocation speed

Reply
Thread Tools

An idea for heap allocation at near stack allocation speed

 
 
Bjarke Hammersholt Roune
Guest
Posts: n/a
 
      02-15-2011
On Feb 13, 4:41*pm, Bjarke Hammersholt Roune <(E-Mail Removed)>
wrote:
> This ignores alignment. ScopeAlloc would have to adjust X to preserve
> alignment by rounding up to the proper alignment. To align to
> alignment Y, that is to round up to the nearest multiple of Y, I would
> calculate (notice no branches)
>
> * X = Y * ((X - 1) / Y + 1)
>

Rounding up with just 2 instructions:

X = (X + (Y - 1)) & (~(Y - 1))

This works because Y is a power of 2 and compile-time constant.

Cheers
Bjarke
 
Reply With Quote
 
 
 
 
Bjarke Hammersholt Roune
Guest
Posts: n/a
 
      02-16-2011
Exceptions make this more complicated that I had thought. If I'm
allocating an array I have to call constructors, and then I have to
handle the case of one of the constructors throwing an exception. I
think I know how that should work. However, what do I do when I'm
deallocating the array, and one of the destructors throws an
exception. Do I still call the remaining destructors? What if I get
two exceptions that way? I recall reading about what should happen in
those cases, but now I can't find it. Anyone knows? I know its bad
style for destructors to throw exceptions and mine don't but I can't
know that that will be true for everyone who might use my code at some
point. My arrays should work the same as usual arrays including with
respect to exceptions.

Btw. you'd think I could just call placement new[] and placement
delete[]. Unfortunately as far as I can tell from discussions on the
internet those functions are completely useless because
implementations are allowed to store information about an array in the
memory for that array and placement new[] and placement delete[] are
allowed to contain the code to actually do this. So to make that work
I'd have to know how much extra space the compiler I'm on wants me to
insert so I can allocate enough space and take the right offset after
having called placement new[] to find the actual beginning of the
array where the first element is stored. There is no way to obtain
that information, indeed I read that the right offset is allowed to
change from one call to placement new[] to another. That's the
stupidest thing I've heard in quite a while and I'd love for someone
to tell me that it's wrong.
 
Reply With Quote
 
 
 
 
gwowen
Guest
Posts: n/a
 
      02-16-2011
On Feb 16, 5:55*am, Bjarke Hammersholt Roune <(E-Mail Removed)>
wrote:
> However, what do I do when I'm
> deallocating the array, and one of the destructors throws an
> exception.


In general, destructors should not throw exceptions. Nearly every
piece of good-practice advice suggests that destructors *must* not
throw exceptions. The most compelling reason -- although not the only
one -- is that exception propagation up through the call-stack
destroys any automatic objects as part of the unwinding, and if those
destructors throw, this will terminate() your program. (Also, you
cannot store such objects in standard containers).

You *can* avoid these problems through careful use of objects whose
destructors can throw (essentially managing their lifetimes yourself),
but extreme care is needed.
 
Reply With Quote
 
itaj sherman
Guest
Posts: n/a
 
      02-16-2011
On Feb 16, 7:55 am, Bjarke Hammersholt Roune <(E-Mail Removed)>
wrote:
> Exceptions make this more complicated that I had thought. If I'm
> allocating an array I have to call constructors, and then I have to
> handle the case of one of the constructors throwing an exception. I
> think I know how that should work. However, what do I do when I'm
> deallocating the array, and one of the destructors throws an
> exception. Do I still call the remaining destructors? What if I get
> two exceptions that way? I recall reading about what should happen in
> those cases, but now I can't find it. Anyone knows? I know its bad
> style for destructors to throw exceptions and mine don't but I can't
> know that that will be true for everyone who might use my code at some
> point. My arrays should work the same as usual arrays including with
> respect to exceptions.
>


I don't think you need to support elements with throwing destructors.
All standard containers for example don't, for the same reason.
You should require the elements to have a no-throw destructor. I mean,
in POV of the module that allocates, its contract only allows to be
used with no-throw destructors.

It is generally accepted that all classes should have no-throw
destructor (unless it is some very special case, but then has to give
up using such class with almost any core libraries such std
containers).

If one constructor throws you have to destruct all the other elements
that already constructed in reverse order, and let that exception
continue throw. Like primitive arrays, and call std containers do.
Because you know elements have no-throw destructors, another exception
should not be thrown in that process.

itaj
 
Reply With Quote
 
Bjarke Hammersholt Roune
Guest
Posts: n/a
 
      03-06-2011
As an update, it turns out that the GNU libc comes with obstacks which
does something very close to what I'm suggesting here

http://www.gnu.org/s/libc/manual/htm.../Obstacks.html

However, the implementation is not so good for my purpose. The code is
obfuscated by being part of a library (so weird variable names) and by
being written almost entirely as macroes. However, as far as I can
tell, an allocate/deallocate pair takes 9 ops (similar to add) and 3
branches in the best case plus a significant number of heap reads and
writes. This is when you specify the size in bytes. The scheme
described here takes 7 ops and 2 branches in the best case to do the
same thing and only accesses the heap to update the remaining capacity
member.

It gets a lot worse, however, because obstack allocates in fixed-size
chunks and it frees a chunk immediately when it is empty. As the
chunks are fixed-size the number of chunks that have to be allocated
is linear in the size of the total amount of space that is allocated.
Even worse, if the current chunk is full and you allocate 1 byte, a
new chunk will be allocated. When you deallocate that 1 byte, that new
chunk will be deallocated. So potentially every single allocation and
deallocation will cause a call to the backing memory allocator, at
which point performance will be worse than if the backing memory
allocator had been used directly.

From comments in the code obstacks seems to have been written with a
very specific use in mind: storage of symbols while parsing source
code. This focus makes obstacks unsuitable as a general purpose
replacement for stack allocation. So I'll still need to make my own.

Cheers
Bjarke
 
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
How much heap can I reserve for JVM? Error when allocation very much heap Raymond Schanks Java 0 04-11-2010 04:25 PM
C/C++ compilers have one stack for local variables and return addresses and then another stack for array allocations on the stack. Casey Hawthorne C Programming 3 11-01-2009 08:23 PM
function implementation with stack vs heap allocation Hicham Mouline C++ 4 05-08-2009 02:56 PM
Heap dump file size vs heap size Michal Slocinski Java 1 03-25-2008 12:54 PM
What is the difference between dynamic memory allocation,and stack allocation ? chris C++ 6 10-28-2005 05:27 AM



Advertisments