headers
Michael FIG | 2 May 15:02
Favicon

PipeStreams (aka. generators)

Hi all,

I created an interesting derivative of function/objects/Stream.st
called PipeStream.st.  It uses the POSIX <ucontext.h> functions to
implement fully deterministic coroutine-based streams whose producer
is a BlockClosure.  Any attempt to read the stream transfers control
to the producer coroutine (running on the same OS thread) where it
attempts to provide enough data to fill the request.  From the
producer's point of view, they just run to completion.

It's like other languages' "generators" feature, but without having to
do an explicit "yield".  The PipeStream machinery just detects when
you write enough objects back to it (or write a few then exit), then
resumes control in the reader.

I'm quite happy with it, and will be using it to separate my C
preprocessor into multiple pipelined parsing stages so that each stage
is independent and easier to debug.

The only downside I can see is that <ucontext.h> is not all that
common.  I don't know if something like it exists for Windows
(actually, NT Fibers could be abused to provide the same thing, I
think) or MacOS.  GNU Pth provides similar functionality, so it may be
possible to learn how to reimplement the context-switching features on
other platforms.

You also have to assign some stack space to the BlockClosure, and
eventually, it will be best to allocate that space from the caller's
stack so that it has the correct permissions.
(Continue reading)

Permalink | Reply |
headers
Andrew Gaylard | 2 May 15:18
Picon

Re: PipeStreams (aka. generators)

Hi Michael,

On Fri, May 2, 2008 at 3:04 PM, Michael FIG <michael-y8U0i/lyZOM@public.gmane.org> wrote:

The only downside I can see is that <ucontext.h> is not all that
common.  

A quick answer to your question: ucontext.h is part of the Single Unix
Specification, a superset of POSIX.1.  It is included in FreeBSD 5.2.1,
Linux 2.4.22, MacOS 10.3, and Solaris 9.  This is according to
"Advanced Programming in the Unix Environment" by Stevens and Rago,
second edition, p.30, a book I can recommend for answers to these
sorts of questions.
 
I don't know if something like it exists for Windows
(actually, NT Fibers could be abused to provide the same thing, I
think) or MacOS.  GNU Pth provides similar functionality, so it may be
possible to learn how to reimplement the context-switching features on
other platforms.

Of course, this doesn't say anything about Windows.  So I wouldn't bet
the farm on it working under Windows...

Andrew

<div>
<p>Hi Michael,<br><br></p>
<div class="gmail_quote">On Fri, May 2, 2008 at 3:04 PM, Michael FIG &lt;<a href="mailto:michael@...">michael@...</a>&gt; wrote:<br><blockquote class="gmail_quote">
<br>
The only downside I can see is that &lt;ucontext.h&gt; is not all that<br>
common. &nbsp;</blockquote>
<div>
<br>A quick answer to your question: ucontext.h is part of the Single Unix<br>
Specification, a superset of POSIX.1.&nbsp; It is included in FreeBSD 5.2.1,<br>
Linux 2.4.22, MacOS 10.3, and Solaris 9.&nbsp; This is according to<br>
"Advanced Programming in the Unix Environment" by Stevens and Rago,<br>
second edition, p.30, a book I can recommend for answers to these<br>
sorts of questions.<br>&nbsp;
<br>
</div>
<blockquote class="gmail_quote">I don't know if something like it exists for Windows<br>
(actually, NT Fibers could be abused to provide the same thing, I<br>
think) or MacOS. &nbsp;GNU Pth provides similar functionality, so it may be<br>
possible to learn how to reimplement the context-switching features on<br>
other platforms.</blockquote>
<div>
<br>Of course, this doesn't say anything about Windows.&nbsp; So I wouldn't bet<br>
the farm on it working under Windows...<br><br>Andrew<br>
</div>
</div>
<br>
</div>
Permalink | Reply |
headers
Cornelius Toole | 2 May 16:32
Picon

Re: PipeStreams (aka. generators)

The Windows NT Kernel is Posix compliant when using MS Windows
Services for Unix, so that includes Win XP (SP 1 or later) and Vista.
I believe this happened as a result of the US Federal government
requiring that all it's PCs be POSIX compliant.

On Fri, May 2, 2008 at 8:18 AM, Andrew Gaylard <ag@...> wrote:
> Hi Michael,
>
>
> On Fri, May 2, 2008 at 3:04 PM, Michael FIG <michael@...> wrote:
> >
> > The only downside I can see is that <ucontext.h> is not all that
> > common.
>
> A quick answer to your question: ucontext.h is part of the Single Unix
>  Specification, a superset of POSIX.1.  It is included in FreeBSD 5.2.1,
>  Linux 2.4.22, MacOS 10.3, and Solaris 9.  This is according to
>  "Advanced Programming in the Unix Environment" by Stevens and Rago,
>  second edition, p.30, a book I can recommend for answers to these
>  sorts of questions.
>
>
> > I don't know if something like it exists for Windows
> > (actually, NT Fibers could be abused to provide the same thing, I
> > think) or MacOS.  GNU Pth provides similar functionality, so it may be
> > possible to learn how to reimplement the context-switching features on
> > other platforms.
>
> Of course, this doesn't say anything about Windows.  So I wouldn't bet
>  the farm on it working under Windows...
>
> Andrew
>
>
> _______________________________________________
>  fonc mailing list
>  fonc@...
>  http://vpri.org/mailman/listinfo/fonc
>
>

--

-- 
Cornelius Toole, Jr.
Graduate Research Assistant
Louisiana State University
Center for Computation and Technology
mobile: 601.212.3045
Permalink | Reply |
headers
Michael FIG | 3 May 00:55
Favicon

Re: PipeStreams (aka. generators)

Of course, that all was much too easy. :P

It turns out that changing user contexts interacts badly with the
garbage collector (I now allocate the stacks with _libid->palloc, but
swapping stacks confuses libgc).  I can probably work around it, but
for the record, the patch I posted was too naive and should not be
used.

Sorry,

--

-- 
Michael FIG <michael@...> //\
   http://michael.fig.org/    \//
Permalink | Reply |
headers
Dan Amelang | 3 May 01:18
Picon

Re: PipeStreams (aka. generators)

On Fri, May 2, 2008 at 3:55 PM, Michael FIG <michael@...> wrote:
> Of course, that all was much too easy. :P

But I liked the general idea of your PipeStreams. I hope the
implementation issues can be overcome, perhaps by leveraging future
COLA developments (new GC, freedom from C stack, etc.).

Dan
Permalink | Reply |
headers
Michael FIG | 3 May 08:14
Favicon

Re: PipeStreams (aka. generators)

Hi,

"Dan Amelang" <daniel.amelang@...> writes:

> I hope the implementation issues can be overcome, perhaps by
> leveraging future COLA developments (new GC, freedom from C stack,
> etc.).

Doing some research on it, Hans Boehm seems to recommend treating
coroutines as a new port of libgc to another thread library.  So,
perhaps, the right thing to do for now is create a simple NxM
threading library and adapt libgc to it.

This is something that has been on my personal "fun projects" list for
quite some time, so I wouldn't mind giving it a shot.  Now that I have
VC++ Express Edition, I can even do something that will work under
Windows.

At least any GC changes should be valuable learning for future
architecture,

--

-- 
Michael FIG <michael@...> //\
   http://michael.fig.org/    \//
Permalink | Reply |
headers
Karl Robillard | 4 May 01:23

Re: Building on x86_64 Fedora 8

It looks like object/boot/idc1 fails to run on x86_64 because of a garbage 
collector problem.  It works if USE_GC is commented out in 
object/boot/src/libid.c.  Otherwise, _libid_bind() fails when findKeyOrNil is 
added with this line:

  method(_vtable,   "findKeyOrNil:",      findKeyOrNil_);

On i386, the <methodAt:put:with:> selector is found in _libid_mcache, but on 
x86_64 it looks like some pointers get changed (maybe after _vector__grow?).

-Karl
Permalink | Reply |

Gmane