Re: things i would ban from clc

"io_x" <a@b.c.invalid> writes:

> "Tim Rentsch" <txr@alumni.caltech.edu> ha scritto nel messaggio
>[snip]
>> Even though it is optional, support for threading is not just
>> another library, and that is important - for threads to work, the
>> language definition needs to be augmented so that the semantics
>> of inter-thread operations is well-defined. Furthermore the
>> visible language (as opposed to library) for C was itself changed
>> to accommodate threads, eg, '_Thread_local' storage class
>> specifier.
>
> where is the wrong on this below? where are difficulties?
> there is one u32 space for the struct that
> is used from OS for the thread signals
>
> for example:
> // global to all threads
> #define u8 unsigned char
> #define u32 unsigned
>
> u8 *thisIsAList;
> List(&thisIsAList); // create the list memory, and inizilize
> if(thisIsAList==0) return "this is one errror";
>
> // local thread
> Lock(thisIsAList);
> // for example the first u32 of the list, point to the memory
> // the OS use for block, for multhread
> Operations(thisIsAList);
> UnLock(thisIsAList);

Here is a reference for a paper that explores the issues.

Threads Cannot be Implemented as a Library

Boehm, Hans-J.

HPL-2004-209

Abstract: In many environments, multi-threaded code is written
in a language that was originally designed without thread support
(e.g. C), to which a library of threading primitives was
subsequently added. There appears to be a general understanding
that this is not the right approach. We provide specific
arguments that a pure library approach, in which the compiler is
designed independently of threading issues, cannot guarantee
correctness of the resulting code. We first review why the
approach almost works, and then examine some of the surprising
behavior it may entail. We further illustrate that there are
very simple cases in which a pure library-based approach seems
incapable of expressing an efficient parallel algorithm. Our
discussion takes place in the context of C with Pthreads, since
it is commonly used, reasonably well specified, and does not
attempt to ensure type-safety, which would entail even stronger
constraints. The issues we raise are not specific to that
context.

http://www.hpl.hp.com/techreports/2004/HPL-2004-209.pdf

Don Y <this@isnotme.com> writes:

> Hi Tim,
>
> On 3/13/2012 4:25 PM, Tim Rentsch wrote:
>> blp@cs.stanford.edu (Ben Pfaff) writes:
>>> Don Y<this@isnotme.com> writes:
>>>> On 3/13/2012 5:59 AM, Keith Thompson wrote:
>>>>> Don Y<this@isnotme.com> writes:
>>>>>> Why not support for *tasking* -- native to the language
>>>>>> (instead of in a library!) like Limbo?
>>>>>
>>>>> The 2011 ISO C standard includes (optional) support for threading.
>>>>>
>>>>> See<http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf>
>>>>> section 7.26.
>>>>
>>>> OK. But that's just another standard library. The language
>>>> itself doesn't include those provisions.
>>
>> (to repeat myself, IMO this statement is inaccurate for C2011.)
>>
>>> What's the advantage of putting threading into language instead
>>> of the library? (You explained *how* Limbo integrates threading
>>> into the language, but not why it does.)
>>
>> I assume most people in the group have seen this, but for those
>> who have not:
>>
>> Threads Cannot be Implemented as a Library
>>
>> Boehm, Hans-J.
>>
>> HPL-2004-209
>>
>> Abstract: In many environments, multi-threaded code is written
>> in a language that was originally designed without thread support
>> (e.g. C), to which a library of threading primitives was
>> subsequently added. There appears to be a general understanding
>> that this is not the right approach. We provide specific
>> arguments that a pure library approach, in which the compiler is
>> designed independently of threading issues, cannot guarantee
>> correctness of the resulting code. We first review why the
>> approach almost works, and then examine some of the surprising
>> behavior it may entail. We further illustrate that there are
>> very simple cases in which a pure library-based approach seems
>> incapable of expressing an efficient parallel algorithm. Our
>> discussion takes place in the context of C with Pthreads, since
>> it is commonly used, reasonably well specified, and does not
>> attempt to ensure type-safety, which would entail even stronger
>> constraints. The issues we raise are not specific to that
>> context.
>>
>> http://www.hpl.hp.com/techreports/2004/HPL-2004-209.pdf
>
> I think the problem being addressed, here,

Did you read the paper?

> boil down to
> removing the need for the developer to "take precautions"
> (i.e., manually ensure that the compiler doesn't "get ahead
> of him") along with wanting to be able to use the language
> to *efficiently* implement truly parallel threads of
> execution. [snip elaboration]

The problem is the compiler is operating at the wrong level of
abstraction. Whether the compiler "gets ahead" of a developer
(a frightening concept in and of itself, but let's ignore
that) doesn't matter, because the operating environment that
(non-thread-aware) compilers generate code for doesn't make
strong enough guarantees about inter-thread or inter-processor
memory consistency. To get threads to work usably, at least
part of the compiler needs to be aware of a lower level of
abstraction, below the architectural level for a single
process (which is where essentially all pre-thread-aware
compilers operate).

On Tue, 2012-03-13, Don Y wrote:
....
> I often rewrite major portions of the standard libraries
> as I move from project to project -- because the execution
> environments frequently differ and I don't need the "generality"
> that most of the libraries provide. Or, I am bastardizing a
> standard data type, etc.
>
> When was the last time you used:
>
> digits = INT_MAX
> decimals = INT_MAX
> printf("The answer is %*.*e", value, digits, decimals)
>
> In fact, when was the last time you used the '*' flag in printf??
> Will your copy of the libraries even *handle* this specific
> case??

It will, on Linux and VxWorks which is where I happen to live right
now. If it doesn't, it's not C, and I have to wonder what else is
omitted.

Actually, I find that * is underused. Lots of code gets duplicated
because you want the width 9 here, but 12 there, and so on.

(Note that I'm not saying it's always wrong to hack away the support
for %e, * etc from printf().)

/Jorgen

--
// Jorgen Grahn <grahn@ Oo o. . .
\X/ snipabacken.se> O o .

Don Y <this@isnotme.com> writes:
<snip>
> When was the last time you used:
>
> digits = INT_MAX
> decimals = INT_MAX
> printf("The answer is %*.*e", value, digits, decimals)

Never! It needs semi-colons, and it needs the printf arguments to be in
the right order! Also, making the field width equal to the precision is
a little odd for the 'e' conversion.

> In fact, when was the last time you used the '*' flag in printf??

I use it quite a lot, but that may just be that I like to parametrise my
code a lot. By the way, it's not a "flag". printf specifiers do have
flags (there are +, -, #, ' ' and 0) so using the wrong term might be
confusing.

> Will your copy of the libraries even *handle* this specific
> case??

It doesn't need to. printf need only support conversions that generate
no more than 4095 characters.

<snip>
--
Ben.

Hi Ben,

On 3/15/2012 9:36 AM, Ben Bacarisse wrote:
> Don Y<this@isnotme.com> writes:
> <snip>
>> When was the last time you used:
>>
>> digits = INT_MAX
>> decimals = INT_MAX
>> printf("The answer is %*.*e", value, digits, decimals)
>
> Never! It needs semi-colons, and it needs the printf arguments to be in
> the right order! Also, making the field width equal to the precision is
> a little odd for the 'e' conversion.
>
>> In fact, when was the last time you used the '*' flag in printf??
>
> I use it quite a lot, but that may just be that I like to parametrise my
> code a lot. By the way, it's not a "flag". printf specifiers do have
> flags (there are +, -, #, ' ' and 0) so using the wrong term might be
> confusing.

Wow, I am *so* relieved! With all your criticisms, I was
afraid you might not have UNDERSTOOD WHAT I INTENDED! Whew!
Glad I won't have to worry about *that*!

[If you have some EXTRA free time, how about checking my past
posts for spelling and grammatical errors. It might help
others who are confused by a typo here or there... e.g., my
recent use of 'int' in place of 'age'... There might be
*other* folks who would also welcome your attention to this
level of detail!]

Of course, aside from the obligatory picking of nits, you
*did* (?) realize that the point I was making to Jacob was that
certain things are moved into LIBRARIES vs. part of the
language "proper" so that they *can* be elided from
particular applications without compromising the language's
functionality. That you can still successfully deploy an
application with a printf(3) implementation that *won't*
handle the case illustrated above.

You can't elide "int's" from C. Nor support for arrays. etc.

>> Will your copy of the libraries even *handle* this specific
>> case??
>
> It doesn't need to. printf need only support conversions that generate
> no more than 4095 characters.

You may be lucky enough to work in environments where you
can be assured that the tools are strictly conforming AND
when you encounter something that *isn't*, your employer/client
is willing to wait for <someone> to fix it so you can get back
to work.

But, if you look at a wider range of products claiming to
be "C compilers", you will find these sorts of "problems"
are commonplace. When confronted, the vendor will often
skirt the issue with "Well why would you want to do *that*?"
(instead of addressing a documented PROBLEM, let's infer
that the developer is doing something 'wrong' or that could
be done in a DIFFERENT manner).

I work with a *lot* of compilers for a lot of different
iron. I've taken up the practice of adding examples of
test cases that I've encountered that weren't well-behaved.
I apply that test suite as one of the first things I do
when using a "new" compiler to see what sort of confidence
I can have in its results.

As I spot things that don't work, I gauge how much I will
either have to *avoid*, *fix* or replace with my own
library components. Or, how strong a case I will have to
recommend to client that he abandon a particular toolchain
in favor of another ("What *exactly* is wrong with the
product we purchased? We've got a lot of money invested
in those tools! Not to mention several deployed products!")

Hi Jorgen,

On 3/15/2012 8:22 AM, Jorgen Grahn wrote:
> On Tue, 2012-03-13, Don Y wrote:
> ...
>> I often rewrite major portions of the standard libraries
>> as I move from project to project -- because the execution
>> environments frequently differ and I don't need the "generality"
>> that most of the libraries provide. Or, I am bastardizing a
>> standard data type, etc.
>>
>> When was the last time you used:
>>
>> digits = INT_MAX
>> decimals = INT_MAX
>> printf("The answer is %*.*e", value, digits, decimals)
>>
>> In fact, when was the last time you used the '*' flag in printf??
>> Will your copy of the libraries even *handle* this specific
>> case??
>
> It will, on Linux and VxWorks which is where I happen to live right
> now. If it doesn't, it's not C, and I have to wonder what else is
> omitted.

Exactly. If you are the proprietor, then *you* can decide
how much effort to expend figuring out what's missing/broken.
Or, simply abandoning the tool in favor of something you
*know* "works".

OTOH, if that decision comes from "on high", you can gripe all
you want but you're still going to have to *live* with it!

> Actually, I find that * is underused. Lots of code gets duplicated
> because you want the width 9 here, but 12 there, and so on.

Yes! And, if you're like me and drive lots of algorithms
from tables, every place you can eliminate a hard constant
is a blessing!

But, I find many libraries use fixed size, internal buffers to
perform these conversions. Or, allocate a "huge" buffer
which might exceed available memory. The desired functionality
can be obtained with a small buffer (~LDBL_DIG) and more
*smarts* in the implementation. E.g., fprintf() should be
able to support "printing" thousands of digits with no more
than ~100 bytes of R/W memory dedicated to its own use.

> (Note that I'm not saying it's always wrong to hack away the support
> for %e, * etc from printf().)

OTOH, there are applications where all of printf's different
formats are just excess baggage. The size of printf()'s
executable is *staggering* when you think of how "little"
it (appears to) does. Yet, it seems to be one of the first
modules that a developer draws into his project...

Le 15/03/12 20:26, Don Y a écrit :
>
> OTOH, there are applications where all of printf's different
> formats are just excess baggage. The size of printf()'s
> executable is *staggering* when you think of how "little"
> it (appears to) does. Yet, it seems to be one of the first
> modules that a developer draws into his project...

I know, I have written printf for my compiler system lcc-win.

It is quite big mind you:

d:\repos\lcc-src\libc>pedump /summary xprintf.obj
xprintf.obj 41871 bytes, linked Tue Mar 13 19:22:37 2012

Section Name Size
01 .text 14780
02 .data 1112


almost 15K, + 12 K for character strings, tables, etc...

But it will print a denormalized number extracting all the
available precision from it.

Supports all the C99 formats, etc. Actually printf is a
run time intepreter of the format string. My printf also
must support all the extensions: 450 significant digits
qfloats, printng the comma separator to separate the number
in thousands, and many other "goodies".

I would like to have to possibility of trimming it, something
like "slimPrintf()" but it would make programming more complex
than it needs to.

And with only 15K, it is not THAT big, compared to other
implementations that do less with more.

jacob

Hi Tim,

On 3/14/2012 2:25 PM, Tim Rentsch wrote:

>>> I assume most people in the group have seen this, but for those
>>> who have not:
>>>
>>> Threads Cannot be Implemented as a Library
>>>
>>> Boehm, Hans-J.
>>>
>>> HPL-2004-209
>>>
>>> Abstract: In many environments, multi-threaded code is written
>>> in a language that was originally designed without thread support
>>> (e.g. C), to which a library of threading primitives was
>>> subsequently added. There appears to be a general understanding
>>> that this is not the right approach. We provide specific
>>> arguments that a pure library approach, in which the compiler is
>>> designed independently of threading issues, cannot guarantee
>>> correctness of the resulting code. We first review why the
>>> approach almost works, and then examine some of the surprising
>>> behavior it may entail. We further illustrate that there are
>>> very simple cases in which a pure library-based approach seems
>>> incapable of expressing an efficient parallel algorithm. Our
>>> discussion takes place in the context of C with Pthreads, since
>>> it is commonly used, reasonably well specified, and does not
>>> attempt to ensure type-safety, which would entail even stronger
>>> constraints. The issues we raise are not specific to that
>>> context.
>>>
>>> http://www.hpl.hp.com/techreports/2004/HPL-2004-209.pdf
>>
>> I think the problem being addressed, here,
>
> Did you read the paper?

Yes, hence my comments. To take (roughly) the cases presented
in the paper:

4.1) You *know* when writing multithreaded code that
control to *any* shared object has to be arbitrated
(this is, IMO, one of the key points the article
tries to skirt... as if wanting NOT to have the
developer be concerned with these issues -- an
admirable goal but not one that rules out threading
libraries as a possible solution). The examples given
in this section show *no* explicit acknowledgement that
the objects/data are shared nor any mechanism to ensure
that sharing works (i.e., not even a library call is
present!)

4.2) is yet another example of the above. Except, in
addition to the lack of any formal access control
mechanism, there is now the acknowledgement that a
datum may span "objects". I.e., yet another case of
wanting to protect the programmer from things he might
have failed to notice (though still not anything that
precludes a library based solution)

4.3) Frankly, I don't see the problem here (too early
in the day?). Aside from the INEFFICIENCY that is
introduced... where is the code "broken"? OK, the
compiler's optimizations may have been unfortunate
but does the code perform as intended?

5.1) Makes the efficiency argument explicit -- and
goes to my comment regarding truly parallel implementations.

for (my_prime = start; my_prime < 10000; ++my_prime) {
if (!get(my_prime)) {
for (mult = my_prime; mult < 100000000; mult += my_prime) {
if (!get(mult)) {
set(mult);
}
}
}
}

is written *assuming* multiple threads can access the array
(sieve) hidden behind get()/set() inexpensively and concurrently.
The author then complains that the implementation of set()/get()
can cause problems -- for exactly the same reasons in 4.x.

I.e., the authors are advocating freeing the developer from
any concerns associated with implementing concurrency.
"Let's let the compiler consider all of these possible
cases and craft some rules that are *different* from the
rules a multithreaded programmer already SHOULD know..."
Yet, complain when safeguarding against those problems
(e.g., by invoking a mutex per shared object) becomes
"expensive": "Where's *my* free lunch??"

Sure, it would be delightful to *have* such protection
(i.e., scissors that automatically cover their blades
when they detect that you are "running with them").
But, I don't see how that PREVENTS a library based solution
from working.

E.g., wrap the internals of get()/set() with a lock.
The concurrency problems go away -- but performance
plummets. BECAUSE YOUR THREADS ARE COMPETING FOR TOO
MUCH DATA.

OTOH, having a thread doing this while another thread is
balancing your checkbook and still another is darning
your socks incurs NO performance penalty.

Yeah, its unfortunate that I can't get 500 digits of
precision in all of my math "for free". But, I don't
*expect* it to be free!

>> boil down to
>> removing the need for the developer to "take precautions"
>> (i.e., manually ensure that the compiler doesn't "get ahead
>> of him") along with wanting to be able to use the language
>> to *efficiently* implement truly parallel threads of
>> execution. [snip elaboration]
>
> The problem is the compiler is operating at the wrong level of
> abstraction. Whether the compiler "gets ahead" of a developer
> (a frightening concept in and of itself, but let's ignore
> that) doesn't matter, because the operating environment that
> (non-thread-aware) compilers generate code for doesn't make
> strong enough guarantees about inter-thread or inter-processor
> memory consistency. To get threads to work usably, at least
> part of the compiler needs to be aware of a lower level of
> abstraction, below the architectural level for a single
> process (which is where essentially all pre-thread-aware
> compilers operate).

I don't see that. I think that's only the case if you want
the compiler to be able to implement the safeguards *for* you.
And, I only see it pertaining to certain types of optimizations
(if the compiler doesn't make those optimizations, then your
code isn't at risk for them!)

I.e., I don't see how that PRECLUDES the use of a library.

Compilers are unaware of interrupts. An interrupt can occur
between any two instructions. Does that mean a you can't write
code in C that will operate in the presence of interrupts?

What it *does* mean is that anything that your code could be
doing that an interrupt might want to ASYNCHRONOUSLY interfere
with needs to be protected against that interference. Likewise,
anything your code wants to be able to *convey* to your ISR
needs to take precautions that the ISR sees "the whole picture"
and not just *part* of it.

Am I missing something, here?

Hi Jacob,

On 3/15/2012 1:28 PM, jacob navia wrote:
> Le 15/03/12 20:26, Don Y a écrit :
>>
>> OTOH, there are applications where all of printf's different
>> formats are just excess baggage. The size of printf()'s
>> executable is *staggering* when you think of how "little"
>> it (appears to) does. Yet, it seems to be one of the first
>> modules that a developer draws into his project...
>
> I know, I have written printf for my compiler system lcc-win.
> It is quite big mind you:
>
> d:\repos\lcc-src\libc>pedump /summary xprintf.obj
> xprintf.obj 41871 bytes, linked Tue Mar 13 19:22:37 2012
>
> Section Name Size
> 01 .text 14780
> 02 .data 1112
>
> almost 15K, + 12 K for character strings, tables, etc...

Exactly. You can write an *application* in that much
space! And all *it* does is "print stuff".

> But it will print a denormalized number extracting all the
> available precision from it.
>
> Supports all the C99 formats, etc. Actually printf is a
> run time intepreter of the format string. My printf also
> must support all the extensions: 450 significant digits
> qfloats, printng the comma separator to separate the number
> in thousands, and many other "goodies".
>
> I would like to have to possibility of trimming it, something
> like "slimPrintf()" but it would make programming more complex
> than it needs to.

If you have support for late/lazy binding, you can modularize
it and have only the portions that are actually *used*
dragged into the executable (e.g., in a hosted environment).

A more practical approach, IME, is to discard printf and
adopt hybrid functions that handle the formats of interest
to you.

E.g., I take great pains *not* to use floats/doubles in
most of my applications. The cost is usually too high
and the results they make available don't warrant the
expense (floating point emulation library, suppporting
floating point context in the OS, etc.).

Instead, I put the binary point where I want it and
carefully analyze the range and domain of each operation
that I perform to ensure I get the precision I need
in my results. (yeah, more tedious but cuts the
resource requirement$ significantly)

> And with only 15K, it is not THAT big, compared to other
> implementations that do less with more.

>>> // at end of progr someone has to free the list children
>>> i32 greetings(
>>> u8 *output, # communication channel named "output"
>>
>> No. The *data type* of "output" is "communication channel".
>> There is no counterpart in C. Think of it as a "named pipe"
>> that connects two threads -- possibly across machine boundaries.
>> You could provide similar functionality with a *socket*, a FIFO
>> or a managed shared memory region (in some contexts). But, you
>> would have to explicitly set up this mechanism (function calls).
>
> a pointer can point to each region of memory, that can be used
> from functions for doing all is possible to do

Sure! And where do you synchronize access to that region with
other threads? What happens when the region is "full"? Do you
reset the pointer to the "beginning" and keep going? How does
the thread on the other end know *where* you are in this region
and where the "still undefined" portion of the region begins
(so it doesn't look for real data in those places)

>> Limbo lets you just create one (and "pass it around") just like
>> you would an int, etc.
>>
>> So, while you can accumulate the stuff intended to be transfered
>> across that channel *in* a string (assuming the channel is
>
> is not a string is a pointer to a unsigned char
> [but it could be aligned to unsigned if the function initialize
> it allow...]

Understood. But it still isn't a complete communication
system. See above

>> declared to support strings -- and not ints or some other
>> data type!), you still have to actively *pass* it across
>> some communication mechanism.
>>
>> Threading implies communication between threads. Channels
>> formalize that.
>>
>>> u8 *surname, # parameter of type "string"
>>> u8 *children # a list of tuples each
>>
>> Not sure how you plan on storing those, yet... Note that Limbo
>> makes it clear what you are intending *in* the declaration:
>> "This is a LIST of TUPLES where each is tuple consists of
>> a string (the child's name) and an integer (his age)"
>
> i have no problem with these char pointers...

But *you* are responsible for implementing the list and the
tuples within it. I have no problem multiplying integers
in a loop of successive shifts and conditional adds. But,
I would much rather type an '*' between the two variable
names! :>

>>> ) {u8 *tmpStr, *tmpPlist;
>>> i32 r=0;
>>> if(surname==0||output==0||children==0||ListNotOk(c hildren))
>>> R 1;
>>>
>>> # create a string by concatenating the two string constants
>>> # with the string *variable* passed to the function as "surname"
>>> # pass the resulting string out the channel named "output"
>>> # output<-= "Season's Greetings from the "
>>> # + surname + " family!\n";
>>>
>>> // StrMultiCat(u8** , ...) where ... are C string u8*
>>> if( StrMultiCat(&tmpStr, "Season's Greetings from the ",
>>> surname, " family!\n" )==-1 )
>>> {err:
>>> StrDel(&tmpStr); R r
>>> }
>>
>> Notice that you have to explicitly manage memory (to avoid leaks).
>
> yes that is supposed a real programmer should do

Sure. IF THE LANGUAGE DOESN'T DO IT FOR YOU!

I.e., when a UN*X process ends, the system doesn't complain
that you forgot to free() some memory that you had allocated
BEFORE the process terminated.

The designers of the process semantics opted to take care of
this little detail *for* you because it is something that
is common enough in actual use. "Sorry, you forgot to
free() your resources so we are going to mess with the
operation of other UNRELATED processes in the system just
to ensure those folks get REALLY mad at you and force you
to behave more hospitably" :>

>> Limbo ensures that the resources you hold are automatically
>> free-d when you terminate. I.e., it is part of the *language*
>> specification, not the "hosting environment".
>
> i have not problem with memory leak
>
>>> if( StrSPut(output, tmpStr) == -1) {r=5; G err;}
>>
>> Again, all you have done is built a string. No one else
>> can *see* it! You haven't, yet:
>
> no "output" can point, for example to a C like FILE struct etc

Again, see above. How does "logging()" know that you have
added something to that region of memory? What happens when
logging() gets ahead of you? Does it just print whatever
jibberish happened to reside in that region of memory
BEFORE you got around to stuffing tmpStr into it?

[big snip]

>> The "children" list could be implemented as either a linked list
>> of these structs *or* an array -- with suitable code wrapped
>> around it to allow it to grow and shrink as needed.
>
> can be upside down and down upside, at end i say it should be ok
>
>>> if( StrCat(&tmpStr, " (") == -1 ){r=10; G err;}
>>> if( StrCat_u32(&tmpStr, age) == -1 ){r=11; G err;}
>>> if( StrCat(&tmpStr, " years old)") == -1 )
>>> {r=12; G err;}
>>>
>>> # pass the "fullname" (grrr... should have been "description")
>>> # string to the communication channel named "output"
>>> # output<-= fullname;
>>>
>>> if( StrSPut(output, tmpStr) == -1 ) {r=13; G err;}
>>>
>>> # assign the balance (everything beyond the "head") of the children
>>> # list to the children list variable
>>>
>>> # children = tl children;
>>> not traslated: what is t1?
>>
>> tl == "tail"
>>
>> # assign the balance (everything beyond the "head") of the children
>> -------------^^^^^^^^^^^---^^^^^^^^^^^^^^^^^^^^^^^^^^
>> # list to the children list variable
>>
>>> }
>>> StrDel(&tmpStr);
>>> R r;
>>> }
>>
>> Notice how much "manual" work you have to do to implement the
>> same sorts of functionality?
>
> i'm not agree

That's your perogative! :> Some of us even use assembly language
(gasp! heresy!!)

>> More opportunities for mistakes
>> (did you remember to free all your resources regardless of
>> the path you took through the code, etc.). Limbo's syntax
>> is a lot cleaner (though admittedly cryptic for novices)
>
> leak are not my problems, but problem of my malloc()
> function implementation ...

If you forget to free something that *you* caused to be allocated
(either directly or indirectly), then the leak is *your* problem.
You can't blame the memory subsystem for failing to read your
mind.

Don Y <this@isnotme.com> writes:

> Hi Ben,
>
> On 3/15/2012 9:36 AM, Ben Bacarisse wrote:
>> Don Y<this@isnotme.com> writes:
>> <snip>
>>> When was the last time you used:
>>>
>>> digits = INT_MAX
>>> decimals = INT_MAX
>>> printf("The answer is %*.*e", value, digits, decimals)
>>
>> Never! It needs semi-colons, and it needs the printf arguments to be in
>> the right order! Also, making the field width equal to the precision is
>> a little odd for the 'e' conversion.
>>
>>> In fact, when was the last time you used the '*' flag in printf??
>>
>> I use it quite a lot, but that may just be that I like to parametrise my
>> code a lot. By the way, it's not a "flag". printf specifiers do have
>> flags (there are +, -, #, ' ' and 0) so using the wrong term might be
>> confusing.
>
> Wow, I am *so* relieved! With all your criticisms, I was
> afraid you might not have UNDERSTOOD WHAT I INTENDED! Whew!
> Glad I won't have to worry about *that*!
>
> [If you have some EXTRA free time, how about checking my past
> posts for spelling and grammatical errors. It might help
> others who are confused by a typo here or there... e.g., my
> recent use of 'int' in place of 'age'... There might be
> *other* folks who would also welcome your attention to this
> level of detail!]

I'm sorry. I have no desire to annoy you with details that don't
interest you. Some people are interested in details and some are not
and I made the wrong call. I will try not to do it again.

<snip>
--
Ben.

Hi Ben,

On 3/15/2012 5:13 PM, Ben Bacarisse wrote:
> Don Y<this@isnotme.com> writes:
>
>> Hi Ben,
>>
>> On 3/15/2012 9:36 AM, Ben Bacarisse wrote:
>>> Don Y<this@isnotme.com> writes:
>>> <snip>
>>>> When was the last time you used:
>>>>
>>>> digits = INT_MAX
>>>> decimals = INT_MAX
>>>> printf("The answer is %*.*e", value, digits, decimals)
>>>
>>> Never! It needs semi-colons, and it needs the printf arguments to be in
>>> the right order! Also, making the field width equal to the precision is
>>> a little odd for the 'e' conversion.
>>>
>>>> In fact, when was the last time you used the '*' flag in printf??
>>>
>>> I use it quite a lot, but that may just be that I like to parametrise my
>>> code a lot. By the way, it's not a "flag". printf specifiers do have
>>> flags (there are +, -, #, ' ' and 0) so using the wrong term might be
>>> confusing.
>>
>> Wow, I am *so* relieved! With all your criticisms, I was
>> afraid you might not have UNDERSTOOD WHAT I INTENDED! Whew!
>> Glad I won't have to worry about *that*!
>>
>> [If you have some EXTRA free time, how about checking my past
>> posts for spelling and grammatical errors. It might help
>> others who are confused by a typo here or there... e.g., my
>> recent use of 'int' in place of 'age'... There might be
>> *other* folks who would also welcome your attention to this
>> level of detail!]
>
> I'm sorry. I have no desire to annoy you with details that don't
> interest you. Some people are interested in details and some are not
> and I made the wrong call. I will try not to do it again.

No, I apologize for "jumping down your throat". I understand
the point(s) you were trying to make.

OTOH, it is very annoying to have little "distractions" that
don't address the *substance* of the argument being made.
Too often, a thread wanders into totally arcane territory
at the expense of the original subject matter. Lots of
text flows back and forth but very little information
gets added to the actual discussion.

If someone posts a code fragment or makes a statement that
"doesn't look right" (to me), I *assume* they are intelligent
and wonder what *my* problem might be in grasping what they
are trying to convey. Am I not seeing some issue that *they*
have (and are trying to draw my attention to)? Has some
previous comment of mine been misinterpreted/unclear? Is
there a typographical error that could explain the confusion
on my part? Is natural *language* a problem? etc.

I'm not a teacher "grading papers". Nor do I have a desire to
be. And, unless the comments/code/etc. are *clearly* off the
mark, I suspect the other person isn't interested in my
corrections -- if they re-read their post, chances are, they
will find them independently. Nor do I want folks feeling they
have to quickly update their posts to correct piddly errors
to avoid having others correct them on their behalf.

E.g., in a discussion with "io_x", I have to consider if the
code he (?) presented glossed over a key feature of my
example -- or, if it addressed that feature in a different
manner. *Not* whether his code would compile without errors.
Or whether it would achieve the intended results. (a compiler
and debugger can comment more authoritatively on those issues
WITHOUT my involvement).

Instead, my focus is on "do you understand what this
*mechanism* is and what it does *for* you?" I.e., do you
understand what *I* am saying and do I understand what
*you* are saying...

Again, my apologies.

"Don Y" <this@isnotme.com> ha scritto nel messaggio
news:jjtm7m$nj5$1@speranza.aioe.org...
>>>> // at end of progr someone has to free the list children
>>>> i32 greetings(
>>>> u8 *output, # communication channel named "output"
>>>
>>> No. The *data type* of "output" is "communication channel".
>>> There is no counterpart in C. Think of it as a "named pipe"
>>> that connects two threads -- possibly across machine boundaries.
>>> You could provide similar functionality with a *socket*, a FIFO
>>> or a managed shared memory region (in some contexts). But, you
>>> would have to explicitly set up this mechanism (function calls).
>>
>> a pointer can point to each region of memory, that can be used
>> from functions for doing all is possible to do
>
> Sure! And where do you synchronize access to that region with
> other threads?

it is the OS that, using one unsigned 32 bit region of mem,
say to function if it is safe to read write to list struct,
if it is safe to use the list or not...

>What happens when the region is "full"? Do you
> reset the pointer to the "beginning" and keep going? How does
> the thread on the other end know *where* you are in this region
> and where the "still undefined" portion of the region begins
> (so it doesn't look for real data in those places)

OS know one single thread use the list

Don Y <this@isnotme.com> writes:

> Hi Tim,
>
> On 3/14/2012 2:25 PM, Tim Rentsch wrote:
>
>>>> I assume most people in the group have seen this, but for those
>>>> who have not:
>>>>
>>>> Threads Cannot be Implemented as a Library
>>>>
>>>> Boehm, Hans-J.
>>>>
>>>> HPL-2004-209
>>>>
>>>> Abstract: In many environments, multi-threaded code is written
>>>> in a language that was originally designed without thread support
>>>> (e.g. C), to which a library of threading primitives was
>>>> subsequently added. There appears to be a general understanding
>>>> that this is not the right approach. We provide specific
>>>> arguments that a pure library approach, in which the compiler is
>>>> designed independently of threading issues, cannot guarantee
>>>> correctness of the resulting code. We first review why the
>>>> approach almost works, and then examine some of the surprising
>>>> behavior it may entail. We further illustrate that there are
>>>> very simple cases in which a pure library-based approach seems
>>>> incapable of expressing an efficient parallel algorithm. Our
>>>> discussion takes place in the context of C with Pthreads, since
>>>> it is commonly used, reasonably well specified, and does not
>>>> attempt to ensure type-safety, which would entail even stronger
>>>> constraints. The issues we raise are not specific to that
>>>> context.
>>>>
>>>> http://www.hpl.hp.com/techreports/2004/HPL-2004-209.pdf
>>>
>>> I think the problem being addressed, here,
>>
>> Did you read the paper?
>
> Yes, hence my comments. To take (roughly) the cases presented
> in the paper:
>
> 4.1) You *know* when writing multithreaded code that
> control to *any* shared object has to be arbitrated
> [snip elaboration]

You missed the point of the example, which was to illustrate a
problem in defining how the thread library will behave when the
language specification doesn't say anything about inter-thread
memory access semantics.

> 4.2) is yet another example of the above. Except, in
> addition to the lack of any formal access control
> mechanism, there is now the acknowledgement that a
> datum may span "objects". I.e., yet another case of
> wanting to protect the programmer from things he might
> have failed to notice (though still not anything that
> precludes a library based solution)

You are misreading the example. 4.1 and 4.2 bring up different
issues. Your characterization of the example is just silly,
because it presumes that the very problem being identified has
been solved already.

> 4.3) Frankly, I don't see the problem here (too early
> in the day?). Aside from the INEFFICIENCY that is
> introduced... where is the code "broken"? OK, the
> compiler's optimizations may have been unfortunate
> but does the code perform as intended?

No, that's the point - the optimizing process has introduced a
race condition.

> 5.1) Makes the efficiency argument explicit -- and
> goes to my comment regarding truly parallel implementations.
>
> for (my_prime = start; my_prime < 10000; ++my_prime) {
> if (!get(my_prime)) {
> for (mult = my_prime; mult < 100000000; mult += my_prime) {
> if (!get(mult)) {
> set(mult);
> }
> }
> }
> }
>
> is written *assuming* multiple threads can access the array
> (sieve) hidden behind get()/set() inexpensively and concurrently.
> The author then complains that the implementation of set()/get()
> can cause problems -- for exactly the same reasons in 4.x.

You have misunderstood the point. The one case that behaves
incorrectly is included only for performance comparison. That
case is irrelevant to the issue being discussed in this section.

> I.e., the authors are advocating freeing the developer from
> any concerns associated with implementing concurrency.

No, they aren't.

> "Let's let the compiler consider all of these possible
> cases and craft some rules that are *different* from the
> rules a multithreaded programmer already SHOULD know..."
> Yet, complain when safeguarding against those problems
> (e.g., by invoking a mutex per shared object) becomes
> "expensive": "Where's *my* free lunch??" [snip elaboration]

It appears you have completely misunderstood the issue the paper
is trying to identify. Unless a language specification defines
inter-thread memory access semantics, it simply is not possible
for a developer to know what "rules" he should follow for
multithreaded programs.


>>> boil down to
>>> removing the need for the developer to "take precautions"
>>> (i.e., manually ensure that the compiler doesn't "get ahead
>>> of him") along with wanting to be able to use the language
>>> to *efficiently* implement truly parallel threads of
>>> execution. [snip elaboration]
>>
>> The problem is the compiler is operating at the wrong level of
>> abstraction. Whether the compiler "gets ahead" of a developer
>> (a frightening concept in and of itself, but let's ignore
>> that) doesn't matter, because the operating environment that
>> (non-thread-aware) compilers generate code for doesn't make
>> strong enough guarantees about inter-thread or inter-processor
>> memory consistency. To get threads to work usably, at least
>> part of the compiler needs to be aware of a lower level of
>> abstraction, below the architectural level for a single
>> process (which is where essentially all pre-thread-aware
>> compilers operate).
>
> I don't see that. I think that's only the case if you want
> the compiler to be able to implement the safeguards *for* you.

No, it's true regardless of whether the burden for putting in the
safeguards rests on the compiler or the developer.

> And, I only see it pertaining to certain types of optimizations
> (if the compiler doesn't make those optimizations, then your
> code isn't at risk for them!)

There may have been a time when that was true, but for most
modern processors these kinds of optimizations can take place in
hardware at run-time without the compiler ever being aware of
them.

> I.e., I don't see how that PRECLUDES the use of a library.

It doesn't preclude the use of a library; it just means
a library by itself is not sufficient.

> Compilers are unaware of interrupts. An interrupt can occur
> between any two instructions. Does that mean a you can't write
> code in C that will operate in the presence of interrupts?

Yes, it does mean that, if by "C" what is meant is ISO standard C
with no dependencies on implementation-defined or undefined
behavior.

> What it *does* mean is that anything that your code could be
> doing that an interrupt might want to ASYNCHRONOUSLY interfere
> with needs to be protected against that interference. Likewise,
> anything your code wants to be able to *convey* to your ISR
> needs to take precautions that the ISR sees "the whole picture"
> and not just *part* of it.

There is no way to do this without involving the implementation
at some level, because standard C does not have expressive enough
semantics -- without making guarantees beyond what the language
definition itself provides -- to convey what needs conveying.

> Am I missing something, here?

I think you are confusing (1) how an individual implementation
behaves, and (2) what the language definition, by itself, guarantees
for the behavior of all implementations. They aren't the same.

Hi Tim,

[Apologies for the delay in replying -- I'm dealing with travel
& meetings for the next bit]

On 3/18/2012 5:05 PM, Tim Rentsch wrote:
> Don Y<this@isnotme.com> writes:
>
>> Hi Tim,
>>
>> On 3/14/2012 2:25 PM, Tim Rentsch wrote:
>>
>>>>> I assume most people in the group have seen this, but for those
>>>>> who have not:
>>>>>
>>>>> Threads Cannot be Implemented as a Library

>>>>> http://www.hpl.hp.com/techreports/2004/HPL-2004-209.pdf
>>>>
>>>> I think the problem being addressed, here,
>>>
>>> Did you read the paper?
>>
>> Yes, hence my comments. To take (roughly) the cases presented
>> in the paper:
>>
>> 4.1) You *know* when writing multithreaded code that
>> control to *any* shared object has to be arbitrated
>> [snip elaboration]
>
> You missed the point of the example, which was to illustrate a
> problem in defining how the thread library will behave when the
> language specification doesn't say anything about inter-thread
> memory access semantics.

I see no library functions in this example. How will:

printf("Hello\n");

printf("Goodbyte\n");

behave (in different threads)? Will you see:
Hello
Goodbye
or
Goodbye
Hello
or
HGeololdobye

or
a flashing "screen" of noise?

Races are a fact of life in multithreaded applications.
TO THE EXTENT THAT THOSE THREADS SHARE ACCESS TO A RESOURCE(s).
That's why there are synchronization primitives, etc.

If you read each of the examples, the author wants the
language itself to make guarantees about how these races
are resolved.

In reality, you would bracket each such thread access with
a mutex or other mechanism to effectively guarantee atomic
operation. The author complains (just before section 4)
that:

"This approach clearly works most of the time.

Gee! :>

"Unfortunately, we will see that it is too imprecise
to allow the programmer to reason convincingly about
program correctness, or to provide clear guidance to
the compiler implementor.

OK, so writing multithreaded code isn't easy. Nor is writing
functionally correct code. Nor real-time code. Nor...

"As a result, apparently correct programs may fail
intermittently, or start to fail when a new compiler
or hardware version is used.

Sure! And:
hourly_wage = pay / hours_worked;
will ALSO fail intermittently -- when hours_worked is *0*!

"The resulting failures are triggered by specific thread
schedules, and are thus relatively hard to detect during
testing.

Yes. But, so far, I hear nothing that says why a *library*
based solution WILL NOT WORK. After all, the title of the
paper clearly makes that assertion:
_Threads Cannot Be Implemented As a Library_
I contend that the author would have been better served using:
_Threads SHOULD NOT Be Implemented As a Library_
to convey his *opinion* on their suitability.

"A secondary problem with this approach is that, in some
cases, it excludes the best performing algorithmic solutions.

Yes. But, that's a consequence of the language. FORTRAN
makes it hard to implement lists. You find another way.
Again, nothing that precludes a library for threading.

"As a result, many large systems, either intentionally, or
unintentionally, violate the above rules. The resulting
programs are then even more susceptible to the above problems."

So, are we to be paternalistic, now? Let's make the language
such that the developer *can't* make a mistake? Shall we get
rid of division out of fear that the programmer might fail to
test for a divisor of 0? Ban pointers because someone might
fiddle with something that should be faddled, instead?

Didn't *Java* try to solve all these problems??

>> 4.2) is yet another example of the above. Except, in
>> addition to the lack of any formal access control
>> mechanism, there is now the acknowledgement that a
>> datum may span "objects". I.e., yet another case of
>> wanting to protect the programmer from things he might
>> have failed to notice (though still not anything that
>> precludes a library based solution)
>
> You are misreading the example. 4.1 and 4.2 bring up different
> issues. Your characterization of the example is just silly,
> because it presumes that the very problem being identified has
> been solved already.

Again, where has the author demonstrated the "problem" with
the library approach? He's just shown another race -- that's
a bit subtler to spot.

The same argument applies to:
struct {
int dozens;
int individual_eggs;
} x;
with:
x.individual_eggs++;
if (x.individual_eggs >= 12) {
x.individual_eggs = 0;
x.dozens++;
}
in which a concurrent thread could see a MONOTONICALLY
INCREASING "egg count" progress as:
{4, 10}
(4, 11}
{4, 12}
{4, 0}
{5, 0}
Again, why hasn't the author demonstrated why a library
--->CANNOT<--- be used for threading??

>> 4.3) Frankly, I don't see the problem here (too early
>> in the day?). Aside from the INEFFICIENCY that is
>> introduced... where is the code "broken"? OK, the
>> compiler's optimizations may have been unfortunate
>> but does the code perform as intended?
>
> No, that's the point - the optimizing process has introduced a
> race condition.

How does the code "not work" -- how does the library NOT
provide the guarantees sought?

>> 5.1) Makes the efficiency argument explicit -- and
>> goes to my comment regarding truly parallel implementations.
>>
>> for (my_prime = start; my_prime< 10000; ++my_prime) {
>> if (!get(my_prime)) {
>> for (mult = my_prime; mult< 100000000; mult += my_prime) {
>> if (!get(mult)) {
>> set(mult);
>> }
>> }
>> }
>> }
>>
>> is written *assuming* multiple threads can access the array
>> (sieve) hidden behind get()/set() inexpensively and concurrently.
>> The author then complains that the implementation of set()/get()
>> can cause problems -- for exactly the same reasons in 4.x.
>
> You have misunderstood the point. The one case that behaves
> incorrectly is included only for performance comparison. That
> case is irrelevant to the issue being discussed in this section.

Section 5 focuses on "Performance". 5.1 highlights "Expensive
Synchronization". The sieve example tries to illustrate how
locking isn't "technically" needed (it assumes true and false
values can be obtained in an inherently atomic fashion). But,
that the developer can make no claims as to how effective the
speedup will actually be for this algorithm -- since events
can conspire so arrange updates to always be "just out of
step" with competing threads -- so that those threads end up NOT
being able to take advantage of the work of their peers
(because that work's progress has been disclosed to them
just a tiny bit too late).

Per the last paragraph in section 5.1:
"But even with 4 threads, the properly synchronized code
only barely exceeds the performance of a single
synchronization-free thread, and that only with the use
of spin-locks"
Sure sounds like the author is complaining about the *cost* of
these primitives!

>> I.e., the authors are advocating freeing the developer from
>> any concerns associated with implementing concurrency.
>
> No, they aren't.

I see nothing where the use of a library implementation has been
demonstrated as not working. If this is the point, then *litter*
every example with specific library invocations and point out
how they *can't* address the problem.

>> "Let's let the compiler consider all of these possible
>> cases and craft some rules that are *different* from the
>> rules a multithreaded programmer already SHOULD know..."
>> Yet, complain when safeguarding against those problems
>> (e.g., by invoking a mutex per shared object) becomes
>> "expensive": "Where's *my* free lunch??" [snip elaboration]
>
> It appears you have completely misunderstood the issue the paper
> is trying to identify. Unless a language specification defines
> inter-thread memory access semantics, it simply is not possible
> for a developer to know what "rules" he should follow for
> multithreaded programs.

The rules are simple: if a resource is accessed in different
threads, then *you* have to ensure those accesses don't
"interfere" with each other. All of the author's examples
illustrated cases where the author appears to want the
*compiler* to be able to resolve these issues *for* you.

Should the compiler look at how I initialize a pointer and,
based on that knowledge, *limit* the range of operations
that I can perform on that pointer and the range of values
that it can take on? E.g., if I initialize the pointer
to the start of a const char array, should the compiler
PREVENT me from advancing it beyond the end of that array?
Surely, there is no reason for me to refer to a location
"much beyond" the end of the array (i.e., strlen+1)!

We're perfectly content to NOT have the language prescribe
what happens in this case. And, our code somehow manages
to work despite this "implementation (un)defined" behavior.

>>>> boil down to
>>>> removing the need for the developer to "take precautions"
>>>> (i.e., manually ensure that the compiler doesn't "get ahead
>>>> of him") along with wanting to be able to use the language
>>>> to *efficiently* implement truly parallel threads of
>>>> execution. [snip elaboration]
>>>
>>> The problem is the compiler is operating at the wrong level of
>>> abstraction. Whether the compiler "gets ahead" of a developer
>>> (a frightening concept in and of itself, but let's ignore
>>> that) doesn't matter, because the operating environment that
>>> (non-thread-aware) compilers generate code for doesn't make
>>> strong enough guarantees about inter-thread or inter-processor
>>> memory consistency. To get threads to work usably, at least
>>> part of the compiler needs to be aware of a lower level of
>>> abstraction, below the architectural level for a single
>>> process (which is where essentially all pre-thread-aware
>>> compilers operate).
>>
>> I don't see that. I think that's only the case if you want
>> the compiler to be able to implement the safeguards *for* you.
>
> No, it's true regardless of whether the burden for putting in the
> safeguards rests on the compiler or the developer.

Again, I don't see that. The compiler can't arbitrarily rewrite
code. Otherwise, the ultimate compiler would rewrite ALL
programs:
main() {
...
exit();
}
as:
main() {
exit();
...
}
I don't see how a library *can't* (author's words) provide
that.

>> And, I only see it pertaining to certain types of optimizations
>> (if the compiler doesn't make those optimizations, then your
>> code isn't at risk for them!)
>
> There may have been a time when that was true, but for most
> modern processors these kinds of optimizations can take place in
> hardware at run-time without the compiler ever being aware of
> them.

And that's why you design memory barriers, etc. in your
application. To *force* the hardware to get back into
lock-step with the application.

>> I.e., I don't see how that PRECLUDES the use of a library.
>
> It doesn't preclude the use of a library; it just means
> a library by itself is not sufficient.

*Why*? What *can't* the library do?

>> Compilers are unaware of interrupts. An interrupt can occur
>> between any two instructions. Does that mean a you can't write
>> code in C that will operate in the presence of interrupts?
>
> Yes, it does mean that, if by "C" what is meant is ISO standard C
> with no dependencies on implementation-defined or undefined
> behavior.

But libraries can be implemented *outside* of the Standard -- as
long as the interface to the library conforms. Or, are you
claiming that the library *also* has to be "portable C"?

>> What it *does* mean is that anything that your code could be
>> doing that an interrupt might want to ASYNCHRONOUSLY interfere
>> with needs to be protected against that interference. Likewise,
>> anything your code wants to be able to *convey* to your ISR
>> needs to take precautions that the ISR sees "the whole picture"
>> and not just *part* of it.
>
> There is no way to do this without involving the implementation
> at some level, because standard C does not have expressive enough
> semantics -- without making guarantees beyond what the language
> definition itself provides -- to convey what needs conveying.

You can interface to the language without being *part* of
the language. I.e., I can create a function that causes
the interrupts to be disabled in a processor. I can put that
function into a library. I can create different versions of
that function for different processor architectures. How
does that "not work"?

>> Am I missing something, here?
>
> I think you are confusing (1) how an individual implementation
> behaves, and (2) what the language definition, by itself, guarantees
> for the behavior of all implementations. They aren't the same.

I understand that you can't do these things ENTIRELY within the
formally defined domain of the C language.

But, the title of the article was:
"Threads Cannot be Implemented as a Library"
it didn't say that the library had to be written in portable C.
It didn't say that the library had to be written in C at all!

I've got this great new Hardware Abstraction Language. The
primitives in this language are 'flush_cache', 'synchronize_caches',
'begin_atomic_operation', etc. The beauty of this language is
that a conforming HAL compiler will "do the right thing" for
the processor for which it is targeted. A command line
option to the HAL compiler lets you create a binding for
C, Pascal, Java, etc. The output can be in COFF, ELF, etc.

So, it's relatively straightforward to build a library with
C bindings that a C *application* can use to reliably provide
these mechanisms.

The unfortunate thing is that the HAL compiler exists "between
the ears" of a select few developers instead of as an executable.

Again, I see the author's failure being the choice of title;
"Threads SHOULD NOT be Implemented as a Library"
highlighting how hard it is to write multithreaded code (in
which case, why bother with yet another article stating the
obvious?) or:
"Threads Cannot be Implemented as a Library Written in C"
highlighting the guarantees that the library would have to
provide to the application developer and WHY THE LANGUAGE
(as it stands) CAN'T MAKE THOSE GUARANTEES, etc.