Re: Is C99 the final C? (some suggestions)

From: Arthur J. O'Dwyer (ajo_at_nospam.andrew.cmu.edu)
Date: 12/13/03 

Date: Fri, 12 Dec 2003 19:17:09 -0500 (EST)

On Fri, 12 Dec 2003, Sidney Cadot wrote:
>
> Paul Hsieh wrote:
> [Sidney Cadot wrote:]
> >>>>Why do you need to distinguish process instances?
> >>>
> >>>Reread the Lamport's bakery algorithm. One of the crucial steps is
> >>>"for each process, check their number, and pick the max, then add
> >>>1". Another is "for each process that has a lower number, wait in
> >>>line behind them." This means you have a way of knowing how many
> >>>processes there are, and how to index them. This means you have
> >>>to hook out or wrap whatever "spawn" mechanism you have in your
> >>>language (or use some other platform specific mechanism to iterate
> >>>through all running threads.)
> >>
> >>Could you provide a reference to the description of the algorithm
> >>you're using?
> >
> > Typed it into google and felt lucky. Its the first hit. Notice
> > language like "Process i", and statements like for (j=0; j < n; j++),
> > where each j indexes a process id, and n is the number of processes.
> > I tried to think up a way of implementing that algorithm without
> > specifically requiring an enumeration of processes, but it seems that
> > that is central to the way the algorithm works. Which is only *one*
> > of the reasons why that algorithm is worthless.
>
> Typed -what- into google? Is it so hard to provide a link?

Typed "Lamport bakery algorithm," naturally, and then clicked the
button labeled "I'm Feeling Lucky." It takes you right to
http://www.csee.wvu.edu/~jdm/classes/cs356/notes/mutex/Bakery.html

> I'm not doing this to piss you off... Like with many important
> algorithms, there are different formulations of the bakery algorithm
> floating around. I'll look up the original Lamport papers later on, and
> see if the process-id thing is truly essential.

  Well, you obviously don't need access to UNIX "pids" to do the
algorithm, but you *do* need a reliable source of unique integer
identifiers for each thread. And that's something that standard
C simply cannot give you without specific language support.

> >>>Yes, but if two threads simultaneously call heap functions on the same
> >>>heap (heaps are not restricted to being distinct across threads) then
> >>>there is a race condition.
> >>
> >>So we need to put a mutex around the critical section, no big deal.
>
> > It *is* a big deal. Mutexes, and other similar multithreading objects
> > are not expressible is a portable way in language like C or C++.
>
> I already established that if you cannot portably get mutexes in C, I
> will concede. This very specific point of contention is *not* decided
> yet, in this discussion.

  I agree with Paul that this is a very basic and very obvious fact
that shouldn't be too hard to grasp. If you've done any thread-based
programming (nothing complicated, just anything that requires a
shared resource), you've noticed that every time two threads want
access to the same bit of memory at the same time, you need some
kind of mutex to block out one of the threads while the other one
does its thing, and then block out the other one while the first one
does *its* thing.
  Mutexes cannot be expressed in standard C, because standard C has
no way of specifying "this block of data behaves like a mutex." I'm
sorry if that sounds circular, but it's hard for me to describe the
effect of a mutex except by jargon. Suffice it to say that you can
feel free to post snippets illustrating anything you think qualifies
as a mutex algorithm written in standard C, and I will be only too
glad to poke holes in it.

> > It only took me only 30 seconds to understand [the bakery
> > algorithm].
>
> Well, that would surely make you quite brilliant. Took me a couple of
> hours, the first time I read it, to get my head around it, and to see
> that it is correct.

  Maybe it's the changing times. Or maybe it's the way that web
page explains it -- it's intuitively obvious to me from their
description that if Thread A has a lower number than Thread B, then
Thread A naturally goes first. It just makes sense.

> >>[...] I feel rather silly getting dragged in this line of
> >>discussion (multithreading has little to do with the C execution
> >>model) but we'll see where this leads us.
>
> > Then let me review the facts for you. Multithreading is inextricably
> > intertwined with the implementation of malloc. Thus if a compiler
> > vendor wants to provide a multithreading extension to C (which they
> > pretty much all do) discussions of implementation of malloc, or
> > malloc-like functions have to at least acknowledge this as a
> > consideration. There is no such thing as a portable mutex in pure C
> > that actually encodes all the expected notions of a mutex unless tied
> > specifically to the extension mechanisms that are used to provide the
> > multitasking in the first place. The inevitable conclusion is that
> > its impossible to make a portable library for extending the heap
> > functions that are multithreading safe.
>
> Ok, except that "There is no such thing as a portable mutex in pure C
> that actually encodes all the expected notions of a mutex unless tied
> specifically to the extension mechanisms that are used to provide the
> multitasking in the first place" is not a fact. That's what we're
> arguing about, now.

  Well, Paul's right and you're wrong. That's all.

[re: the rest of the miscellaneous arguments in this subthread]

[re stack bounds checking]
> > It means you are expecting compilers to come as close to solving the
> > halting problem as they can.
>
> No. I don't expect the compiler to do anything with this information.
> It's there for the programmer to use, for checks at runtime (e.g. at the
> start of main() in heavy recursive programs). It can't be done at
> compile time since, in general, you don't know the stack size at that point.

  This proposal sounds both reasonable and possible to me. I do
agree that it requires a *lot* more thought, though; and you'll see
if you search Google Groups that this topic has been discussed both
here and in comp.programming (IIRC) quite a lot before.

> > And you think variable length operators based on a grammar is an
> > impossible, intractible problem in practice?!?!
>
> I think it's very difficult, and it may be even impossible, yes. But
> surely, you're going to demonstrate that I am wrong? :-)

  Of course it's *possible* to create an arbitrary-operator-parsing
grammar! But it would require work, and it's not going to make it
into C, so IMHO that discussion should move to comp.programming or
comp.lang.misc, where someone will no doubt be glad to demonstrate
how their magic compiler compiler will handle arbitrary operator
syntaxes with ease.

<gigantic snip>
> I'm really interested to see how you would write a big number multiply
> that doesn't presuppose 2-complement, but works in 1-complement as well.
> For the sake of argument, feel free to introduce a wide-mul operation
> (but let's have a semantics for it... The x86 MUL obviously won't do).

  Why do you say that? It's not dishonest to use the well-thought-out
and publicly-reviewed specification of an x86 operation in this
context. I myself am not familiar enough with the MUL opcodes anymore
to give a nice description, so here's my proposal, without any x86
jargon, which I think *would* rhyme fairly well with C. It's a
library function.

  #include <math.h>

  unsigned long lmulu(unsigned long p, unsigned long q,
                      unsigned long *hi, unsigned long *lo);

    The 'lmulu' function accepts arguments 'p' and 'q', multiplies
  them using normal integer arithmetic, and stores the high-order
  bytes of the result in '*hi' and the low-order bytes in '*lo'.
  Specifically, if ULONG_MAX = 2**N - 1, then mathematically
  (*hi << N) + *lo == (p * q); but note that this expression
  invokes undefined behavior as a C expression.
    'lmulu' may be implemented as a macro.
    'lmulu' returns the value stored in '*hi'.

  signed long lmuls(signed long p, signed long q,
                    signed long *hi, signed long *lo);

    The 'lmuls' function accepts arguments 'p' and 'q', multiplies
  them using normal integer arithmetic, and stores the high-order
  bytes of the result in '*hi' and the low-order bytes in '*lo'.
  [Needs someone more familiar with bitwise representations, and
  more awake, to define exact semantics in mathematical terms.]
    'lmuls' may be implemented as a macro.
    'lmuls' returns the value stored in '*hi'.

It would have been nice to add defined behavior for when 'hi' or
'lo' were NULL, but that would have killed the whole point of
making the function in the first place -- the ability to optimize
away a lot of code on many popular systems.
  [And before Paul contradicts that last sentence, I re-iterate: This
is *not* about adding functionality to C; it's about giving the compiler
better optimization hints. The ability to do wide multiplies already
exists in C; language support for them will only make them faster.]

  That said, I think this thread needs to start splitting up. :)

-Arthur

Loading