Sorry for the delay in responding. On Mon, 13 Jun 2011, Rafael Avila de Espindola wrote:> On 11-06-02 07:47 PM, Peter Lawrence wrote: >> Guys, >> regarding alloca. >> >> not only are exceptions a problem here, but just plain old "longjmp". > > Yes, > On IRC Sanjoy pointed out that it should be possible to handle this by > changing longjmp. I am not sure it can be done in general. The alloca > might have been called a dynamic number of times for example. > > In fact, now that I think of it, the presence of longjmp pretty much > forces a model where stacklets are not deallocated on return, just > reused if stack grows again.Perhaps only longjmp/exception throws need to not free stacklets- returns still do. Segmented stacks are exciting to me, but only if the stacklets can be freed. Here's why: if segmented stacks allow for "infinite" stacks, tail call optimization becomes a lot less important in functional languages- still useful, but not live or die. For example, the natural way to implement the map function over lists is: let rec map f lst match lst with | x :: xs -> (f x) :: (map f xs) | [] -> [] ;; Interestingly enough, this is also the fastest implementation of map. But it's not tail recursive- which means if you pass in a list long enough, you run out stack space and your program blows up. So you end up writing a much more complicated version which is also slower, but which is tail recursive. I'd love to have virtual infinite stacks- stacks which expanded as needed, but got freed when no longer needed. That means being tail recursive goes back to being nice, not necessary. Just my $0.02. Brian
On Thu, Jun 23, 2011 at 03:21:58PM -0400, Brian Hurt wrote:> Segmented stacks are exciting to me, but only if the stacklets can be > freed. Here's why: if segmented stacks allow for "infinite" stacks, tail > call optimization becomes a lot less important in functional languages- > still useful, but not live or die.We discussed this on IRC a while ago. IMHO it is good enough if the stack segments are kept in a double linked list and the allocation callback (slow path!) checks if the current segment is the last. If it isn't, it can reuse the next segment and free all others. Advantage is that longjmp/setjmp and stack unwinding functions just work. Function exit doesn't have to do any checks either, so it is faster. Down side is that a deep recursion followed by code not using much stack will keep the unused stack around potentially for ever. Joerg
On Thu, 23 Jun 2011, Joerg Sonnenberger wrote:> On Thu, Jun 23, 2011 at 03:21:58PM -0400, Brian Hurt wrote: >> Segmented stacks are exciting to me, but only if the stacklets can be >> freed. Here's why: if segmented stacks allow for "infinite" stacks, tail >> call optimization becomes a lot less important in functional languages- >> still useful, but not live or die. > > We discussed this on IRC a while ago. IMHO it is good enough if the > stack segments are kept in a double linked list and the allocation > callback (slow path!) checks if the current segment is the last. If it > isn't, it can reuse the next segment and free all others. > > Advantage is that longjmp/setjmp and stack unwinding functions just > work. Function exit doesn't have to do any checks either, so it is > faster. Down side is that a deep recursion followed by code not using > much stack will keep the unused stack around potentially for ever.Perhaps there can be a function that can be called to trim the stack (keep 1 segment and free the rest)? This could then be called occassionally- say, at the start of a GC pass. Brian