Thinking Parallel

A Blog on Parallel Programming and Concurrency by Michael Suess

The Most Overused Word in Parallel Programming: Reentrancy

Great Wall of ChinaI am a little late with my post this week, I apologize for that but I am still in Beijing at IWOMP with little time to post. Actually, now that the conference is over, I am staying for two more days to see the city, the Great Wall and a couple of other sites – which still leaves me with no time to post :grin:. Therefore you are going to have to live with a timeless one that I have recorded beforehand just for this purpose. Here it goes.

It is difficult enough already to teach my students about parallel programming, but when even some of the terms used are misleading, something is seriously wrong. Take this very simple example: the term reentrancy. I have just found the fourth definition of it, all from the field of parallel programming and all of them mean something (at least slightly) different.

  • Goetz: But because intrinsic locks are reentrant, if a thread tries to acquire a lock that it already holds, the request succeeds. Reentrancy means that locks are acquired on a per-thread rather than per-invocation basis.
  • Albahari: A method which is thread-safe in any scenario is called reentrant.
  • Butenhof: The term “reentrant” is sometimes used to mean “efficiently thread-safe”. That is, the code was made thread-safe by some more sophisticated measures than converting the function or library into a single serial region.
  • Wikipedia: A computer program or routine is described as reentrant if it can be safely called recursively or from multiple processes. To be reentrant, a function must hold no static data, must not return a pointer to static data, must work only on the data provided to it by the caller, and must not call non-reentrant functions.

*sigh*. You may argue that the last three definitions all mean the same thing. Yet, if you think about it some more you will realize that these tiny differences in wording make a whole lot of difference for a particular implementation. If I document my function as being reentrant, how do you know which definition I mean? How do you know what you can count on? You don’t, because you don’t know which definition of reentrancy I was aware of and using. I do realize that human languages are context sensitive. But four different meanings in the same field? Or if some of them really wanted to say the same thing: could we please be a little more precise? There has got to be a better way…

4 Responses to The Most Overused Word in Parallel Programming: Reentrancy »»


Comments

  1. Comment by Kragen Sitaker | 2007/06/08 at 21:54:42

    In theory, there are at least two versions of the last definition — a function that is reentrant in the sense that you can call it safely from an interrupt even if it’s suspended on the stack is not necessarily reentrant in the sense that you can call it safely from multiple threads, for example if it saves the state of some piece of hardware upon entry and restores it upon exit. I can’t think of a realistic example, though.

  2. Comment by Bart Samwel | 2007/06/08 at 23:26:09

    I think there are two separate issues here: safe for recursion and safe for multithreading. I can easily think of something that is not safe for recursion but that is safe for multithreading (i.e., a function that uses nonreentrant locks). I can also easily think of something that is safe for recursion but not for multithreading. Reentrancy can be used to describe only “safe for recursion” (in a single-threaded context), only “safe for multithreading” (in a context where recursion simply cannot happen), or both.

    I think the Butenhof definition is especially vague, it specifies a method for achieving the “safe for multithreading” guarantee, not the guarantee itself. And the method itself somewhat implies “safe for recursion”, but it isn’t explicitly stated.

    Any tips for Beijing BTW? I’m flying there tomorrow to go to PODS 2007…

  3. Comment by Michael Suess | 2007/06/09 at 16:14:23

    @Bart: I agree with your analysis. But why use the same word to describe all of this??

    Regarding Beijing: Get a good tour guide (I liked the one from Lonely Planet) and spend some time with it before you go into the city searching for spots that you may like. Take a taxi to the location, as they are cheap and then you don’t need to read the chinese characters to find anything. If you are a little more adventurous take the subway – they have English signs in there now. Remember to always take a buisness card of the hotel with you that has the name and address written on it in chinese, as almost nobody here speaks English – just in case you get lost (you can always take a taxi back home then – they are everywhere). Practice your barganing skills, as almost everything here can be had for a fraction of the initial price offered.

    And last but not least: prepare for the heat and the smog, as the air in Beijing is thick, hot and moist at this time of the year. Hope it helps and have fun here!

  4. Comment by Alejo | 2007/06/09 at 16:18:00

    Reentrant in the sense of Idempotent?

    http://en.wikipedia.org/wiki/Idempotence

    In mathematics and computer science, the concept of idempotence (IPA: [ˈaɪdɪmpoʊtəns]) arises in a number of places in abstract algebra (in particular, in the theory of projectors, closure operators and functional programming (in which it is connected to the property of referential transparency). Roughly, if an operation is idempotent, then multiple applications of that operation will yield the same result.


Leave a Reply

HTML allowed: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>