Archived

This topic is now archived and is closed to further replies.

memory management w/ multithreading

This topic is 5127 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

i tried running a search here, but i keep getting errors, so i''ll just go ahead and post. i''ve got a graphics app that i''m working on that i want to multi-thread. everything works fine for me, but i want the ability to abort a thread if it''s taking too long to compute. that''s not a big deal either -- i''ve gotten that to work. the issue i''m running into is managing my memory. if i allocate memory and then abort part way thru, i need some way to know to clean up the private memory the thread allocated to do the particular operation it was working on. i''ve come up with a simple linked list wrapper for malloc/free/realloc that associates a thread ID with an allocated piece of memory, but since it''s a linked list, it''s really slow when the number of memory allocations gets up there. am i approaching this the wrong way? do i just need to tune my wrapper functions to be faster or should i rethink the system?

Share this post


Link to post
Share on other sites
Hello miles vignol,

How are you stopping the threads?

You sould be able the signal the thread and have it clean up it self.
Or if the thread has certen points when it can check a var to see if it needs to stop you could just set the threads var and when it got around to check it would stop and clean up.

If that can''t work then use a map not a list for each thread id.
maps are faster at finding then list are going through.

Find out what the OS threads have as a way of interuputing a thread.

Just try to avoid the terminate thread cold.

Lord Bart

Share this post


Link to post
Share on other sites
lord bart:

i wanted to avoid having to write operations that check for exit conditions. since it's a geometry app, there's alot of loops going thru point and poly lists.

what i'm doing now is having the ui thread just straight out kill the process and then clean up the allocated memory.

basically, all the memory allocations are done via my wrapper and after the thread is stopped, it's trivial to go thru the master memory list and free up memory associated with a particular thread. the long process is freeing up memory specifically.

ironically, i could just comment out my memory freeing functions in the operations and it'd be fine (since there's a cleanup before exiting the thread)... but that just rubs me the wrong way. mainly because i don't want the threading aspect to really have to be considered in the actual operation...

what do you mean by a map?

my current situation is this:

a linked list (memory_thread) of linked lists (memory_block).

memory_blocks are linked to the appropriate memory_thread based on their thread id, such that the all memory_blocks of a particular memory_thread are owned by the same calling thread.

how would a map work? is that some sort of hash table or something? some of those more complex storage systems have always left me scratching my head.

i thought about even taking a public malloc implementation and adding a thread id to the mix... but that seems like a bit of overkill.

oh yeah, i'm writing this in C with SDL as the thread handler. if you're not familiar with SDL, it's cross platform library designed for low level graphics and sound operations with some UI and simple thread interaction thrown in.


[edited by - miles vignol on November 29, 2003 6:23:20 PM]

Share this post


Link to post
Share on other sites
If I was you I would probably free the memory at a convenient time (ie, when loading a level, when the game is paused, etc.).
quote:

how would a map work? is that some sort of hash table or something? some of those more complex storage systems have always left me scratching my head.


Yep, it basically associates a key with a value (in your case a thread id and memory). Although map wouldn''t work in your case because 1) it''s in the C++ standard library and 2) it doesn''t allow multiple key values.

--------
"Hey, what about those baggy pants you kids are wearin'' these days? Aren''t they hip and cool and poppin'' fresh?"-Peter Griffin
"Everytime I see an M followed by a dollar sign I just say "oh god" and go to the next post."-Neurokaotix
the D programming language

Share this post


Link to post
Share on other sites
okay, well, what i''ve done to help matters was add a simple hash table to each thread node.

basically, a thread allocation node is a thread ID and a linked list of all the pointers that malloc has given me for that thread. as i add memory, i just stuff my memory blocks onto the head of the list.

i''ve changed things to have 256 linked lists in the thread allocation node, and i''m using a simple hash function to take bits 3-10 of the pointer (returned from malloc) as my hash key. i''ll check to see what kind of distribution that yields, but it should be pretty good. it was really easy to add and it''s made things MUCH faster. i might increase the hash table size even more since there''s only 1 thread allocation node per thread and the max # of threads shouldn''t be too high...

Share this post


Link to post
Share on other sites
Hello miles vignol,

Ok your in C, well that sucks a little.
Is there a particle reason to use C, and not C++. You can always call and use C in C++.

Any way sounds like your on the right track keep memory block store by thread id. And as long as you know what thread your killing. Which you do, you just need to find the memory_tid list that holds all the memory use by that thread right.

Have the a structure that the thread used th hold all infomation about the thread. one of these info would be the list entry then right before you kill the thread go to this list entry and grab the entry. then kill hte thread and fread the memory in the list enter. Do you get what I trying to say.

When you started the thread you should pass in the use defiend structure that the funtcion the thread runs uses to store states for the thread. this is your bridge between your ui thread and the process thread. The ui give this structure or more correctly a pointer to it, and the thread use it to store suff that the calling thread (ui) would like to know, like what list it use to keep all it memory.

don''t worry about sync htis structure since it a write by process thread and read by ui thread bridge and would only be use when your killing the process thread.

Does this help some ?

Lord Bart

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
quote:
Original post by Lord Bart
Ok your in C, well that sucks a little.
Is there a particle reason to use C, and not C++. You can always call and use C in C++.



Is there a particular reason you seem to think C sucks?

*mutters under breath at this guy*

quote:
vignol wrote:
ironically, i could just comment out my memory freeing functions in the operations and it''d be fine (since there''s a cleanup before exiting the thread)... but that just rubs me the wrong way. mainly because i don''t want the threading aspect to really have to be considered in the actual operation...



hmmm? if the OS takes care of the clean up, let it.

Share this post


Link to post
Share on other sites
Yes C sucks a little compare to C++ in some aspects.
Like in this case no STL containers.

But since you can do everything in C also in C++ it realy doesn't suck

Could warp a C function around the C++ map and have the your cake and eat it to.

On the freeing of memory.
I not sure about the system freeing up resources/memory form a thread.
It would depend greatly on the OS. You are only almost sure at process exit and system resource would be free. But I would not say thread is clean up only the OS stuf need to create the thread would be cleaned up. Since a thread is actual in the same memory space as the main process(main thread) how would the system know which thread a memory bolck belong to. I think it can't therefore you can assume memory will be realease back to the OS at thread termiantion.

Lord Bart


[edited by - lord bart on November 29, 2003 7:35:56 PM]

Share this post


Link to post
Share on other sites
as seems to be the case with programming, the act of describing my problem has actually given me insight into fixing it. i think it''s pretty good now...

here''s what i''m doing:

i''ve got two memory allocation functions -- one public and one private. the public allocations are the basic malloc/free functions that affect data that the whole program has access to. the private functions are designed to allocate memory for short term use for a particular function. the reason i need to tag these is to clean up in case a function is aborted by the user.

if a function does get aborted, i kill the thread and clean up it''s private memory. this version of memory cleanup is very quick because it''s simply stepping thru a list of malloc''d memory and it just free''s them one by one. it''s handled by the main/ui thread and not the OS.

if the function exits normally, it''s expected to clean up after itself (tho i do include the same cleanup function at normal termination just in case). the reason i want to do this is purely for algorithmic hygene. i don''t like the idea of just gabbing memory and assuming a garbage collection routine will straighten up after me. this is the slow part, having to search all the memory i''ve allocated for a particular block to free. this is where i''ve added the hash function and a table that''s now 1024 entries and pretty well distributed (i''m using bits 9-18 of the memory pointer).

anyway, it''s always "worked" but it was horribly slow before to free individual blocks of memory. particularly so because i was stuffing them at the begining of the list instead of the end which meant that if i free''d in the same order as they were allocated (which would happen a lot in this type of program) it would be a worse-case scenario. so now it seems to work and it''s much faster.

i use C because i like C (and never really learned C++). not to start the inevitable flame war, but C++ always struck me as a bit too much. i like the exlicitness and the terseness of C.

Share this post


Link to post
Share on other sites
Yeap I always find that after I talk about a programing problem with someelse I come up with better ways to program it to.

you should realy look at use C++, since you can still code with the erseness of C but you can use some of the tools(STL) when you need to.

basicly you can code C++ code just like C execpt the dumb stream format mess. I always default to printf and sprintf if I need to format.

But I love the constructor/destuctor for structs/class.

Lord Bart

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
quote:
Original post by miles vignol
the reason i want to do this is purely for algorithmic hygene. i don''t like the idea of just gabbing memory and assuming a garbage collection routine will straighten up after me.


If you are using C, and the memory allocated by a thread IS deleted upon termination of this thread WITHOUT manual intervention like you''re trying to do, THEN LET IT HAPPEN.

It is NOT garbage collection. Consider

malloc(34534534); exit(0);

Memory leak? NO! its fine! The OS dumps the allocated memory without even thinking twice about it. Its normal. The executable''s code loaded into memory is represented the exact same way as the allocated block of memory, are you going to come up with some convoluted method of figuring out where you''re exectuable memory block begins so you can free() that too? It''ll mean your code crashes, BUT AT LEAST WE EXPLICIT FREED ALL OUR MEMORY BEFORE EXITING! YEAH!

If you''re one of the freaks who gets bent out of shape with things like the above, GET RID OF YOUR OBSESSION. It is obviously detrimental to your code since you have now added (a) significant code complexity, (b) significant development time, and (c) additional bloat and increases in execution time.

In short, run a little test that creates a thread, allocates a bunch of memory, and terminates that thread, and repeats. If it doesn''t start eating up memory, delete all this excess code you''ve written.

Share this post


Link to post
Share on other sites
killing the thread doesn''t clean up the memory that thread has allocated. if it did, you''d need some way of "publishing" the thread''s allocated memory into the shared memory of the system.

if i simply leave off the self cleaning for each function, i can let my "free everything this thread has allocated" routine deal with it at a much faster rate (well, it''s not THAT much fastr now with the hash table)... but there''s a few drawbacks.

namely, it''s not what i expect to happen and that tends to cause confusion later down the road if the system isn''t doing what i (or others) naturally expect.

also, the execution path is not necessarily going to always split off a thread to run a particular function and i don''t want to get into having multiple versions of functions to support single thread or multi-thread. hell, i may even ditch the multi-thread approach entirely...


so now i''ve got another issue...

when interrupting a thread, i seem to hang up some times during a call to free in my cleanup routine. it seems to be waiting for the memory lock to clear, as though i''ve interrupted the thread in the middle of a call to free. so now i can''t call free anymore since it''s locked out (for MT purposes). that seems too dangerous to be how it works (killing a thread that owns a lock not releasing the lock) but that''s what seems to be happening... this is on win 2k...

Share this post


Link to post
Share on other sites
quote:
Original post by miles vignol
if i allocate memory and then abort part way thru, i need some way to know to clean up the private memory the thread allocated to do the particular operation it was working on. i''ve come up with a simple linked list wrapper for malloc/free/realloc that associates a thread ID with an allocated piece of memory, but since it''s a linked list, it''s really slow when the number of memory allocations gets up there.



Right, sorry this is more of a question and not an answer to your problem, but when you say private memory, what do you mean by that? I''ve always been under the impression that memory is shared by all threads of a task. So can''t you just enqueue pointers to no longer needed pieces of memory to some list and then at some later point signal some kind of cleanup thread to commence freeing the memory chunks referenced in that list? Sorry if I just totally misunderstood you.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
quote:
Original post by Red Ant
Right, sorry this is more of a question and not an answer to your problem, but when you say private memory, what do you mean by that? I''ve always been under the impression that memory is shared by all threads of a task. So can''t you just enqueue pointers to no longer needed pieces of memory to some list and then at some later point signal some kind of cleanup thread to commence freeing the memory chunks referenced in that list? Sorry if I just totally misunderstood you.


by "private", i just mean memory that other functions/threads don''t know or care about. certainly the memory is shared, but if the other threads don''t know where a block of memory is located, they can''t really use it till it''s returned to the pool.

the problem with the solution you suggest -- adding memory that needs to be free''d to a big list for later cleanup -- is that if you abort the process, you never get to the cleanup step. unless you add the memory right after you allocate it, which is pretty much what i''m doing.

Share this post


Link to post
Share on other sites
if your "worker" thread only uses your calls to your "private" alloc functions, simply add a critical section inside those, (EnterCriticalSection and LeaveCriticalSection in MSDN)

then you simply EnterCritcialSection on the same critical section in the main thread before you terminate the worker thread, if the worker thread is already in the crit sec (eg its allocating mem), then the main thread will stall momentarily until the worker thread is out of it, at which point the main thread will enter it, and can then terminate the worker thread knowing that the worker thread cant possibly be inside malloc or free).

Share this post


Link to post
Share on other sites
The easiest way is probably to make a special placement-new that allocates from a separately created heap. That way, you can destroy that heap on thread termination, and objects within it will disappear (though their destructors will not fire). You''ll also need a custom allocator for STL containers.

This is clumsy, however. It really comes down to the fact that C++ does not support asynchronous exceptions. If you can, avoid stuff like this. Why would the thread run for too long?


"Sneftel is correct, if rather vulgar." --Flarelocke

Share this post


Link to post
Share on other sites
narcist: i''m writing this to be cross-platform, so MS specific solutions are a little out of bounds. but i''m intrigued by your solution. if i understand, the "ciritical section" calls create a sort of resistance to termination? does the interrupt signal block until the critical section is over? perhaps i could simulate this with semaphores...


sneftel: i considered hacking an implementation of malloc to do something along those lines, but decided to post here first. i then figured out a hashing scheme that''s good enough for me.


''cept now i''ve got this damned deadlock thing which may still be a bug on my part. i can''t imagine killing a thread would leave things locked. it''s a new symptom that''s showing up after i made a change to avoid spawning threads that aren''t needed.

my program is a data-flow type system. in the quick and dirty threaded version, i spawn a thread for each operation and block until child threads are done. the better way is to only spawn a thread when there''s a bifrication in the flow chart. since implementing this, the new deadlock issue has come up... it may be something i''m doing.

oh yeah, a thread may run too long because it''s easy to make way too much geometry or to give bad parameters to a operation. or you just may become impatient and decide that waiting 5 minutes for something to finish is impractical.

Share this post


Link to post
Share on other sites
> my program is a data-flow type system.

I wrote such a system a while back. It used a thread pool that would pull tasks from a DAG-based task list and append them in the ''done'' list when finished. Each task could be split into other tasks, which were put back in the task list and their dependencies updated for other threads to pick up. The available tasks were locked with a semaphore whose count was based on the number of readily available tasks to run (using a dynamic topological sorting algo); threads would wait until a dependent task was finished if that was needed. By using a DAG-based task list, you can control the number of tasks that are concurently running.

> it''s easy to make way too much geometry or
> to give bad parameters to a operation

Tasks parameters should be pre-validated before entering the task list and you should look into the ability to split tasks into sub-tasks you put back in the task list. I don''t know what you are doing with your geometry, but things like NURBS tesselation can be split into a task tree fairly easily even when there are trim curves to deal with. (note: REYES aka RenderMan does that).

> you just may become impatient and decide that
> waiting 5 minutes for something to finish is impractical.

There could be a way to separate the task manager from the task execution code such as the task code is in a separate executable and the task manager spawns new processes with command-line parameters that correspond with your task parameters and recuperate results via a pipe; that way the cost of creating a new process is small compared to the computational time (5 minutes) of one single task and you can kill a task without causing heap problems.

-cb

Share this post


Link to post
Share on other sites
quote:
Original post by miles vignol
narcist: i''m writing this to be cross-platform, so MS specific solutions are a little out of bounds. but i''m intrigued by your solution. if i understand, the "ciritical section" calls create a sort of resistance to termination? does the interrupt signal block until the critical section is over? perhaps i could simulate this with semaphores...



I have never done any threading (other than really simple fork() stuff) on anything but windows so i dont know what is available on other platforms, but i can easily explain what a CriticalSection
is and you can see if there is analogy you can use to simulate it

basically the idea is that its an object that only one thread can own at once, a thread can "enter" or grab ownership of that object. If any other thread currently has ownership, then the thread will block until the other thread gives up ownership (by "leaving" the crit sec).

Another way of thinking of them, is that all the "space" between the enter and leave calls is protected, and only one thread can be in that space at once, if another thread is within that space, all other threads will wait at the "entrance" to the space, until the thread currently inside has left it.

They have nothing whatsoever to do with the thread termination, i was simply saying you put it around both the memory functions and the terminate thread function, that way you will only terminate the thread when its not in a memory func

Share this post


Link to post
Share on other sites
The best method is to jsut set a flag that the other thread sees and then exits normally.

I''m posting this real quick now, sorry if someone already suggested this and you didn''t think it was gonna work well enough...

Share this post


Link to post
Share on other sites
Am I the only one that thinks it''s ridiculous to create and destroy processes in an attempt to gain MT performance and automate the clean-up?

Make a thread pool, make the threads work, don''t terminate any of them until the entire app exits. Use a semaphore to synchronize the work load and a condition variable to signal when it''s time to exit and another cv to signal an abort the current operation.

Share this post


Link to post
Share on other sites
as for critical sections, that''s being dealt with via locks (mutex''s). the memory management uses these to keep two threads from trying to manipulate the memory structures at the same time.

the reason for creating threads and allowing them to be terminated is that i don''t want to get into having to write special code to routinely check for a particular exit condition. it seems easier to just start a thread when needed and then kill the thread if you need it to abort (or let it just finish on its own). perhaps there''s a performance hit, but i suspect there''d also be a performance hit if you''re constantly checking a variable to see if the system should abort itself.

the way i''m doing things now, i''ve got operations that rely on other operations. if an operation only has a single input, then there''s no thread created, it just executes that sub-operation and returns to continue the parent operation.

there''s no real way i can figure to pre-validate parameters. certainly i can check for errors, but if somebody wants to subdivide a piece of geometry into a particular number of polys, who am i to say they shouldn''t? because of the plug and unplug nature, i anticipate that somebody might plug something together they might not exactly have meant to, so perhaps two long operations might get stuck together than not only take forever, but return results that aren''t even useful.

also, there''s the aspect of updates. when a parameter is altered, it forces a recomputation of the geometry chain. but if the user is actually wanting to alter 3 or 4 parameters, it seems like torture to make them wait for a computation cycle after each. certainly they could alter their work habits to get around this, but i''d rather give them the control to pre-empt a task currently running.

Share this post


Link to post
Share on other sites
the deadlock issue i''m running into is because of the way SDL kills a signal. it warns that it''s not the best way and suggests that sending a signal to the thread is a better system. sounds good to me. but how the F do you send a signal in windows? i suppose raise() might work for me here, but i was hoping for kill()...

Share this post


Link to post
Share on other sites