Re: [Caml-list] OCaml troll on Slashdot

["Marcin 'Qrczak' Kowalczyk" <qrczak@knm.org.pl>]

brogoff <brogoff@speakeasy.net> writes:

>> It's not the fault of the mapping function but of the stack
>> being non-extensible. A user-written recursion can blow it too.
>> Functional programming is supposed to encourage recursion, and a
>> non-tail-recursive 'map' is much more readable than alternatives.
>
> Interesting approach. Do you have any information as to how big the
> performance hit is?

No.

I recall there was some paper which claimed that heap allocation is
significantly more expensive than stack allocation even with the most
clever GCs. I couldn't find it now. My stack frame allocation is very
similar to heap allocation.

What matters is not only the overhead of stack overflow checking
itself, but the combined effect of several interdependent design
choices. Even if I measured the cost of stack overflow checking in
isolation, it would not give a meaningful answer because it requires
and provides other things and thus the cost would be different if
applied to an implementation with different properties.

I implement a custom stack instead of using the system stack. Effects:
- a C global variable is used for the stack pointer instead of a
  machine register, thus stack frame allocation and access to stack
  contents is slower (even if it was not checked for overflow)
- checking for stack overflow adds overhead
+ tail call optimization is easier
+ scanning the stack by the GC is easier
+ portable green threads are easier
+ stack overflow is not fatal
+ triggering a context switch is done by faking the stack overflow
  condition, so it doesn't need an *additional* overhead (except that
  the stack limit is a volatile variable and allocation of a stack
  frame is one machine instruction longer because of that)

> I've never used SML/NJ except for a few toy programs, but I recall
> that it puts activation records on the Gc'ed heap (correct me if I'm
> wrong someone) so that call/cc is more efficient, so stack overflows
> shouldn't be a problem there either. Could you comment on why you
> chose extensible stacks rather than the SMLNJ approach for Kogut.

It should be slightly more efficient because allocating stack frames
doesn't increase the frequency of GCs, because stack frames don't need
to be copied by a copying GC, and because they don't need a link to
the previous frame (they do have a "descriptor" pointer though, which
stores their size and is also used to generate stack trace on uncaught
exceptions).

I haven't measured how large the efficiency difference is. It could
even be negative, because I must deallocate a stack frame explicitly,
but I doubt that.

> What I think you intend is that you'd rather it be easy to write
> safe code than that it be asy to write fast code, in the language.
> I wouldn't mind that, as long as it isn't ridiculously hard or
> impossible to do the latter in the language.

It's hard to allow everything...

The combined effect of dynamic typing, passing function arguments in
C global variables, using a custom stack and stack overflow checking
caused the Ackermann function to be 5 times slower than in C.

-- 
   __("<         Marcin Kowalczyk
   \__/       qrczak@knm.org.pl
    ^^     http://qrnik.knm.org.pl/~qrczak/