Beta
×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

Protothreads and Other Wicked C Tricks

CowboyNeal posted about 9 years ago | from the working-as-intended dept.

Programming 229

lwb writes "For those of you interested in interesting hard-core C programming tricks: Adam Dunkels' protothreads library implements an unusually lightweight type of threads. Protothreads are not real threads, but rather something in between an event-driven state machine and regular threads. But they are implemented in 100% portable ANSI C and with an interesting but quite unintuitive use of the switch/case construct. The same trick has previously been used by Simon Tatham to implement coroutines in C. The trick was originally invented by Tom Duff and dubbed Duff's device. You either love it or you hate it!"

Sorry! There are no comments related to the filter you selected.

it.slashdot.org? (-1, Offtopic)

bit trollent (824666) | about 9 years ago | (#13735815)

more like developers.slashdot.org

amicorrect?

Looks pretty cool (4, Interesting)

bobalu (1921) | about 9 years ago | (#13735824)

I used a Lifeboat lib back in the late 80's that this reminds me of. Cooperative multitasking. Eventually ported the whole thing to OS/2 and used that threading instead. All the code pretyy much worked as-is.

I guess the idea is it's extremely portable. (5, Informative)

skids (119237) | about 9 years ago | (#13736017)

...not bound to any particular OS.

If that's what folks are looking for, another option is the tasks added to LibGG a while back. Tradeoffs either way -- LibGG's requires at least C signals (but will use pthreads or windows threads if detected during compile time), whereas this can be used in OS-less firmware. But on the positive side you can use switch() in LibGG tasks -- what
you can't use are a lot of non-MT-safe system calls. It's an OK abstraction but of course there are so very many ways to accidentally ruin portability that it is far from foolproof.

http://www.ggi-project.org/documentation/libgg/1.0 .x/ggAddTask.3.html [ggi-project.org]

Re:I guess the idea is it's extremely portable. (5, Insightful)

twiddlingbits (707452) | about 9 years ago | (#13736089)

It is bound to a paticular KIND of OS. This code would not work right in a pre-emptive multi-tasking OS unless it was the highest priority task. It works best without an OS as it makes it's own blocking.

I read his paper where he said "writing an event-driven system is hard". I guess he has never heard of a using Finite State Automata for the design? State machines are very simple to program. An event driven system is not at all hard to write, although you often times do have to have some deep hardware and/or procesor knowledge to do it well. I wrote many of them in the 1980's when I did embedded C code for DOD work, although I have not done so in quite a few years. Once Ada came along everyone abandoned C as too obtuse for embedded work for the DOD. I once did benchmarks that showed decent C code without strong optimization outperformed Ada code, but C was dead already in their minds. I'm glad to see some folks are still interested in it on the commercial side of programming. After all we can't write everything in Java ;)

Re:I guess the idea is it's extremely portable. (5, Informative)

plalonde2 (527372) | about 9 years ago | (#13736397)

The challenge is making the design maintainable. There isn't a program that can't be written as a state machine; but most programs expressed this way are difficult to understand and maintain.

The argument that Rob Pike makes in A Concurrent Window System [swtch.com] and with Luca Cardelli in Squeak: a Language for Communicating with Mice [microsoft.com] is that many of the event systems and associated state machines that we write can be much simplified by treating input multiplexing, and thus coroutine-like structures, as language primitives.

This work follows directly from Hoare's Communicating Sequential Processes - a good summary can be found here [swtch.com] . Working with CSP only a little has convinced me of how much easier so many systems tasks are in this framework than in the world of the massive state-system/event loop world.

Re:I guess the idea is it's extremely portable. (1)

Curate (783077) | about 9 years ago | (#13737000)

Once Ada came along everyone abandoned C as too obtuse for embedded work for the DOD. Point of clarification: Ada predates C. Your group may have switched to Ada at one point in the 80s, but Ada was very old by then. DoD used Ada for some things over C because they perceived (correctly) that Ada was a safer language. For instance, it is impossible to have a dangling pointer in Ada. It is also impossible for variables to take on values outside of bounds that you specify.

Job security? (4, Funny)

elgee (308600) | about 9 years ago | (#13735829)

So this is so "counterintuitive" that no one else will ever understand your code?

Sounds ideal!

This is cool. (-1, Flamebait)

Anonymous Coward | about 9 years ago | (#13735843)

But all you Java lovers will no doubt sneer at it. You suck.

Wait just a minute ... (0, Offtopic)

Anonymous Coward | about 9 years ago | (#13735902)

1) Your operating system in written in Java.
2) Your email client in written in Java.
3) Your browser is written in Java.
4) Your music player is written in Java.
5) Perl in written in Java.
6) Your word processer is written in Java.

So there !!! Java rules !!!

Re:Wait just a minute ... (-1, Offtopic)

Anonymous Coward | about 9 years ago | (#13735922)

I'm glad to see that you realized the 's' key is not next to the 'n' key and that is != in.

Re:Wait just a minute ... (0)

Anonymous Coward | about 9 years ago | (#13735999)

my grammar checker is written in c

Re:Wait just a minute ... (4, Funny)

LLuthor (909583) | about 9 years ago | (#13735970)

And the JVM is written in C :)

Re:Wait just a minute ... (1)

InvalidError (771317) | about 9 years ago | (#13736203)

Actually, since Java has some machine binary compilers, nothing stops people from rewriting most of the JRE in Java.

Before people could use text editors, someone had to input them as direct machine language... same thing goes even for ASM compilers. The first compiler and runtime environment generation has to be created from existing technologies but nothing (other than motivation or justification) is preventing it from coming full-circle.

Re:This is cool. (1)

idiotdevel (654397) | about 9 years ago | (#13735916)

not a problem in c# though :)

just put a nice "unsafe" modifier and start using pointers... on linux via mono... oh yeah

From the source: (5, Informative)

MythMoth (73648) | about 9 years ago | (#13735847)

Duff on Duff's Device:
http://www.lysator.liu.se/c/duffs-device.html [lysator.liu.se]

Re:From the source: (1)

HappyCleanerDude (153109) | about 9 years ago | (#13736016)

Amazing code. Loved the comment: "Disgusting, no? But it compiles and runs just fine. I feel a combination of pride and revulsion at this discovery." that Duff made -- back in '83!

This is both the strength and weakness of C -- you can do anything you want, and, you can do anything you want!

It is refreshing to see this in a sea of "development environments."

Re:From the source: (0)

Anonymous Coward | about 9 years ago | (#13736202)

Hey ive been tricked wheres the hillary duff pron?

...sane detexi hanc marginis exiguitas non caperet (2, Interesting)

abb3w (696381) | about 9 years ago | (#13736240)

From the summary: Protothreads are not real threads, but rather something in between an event-driven state machine and regular threads.

From the above Duff on Duff's Device: I have another revolting way to use switches to implement interrupt driven state machines but it's too horrid to go into.

Perhaps this is the Duff's Device equivalent of a proof of Fermat's Last Theorem? Or is my ignorance of the history of Evil Computing showing?

Re:From the source: (4, Funny)

Bastian (66383) | about 9 years ago | (#13736243)

Wow. And I used to think C was frightening when I discovered the fun you can have with a program that takes command-line arguments when you start making recursive calls to main().

When I saw that code snippet, I found myself switching back and forth between thinking "this is the most beautiful thing I have ever seen" and "dear god, who ordered that monster" so rapidly my brain almost a sploded.

Recursive main() (1)

David Gould (4938) | about 9 years ago | (#13736270)


  Wow. And I used to think C was frightening when I discovered the fun you can have with a program that takes command-line arguments when you start making recursive calls to main().

And just what's wrong with that?

Recursive main() (0)

Anonymous Coward | about 9 years ago | (#13736833)

sweet jesus. i remeber learning recursion in college (not too long ago). now i find out main() can be recursive? will the madness never end?? God i need to code again... too much tech support...

sobleq??? (1)

yonyonson (645097) | about 9 years ago | (#13736345)

The VAX C compiler compiles the loop into 2 instructions (a movw and a sobleq, I think.) As it turns out, this loop was the bottleneck in a real-time animation playback program which ran too slowly by about 50%. The standard way to get more speed out of something like this is to unwind the loop a few times, decreasing the number of sobleqs.
What exactly is a sobleq? i'm assuming it's a VAX assembler statement, but i've never seen it before and was wondering if any of you knew how it worked.

Thanks

Re:sobleq??? (1)

plalonde2 (527372) | about 9 years ago | (#13736412)

Subtract One and Branch if Less than or EQual

Re:From the source: (1)

astrosmash (3561) | about 9 years ago | (#13736646)

And for context, here's the original thread in which Duff's post appears:

Google Groups [google.com]

Seen this already (5, Funny)

Anonymous Coward | about 9 years ago | (#13735848)

I first came across this while I was working on the e-voting machines. There was a dept especially allocated to investigating how to hide certain features in c code to make them look like soemthing else.

what a stoner sees (0)

FFON (266696) | about 9 years ago | (#13735858)

Potheads and other wicked cool tricks

Implementation in languages? (2, Insightful)

Poromenos1 (830658) | about 9 years ago | (#13735861)

I don't program in C that much any more, but it would be nice if this was implemented in higher level languages. I don't know if they would gain anything, but it's at least interesting.

Re:Implementation in languages? (1)

Poromenos1 (830658) | about 9 years ago | (#13735883)

And by that, I mean that the interpreters of languages (Python, Lua, etc) would use this to implement their threads in.

Re:Implementation in languages? (2, Interesting)

Anonymous Coward | about 9 years ago | (#13735957)

Protothreads are quite limited in what they can do - they are just a way of expressing a state machine using co-routines.

Real threads are much better for things like interpreters. JIT compilation with native threads is even better.

Re:Implementation in languages? (1)

meowsqueak (599208) | about 9 years ago | (#13736179)

Just curious - in what ways do you think they are more limited? A OS threading mechanism is just a glorified state machine anyway. I agree that these sorts of 'threads' (or 'fibers' as they are known in Windows) run into troubles with blocking I/O, but with async. I/O they are quite useful once you've got some thread management mechanisms incorporated.

Re:Implementation in languages? (1)

BillyBlaze (746775) | about 9 years ago | (#13736358)

One big practical limitation is that you can't actually take advantage of multiple CPUs. This used to not be very important, but with dual-core CPUs available, it's likely there will be a huge increase in the number of desktop machines with SMP. Granted you could modify these systems to run in two threads, but then you lose the cross-platform abilities which are the main benefit. If you can create 2 threads on all systems you support, why not just create as many as you need? It ends up making more sense to abstract the threading and locking primitives provided by the OSs you run on.

Python (4, Interesting)

meowsqueak (599208) | about 9 years ago | (#13736166)

Weightless threads in Python:

http://www-128.ibm.com/developerworks/library/l-py thrd.html [ibm.com]

They are cooperative but far more efficient than Python's own threading model. You can easily create hundreds of thousands of concurrent threads.

Re:Python (1)

Hast (24833) | about 9 years ago | (#13736621)

From the desription it seems like Python stackless [stackless.com] .

Re:Python (1)

meowsqueak (599208) | about 9 years ago | (#13736715)

Yes, it's similar in many respects, but does not require the Stackless infrastructure. I'm not saying either way which is better.

Python's way ahead of ya (2, Informative)

xant (99438) | about 9 years ago | (#13736287)

Actually, I don't know if this is exactly the same feature, but it sounds like it can be used that way. Check out the What's new in Python [python.org] entry. This is currently implemented in Python CVS, to be available in Python 2.5.

The actual Python Enhancement Proposal [python.org] gives more detail and several badass use-cases.

Re:Python's way ahead of ya (0)

Anonymous Coward | about 9 years ago | (#13736632)

YUCK! Why do the Python folks insist on crapifying and half-baking concepts like this all the time?
Are they allergic to *generality*? They should just implement continuations and be done with it.

def counter (maximum):
    i = 0
    while i < maximum:
        val = (yield i)
        # If value provided, change counter
        if val is not None:
            i = val
        else:
            i += 1

Re:Python's way ahead of ya (1)

Courageous (228506) | about 9 years ago | (#13736720)

They should just implement continuations and be done with it.

It's been tried. There were problem with 3rd party C libraries. It's not like you can hand-wavey, hand-wavey, and suddenly C itself is stackless. That's what Christian Tismer ran up against, why the PEP to add continuations to Python was ultimately rejected.

C//

Re:Implementation in languages? (1)

The boojum (70419) | about 9 years ago | (#13736995)

Lua at least already has something like this. They're called asymmetric coroutines. Also check out Scheme, Scheme's had continuations forever and some folks have done interesting things with them.

Re:Implementation in languages? (1)

lux55 (532736) | about 9 years ago | (#13736094)

I agree. What about PHP for example? Is there some clever trick that could be done like this that would enable a thread-like behaviour, since PHP currently lacks the ability to spawn threads? Processes it does, but not threads, and the two are just different enough to limit PHP's general applicability outside of web apps...

Re:Implementation in languages? (0)

Anonymous Coward | about 9 years ago | (#13736170)

Yeah, it's kind of sad that in PHP the best way to spawn threads (conceptually, not per computer-science) in PHP is to open a socket to a page on your own system and close it immediately thus running another page in the background. Actually, it's not even conceptually the same as a thread... damn PHP.

Re:Implementation in languages? (1)

nerdwarrior (154941) | about 9 years ago | (#13736520)

Try call-with-current-continuation (a.k.a. call/cc) in Scheme or any of the other functional languages. call/cc lets you write co-routines (and many other powerful control constructs) quite easily, and co-routines are much more powerful than this protothread trick. A favorite for Schemers showing off the power of call/cc is the amb macro (which uses call/cc internally). The following code can actually be written in Scheme (after adding the amb and assert macros): (let ((x (amb 1 2 3)) (y (amb 4 5 6))) (begin (assert (= (+ x y) 7) ; once execution reaches here, x and y have values such that x + y = 7. ...))) amb "magically" chooses one of its arguments which causes the computation to eventually succeed. Under the hood, amb uses call/cc to save away the current context and backtrack when a failure occurs.

Re:Implementation in languages? (2, Informative)

betterthancats (660632) | about 9 years ago | (#13736582)

Well, there is always erlang [erlang.org] .

I'm kind of surprised it hasn't been mentioned yet.

It isn't Duff's device. (3, Interesting)

mc6809e (214243) | about 9 years ago | (#13735872)


Duff's device is a way of forcing C to do a form of loop unrolling. It has nothing to do with coroutines.

Re:It isn't Duff's device. (0)

Anonymous Coward | about 9 years ago | (#13735910)

But it uses the switch-statement in a non-standard way. Nobody claimed that this was Duff's device.

Re:It isn't Duff's device. (1)

plalonde2 (527372) | about 9 years ago | (#13736083)

Perhaps "non-standard" but it is standards compliant.

Re:It isn't Duff's device. (4, Informative)

LLuthor (909583) | about 9 years ago | (#13735911)

Duff's device was the first convoluted form of a switch() statement which became well known.
All these C "tricks" employ the same technique (though more elegantly) for different goals. Nonetheless, Duff's device can be said to have inspired such code.

Re:It isn't Duff's device. (3, Insightful)

Anonymous Coward | about 9 years ago | (#13736021)

From Duff's 1983 usenet post:

"Actually, I have another revolting way to use switches to implement interrupt driven state machines but it's too horrid to go into."

Re:It isn't Duff's device. (0)

Anonymous Coward | about 9 years ago | (#13736450)

ya and I have a proof for fermat's last theorm but I don't have enough room in the margin to write it, so I won't. k thx gg

Re:It isn't Duff's device. (2, Interesting)

raytracer (51035) | about 9 years ago | (#13736648)

Tom clarified this on my blog. [brainwagon.org]
Yeah. I knew this. In my piece about The Device, I mention something about a similar trick for interrupt-driven state machines that is too horrible to go into. This is what I was referring to. I never thought it was an adequate general-purpose coroutine implementation because it's not easy to have multiple simultaneous activations of a coroutine and it's not possible using this method to have coroutines give up control anywhere but in their top-level routine. A simple assembly-language stack-switching library lets you do both of those.
Still, a pretty cute thing.

Re:It isn't Duff's device. (1)

eraserewind (446891) | about 9 years ago | (#13736106)

It can be used to implement coroutines in C. Google for "coroutines in C". any of the first bunch of links talk about it.

Re: It isn't Duff's device. (4, Informative)

shalunov (149369) | about 9 years ago | (#13736336)

It most certainly is the Duff's device, or at least is very close to it. Duff's device is, indeed, a way to unroll loops; specifically, a way to unroll loops that uses a peculiarity in switch statement syntax that allows case to point inside a loop body. Now, take a look at lc-switch.h in the Protothreads tarball. It contains macros that use the same peculiarity to jump inside functions instead of loops.

you misread (1)

toby (759) | about 9 years ago | (#13736654)

The summary only claims that the 'interesting but quite unintuitive use of the switch/case construct' is originally Duff's device, not application to coroutines.

Rob Pike invented this in 1985 (4, Informative)

dmoen (88623) | about 9 years ago | (#13735876)

This looks very similar to the implementation technique used for the Squeak programming language (not the Smalltalk Squeak). Squeak is a preprocessor for C that makes it very easy to use this technique.

http://citeseer.ist.psu.edu/cardelli85squeak.html [psu.edu]

Doug Moen

Re:Rob Pike invented this in 1985 (2, Informative)

Anonymous Coward | about 9 years ago | (#13736123)

He couldn't have invented it in 1985 since Duff sent his original mail in 1983:

From research!ucbvax!dagobah!td Sun Nov 13 07:35:46 1983
Received: by ucbvax.ARPA (4.16/4.13) id AA18997; Sun, 13 Nov 83 07:35:46 pst
Received: by dagobah.LFL (4.6/4.6b) id AA01034; Thu, 10 Nov 83 17:57:56 PST
Date: Thu, 10 Nov 83 17:57:56 PST
From: ucbvax!dagobah!td (Tom Duff)
Message-Id:
To: ucbvax!decvax!hcr!rrg, ucbvax!ihnp4!hcr!rrg, ucbvax!research!dmr, ucbvax!research!rob

neat way in C to express an old trick (2, Informative)

bani (467531) | about 9 years ago | (#13735886)

While it is probably the first time the copy technique had been expressed in C, it's certainly not the first time the actual technique had been expressed in code.

I recall seeing the same trick implemented in assembler somewhat earlier, I think the technique was called towers?

Not new (4, Informative)

Anonymous Coward | about 9 years ago | (#13735928)

SGI had state threads library since long http://oss.sgi.com/state-threads [sgi.com]

Re:Not new (0)

Anonymous Coward | about 9 years ago | (#13736944)

Yep, state threads library is 1000% more useful than this hack. Can be found here: http://state-threads.sourceforge.net/ [sourceforge.net]

Dosen't work as advertised! (-1, Troll)

Anonymous Coward | about 9 years ago | (#13735956)

NAA Announces Corporate Downsizing and Administrative Reformation
GNAA Announces Corporate Downsizing and Administrative Reformation

Misha Borovsky (GNAP) - Hollywood - GNAA President timecop announced at a press conference this morning that the Gay Nigger Association of America is in the midst of a large effort to reduce operating costs and streamline business processes. "Layoffs of approximately fifty percent of the gay workforce are to be expected, as well as a shifting in administrative functions," timecop was quoted as saying. Analysts predict this corporate downsizing was made necessary due to over-investment into the New Orleans area, when it was announced last year that the GNAA would be opening a state-of-the-art branch office on the coast. The building was nearing completion and just opening for business when it was destroyed by hurricane Katrina, which has been recently found to be the responsibility of Jews. As George W. Bush is noted for not caring about black people, FEMA has refused to pay for the repairs, and the project was scrapped.

"We are also making internal changes to the corporate information technology intranet," said supers, CTO for GNAA Worldwide Operations. "Many of our information moving processes were running on the Lunix platform, and this was generating large costs due to system slowness and instability. After a careful usability study, we have found that we will be saving millions of dollars [USD] per year by switching to the Microsoft Windows 2003 Server System".

timecop ended the conference by announcing, "We'll always be there for the gay niggers of the world. With this restructuring of the organization, we are enabled to offer twice the service for a fraction of the cost. It's a new gay universe ahead."



About GNAA:
GNAA (GAY NIGGER ASSOCIATION OF AMERICA) is the first organization which gathers GAY NIGGERS from all over America and abroad for one common goal - being GAY NIGGERS.

Are you GAY [klerck.org] ?
Are you a NIGGER [mugshots.org] ?
Are you a GAY NIGGER [gay-sex-access.com] ?

If you answered "Yes" to all of the above questions, then GNAA (GAY NIGGER ASSOCIATION OF AMERICA) might be exactly what you've been looking for!
Join GNAA (GAY NIGGER ASSOCIATION OF AMERICA) today, and enjoy all the benefits of being a full-time GNAA member.
GNAA (GAY NIGGER ASSOCIATION OF AMERICA) is the fastest-growing GAY NIGGER community with THOUSANDS of members all over United States of America and the World! You, too, can be a part of GNAA if you join today!

Why not? It's quick and easy - only 3 simple steps!
  • First, you have to obtain a copy of GAYNIGGERS FROM OUTER SPACE THE MOVIE [imdb.com] and watch it. You can download the movie [idge.net] (~130mb) using BitTorrent.
  • Second, you need to succeed in posting a GNAA First Post [wikipedia.org] on slashdot.org [slashdot.org] , a popular "news for trolls" website.
  • Third, you need to join the official GNAA irc channel #GNAA on irc.gnaa.us, and apply for membership.
Talk to one of the ops or any of the other members in the channel to sign up today! Upon submitting your application, you will be required to submit links to your successful First Post, and you will be tested on your knowledge of GAYNIGGERS FROM OUTER SPACE.

If you are having trouble locating #GNAA, the official GAY NIGGER ASSOCIATION OF AMERICA irc channel, you might be on a wrong irc network. The correct network is NiggerNET, and you can connect to irc.gnaa.us as our official server. Follow this link [irc] if you are using an irc client such as mIRC.

If you have mod points and would like to support GNAA, please moderate this post up.

.________________________________________________.
| ______________________________________._a,____ | Press contact:
| _______a_._______a_______aj#0s_____aWY!400.___ | Gary Niger
| __ad#7!!*P____a.d#0a____#!-_#0i___.#!__W#0#___ | gary_niger@gnaa.us [mailto]
| _j#'_.00#,___4#dP_"#,__j#,__0#Wi___*00P!_"#L,_ | GNAA Corporate Headquarters
| _"#ga#9!01___"#01__40,_"4Lj#!_4#g_________"01_ | 143 Rolloffle Avenue
| ________"#,___*@`__-N#____`___-!^_____________ | Tarzana, California 91356
| _________#1__________?________________________ |
| _________j1___________________________________ | All other inquiries:
| ____a,___jk_GAY_NIGGER_ASSOCIATION_OF_AMERICA_ | Enid Al-Punjabi
| ____!4yaa#l___________________________________ | enid_al_punjabi@gnaa.us [mailto]
| ______-"!^____________________________________ | GNAA World Headquarters
` _______________________________________________' 160-0023 Japan Tokyo-to Shinjuku-ku Nishi-Shinjuku 3-20-2

Copyright (c) 2003-2005 Gay Nigger Association of America [www.gnaa.us]

Re: candidate for -2 moderation (0)

Anonymous Coward | about 9 years ago | (#13736027)

Since there's really no place to discuss this type of thing "on topic", I'll suggest it here.

Can we please have a bayesian filter that automatically starts these things out at say -2 (only possible if you upset the filter)? There are often funny posts that get "bad moderation" and wind up modded -1, so I like to read at -1. However, that unfortunately means I have to see all the GNAA trolls, etc.

Re: candidate for -2 moderation (1)

larry bagina (561269) | about 9 years ago | (#13736589)

it will probably never happen, however, you could probably write a greasemonkey script (you are using firefox, right? :) to hide GNAA posts, posts by TripMasterMonkey, etc.

Stupid (-1, Flamebait)

Anonymous Coward | about 9 years ago | (#13736011)

This is stupid. It uses a bunch of god damn scary macros and will never be as efficient as your operating system's context switching mechanism. No professional software developer would go near this.

Re:Stupid (2, Insightful)

plalonde2 (527372) | about 9 years ago | (#13736092)

The macros compile out; you get a switch on a piece of state. Do yourself a favour, compile one of the examples and read the code generated. It's screaming efficient compared to a thread context switch.

Hideous, but efficiency is not it's problem.

Re:Stupid (1)

meowsqueak (599208) | about 9 years ago | (#13736145)

If it's anything like microthreads, then it's not inefficient at all. I have played around with microthreads in python and easily achieved over a million 'concurrently-cooperative' threads.

Disclaimer: I haven't read the article yet, so maybe it has nothing to do with microthreads.

Re:Stupid (3, Insightful)

mvdw (613057) | about 9 years ago | (#13736254)

Ummm, which operating system would that be? Not all programmers have the advantage of an operating system as such; my current development target has no OS, runs at 8MHz, and has 4kbytes of memory. Something like this could be extremely useful for me.

Loop Abuse (4, Interesting)

wildsurf (535389) | about 9 years ago | (#13736028)

Reminded me of a function I once wrote...

The PPC architecture has a special-purpose count register with specialized branch instructions relating to it; e.g., the assembly mnemonic 'bdnz' means "decrement the count register by one, and branch if it has not reached zero." I've used this in some pretty weird loops, including this one that broke the Codewarrior 9.3 compiler (fixed in 9.4.) This computes the location of the n'th trailing one in a 32-bit integer. Pardon my weak attempt at formatting this in HTML:

static uint32 nth_trailing_one(register uint32 p, register uint32 n) {
register uint32 pd;
asm {
mtctr n; bdz end
top: subi pd, p, 1; and p, p, pd; bdz end
subi pd, p, 1; and p, p, pd; bdz end
subi pd, p, 1; and p, p, pd; bdz end
subi pd, p, 1; and p, p, pd; bdz end
subi pd, p, 1; and p, p, pd; bdz end
subi pd, p, 1; and p, p, pd; bdz end
subi pd, p, 1; and p, p, pd; bdz end
subi pd, p, 1; and p, p, pd; bdnz top
end: }

return __cntlzw(p ^ (p - 1));
}

The idea was that the instruction stream should stay as linear as possible; most of the time the branches are not taken, and execution falls through to the next line of code. Ironically (siliconically?), the entire function could probably be implemented in a single cycle in silicon; shoehorning bitwise functions like this into standard instructions tends to be extremely wasteful. Perhaps FPGA's will make an end run around this at some point. I've also tried this function with a dynamically-calculated jump at the beginning, similar to the case statement logic in the article.

Hmm, I had a point I was trying to make with this post, but now it's escaped my mind... :-)

Re:Loop Abuse (1)

proverbialcow (177020) | about 9 years ago | (#13736108)

Pardon my weak attempt at formatting this in HTML:

It came out okay, but for future reference, Slashdot does allow a specialized <CODE> tag similar to <PRE>.

Re:Loop Abuse (1)

ameoba (173803) | about 9 years ago | (#13736148)

...and a "preview" button on the comment page.

Re:Loop Abuse (0, Troll)

slyborg (524607) | about 9 years ago | (#13736112)

Hmm, I had a point I was trying to make with this post, but now it's escaped my mind... :-)
That point being that you will never successfully mate and have offspring :)

Re:Loop Abuse (2, Interesting)

addaon (41825) | about 9 years ago | (#13736458)

Unless you know that n is usually large, wouldn't this be more efficiently implemented with cntlzw?

Adam

Re:Loop Abuse (3, Interesting)

wildsurf (535389) | about 9 years ago | (#13736809)

Unless you know that n is usually large, wouldn't this be more efficiently implemented with cntlzw?

It would be if I were looking for the n'th leading one, but this code is looking for the n'th trailing one. (e.g. for 0b0010011001011100, the 3rd trailing one is in the fifth-lowest bit.) The equivalent code sequence for leading ones is in fact more complicated, requiring three arithmetic instructions and a branch per iteration. (cntlzw, shift, xor, branch).

I actually use this code as part of an algorithm where I have a very large (e.g. 65k-element) packed single-bit histogram array, and need to find the position of (say) the 1000th set bit. Vector instructions can do a coarse population-count from one end fairly efficiently, but once it's narrowed down to a 32-bit region, it comes down to slicing and dicing. My code operates by clearing the rightmost set bit in each iteration (x & (x - 1)), then at the end, isolating the needed bit (x ^ (x - 1)) and using cntlzw to find its position. To clear the leftmost set bit, you need three instructions: first get its position with cntlzw, then shift 0x80000000 right by that number of bits, and finally XOR to clear the bit. (If there's a shorter sequence, I haven't found it.)

(oh, and for the troll responder-- you are quite spectacularly wrong. But thanks for the giggle.)

Either ... or ... (0)

Anonymous Coward | about 9 years ago | (#13736041)

> You either love it or you hate it!

Or you have no clue what this post is about ...

It was looking interesting until (4, Interesting)

achurch (201270) | about 9 years ago | (#13736099)

I got to this little gem:

The advantage of this approach is that blocking is explicit: the programmer knows exactly which functions that block that which functions the never blocks.

My English parser thread shut down at that point . . .

Seriously, this looks like a handy little thing for low-memory systems, though I'd be a bit hesitant about pushing at the C standard like that--the last thing you need is a little compiler bug eating your program because the compiler writers never thought you'd do crazy things to switch blocks like that.

Better for embedded? (0)

Dingo_aus (905721) | about 9 years ago | (#13736103)

Would this technology be more suited to limited embedded systems? From a casual glance it would seem perfect for systems with specs measured in kilobytes not gigabytes. Especially where operations as close to realtime as possible are highly valued.

Re:Better for embedded? (0)

Anonymous Coward | about 9 years ago | (#13736258)

What do you mean "casual glance"? It's in the first line of the site, where they say it's for low memory environments only because otherwise you may as well use read threads.

I took a cursory look at slashdot.org and found that it was a news site for nerds about stuff that matters to them. Upon subsequent casual glances I discovered menu items, and what looks like news stories, but really it's too early to say.

Stackless Python (2, Interesting)

alucinor (849600) | about 9 years ago | (#13736139)

Is this similar to Stackless Python [sjsoft.com] and green threads? I spend most of my time with interpreted languages, so my C is very lacking.

Slow news day? (1)

spankfish (167192) | about 9 years ago | (#13736152)

Um, who cares? Really? Shouldn't this be hidden under "Developers"? I mean, I'm a developer, and this might be great to someone who might use it... but that ain't me. (Self-centered huh?)

extremely limited applicability (5, Informative)

nothings (597917) | about 9 years ago | (#13736169)

Please note that this isn't interesting unless you work in, as, the FA says, a severely memory constrained system. No normal embedded system needs to do this, much less the systems most programmers on Slashdot probably work with.

This is bad, lame, faux cooperative threads.

Local variables are not preserved.

A protothread runs within a single C function and cannot span over other functions. A protothread may call normal C functions, but cannot block inside a called function.

It's also not even particlarly new [mine-control.com] [1998].

Unless memory is at an absolute premium, just use cooperative threading instead. If you try to use prototheads, you'll quickly discover how unlike "real" programming it is. Even just a 4K stack in your cooperative threads will get you way more than protothreads does.

Re:extremely limited applicability (0)

Anonymous Coward | about 9 years ago | (#13736237)

much less the systems most programmers on Slashdot probably work with.

Yeah, how one could do such a thing in Visual B*sic?

Re:extremely limited applicability (2, Funny)

gardyloo (512791) | about 9 years ago | (#13737012)

Please note that this isn't interesting unless you work in, as, the FA says, a severely memory constrained system.

      Yeah, but my brain -- Ooh! Shiny!

This won't help me... (1)

winphreak (915766) | about 9 years ago | (#13736195)

I already crashed Linux with my code, let alone implement something like this.

Not very handy (0)

Anonymous Coward | about 9 years ago | (#13736224)

Don't need a low overhead pseudo-thread implementation for what I do, but would be nice is
a stack-safe and stable(same thing) setjmp() for process oriented posix compliant stuff.
Anyone got an implementation?

You want cool C stuff... (4, Interesting)

Dr. Manhattan (29720) | about 9 years ago | (#13736295)

Get the book Obfiscated C and Other Mysteries [amazon.com] by Don Libes. Explanations of various Obfuscated C contest entries, and alternate chapters illustrate neat corners of C, including a few things similar to this little library. Occupies a place of honor on my shelf.

Dijkstra says... (2, Interesting)

Jeff85 (710722) | about 9 years ago | (#13736315)

"The competent programmer is fully aware of the limited size of his own skull. He therefore approaches his task with full humility, and avoids clever tricks like the plague." -Edsgar Dijkstra

Re:Dijkstra says... (1)

menkhaura (103150) | about 9 years ago | (#13736610)

Dijkstra is not $DEITY. There is a difference between a competent programmer and a brilliant programmer. Sometimes one has to be clever in order to get the job done.

Re:Dijkstra says... (3, Funny)

mikeage (119105) | about 9 years ago | (#13736851)

Dijkstra is not $DEITY. There is a difference between a competent programmer and a brilliant programmer. Sometimes one has to be clever in order to get the job done.

Actually, since the running of $export DEITY=Dijkstra, he is now.

Re:Dijkstra says... (1)

hunterx11 (778171) | about 9 years ago | (#13737030)

Even for a C programmer, the sort of person who would abuse a language this way probably believes in Laziness, Impatience, and Hubris.

a fun trick only useful in very specialized cases. (3, Insightful)

TomRitchford (177931) | about 9 years ago | (#13736392)

It's too clever to be really useful unfortunately. The big issue is of course the no "local variables". Trouble is, if you are writing in C, the compiler may well be creating local variables for you behind your back. In C++ for example there are many cases where this will certainly happen, like
void DoSomething(const string&);
DoSomething("hollow, whirled");
where a local variable of type string will be temporarily created to pass to routine DoSomething.

Even if you are writing in the purest of C, you aren't guaranteed that the optimizer isn't going to very reasonably want to introduce the equivalent of local variables. And even if you are sure there's no optimization going on, you STILL don't know for sure that the compiler isn't using space on the stack. There just is no guarantee built into the language about this. And if you were wrong, you'd get strange, highly intermittent and non-local bugs.

You could be pretty sure. You could force the compiler to use registers as much as possible. You could keep your routines really short. (Hey, if they don't preserve local variables, then how do they do parameter passing?? Parameters are passed on that same stack!)

But to be completely sure, you'd have to look at the output code. It wouldn't be too hard I suppose to write a tool to automatically do it...you'd just look for stack-relative operations and flag them. But then what would you do if something wasn't working? Yell at the compiler? Rewrite the machine language?


I guess I don't quite see the use now I've written this up. When is memory THAT important these days? It ain't like I haven't done this, I've written significant programs that I got paid money to do that fit into 4K (an error correction routine).

But that was an awfully long time ago. Now it's hard to find memory chips below 1Mbit. That two byte number is interesting but your "threads" aren't doing any work for you -- the whole point of threads is that you are preserving some context so that you can go back to them.

And since you can't use local variables, you can't use things like the C libraries or pretty well any library ever written, which is teh sux0r.


For just a few more bytes of memory and a few more cycles, you could save those local variables somewhere and restore 'em later. Suddenly your coding future is a brighter place. Tell the hardware people to give you 128K of RAM, damn the expense!

You could even put in a flag to indicate that that particular routine didn't need its local variables saved so you'd get the best of both worlds, use of external libraries as well as ultra-light switching.

Re:a fun trick only useful in very specialized cas (2, Informative)

plalonde2 (527372) | about 9 years ago | (#13736442)

The absence of local variables is because the stack is not preserved between invocations, and multiple invocations give the appearance of scheduled threads. There is nothing here that the compiler can break with its optimizer, unless it is breaking valid C code: the control flow expressed using the macros is completely legit C control flow. It's worth running the examples through just the C pre-processor in order to understand what gets built.

It's ugly as sin, but your compiler had better get it right, or else it's not a C compiler.

Re:a fun trick only useful in very specialized cas (2, Interesting)

TomRitchford (177931) | about 9 years ago | (#13736828)


The absence of local variables is because the stack is not preserved between invocations, and multiple invocations give the appearance of scheduled threads. There is nothing here that the compiler can break with its optimizer, unless it is breaking valid C code: the control flow expressed using the macros is completely legit C control flow. It's worth running the examples through just the C pre-processor in order to understand what gets built.


I downloaded it. But the version that is there does not, in fact, compile: there's an obvious typo at example-buffer.c, line 137:
PT_WAIT_THREAD(pt, producer(&pt_producer) &
                  consumer(p&t_consumer));
// should be consumer(&pt_consumer));
That aside, I believe your claim is wrong now that I've read the code.
int x = 23;
// Some blocking code here.
// A case statement leads us to here.
if ( x != 23 ) {
// Now x could be anything.
}
right? The reason is that you are simply case-statementing into the code and bypassing the whole subroutine calling mechanism entirely -- so the variable initialization just isn't called.

Now consider the following code:
double x = sin(y*(2*pi)/360)*cos(y*(2*pi)/360);
// Some blocking code here.
// A case statement gets us to here.
double z = tan(y*(2*pi)/360;
Suppose the compiler decided to extract out the common y*(2*pi)/360 term as an optimization. The assignment to that common term will not occur when you jump into the middle of that routine -- so your code will not work as it appears.

Re:a fun trick only useful in very specialized cas (2, Informative)

S. Traaken (28509) | about 9 years ago | (#13736962)

Suppose the compiler decided to extract out the common y*(2*pi)/360 term as an optimization.

But the compiler won't decide to do this because it won't be able to establish that y (or pi) can not be changed between instances of this code.

Re:a fun trick only useful in very specialized cas (2, Informative)

plalonde2 (527372) | about 9 years ago | (#13736982)

But that's precisely the reason you musn't use locals: they are not preserved. The switch in the "thread" setup sets up a new scope in which you might declare locals, but that scope need not be entered cleanly, leading to (in the case of your example) an uninitialized local variable.

In your second example, the compiler *cannot* remove the sub-expression because the case statement that gets you there crosses a basic block boundary; the return statement from the blocking code, and the jump in through the switch are caught as valid C constructs that prevent the common sub-expression optimization.

The macros as given give you a semblance of variable continuity and scoping, but the compiler, after the macro substitutions, just sees a return on the end of the blocking section, and a switch into the code following, something like:

char YourFunc(char foo) {
switch (foo) {
case 'A': /*your blocking code*/
return 'B';
case 'B': /* the stuff after your blocking code */
break;
}
}
The ugliness in the macros is about letting other control constructs live around your switch in, but still generates legit code, but, for example, you can't use a local varible as an index to your for loop. Yuck.

Re:a fun trick only useful in very specialized cas (2)

PsychicX (866028) | about 9 years ago | (#13736633)

As far as ridiculously low memory constraints go...
I was talking to a friend the other day, who had to write the code for a car door opener dealie. You know the one. A really nice, high end one with an LCD that displayed stuff (not your average 100% hardware door opener). His code had a staggering 256 bytes of RAM to work with, and even then they were potentially 7 bytes overbooked. So yes, these kinds of constraints still exist. Sadly.

Re:a fun trick only useful in very specialized cas (4, Informative)

dmadole (528015) | about 9 years ago | (#13736741)

It's too clever to be really useful unfortunately. The big issue is of course the no "local variables". Trouble is, if you are writing in C, the compiler may well be creating local variables for you behind your back. In C++ for example there are many cases where this will certainly happen, like

void DoSomething(const string&);
DoSomething("hollow, whirled");

where a local variable of type string will be temporarily created to pass to routine DoSomething.

You need to read the article.

It only says you can't use local variables across functions that block. Actually, it doesn't even say that you can't use them, it only says don't expect their value to be preserved.

In your example, even if the compiler does create a local variable to call DoSomething, and even if DoSomething does block, who cares if the value of that local variable is preserved, since it's impossible to reference it again after that statement?

But that was an awfully long time ago. Now it's hard to find memory chips below 1Mbit.

I can help you with this problem! Is 16 bytes small enough [microchip.com] ?

And since you can't use local variables, you can't use things like the C libraries or pretty well any library ever written, which is teh sux0r.

But you can use the C libraries. Just don't use local variables across functions that block. Only a very few C library functions block.

This is mostly useless (0)

Dwedit (232252) | about 9 years ago | (#13736485)

Normally if you want multithreading and have no OS to do it for you, you'd use an interrupt handler to swap all registers, as well as the stack location. Even a 400 byte stack is adequate if you have no recursion or local arrays. So really, this is only for situations where you don't even have 400 bytes to spare per thread. The complete inability to use local variables makes this useless except in very specific situations.
I could see this being used if you need a very large number of threads with no local variables. I'd still be very wary about using something that does not preserve the content of registers when switching 'threads'.

Yes, can be useful (depending on platform) (3, Interesting)

ihavnoid (749312) | about 9 years ago | (#13736533)

As the prothread homepage says, it's for extremely small embedded systems, where there are no operating systems, with tiny amount of memory (You can't use DRAMs on systems that cost something less than $1). Want to use threads on those kind of systems, you have no choice.

Another advantage is its portability. Small embedded systems, whether they have operating systems or not, usually can't support some fully-blown threading standard. Those operating systems seem to implement some kind of 'specially tuned' thread APIs.

Using these kind of threads on a full-blown PC (or servers) would have almost no benefit. However, in the embedded software engineer's perspective, it's great to see a ultra-lightweight thread library without any platform-dependent code.

C Language Protothread Benefits (-1, Offtopic)

Anonymous Coward | about 9 years ago | (#13736650)

I know !!! Let's talk politics
on Slashdot !!!!!

Because we all know dorks
incapable of washing themselves
on a regular basis are really
in a position to deliver insightly
and relevant political commentary.

                                  Capitalism Sucks !!!!!!!!!!!!!!!!!
                                  As I type this on a computer which
                                  capitalism made possible.
   

Or... (0)

Anonymous Coward | about 9 years ago | (#13736656)

You either love it or you hate it!

Or you don't care, having long since given up on low-level languages so you can actually be *productive*...

Oh my God! (1)

Snowdrake (139057) | about 9 years ago | (#13736658)

You Slashdotted PuTTY [greenend.org.uk] ! You bastards!

misread (1)

l0rdpestilence (881264) | about 9 years ago | (#13736897)

I read it as pothead, post a smily if you did to.
Just as a question: Why do people thing threading is extra hard to do? without much exp so far it seems to help in that the code snippets are smaller and theirfor less prone to typos (then again only ones I've used to this point are in java with a IDE)
Load More Comments
Slashdot Login

Need an Account?

Forgot your password?