Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #18560 > unrolled thread
| Started by | jgk@panix.com (Joe keane) |
|---|---|
| First post | 2012-03-11 23:05 +0000 |
| Last post | 2012-03-14 13:01 -0700 |
| Articles | 20 on this page of 87 — 22 participants |
Back to article view | Back to comp.lang.c
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
Page 3 of 5 — ← Prev page 1 2 [3] 4 5 Next page →
| From | Tim Rentsch <txr@alumni.caltech.edu> |
|---|---|
| Date | 2012-03-18 17:05 -0700 |
| Message-ID | <kfny5qxjvzf.fsf@x-alumni2.alumni.caltech.edu> |
| In reply to | #18811 |
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.
[toc] | [prev] | [next] | [standalone]
| From | Don Y <this@isnotme.com> |
|---|---|
| Date | 2012-03-23 11:59 -0700 |
| Message-ID | <jkih73$8er$1@speranza.aioe.org> |
| In reply to | #18853 |
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.
[toc] | [prev] | [next] | [standalone]
| From | Robert Wessel <robertwessel2@yahoo.com> |
|---|---|
| Date | 2012-03-23 17:02 -0500 |
| Message-ID | <q0spm79b046c3cp6uup41aaepsd2av3s6d@4ax.com> |
| In reply to | #18964 |
On Fri, 23 Mar 2012 11:59:50 -0700, Don Y <this@isnotme.com> wrote:
>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.
No, you're missing the point. C, as defined by the standard (at least
up to C11 with threading support), does *not* define a language that
can be reliably combined with a threading library, and expected to
produce *any* defined, or even consistent, results.
Threading-with-a-library works *only* if the implementation makes a
number of additional promises about the behavior of the program,
promises that are *not* part of the standard (again excepting C11 with
__STDC_NO_THREADS__ undefined).
Now threading obviously works with C in many cases, but that's just
because the compiler writers have, either by choice or accident,
implemented the required semantics that will make threading work
(consider the word tearing issues mentioned in the paper). It's not
something you can generically expect of C implementations.
The performance issues are separate. As are issues of programmers
managing to get threading correct.
[toc] | [prev] | [next] | [standalone]
| From | Don Y <this@isnotme.com> |
|---|---|
| Date | 2012-03-23 16:51 -0700 |
| Message-ID | <jkj29s$ij5$1@speranza.aioe.org> |
| In reply to | #18972 |
Hi Robert,
On 3/23/2012 3:02 PM, Robert Wessel wrote:
> No, you're missing the point. C, as defined by the standard (at least
> up to C11 with threading support), does *not* define a language that
> can be reliably combined with a threading library, and expected to
> produce *any* defined, or even consistent, results.
>
> Threading-with-a-library works *only* if the implementation makes a
> number of additional promises about the behavior of the program,
> promises that are *not* part of the standard (again excepting C11 with
> __STDC_NO_THREADS__ undefined).
>
> Now threading obviously works with C in many cases, but that's just
> because the compiler writers have, either by choice or accident,
> implemented the required semantics that will make threading work
> (consider the word tearing issues mentioned in the paper). It's not
> something you can generically expect of C implementations.
So, what *specific* language in the specification (pre-2011)
gives the compiler writer latitude to make the following
"misbehave" (pseudo-code):
...
x = y = 0
spawn(A)
spawn(B)
...
begin_atom()
printf("%d %d", x, y)
end_atom()
...
A()
{
...
begin_atom()
x=1
y=2
end_atom()
...
}
B()
{
...
begin_atom()
x=3
y=4
end_atom()
...
}
I.e., anything other than the output of "0 0", "1 2" or "3 4"
would be considered "misbehaving".
And, specifically, why *can't* {begin,end}_atom() provide
the (obvious) functionality?
[OK, language lawyers... strut your stuff! :> ]
> The performance issues are separate. As are issues of programmers
> managing to get threading correct.
[toc] | [prev] | [next] | [standalone]
| From | "io_x" <a@b.c.invalid> |
|---|---|
| Date | 2012-03-24 07:16 +0100 |
| Message-ID | <4f6d6628$0$1383$4fafbaef@reader1.news.tin.it> |
| In reply to | #18981 |
"Don Y" <this@isnotme.com> ha scritto nel messaggio
news:jkj29s$ij5$1@speranza.aioe.org...
> Hi Robert,
> So, what *specific* language in the specification (pre-2011)
> gives the compiler writer latitude to make the following
> "misbehave" (pseudo-code):
>
> ...
> x = y = 0
> spawn(A)
> spawn(B)
> ...
> begin_atom()
> printf("%d %d", x, y)
> end_atom()
> ...
>
>
>
> A()
> {
> ...
> begin_atom()
> x=1
> y=2
> end_atom()
> ...
> }
>
> B()
> {
> ...
> begin_atom()
> x=3
> y=4
> end_atom()
> ...
> }
what about...?
v=0
x = y = 0
spawn(A)
spawn(B)
...
begin_atom(&v)
begin_atom(stdout)
// A() and B() have not use stdout, right?
// otherwise would be deadlock right?
printf("%d %d", x, y)
end_atom(stdout)
end_atom(&v)
...
A()
{
...
begin_atom(&v)
x=1
y=2
end_atom(&v)
...
}
B()
{
...
begin_atom(&v)
x=3
y=4
end_atom(&v)
...
}
> I.e., anything other than the output of "0 0", "1 2" or "3 4"
> would be considered "misbehaving".
>
> And, specifically, why *can't* {begin,end}_atom() provide
> the (obvious) functionality?
i use the variable v
because in a program can be 100000 of code as that, and there is
need some memory space for make OS manage all queues for each
"common to threads space memory struct"...
or my mental picture is wrong?
Buon Giorno
> [OK, language lawyers... strut your stuff! :> ]
>
>> The performance issues are separate. As are issues of programmers
>> managing to get threading correct.
>
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <txr@alumni.caltech.edu> |
|---|---|
| Date | 2012-03-27 11:26 -0700 |
| Message-ID | <kfniphpj3x4.fsf@x-alumni2.alumni.caltech.edu> |
| In reply to | #18964 |
Don Y <this@isnotme.com> writes: > [snip] I echo the comments of Robert Wessel, whose response matches my perception. Beyond that, your reply seems largely nonresponsive and simply repetitive of earlier comments. Usually I think there is not much value in trying to respond to someone who is not being responsive. May I suggest that you put less effort into arguing, and more into reading and listening carefully?
[toc] | [prev] | [next] | [standalone]
| From | Kaz Kylheku <kaz@kylheku.com> |
|---|---|
| Date | 2012-03-23 19:43 +0000 |
| Message-ID | <20120323121849.635@kylheku.com> |
| In reply to | #18853 |
On 2012-03-19, Tim Rentsch <txr@alumni.caltech.edu> wrote: > Don Y <this@isnotme.com> writes: >> "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. A multi-threading API in which a thread cannot pass a pointer to automatic storage into some module, such that this module can then execute code on another thread which accesses that memory, is about as useful as tits on a bull. It means that you cannot do anything which resembles client-server RPC interaction between threads, without marshaling or copying the arguments going back and forth, which is a nonstarter, because one of the aims of threads is
[toc] | [prev] | [next] | [standalone]
| From | Rui Maciel <rui.maciel@gmail.com> |
|---|---|
| Date | 2012-03-23 19:45 +0000 |
| Message-ID | <jkijt5$f1r$1@speranza.aioe.org> |
| In reply to | #18965 |
Kaz Kylheku wrote: > because one of the aims of threads is Hang on tight. The rest of the post will appear once the thread finishes marshalling. Rui Maciel
[toc] | [prev] | [next] | [standalone]
| From | Jens Gustedt <jens.gustedt@loria.fr> |
|---|---|
| Date | 2012-03-23 23:49 +0100 |
| Message-ID | <4F6CFDF6.1020101@loria.fr> |
| In reply to | #18965 |
Am 03/23/2012 08:43 PM, schrieb Kaz Kylheku: > A multi-threading API in which a thread cannot pass a pointer to automatic > storage into some module, such that this module can then execute code on > another thread which accesses that memory, is about as useful as > tits on a bull. Yes, it is probably quite useless. On the other hand C11 says in 6.2.4 p 5 "The result of attempting to indirectly access an object with automatic storage duration from a thread other than the one with which the object is associated is implementation-defined." So an implementation of C11 may not allow this, as long as it documents its behavior properly. Jens
[toc] | [prev] | [next] | [standalone]
| From | Ian Collins <ian-news@hotmail.com> |
|---|---|
| Date | 2012-03-24 11:54 +1300 |
| Message-ID | <9t4d9pF3fiU4@mid.individual.net> |
| In reply to | #18976 |
On 03/24/12 11:49 AM, Jens Gustedt wrote: > Am 03/23/2012 08:43 PM, schrieb Kaz Kylheku: > >> A multi-threading API in which a thread cannot pass a pointer to automatic >> storage into some module, such that this module can then execute code on >> another thread which accesses that memory, is about as useful as >> tits on a bull. > > Yes, it is probably quite useless. On the other hand C11 says in 6.2.4 > p 5 > > "The result of attempting to indirectly access an object with > automatic storage duration from a thread other than the one with which > the object is associated is implementation-defined." > > So an implementation of C11 may not allow this, as long as it > documents its behavior properly. Sometimes I think the standard allows implementations too much latitude! I'm not aware of any threading implementation that doesn't use a shared address space. The use of a shared address space is often used as one of the conditions that differentiate between a threading and a process model. -- Ian Collins
[toc] | [prev] | [next] | [standalone]
| From | Jens Gustedt <jens.gustedt@loria.fr> |
|---|---|
| Date | 2012-03-24 09:26 +0100 |
| Message-ID | <4F6D8537.4050709@loria.fr> |
| In reply to | #18978 |
Am 03/23/2012 11:54 PM, schrieb Ian Collins: >> Yes, it is probably quite useless. On the other hand C11 says in 6.2.4 >> p 5 >> >> "The result of attempting to indirectly access an object with >> automatic storage duration from a thread other than the one with which >> the object is associated is implementation-defined." >> >> So an implementation of C11 may not allow this, as long as it >> documents its behavior properly. > > Sometimes I think the standard allows implementations too much latitude! usually they have the simple reason that there is some implementation that they want to cover > I'm not aware of any threading implementation that doesn't use a shared > address space. The use of a shared address space is often used as one > of the conditions that differentiate between a threading and a process > model. No, no, that is not what it says. Statically allocated and malloc'ed objects *must* work. It is just that an implementation might forbit a thread to peek into the "local variables" of another thread. I could imagine that this can be used on special hardware with per cpu memory. Think of implementing a thread model on a graphics card, for example. But I agree that this is nothing I'd like to program :) Jens
[toc] | [prev] | [next] | [standalone]
| From | gwowen <gwowen@gmail.com> |
|---|---|
| Date | 2012-03-26 07:31 -0700 |
| Message-ID | <3318fcaf-af60-4a94-90c9-870e092aab4a@w32g2000vbt.googlegroups.com> |
| In reply to | #18978 |
On Mar 23, 11:54 pm, Ian Collins <ian-n...@hotmail.com> wrote: > Sometimes I think the standard allows implementations too much latitude! > I'm not aware of any threading implementation that doesn't use a > shared address space. The use of a shared address space is often used > as one of the conditions that differentiate between a threading and a > process model. But one could imagine a distributed system where heap and static allocations refer to some centralised datastore (possibly locally cached, with some higher-level central constraints to maintain consistency).[0] "Threads" are then local processes and sharable- pointers are opaque references to the central store, and the "memory space" spanned by these references is quite distinct from those used by process-local variables. It's a little far fetched, but I'd imagine the standard writers had something in mind when they made it implementation defined (as opposed to undefined). [0] Please don't make me say "cloud" :)
[toc] | [prev] | [next] | [standalone]
| From | Kaz Kylheku <kaz@kylheku.com> |
|---|---|
| Date | 2012-03-24 05:45 +0000 |
| Message-ID | <20120323223911.490@kylheku.com> |
| In reply to | #18976 |
On 2012-03-23, Jens Gustedt <jens.gustedt@loria.fr> wrote: > Am 03/23/2012 08:43 PM, schrieb Kaz Kylheku: > >> A multi-threading API in which a thread cannot pass a pointer to automatic >> storage into some module, such that this module can then execute code on >> another thread which accesses that memory, is about as useful as >> tits on a bull. > > Yes, it is probably quite useless. On the other hand C11 says in 6.2.4 > p 5 > > "The result of attempting to indirectly access an object with > automatic storage duration from a thread other than the one with which > the object is associated is implementation-defined." This kind of waffling is pointless word semantics. Regardless of whether you require this, or allow implementations to duck out of it, there will be the pretty much exactly the same implementations in the world with the same capabilities. It's just a question of whether they are marked as nonconforming on this account, or conforming but with a reduced functionality. To someone coding in the proverbial trenches, it makes no difference. Morally speaking, implementations that break stuff like this shuld be deemed nonconforming, in a kind of "hall of shame". Standards should be bold and just require stuff to work, and not waste words on waffling.
[toc] | [prev] | [next] | [standalone]
| From | Jens Gustedt <jens.gustedt@loria.fr> |
|---|---|
| Date | 2012-03-24 09:31 +0100 |
| Message-ID | <4F6D8679.5040606@loria.fr> |
| In reply to | #18986 |
Am 03/24/2012 06:45 AM, schrieb Kaz Kylheku: > On 2012-03-23, Jens Gustedt <jens.gustedt@loria.fr> wrote: >> Am 03/23/2012 08:43 PM, schrieb Kaz Kylheku: >> >>> A multi-threading API in which a thread cannot pass a pointer to automatic >>> storage into some module, such that this module can then execute code on >>> another thread which accesses that memory, is about as useful as >>> tits on a bull. >> >> Yes, it is probably quite useless. On the other hand C11 says in 6.2.4 >> p 5 >> >> "The result of attempting to indirectly access an object with >> automatic storage duration from a thread other than the one with which >> the object is associated is implementation-defined." > > This kind of waffling is pointless word semantics. Regardless of whether you > require this, or allow implementations to duck out of it, there will be the > pretty much exactly the same implementations in the world with the same > capabilities. > > It's just a question of whether they are marked as nonconforming > on this account, or conforming but with a reduced functionality. > > To someone coding in the proverbial trenches, it makes no difference. > > Morally speaking, implementations that break stuff like this shuld be deemed > nonconforming, in a kind of "hall of shame". > > Standards should be bold and just require stuff to work, and not waste words on > waffling. You are ranting a bit quickly, I find. Such a thing partially covers existing practice for programming e.g on GPUs, where you have something like global memory that all PE can access, statically identified of some sort or malloced, and local memory that is restricted to PE and thus to the thread. I am personally not a great fan of CUDA but if one day they could map the new thread model on this, this would probably a big progress. Jens
[toc] | [prev] | [next] | [standalone]
| From | James Kuyper <jameskuyper@verizon.net> |
|---|---|
| Date | 2012-03-13 14:34 -0400 |
| Message-ID | <4F5F9348.5010809@verizon.net> |
| In reply to | #18684 |
On 03/13/2012 01:55 PM, Don Y wrote: > Hi Keith, > > On 3/13/2012 5:59 AM, Keith Thompson wrote: ... >> 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. It's not just another standard library. The specifications for the language itself required numerous modifications in order for it to be feasible to define the behavior of that library in the way it has been defined. See section 5.1.2.4 "Multi-threaded executions and data races", and section 6.7.2.4 "Atomic type specifiers". There's new pre-defined identifiers __SDTC_NO_ATOMICS__ and __STDC_NO_THREADS__. There's new concepts like "thread storage duration", and new keywords like _Thread_local. Search sections 1-6 for words like "atomic", or "thread", or "sequenced" to see further examples of what I'm referring to.
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <txr@alumni.caltech.edu> |
|---|---|
| Date | 2012-03-13 16:18 -0700 |
| Message-ID | <kfn62e8m6n3.fsf@x-alumni2.alumni.caltech.edu> |
| In reply to | #18684 |
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. [snip re: Limbo] 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.
[toc] | [prev] | [next] | [standalone]
| From | "io_x" <a@b.c.invalid> |
|---|---|
| Date | 2012-03-14 08:18 +0100 |
| Message-ID | <4f60454f$0$1385$4fafbaef@reader2.news.tin.it> |
| In reply to | #18731 |
"Tim Rentsch" <txr@alumni.caltech.edu> ha scritto nel messaggio
news:kfn62e8m6n3.fsf@x-alumni2.alumni.caltech.edu...
> 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. [snip re: Limbo]
>
> 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);
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <txr@alumni.caltech.edu> |
|---|---|
| Date | 2012-03-14 14:06 -0700 |
| Message-ID | <kfnsjhalwow.fsf@x-alumni2.alumni.caltech.edu> |
| In reply to | #18748 |
"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
[toc] | [prev] | [next] | [standalone]
| From | Jorgen Grahn <grahn+nntp@snipabacken.se> |
|---|---|
| Date | 2012-03-15 15:22 +0000 |
| Message-ID | <slrnjm42ae.1ls.grahn+nntp@frailea.sa.invalid> |
| In reply to | #18652 |
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 .
[toc] | [prev] | [next] | [standalone]
| From | Don Y <this@isnotme.com> |
|---|---|
| Date | 2012-03-15 12:26 -0700 |
| Message-ID | <jjtfou$61e$1@speranza.aioe.org> |
| In reply to | #18802 |
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...
[toc] | [prev] | [next] | [standalone]
Page 3 of 5 — ← Prev page 1 2 [3] 4 5 Next page →
Back to top | Article view | comp.lang.c
csiph-web