Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
| From | Don Y <this@isnotme.com> |
|---|---|
| Newsgroups | comp.lang.c |
| Subject | Re: things i would ban from clc |
| Date | 2012-03-23 11:59 -0700 |
| Organization | Aioe.org NNTP Server |
| Message-ID | <jkih73$8er$1@speranza.aioe.org> (permalink) |
| References | (14 earlier) <kfn1uowm6c4.fsf@x-alumni2.alumni.caltech.edu> <jjpim1$vka$1@speranza.aioe.org> <kfnobrylvt0.fsf@x-alumni2.alumni.caltech.edu> <jjtk44$hih$1@speranza.aioe.org> <kfny5qxjvzf.fsf@x-alumni2.alumni.caltech.edu> |
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.
Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
things i would ban from clc jgk@panix.com (Joe keane) - 2012-03-11 23:05 +0000
Re: things i would ban from clc Keith Thompson <kst-u@mib.org> - 2012-03-12 10:33 -0700
Re: things i would ban from clc gazelle@shell.xmission.com (Kenny McCormack) - 2012-03-12 23:57 +0000
Re: things i would ban from clc jacob navia <jacob@spamsink.net> - 2012-03-12 18:44 +0100
Re: things i would ban from clc Don Y <this@isnotme.com> - 2012-03-12 12:26 -0700
Re: things i would ban from clc "osmium" <r124c4u102@comcast.net> - 2012-03-12 14:36 -0600
Re: things i would ban from clc Don Y <this@isnotme.com> - 2012-03-12 13:57 -0700
Re: things i would ban from clc James Kuyper <jameskuyper@verizon.net> - 2012-03-12 17:34 -0400
Re: things i would ban from clc Don Y <this@isnotme.com> - 2012-03-12 15:00 -0700
Re: things i would ban from clc James Kuyper <jameskuyper@verizon.net> - 2012-03-12 18:21 -0400
Re: things i would ban from clc Don Y <this@isnotme.com> - 2012-03-12 15:43 -0700
Re: things i would ban from clc jacob navia <jacob@spamsink.net> - 2012-03-12 23:53 +0100
Re: things i would ban from clc Don Y <this@isnotme.com> - 2012-03-12 17:17 -0700
Re: things i would ban from clc jacob navia <jacob@spamsink.net> - 2012-03-13 09:09 +0100
Re: things i would ban from clc Don Y <this@isnotme.com> - 2012-03-13 01:24 -0700
Re: things i would ban from clc Keith Thompson <kst-u@mib.org> - 2012-03-13 05:59 -0700
Re: things i would ban from clc Don Y <this@isnotme.com> - 2012-03-13 10:55 -0700
Re: things i would ban from clc blp@cs.stanford.edu (Ben Pfaff) - 2012-03-13 11:07 -0700
Re: things i would ban from clc Don Y <this@isnotme.com> - 2012-03-13 11:25 -0700
Re: things i would ban from clc blp@cs.stanford.edu (Ben Pfaff) - 2012-03-13 11:32 -0700
Re: things i would ban from clc Keith Thompson <kst-u@mib.org> - 2012-03-13 12:18 -0700
Re: things i would ban from clc Don Y <this@isnotme.com> - 2012-03-13 16:13 -0700
Re: things i would ban from clc Don Y <this@isnotme.com> - 2012-03-13 13:49 -0700
Re: things i would ban from clc James Kuyper <jameskuyper@verizon.net> - 2012-03-13 17:14 -0400
Re: things i would ban from clc Don Y <this@isnotme.com> - 2012-03-13 14:35 -0700
Re: things i would ban from clc James Kuyper <jameskuyper@verizon.net> - 2012-03-13 18:09 -0400
Re: things i would ban from clc Don Y <this@isnotme.com> - 2012-03-13 16:06 -0700
Re: things i would ban from clc "io_x" <a@b.c.invalid> - 2012-03-14 08:18 +0100
Re: things i would ban from clc "io_x" <a@b.c.invalid> - 2012-03-14 10:07 +0100
Re: things i would ban from clc Don Y <this@isnotme.com> - 2012-03-14 12:41 -0700
Re: things i would ban from clc "io_x" <a@b.c.invalid> - 2012-03-14 21:53 +0100
Re: things i would ban from clc Don Y <this@isnotme.com> - 2012-03-15 14:16 -0700
Re: things i would ban from clc "io_x" <a@b.c.invalid> - 2012-03-18 07:14 +0100
Re: things i would ban from clc Jens Gustedt <jens.gustedt@loria.fr> - 2012-03-14 10:39 +0100
Re: things i would ban from clc Ben Pfaff <blp@cs.stanford.edu> - 2012-03-13 14:33 -0700
Re: things i would ban from clc Don Y <this@isnotme.com> - 2012-03-13 14:40 -0700
Re: things i would ban from clc Tim Rentsch <txr@alumni.caltech.edu> - 2012-03-13 16:25 -0700
Re: things i would ban from clc Don Y <this@isnotme.com> - 2012-03-14 00:51 -0700
Re: things i would ban from clc Tim Rentsch <txr@alumni.caltech.edu> - 2012-03-14 14:25 -0700
Re: things i would ban from clc Don Y <this@isnotme.com> - 2012-03-15 13:40 -0700
Re: things i would ban from clc Tim Rentsch <txr@alumni.caltech.edu> - 2012-03-18 17:05 -0700
Re: things i would ban from clc Don Y <this@isnotme.com> - 2012-03-23 11:59 -0700
Re: things i would ban from clc Robert Wessel <robertwessel2@yahoo.com> - 2012-03-23 17:02 -0500
Re: things i would ban from clc Don Y <this@isnotme.com> - 2012-03-23 16:51 -0700
Re: things i would ban from clc "io_x" <a@b.c.invalid> - 2012-03-24 07:16 +0100
Re: things i would ban from clc Tim Rentsch <txr@alumni.caltech.edu> - 2012-03-27 11:26 -0700
Re: things i would ban from clc Kaz Kylheku <kaz@kylheku.com> - 2012-03-23 19:43 +0000
Re: things i would ban from clc Rui Maciel <rui.maciel@gmail.com> - 2012-03-23 19:45 +0000
Re: things i would ban from clc Jens Gustedt <jens.gustedt@loria.fr> - 2012-03-23 23:49 +0100
Re: things i would ban from clc Ian Collins <ian-news@hotmail.com> - 2012-03-24 11:54 +1300
Re: things i would ban from clc Jens Gustedt <jens.gustedt@loria.fr> - 2012-03-24 09:26 +0100
Re: things i would ban from clc gwowen <gwowen@gmail.com> - 2012-03-26 07:31 -0700
Re: things i would ban from clc Kaz Kylheku <kaz@kylheku.com> - 2012-03-24 05:45 +0000
Re: things i would ban from clc Jens Gustedt <jens.gustedt@loria.fr> - 2012-03-24 09:31 +0100
Re: things i would ban from clc James Kuyper <jameskuyper@verizon.net> - 2012-03-13 14:34 -0400
Re: things i would ban from clc Tim Rentsch <txr@alumni.caltech.edu> - 2012-03-13 16:18 -0700
Re: things i would ban from clc "io_x" <a@b.c.invalid> - 2012-03-14 08:18 +0100
Re: things i would ban from clc Tim Rentsch <txr@alumni.caltech.edu> - 2012-03-14 14:06 -0700
Re: things i would ban from clc Jorgen Grahn <grahn+nntp@snipabacken.se> - 2012-03-15 15:22 +0000
Re: things i would ban from clc Don Y <this@isnotme.com> - 2012-03-15 12:26 -0700
Re: things i would ban from clc jacob navia <jacob@spamsink.net> - 2012-03-15 21:28 +0100
Re: things i would ban from clc Don Y <this@isnotme.com> - 2012-03-15 13:49 -0700
Re: things i would ban from clc Ben Bacarisse <ben.usenet@bsb.me.uk> - 2012-03-15 16:36 +0000
Re: things i would ban from clc Don Y <this@isnotme.com> - 2012-03-15 12:16 -0700
Re: things i would ban from clc Ben Bacarisse <ben.usenet@bsb.me.uk> - 2012-03-16 00:13 +0000
Re: things i would ban from clc Don Y <this@isnotme.com> - 2012-03-15 20:40 -0700
Re: things i would ban from clc gwowen <gwowen@gmail.com> - 2012-03-13 01:52 -0700
Re: things i would ban from clc "io_x" <a@b.c.invalid> - 2012-03-13 11:31 +0100
Re: things i would ban from clc jacob navia <jacob@spamsink.net> - 2012-03-13 11:41 +0100
Re: things i would ban from clc gwowen <gwowen@gmail.com> - 2012-03-13 06:06 -0700
Re: things i would ban from clc jacob navia <jacob@spamsink.net> - 2012-03-13 15:06 +0100
Re: things i would ban from clc ImpalerCore <jadill33@gmail.com> - 2012-03-13 07:46 -0700
Re: things i would ban from clc jacob navia <jacob@spamsink.net> - 2012-03-13 19:08 +0100
Re: things i would ban from clc Ben Bacarisse <ben.usenet@bsb.me.uk> - 2012-03-13 13:20 +0000
Re: things i would ban from clc Jens Gustedt <jens.gustedt@loria.fr> - 2012-03-13 20:41 +0100
Re: things i would ban from clc Kaz Kylheku <kaz@kylheku.com> - 2012-03-13 19:34 +0000
Re: things i would ban from clc Don Y <this@isnotme.com> - 2012-03-13 16:14 -0700
Re: things i would ban from clc Kaz Kylheku <kaz@kylheku.com> - 2012-03-13 23:28 +0000
Re: things i would ban from clc Don Y <this@isnotme.com> - 2012-03-13 21:18 -0700
Re: things i would ban from clc Ian Collins <ian-news@hotmail.com> - 2012-03-13 20:19 +1300
Re: things i would ban from clc Don Y <this@isnotme.com> - 2012-03-13 01:09 -0700
Re: things i would ban from clc Ian Collins <ian-news@hotmail.com> - 2012-03-13 21:32 +1300
Re: things i would ban from clc nick_keighley_nospam@hotmail.com - 2012-03-13 01:52 -0700
Re: things i would ban from clc "io_x" <a@b.c.invalid> - 2012-03-13 11:31 +0100
Re: things i would ban from clc nick_keighley_nospam@hotmail.com - 2012-03-14 01:18 -0700
Re: things i would ban from clc Don Y <this@isnotme.com> - 2012-03-14 12:09 -0700
Re: things i would ban from clc ArifulHossain tuhin <etothepowerpi@gmail.com> - 2012-03-14 13:01 -0700
csiph-web