www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - StackThreads and Phobos

reply mclysenk mtu.edu writes:
Hello fellow D users!  I've been working diligently on improving StackThreads
(http://assertfalse.com), and so far D has worked wonderfully.  The same can not
be said for Phobos...  (This may get a bit long winded.)

---

1.  removeRange is really slow.

In order to prevent the garbage collector from accidentally deleting valid
objects, we need to mark the stack of each user-context.

One naive solution is to simply mark the entire stack region, however this isn't
a very good idea.

Say I create a user context which calls a function and then yields.  If that
function performed any allocations, then they would remain on the stack, and get
scanned by the GC.  Until I overwrite those values, the GC will always see them,
and therefore never collect their memory. 

This results in memory leaks, and a dramatic loss of performance.  The solution
is to dynamically resize the range used by the stack.  When we switch into a
context, we remove the range, and before we leave, we add it back.  This nicely
solves the problem, except for one thing - removeRange requires O(n) time.

This performance penalty applies to each Context, increasing the cost of
switching dramatically.

A simple solution is to use a hash set or another efficient data structure.
This would also be able to detect range address conflicts, such as adding a
range twice.

As a short term fix, I propose changing line 987 of internal/gcx.d from:

memmove(ranges + i, ranges + i + 1, (nranges - i) * ranges[0].sizeof);

to:

memmove(ranges + i, ranges + nranges, ranges[0].sizeof);

While this does not remove the sluggish linear search, it does eliminate a very
large memory copy.  The cost of this approach is that the ordering of ranges is
not preserved, which may increase look up time in some circumstances.

Another possibility is to allow for 'dynamic' ranges, which the user would be
able to resize.  In this situation, we could still use a linear search for
removal, however changing the range's dimensions is a constant time operation.
Thread safety could be insured via an atomic operation, ie CMPXCHG.


2.  It is impossible to safely handle a page fault.

Another problem with StackThreads right now is stack growth.  In a regular
context, the operating system automatically grows the stack once the program
hits the bottom.  It keeps on doing this until there is no more address
space/memory left, and then it throws an overflow.

In StackThreads, I'd like to do the same thing.  However, DMD transforms any
page faults into exceptions, which it then unwinds up the call stack.  This
makes it impossible to trap, since the exception handler will unwind the stack
until it hits a try block with a matching catch - and only then will it get
handled.  From this state, there is no way to recover the program, since we
cannot undo the unwind.  The only tenable option is a global fault and
termination of the context.

In windows, you could try to install a custom exception handler, and trap any
stack overflows yourself - except DMD automatically installs an SEH for each
try..catch block.  It is pretty much inevitable that a hapless user will eat
your page fault when he is trying to catch some other sort of exception.

Call backs are one solution, user programs can carefully handle page faults and
stack overflows without disturbing the state of the program.


---

There are a few more issues, but these are the only two I have encountered that
I couldn't hack around.

My personal view is that integrated user-context switching would fix most of
those issues, and provide a great deal of flexibility.  Once the GC issues are
resolved, it can be made very fast.  In fact, the only overhead (outside GC
management) is equivalent to a single function call.

Standard user level contexts make all sorts of things possible, like coroutines
or micro threads.  They can be used to iterate over complex data structures
trivially.  They are much simpler and faster than threads for GUIs, and
eliminate the need for many state machine objects.

In conjunction with standard preemptive threading, user-contexts provide an
elegant solution to many practical programming problems.  Standard library
integration will result in a much faster context switching and better future
support.


-Mikola Lysenko
Jun 30 2006
parent reply Bruno Medeiros <brunodomedeirosATgmail SPAM.com> writes:
mclysenk mtu.edu wrote:
 Hello fellow D users!  I've been working diligently on improving StackThreads
 (http://assertfalse.com), and so far D has worked wonderfully.  The same can
not
 be said for Phobos...  (This may get a bit long winded.)
 
 ---
 
 1.  removeRange is really slow.
 
 In order to prevent the garbage collector from accidentally deleting valid
 objects, we need to mark the stack of each user-context.
 
 One naive solution is to simply mark the entire stack region, however this
isn't
 a very good idea.
 
 Say I create a user context which calls a function and then yields.  If that
 function performed any allocations, then they would remain on the stack, and
get
 scanned by the GC.  Until I overwrite those values, the GC will always see
them,
 and therefore never collect their memory. 
 
 This results in memory leaks, and a dramatic loss of performance.  The solution
 is to dynamically resize the range used by the stack.  When we switch into a
 context, we remove the range, and before we leave, we add it back.  This nicely
 solves the problem, except for one thing - removeRange requires O(n) time.
 

But isn't that the correct behavior? If one can return to that function instance(context), shouldn't all allocations made previously by that function remain valid? (note: I haven't used your library, I just read your post and this question came up) Also: Where do you keep the data from each context? In the heap? -- Bruno Medeiros - CS/E student http://www.prowiki.org/wiki4d/wiki.cgi?BrunoMedeiros#D
Jul 02 2006
parent reply mclysenk mtu.edu writes:
In article <e88ltq$kvc$3 digitaldaemon.com>, Bruno Medeiros says...
But isn't that the correct behavior? If one can return to that function 
instance(context), shouldn't all allocations made previously by that 
function remain valid?
(note: I haven't used your library, I just read your post and this 
question came up)

It is not correct behavior. Here's an example which may illustrate this better: #void func1() #{ # func2(); # yield(); #} # #void func2() #{ # int[] arr = new int[20]; #} Here is a trace of the execution of func1 alongside it's stack # Instruction | Stack #--------------------------+-------------- # func2() | SP> &func1 + offset # | # int[] arr = new int[20] | &func1 + offset # | SP> &arr # | # return from func2() | SP> &func1 + offset # | &arr <-- Old unused reference # | # yield() | &func1 + offset # | &arr <-- Will NEVER get collected # | In this situation, it is doubtful that arr will ever get collected. In order for the GC to remove it, it must not find ANY references to arr in memory. Period. If the GC scans the entire stack, it will see a reference to arr, and therefore it will never collect arr. This is a trivial example, but it is not difficult to see that these sorts of memory leaks can become very substantial and very difficult to track down. The problem is how to tell the garbage collector not to scan past the stack pointer. The only way at the moment is to use addRange and removeRange, or zero out all of the unused stack memory every time you yield. Either option has a substantial overhead.
Also: Where do you keep the data from each context? In the heap?

Heap. The next version of stackthreads will replace malloc/free with system specific allocators, such as mmap and VirtualAlloc. -Mikola Lysenko
Jul 02 2006
parent reply Bruno Medeiros <brunodomedeirosATgmail SPAM.com> writes:
mclysenk mtu.edu wrote:
 In article <e88ltq$kvc$3 digitaldaemon.com>, Bruno Medeiros says...
 But isn't that the correct behavior? If one can return to that function 
 instance(context), shouldn't all allocations made previously by that 
 function remain valid?
 (note: I haven't used your library, I just read your post and this 
 question came up)

It is not correct behavior. Here's an example which may illustrate this better: #void func1() #{ # func2(); # yield(); #} # #void func2() #{ # int[] arr = new int[20]; #} Here is a trace of the execution of func1 alongside it's stack # Instruction | Stack #--------------------------+-------------- # func2() | SP> &func1 + offset # | # int[] arr = new int[20] | &func1 + offset # | SP> &arr # | # return from func2() | SP> &func1 + offset # | &arr <-- Old unused reference # | # yield() | &func1 + offset # | &arr <-- Will NEVER get collected # | In this situation, it is doubtful that arr will ever get collected. In order for the GC to remove it, it must not find ANY references to arr in memory. Period. If the GC scans the entire stack, it will see a reference to arr, and therefore it will never collect arr. This is a trivial example, but it is not difficult to see that these sorts of memory leaks can become very substantial and very difficult to track down. The problem is how to tell the garbage collector not to scan past the stack pointer. The only way at the moment is to use addRange and removeRange, or zero out all of the unused stack memory every time you yield. Either option has a substantial overhead.
 Also: Where do you keep the data from each context? In the heap?

Heap. The next version of stackthreads will replace malloc/free with system specific allocators, such as mmap and VirtualAlloc. -Mikola Lysenko

Unless my understanding of this is wrong, the use of the word "never" (gets collected) is too strong. If during normal program flow the stack is overwritten again, the reference becomes free. Or am I missing something? Also, doesn't this happen with any regular function? -- Bruno Medeiros - CS/E student http://www.prowiki.org/wiki4d/wiki.cgi?BrunoMedeiros#D
Jul 03 2006
parent reply mclysenk mtu.edu writes:
In article <e8artd$16e0$1 digitaldaemon.com>, Bruno Medeiros says...
Unless my understanding of this is wrong, the use of the word "never" 
(gets collected) is too strong. If during normal program flow the stack 
is overwritten again, the reference becomes free. Or am I missing something?
Also, doesn't this happen with any regular function?

Well, you are correct, that it may still get collected in the future - regardless, its prospects are fairly dim. You are also right in your statement that this is not abnormal behavior for functions, and the GC knows this. It has a special case which handles the stack of a regular function. When the GC does a full collect, it pauses all threads and marks the range from the stack pointer to the bottom of the stack. This prevents it from scanning stuff which is no longer valid, since that range never gets marked. This works very well. The bad part happens when we create multiple stacks for one thread. In order for the GC to properly scan them, we need to mark their stack when it is not in use. If the GC didn't scan their stack, then we'd accidentally over-collect stuff they were using. If we mark the entire stack range, then we'd under-collect and get a bunch of memory leaks. To fix this, we use addRange to mark the active part of their stack before we switch out their context, and removeRange to delete their old - and potentially invalid - stack range when we switch into their context. This part is tricky, and it burned me many times while I was working on stack threads before I finally caught on. It is not a big deal to fix once you know what's happening. The main disadvantage at the moment is removeRange - it's just too slow! It can be fixed, but it requires changing phobos. -Mikola Lysenko
Jul 03 2006
parent reply Bruno Medeiros <brunodomedeirosATgmail SPAM.com> writes:
mclysenk mtu.edu wrote:
 In article <e8artd$16e0$1 digitaldaemon.com>, Bruno Medeiros says...
 Unless my understanding of this is wrong, the use of the word "never" 
 (gets collected) is too strong. If during normal program flow the stack 
 is overwritten again, the reference becomes free. Or am I missing something?
 Also, doesn't this happen with any regular function?

Well, you are correct, that it may still get collected in the future - regardless, its prospects are fairly dim. You are also right in your statement that this is not abnormal behavior for functions, and the GC knows this. It has a special case which handles the stack of a regular function. When the GC does a full collect, it pauses all threads and marks the range from the stack pointer to the bottom of the stack. This prevents it from scanning stuff which is no longer valid, since that range never gets marked. This works very well. The bad part happens when we create multiple stacks for one thread. In order for the GC to properly scan them, we need to mark their stack when it is not in use. If the GC didn't scan their stack, then we'd accidentally over-collect stuff they were using. If we mark the entire stack range, then we'd under-collect and get a bunch of memory leaks. To fix this, we use addRange to mark the active part of their stack before we switch out their context, and removeRange to delete their old - and potentially invalid - stack range when we switch into their context. This part is tricky, and it burned me many times while I was working on stack threads before I finally caught on. It is not a big deal to fix once you know what's happening. The main disadvantage at the moment is removeRange - it's just too slow! It can be fixed, but it requires changing phobos. -Mikola Lysenko

That was clear now, but for what I understand, then your problem is simply that you must use removeRange(and it is slow). That is, it doesn't really have to do with function contexts and stacks. Anyone who allocates manually managed memory for any purpose, and then uses addRange on it, will have the same problem, right? (because they too will have to use removeRange) -- Bruno Medeiros - CS/E student http://www.prowiki.org/wiki4d/wiki.cgi?BrunoMedeiros#D
Jul 03 2006
parent mclysenk mtu.edu writes:
In article <e8baer$1ond$1 digitaldaemon.com>, Bruno Medeiros says...
That was clear now, but for what I understand, then your problem is 
simply that you must use removeRange(and it is slow).
That is, it doesn't really have to do with function contexts and stacks. 
Anyone who allocates manually managed memory for any purpose, and then 
uses addRange on it, will have the same problem, right? (because they 
too will have to use removeRange)

Correct. This problem will affect everyone who uses addRange/removeRange. -Mikola Lysenko
Jul 03 2006