Re: Single-threading servers and select()

[David Given <dg@...>]

On Monday 24 January 2005 02:54, skaller wrote:
[...]
> The problem doing that with the machine stack pointer
> is linear addressing -- the very thing that makes stacks
> fast also means you have to pre-allocate enough address
> space for their maximum size -- CPU's just don't
> have enough address space for lots of stacks.

A while back I was working on a Smalltalk-ish system. It's unfinished, but you 
can find the code here:

http://cvs.sourceforge.net/viewcvs.py/minitalk/minitalk/

Smalltalk has the very interesting feature that stack blocks are allocated off 
the garbage-collected heap, one per code invocation.

This means that while you need a memory allocation every time something is 
called (which is very cheap on a sufficiently advanced garbage collector), 
managing the stack is incredibly easy: they get garbage collected on demand. 
Code blocks (Smalltalk's version of continuations) just reference the stack 
block they were defined in, which means that that stack block won't get 
collected until the code block has gone away, which means that the code block 
can safely reference any locals in the stack block. (This is a cheap and easy 
way to do upvalues, although it's better to do them properly.)

You still need some compiler support to short-circuit the stack whereever 
possible --- for example, this code:

recursiveFunction
 'Hello, world!' printNl.
 self recursiveFunction

should *not* lead to a stack overflow, at least on any reputable Smalltalk 
system --- but it does make life an awful lot easier.

You can use this kind of feature for traditional languages, too, but you need 
compiler support. intent has the ability to chain to a new stack block on any 
call, if you ask it to. This doesn't happen very often, because the code 
needed to do this (that needs to get emitted in the function prologue) is a 
bit expensive, but it's useful on the entry points to, say, libraries.

Unix systems use the memory manager to allocate the stack on-demand. Each 
process gets a vast stack block, on the order of tens of megabytes, most of 
which is left unmapped. Whenever the stack extends into a new unmapped page, 
the kernel allocates a new page and drops it in. The process never notices 
the difference. This means you get a nice, linear stack very cheaply, but 
it's very wasteful of address space (as you're noticing), particularly on 
32-bit systems.

(Smalltalk is depressing. It was practically the first OO language, invented 
in the 80s, and if you study it you can see all the hot new features we're 
just discovering today: interfaces, aspect-oriented programming, pervasive OO 
(of course), fast VMs with JIT, extreme polymorphism, visual programming, 
persistance... it's a beautiful language to code in, and it's so *dead*.)

(If anyone cares, most of Minitalk is done; it'll happily run most code you 
throw at it. What I got bogged down doing was the 
message:notRecognizedWithArguments: selector that gets called if you call a 
method on an object that's not recognised, which requires some slightly hairy 
stack manipulation. It needs rewriting.)

-- 
+- David Given --McQ-+ "Quantum materiae materietur marmota monax si
|  dg@cowlark.com    | marmota monax meteriam possit materiari?" --- Henry
| (dg@tao-group.com) | Beard
+- www.cowlark.com --+