• Advertisement
Sign in to follow this  

Simple memory allocation question

This topic is 3350 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

So I have a struct and I need to allocate memory to a new instance when I create it. Trouble is I cannot use malloc or new since they are said to use variable amounts of time for execution and I need to do it in fixed time. Is there something else for memory allocation in C++? Thanks jan

Share this post


Link to post
Share on other sites
Advertisement
For one thing, could the instances go on the stack?

It might also be possible not to create that many objects? Or short-lived objects within a tight loop?

There is also a possibility of custom allocators (memory pools and things which I haven't used so far).

However, is creating the objects really a problem. You can't just base design decisions on hearsay and start to optimize furiously upfront.

Share this post


Link to post
Share on other sites
Quote:
Original post by visitor
For one thing, could the instances go on the stack?

It might also be possible not to create that many objects? Or short-lived objects within a tight loop?

There is also a possibility of custom allocators (memory pools and things which I haven't used so far).

However, is creating the objects really a problem. You can't just base design decisions on hearsay and start to optimize furiously upfront.


Well I was thinking of the stack option as well but then I was wondering if creating the total allowed instances right from start is allowed or not.

Also I was wondering if I should create an stl vector or list.Do you know how they work under the hood?Do they take a fixed time to create?

Could you tell me more about this custom allocators thing or give me some link where I can check it out?

*Actually this is a test question and I want to give the best answer,not just from what I currently know.

Share this post


Link to post
Share on other sites
There are two key questions here:

1) Do you know how many times you are going to need to allocate this struct?

2) What is the scope of the object? What should it's lifetime be?

Share this post


Link to post
Share on other sites
Quote:
Original post by Dave
There are two key questions here:

1) Do you know how many times you are going to need to allocate this struct?

2) What is the scope of the object? What should it's lifetime be?


1)This is dynamic.I have to remove the object when the character is killed by the player.
2)The scope of the object would be a data member i guess. It should be an array of the struct or a pointer pointing to an array.

Share this post


Link to post
Share on other sites
*Use a pool allocator.
*Use a std::vector. First std::vector::reserve() the max number of instances, then use vector::remove_if and vector::erase to get rid of instances. (a vector won't normally shrink in memory usage, and reserve allows you to only have the initial allocation)
+std::vector and std::list use a std::allocator to allocate memory, the default one uses new/delete for each requested allocation (each allocation isn't necessarily 1 item, but usually many items to make room for additional push_back() calls later).
std::vector keeps a block of memory where the first vector::size() items are alive and active and all items from there to vector::capacity() are allocated but inactive and awaiting construction so they can be used. (constructed using placement new() by default)

Share this post


Link to post
Share on other sites
Quote:
Original post by altra4u
Trouble is I cannot use malloc or new since they are said to use variable amounts of time for execution and I need to do it in fixed time.


What kind of application is this for? If it's simply for a game, then I'd say you're seriously micro-optimizing here. You shouldn't be worrying about alternate memory allocation techniques until you've profiled your application and discovered that memory allocation is your bottleneck.

Share this post


Link to post
Share on other sites
Quote:
Original post by altra4u
and I need to do (memory allocation) in fixed time.


Prove it. (I am highly doubtful that any sane company would give a job with such a requirement, to a person who needs to post in For Beginners for help.)

Share this post


Link to post
Share on other sites
Quote:
Original post by Zahlman
Quote:
Original post by altra4u
and I need to do (memory allocation) in fixed time.


Prove it. (I am highly doubtful that any sane company would give a job with such a requirement, to a person who needs to post in For Beginners for help.)


Ha ha dude why are you getting so edgy???Its not like I put it in just the beginner's forum and I don't know anything.I had a couple of answers of my own but I just wanted other people's opinion and I was posting it around where I expected some expert people's replies.
And yes it is from a job test not my personal will to scour the trenches of C++ memory allocation.(No need to prove it anyone)
Thx anyways for ur concern

Share this post


Link to post
Share on other sites
Generally speaking, if you know how much you want to allocate, allocate it up front. If you think it will fit on the stack, make it an array and if you don't think it will then allocate it dynamically, or better still use a container to do it for you.

Share this post


Link to post
Share on other sites
Quote:
Is there something else for memory allocation in C++?


No, C++ only has new.

For anything else, you need a real-time OS which will guarantee fixed time allocation or fail otherwise.

Quote:
Original post by altra4u
So I have a struct and I need to allocate memory to a new instance when I create it.
Trouble is I cannot use malloc or new since they are said to use variable amounts of time for execution and I need to do it in fixed time.


The problem is following:
int main() {
Foo foo; // fixed time, right?
};
Unless your OS guarantees that code that constructs foo will not be pre-empted, the "fixed" time may take 5 cycles on one run, and 20ms on another.

So long story short, if you're running multi-threaded OS, there is no fixed time. That is only possible in real-time OS, and without any kind of energy managed CPU (such as laptops usually have).

Share this post


Link to post
Share on other sites
I think what he was being told is surely memory allocation in fixed time.

But this cannot work, until you have always guarenteed to have the needed memory size available in one piece (memory framentation).

secondly, your OS must always know in advance where this location is (fixed time search).


both is impossible for any OS, especially since memory is divided into pages of memory. if you search for it, and its not in the cache/current page, you need too
load the proper page (searching again). so even when trying to reading data just in common, you can get a cache miss and a load of the proper memory page containing the data you want to acces in your current block of code.

so fixed time? i say "never"...
any comments welcome!


if you want to get fast allocation, use memory pools/preallocate. also "fixed time" *COULD* mean you are NOT allowed to use construction like this:

if(a)
(
allocVariantA())
)
else
(
if(b)
(
if(c)
allocVariantC()
else if (d)
allocVariantD()
)
)

because if condition A is met, you could allocate the subvariant A of your struct faster as the other, since they include additional expressions to be evaluated.

Share this post


Link to post
Share on other sites
Quote:
Original post by Dave
Generally speaking, if you know how much you want to allocate, allocate it up front. If you think it will fit on the stack, make it an array and if you don't think it will then allocate it dynamically, or better still use a container to do it for you.

Creating an array and putting it on the stack-Thats what I think the answer is as they want the allocation to happen in fixed time.I can't think of anything else.I don't know about the pool allocator thing but stl entities use new/malloc under the hood which again will result in varying time for allocation.

Share this post


Link to post
Share on other sites
You can't say that using new and delete uses varying time without being sure of what the scenario is. If you are running a piece of software running on a hard real time operating system, using dynamic allocation might be unsuitably slow, but still percieved as instant to the onlooker. Note also that you may not be able to allocate with new and delete on hard real time operating systems because they may not be able to page or guarantee memory availability at run time.

I think terminology has been confusing in this thread.

Also, as i think i mentioned in one of my earlier posts, if you reserve the size of the container, then only a single allocation is made unless you fill it past the reserve size. So actually, this is a pretty 'constant' allocation time.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement