On 2021-07-19, Stefan Monnier wrote:
>> This is the reason that when you need instant threads, you set up a
>> thread pool of dormant threads instead of spawning a new OS thread
>> every time you need one. I personally consider that an ugly work-around
>> for inefficient thread creation.
>
> Part of the problem is linked to the precise meaning of "thread" (as in
> whether or not you care about all the different features offered for
> threads by the OS) and the devil in the details.

Yes, and short of language support for "thin" threads (e.g. without
proper OS support) most solutions are based on full OS threads.

>
> Also "instant threads" is still a lie for thread created from a thread
> pool of dormant threads, so it would be valuable to have benchmark
> numbers to see whether those are closer to "0 cycles" or to "1000
> cycle".

True. Starting up a thread usually requires things like passing a
function pointer in a message queue and sending a message.

/Marcus

On Monday, July 19, 2021 at 5:09:49 AM UTC-6, Thomas Koenig wrote:

> In the computer magazine I read this puzzle ("Chip"), it was
> actually 7,47 DM. And the issue must have been around October or
> November of that year.

There were issues of that magazine on the Internet Archive...

John Savard

On Tuesday, July 20, 2021 at 12:53:12 AM UTC-6, Quadibloc wrote:
> On Monday, July 19, 2021 at 5:09:49 AM UTC-6, Thomas Koenig wrote:

> > In the computer magazine I read this puzzle ("Chip"), it was
> > actually 7,47 DM. And the issue must have been around October or
> > November of that year.

> There were issues of that magazine on the Internet Archive...

Or so I thought. Actually, only the very first issue, plus some of their
CHIP Specials, including one on computerizing one's Marklin
model railroad, are there.

Plus, there is another computer magazine of the same name
which publishes in Hungary, Romania, and Russia... and yet
another one which is in English and in Malaysia.

John Savard

poniedziałek, 19 lipca 2021 o 14:35:40 UTC+2 Thomas Koenig napisał(a):
> That's a pretty good guess, going through three variables i <=
> j <= k and setting m = 7-i-j-k, while removing duplicates setting
> the bounds so that k <= m, gives around 2.9e6 iterations.

You are not serious...
def brahmagupta(c):
return (c-(c**2-4*c))/2,(c+(c**2-4*c))/2
brahmagupta(7.47) = (1.1893713939382278, 6.2806286060617715)
brahmagupta(6.2806286060617715) = (1.2480169133948371, 5.031983086605163)
brahmagupta(5.031983086605163)=(1.3764817684693538, 3.656171118366921)
"real" solution:
1.1893713939382278,1.2480169133948371,1.3764817684693538,3.656171118366921
starting point:
1.19+1.25+1.37+3.66=7.470000000000001
1.19*1.25*1.37*3.66 = 7.458622500000001
few manual iterations:
1.20*1.25*1.37*3.65=7.50075
1.19*1.25*1.38*3.65=7.492537499999998
1.18*1.25*1.39*3.65=7.483412499999998
1.17*1.25*1.40*3.65=7.473374999999999 - "upper bound"
1.16*1.25*1.41*3.65=7.462424999999999
1.17*1.24*1.41*3.65=7.466542199999999 - "lower bound"

pec...@gmail.com <peceed@gmail.com> schrieb:
> poniedziałek, 19 lipca 2021 o 14:35:40 UTC+2 Thomas Koenig napisał(a):
>> That's a pretty good guess, going through three variables i <=
>> j <= k and setting m = 7-i-j-k, while removing duplicates setting
>> the bounds so that k <= m, gives around 2.9e6 iterations.
>
> You are not serious...
> def brahmagupta(c):
> return (c-(c**2-4*c))/2,(c+(c**2-4*c))/2
> brahmagupta(7.47) = (1.1893713939382278, 6.2806286060617715)
> brahmagupta(6.2806286060617715) = (1.2480169133948371, 5.031983086605163)
> brahmagupta(5.031983086605163)=(1.3764817684693538, 3.656171118366921)
> "real" solution:
> 1.1893713939382278,1.2480169133948371,1.3764817684693538,3.656171118366921
> starting point:
> 1.19+1.25+1.37+3.66=7.470000000000001
> 1.19*1.25*1.37*3.66 = 7.458622500000001
> few manual iterations:
> 1.20*1.25*1.37*3.65=7.50075
> 1.19*1.25*1.38*3.65=7.492537499999998
> 1.18*1.25*1.39*3.65=7.483412499999998
> 1.17*1.25*1.40*3.65=7.473374999999999 - "upper bound"
> 1.16*1.25*1.41*3.65=7.462424999999999
> 1.17*1.24*1.41*3.65=7.466542199999999 - "lower bound"

I'm not sure what you calculated here.

However, as stated, this is a Diophantine equation (integer solutions
only), so approximate solutions are not valid.

Diophantine equations are generally much harder to solve than
equations that involve real numbers that can be solved approximately
using floating point values.

Thomas Koenig wrote:
> pec...@gmail.com <peceed@gmail.com> schrieb:
>> poniedziałek, 19 lipca 2021 o 14:35:40 UTC+2 Thomas Koenig napisał(a):
>>> That's a pretty good guess, going through three variables i <=
>>> j <= k and setting m = 7-i-j-k, while removing duplicates setting
>>> the bounds so that k <= m, gives around 2.9e6 iterations.
>>
>> You are not serious...
>> def brahmagupta(c):
>> return (c-(c**2-4*c))/2,(c+(c**2-4*c))/2
>> brahmagupta(7.47) = (1.1893713939382278, 6.2806286060617715)
>> brahmagupta(6.2806286060617715) = (1.2480169133948371, 5.031983086605163)
>> brahmagupta(5.031983086605163)=(1.3764817684693538, 3.656171118366921)
>> "real" solution:
>> 1.1893713939382278,1.2480169133948371,1.3764817684693538,3.656171118366921
>> starting point:
>> 1.19+1.25+1.37+3.66=7.470000000000001
>> 1.19*1.25*1.37*3.66 = 7.458622500000001
>> few manual iterations:
>> 1.20*1.25*1.37*3.65=7.50075
>> 1.19*1.25*1.38*3.65=7.492537499999998
>> 1.18*1.25*1.39*3.65=7.483412499999998
>> 1.17*1.25*1.40*3.65=7.473374999999999 - "upper bound"
>> 1.16*1.25*1.41*3.65=7.462424999999999
>> 1.17*1.24*1.41*3.65=7.466542199999999 - "lower bound"
>
> I'm not sure what you calculated here.
>
> However, as stated, this is a Diophantine equation (integer solutions
> only), so approximate solutions are not valid.
>
> Diophantine equations are generally much harder to solve than
> equations that involve real numbers that can be solved approximately
> using floating point values.
>
I broke down and wrote a perl solver for this question:

Even with perl's slow interpreter, and no attempt to extract prime
factors from 747000000, just a brute force scan, it took about 0.2
seconds to find the solutions for either 7.47 or 7.11 as the total sum.
(Verifying that they were in fact unique took another 40 ms.)

C(++) would almost certainly run this at least an order of magnitude
faster, but using the prime roots as the starting point, noting that
there is a single large factor (of 747/9=83), and then use that as the
first term would help even more:
....
Yes indeed!

Starting the search with n*0.83 as one of the item prices reduced the
search time from 200ms to less than 9, and full verification took just
11 ms.

Terje

--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

Terje Mathisen <terje.mathisen@tmsw.no> schrieb:

> Even with perl's slow interpreter, and no attempt to extract prime
> factors from 747000000, just a brute force scan, it took about 0.2
> seconds to find the solutions for either 7.47 or 7.11 as the total sum.
> (Verifying that they were in fact unique took another 40 ms.)

Which shows that an interpreter on a (I assume) relatively modern
machine 2021 is _much_ faster than an interpreter on a machine
introduced in 1982, whose CPU ran at ~ 0.3% of the clock speed of
today's machine, which had an 8-bit processor doing floating point
on a 40-bit format with a 32-bit mantissa without even instructions
for an 8-bit integer multiply.

It was _all_ shift and add for multiplication.

>
> C(++) would almost certainly run this at least an order of magnitude
> faster, but using the prime roots as the starting point, noting that
> there is a single large factor (of 747/9=83), and then use that as the
> first term would help even more:
> ...
> Yes indeed!

Ah, I don't think we noticed that at the time. Good catch!

> Starting the search with n*0.83 as one of the item prices reduced the
> search time from 200ms to less than 9, and full verification took just
> 11 ms.

There is actually a bit more to the story. It was one of the
first days after I had started studying, which is why I remember
the approximate date so well. The people I shared a flat with had
looked at the problem for a short time without even hitting on the
rather obvious fact that, for a+b+c+d=s, you only need three loops.

We ran a few benchmarks and concluded that a run would take a
few months on the C-64, and gave up for a time.

One of us, a first-semester computer science studend, then left.
The rest of us looked at the problem again, noticed d=s-a-b-c, and
used a few more simplifications, which brought down the calculation
time to around half an hour.

One of us (not me) then had an idea. He sat down and wrote down
random formulas from "Bronstein"The formulas looked impressive,
but had absolutely no bearing on the problem. When the C.S. student
returned late in the evening, we gave him the sheets of paper
and told him this was the analytical soluttion. The unsuspecting
C.S. student believed us for a few weeks, because he still thought
that a calculation would have taken months, and was quite impressed.

George Neuner <gneuner2@comcast.net> writes:
>On Sun, 18 Jul 2021 15:55:24 GMT, anton@mips.complang.tuwien.ac.at
>(Anton Ertl) wrote:
>
>>George Neuner <gneuner2@comcast.net> writes:
>>
>>>The problem - at least with current hardware - is that programmers are
>>>much better at identifying what CAN be done in parallel than what
>>>SHOULD be done in parallel.
>>
>>You make it sound as if that's a problem with the programmers, not
>>with the hardware. But it's fundamental to programming (at least in
>>areas affected by the software crisis, i.e., not supercomputers), so
>>it has to be solved at the system level (i.e., hardware, compiler,
>>etc.).
>
>It /IS/ a problem with the programmers. The average "developer" now
>has no CS, engineering, or (advanced) mathematics education, and their
>programming skills are pitiful - only slightly above "script kiddie".
>This is an unfortunate fact of life that I think too often is lost on
>some denizens of this group.

One could have an interesting discussion about that, but that's
besides the point wrt the parallelization problem. Even if the
developers have all the education one could wish for, if they have to
produce a maintainable program for a big problem (resulting in a big
program) with the minimal development effort, they will divide the
problem into subproblems and divide the program into parts for dealing
with the subproblems etc. But parallelization with the current cost
structure has to be done for the whole program and cannot be
subdivided in the same way.

>Given the ability to create "parallel" tasks, an /average/ programmer
>is very likely to naively create large numbers of new tasks regardless
>of resources being available to actually execute them.

Yes, if you tell them to create parallel tasks. And good programmers
will do so, too, unless you tell them that efficient parallelization
is more important than maintainability.

>Which maybe is fine if the number of tasks (relatively) is small, or
>if many of them are I/O bound and the use is for /concurrency/. But
>most programmers do not understand the difference between "parallel"
>and "concurrent", and too many don't understand why spawning large
>numbers of tasks can slow down the program.

Sure. That's the way to write parallel programs that is in line with
the divide-and-conquer approach we have established for writing
programs for big problems. So if it slows down programs, the solution
is not to tell the programmers not to do that, but to make systems
that run such programs efficiently. E.g., have hardware where having
many more tasks than hardware threads does not slow down the program.
Or have a compiler and run-time system that combines the many tasks
written by the programmer into so few intermediate tasks that the
overheads of having more tasks than threads play little role. Or
both.

>>Why is it fundamental? Because we build maintainable software by
>>splitting it into mostly-independent parts. Deciding how much to
>>parallelize on current hardware needs a global view of the program,
>>which programmers usually do not have; and even when they have it,
>>their decisions will probably be outdated after a while of maintaining
>>the program.
>>
>>We have similar problems with explicitly managed fast memory, which is
>>why we don't see that in general-purpose computers; instead, we see
>>caches (a software-crisis-compatible variant of fast memory).
>
>We have similar problems with programmer managed dynamic allocation.
>All the modern languages use GC /because/ repeated studies have shown
>that average programmers largely are incapable of writing leak-proof
>code without it.

Good example. Garbage collection is a good solution to the dynamic
memory allocation problem, including for good programmers. Now we
need such a solution for the parallelization problem.

>>Yet another problem of this kind is fixed-point scaling. That's why
>>we have floating-point.
>
>And the same people who, in the past, would not have understood the
>issues of using fixed-point now don't understand the issues of using
>floating point.

Sure, FP has its pitfalls, but it's possible to write, say, a general
FP matrix multiplication subroutine (and the pitfalls of FP typically
don't play much role in that), while for fixed-point you would have to
write one with the right scaling for every application it is used in;
or maybe these days have a templated C++ library, and instantiate it
with the appropriate scalings for each use.

>>So what do we need of the system? Ideally having more parallel parts
>>than needed should not cause a slowdown. This has two aspects:
>>
>>1) Thread creation and destruction should be cheap.
>>
>>2) The harder part is memory locality: Sequential code often works
>>very well on caches because it has a lot of temporal and spatial
>>locality. If the code is split into more tasks than necessary, how do
>>we avoid losing locality and thus losing some of the benefits of
>>caching?
>
>Agreed! But this has little to do with any of my points.

But it has to do with the parallelization problem, and more realistic
solutions for it than perfect programmers with unlimited time on their
hands.

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <c17fcd89-f024-40e7-a594-88a85ac10d20o@googlegroups.com>

Anton Ertl [2021-07-20 16:54:54] wrote:
> programs for big problems. So if it slows down programs, the solution
> is not to tell the programmers not to do that, but to make systems
> that run such programs efficiently. E.g., have hardware where having

Indeed, I think the only viable "solution" is to ask the programmers to
write code in a way that exposes as much parallelism as possible, and
then have the compiler "auto-sequentialize" the code.

It should be a bit easier for the compiler: at least it's easy to
sequentialize correctly, so the main difficulty is to sequentialize in
a way that maximizes the performance.

Stefan

On 2021-07-20, Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
> George Neuner <gneuner2@comcast.net> writes:
>>On Sun, 18 Jul 2021 15:55:24 GMT, anton@mips.complang.tuwien.ac.at
>>(Anton Ertl) wrote:
>>
>>>George Neuner <gneuner2@comcast.net> writes:
>>>
>>>>The problem - at least with current hardware - is that programmers are
>>>>much better at identifying what CAN be done in parallel than what
>>>>SHOULD be done in parallel.
>>>
>>>You make it sound as if that's a problem with the programmers, not
>>>with the hardware. But it's fundamental to programming (at least in
>>>areas affected by the software crisis, i.e., not supercomputers), so
>>>it has to be solved at the system level (i.e., hardware, compiler,
>>>etc.).
>>
>>It /IS/ a problem with the programmers. The average "developer" now
>>has no CS, engineering, or (advanced) mathematics education, and their
>>programming skills are pitiful - only slightly above "script kiddie".
>>This is an unfortunate fact of life that I think too often is lost on
>>some denizens of this group.
>
> One could have an interesting discussion about that, but that's
> besides the point wrt the parallelization problem. Even if the
> developers have all the education one could wish for, if they have to
> produce a maintainable program for a big problem (resulting in a big
> program) with the minimal development effort, they will divide the
> problem into subproblems and divide the program into parts for dealing
> with the subproblems etc. But parallelization with the current cost
> structure has to be done for the whole program and cannot be
> subdivided in the same way.

Well almost all new languages have async/await mechanism which makes
concurrent programming trivial...
Swift got it in 5.5 which is still beta..

>
>>Given the ability to create "parallel" tasks, an /average/ programmer
>>is very likely to naively create large numbers of new tasks regardless
>>of resources being available to actually execute them.
>
> Yes, if you tell them to create parallel tasks. And good programmers
> will do so, too, unless you tell them that efficient parallelization
> is more important than maintainability.

Not issue any more...

>
>>Which maybe is fine if the number of tasks (relatively) is small, or
>>if many of them are I/O bound and the use is for /concurrency/. But
>>most programmers do not understand the difference between "parallel"
>>and "concurrent", and too many don't understand why spawning large
>>numbers of tasks can slow down the program.
>
> Sure. That's the way to write parallel programs that is in line with
> the divide-and-conquer approach we have established for writing
> programs for big problems. So if it slows down programs, the solution
> is not to tell the programmers not to do that, but to make systems
> that run such programs efficiently. E.g., have hardware where having
> many more tasks than hardware threads does not slow down the program.
> Or have a compiler and run-time system that combines the many tasks
> written by the programmer into so few intermediate tasks that the
> overheads of having more tasks than threads play little role. Or
> both.

Parallel and concurrent is same thing :P
Someone told me that depends on definition, but it is dim :P

>
>>>Why is it fundamental? Because we build maintainable software by
>>>splitting it into mostly-independent parts. Deciding how much to
>>>parallelize on current hardware needs a global view of the program,
>>>which programmers usually do not have; and even when they have it,
>>>their decisions will probably be outdated after a while of maintaining
>>>the program.
>>>
>>>We have similar problems with explicitly managed fast memory, which is
>>>why we don't see that in general-purpose computers; instead, we see
>>>caches (a software-crisis-compatible variant of fast memory).
>>
>>We have similar problems with programmer managed dynamic allocation.
>>All the modern languages use GC /because/ repeated studies have shown
>>that average programmers largely are incapable of writing leak-proof
>>code without it.
>
> Good example. Garbage collection is a good solution to the dynamic
> memory allocation problem, including for good programmers. Now we
> need such a solution for the parallelization problem.

C++, Rust , Swift all does not have GC...
They use RAII and reference counting (shared_ptr and such)

>
>>>Yet another problem of this kind is fixed-point scaling. That's why
>>>we have floating-point.
>>
>>And the same people who, in the past, would not have understood the
>>issues of using fixed-point now don't understand the issues of using
>>floating point.
>
> Sure, FP has its pitfalls, but it's possible to write, say, a general
> FP matrix multiplication subroutine (and the pitfalls of FP typically
> don't play much role in that), while for fixed-point you would have to
> write one with the right scaling for every application it is used in;
> or maybe these days have a templated C++ library, and instantiate it
> with the appropriate scalings for each use.
>
>>>So what do we need of the system? Ideally having more parallel parts
>>>than needed should not cause a slowdown. This has two aspects:
>>>
>>>1) Thread creation and destruction should be cheap.
>>>
>>>2) The harder part is memory locality: Sequential code often works
>>>very well on caches because it has a lot of temporal and spatial
>>>locality. If the code is split into more tasks than necessary, how do
>>>we avoid losing locality and thus losing some of the benefits of
>>>caching?
>>
>>Agreed! But this has little to do with any of my points.
>
> But it has to do with the parallelization problem, and more realistic
> solutions for it than perfect programmers with unlimited time on their
> hands.
Well, Rust and Swift mad efforts to make less bugs with concurrent tasks,
that is with shared state :P
Swift mad efforts to make less bugs with concurrent tasks,
that is with shared state :P

>
> - anton

--
bmaxa now listens Arguments by Robots in disguise from Robots in disguise

On 7/20/2021 9:54 AM, Anton Ertl wrote:
> George Neuner <gneuner2@comcast.net> writes:
>> On Sun, 18 Jul 2021 15:55:24 GMT, anton@mips.complang.tuwien.ac.at
>> (Anton Ertl) wrote:
>>
>>> George Neuner <gneuner2@comcast.net> writes:
>>>
>>>> The problem - at least with current hardware - is that programmers are
>>>> much better at identifying what CAN be done in parallel than what
>>>> SHOULD be done in parallel.
>>>
>>> You make it sound as if that's a problem with the programmers, not
>>> with the hardware. But it's fundamental to programming (at least in
>>> areas affected by the software crisis, i.e., not supercomputers), so
>>> it has to be solved at the system level (i.e., hardware, compiler,
>>> etc.).
>>
>> It /IS/ a problem with the programmers. The average "developer" now
>> has no CS, engineering, or (advanced) mathematics education, and their
>> programming skills are pitiful - only slightly above "script kiddie".
>> This is an unfortunate fact of life that I think too often is lost on
>> some denizens of this group.
>
> One could have an interesting discussion about that, but that's
> besides the point wrt the parallelization problem. Even if the
> developers have all the education one could wish for, if they have to
> produce a maintainable program for a big problem (resulting in a big
> program) with the minimal development effort, they will divide the
> problem into subproblems and divide the program into parts for dealing
> with the subproblems etc. But parallelization with the current cost
> structure has to be done for the whole program and cannot be
> subdivided in the same way.
>
>> Given the ability to create "parallel" tasks, an /average/ programmer
>> is very likely to naively create large numbers of new tasks regardless
>> of resources being available to actually execute them.
>
> Yes, if you tell them to create parallel tasks. And good programmers
> will do so, too, unless you tell them that efficient parallelization
> is more important than maintainability.
>
>> Which maybe is fine if the number of tasks (relatively) is small, or
>> if many of them are I/O bound and the use is for /concurrency/. But
>> most programmers do not understand the difference between "parallel"
>> and "concurrent", and too many don't understand why spawning large
>> numbers of tasks can slow down the program.
>
> Sure. That's the way to write parallel programs that is in line with
> the divide-and-conquer approach we have established for writing
> programs for big problems. So if it slows down programs, the solution
> is not to tell the programmers not to do that, but to make systems
> that run such programs efficiently. E.g., have hardware where having
> many more tasks than hardware threads does not slow down the program.
> Or have a compiler and run-time system that combines the many tasks
> written by the programmer into so few intermediate tasks that the
> overheads of having more tasks than threads play little role. Or
> both.
>
>>> Why is it fundamental? Because we build maintainable software by
>>> splitting it into mostly-independent parts. Deciding how much to
>>> parallelize on current hardware needs a global view of the program,
>>> which programmers usually do not have; and even when they have it,
>>> their decisions will probably be outdated after a while of maintaining
>>> the program.
>>>
>>> We have similar problems with explicitly managed fast memory, which is
>>> why we don't see that in general-purpose computers; instead, we see
>>> caches (a software-crisis-compatible variant of fast memory).
>>
>> We have similar problems with programmer managed dynamic allocation.
>> All the modern languages use GC /because/ repeated studies have shown
>> that average programmers largely are incapable of writing leak-proof
>> code without it.
>
> Good example. Garbage collection is a good solution to the dynamic
> memory allocation problem, including for good programmers. Now we
> need such a solution for the parallelization problem.
[...]

I remember way back when somebody was having a performance issue in a
GC'ed environment when the system was under a great deal of sustained
load. Memory would grow and grow, and the GC was spending a lot of time
trying to handle all of it. So, I suggested using distributed lock-free
node caches, it sped things up by orders of magnitude. However,
pushing/popping from the node cache is a form of manual memory
management. They did not like it because of that, but ended up using it
anyway. So, manual memory management can "help" a GC under a large
amount of stress.

On 2021-07-20, Chris M. Thomasson <chris.m.thomasson.1@gmail.com> wrote:
> On 7/20/2021 9:54 AM, Anton Ertl wrote:
>> George Neuner <gneuner2@comcast.net> writes:
>>> On Sun, 18 Jul 2021 15:55:24 GMT, anton@mips.complang.tuwien.ac.at
>>> (Anton Ertl) wrote:
>>>
>>>> George Neuner <gneuner2@comcast.net> writes:
>>>>
>>>>> The problem - at least with current hardware - is that programmers are
>>>>> much better at identifying what CAN be done in parallel than what
>>>>> SHOULD be done in parallel.
>>>>
>>>> You make it sound as if that's a problem with the programmers, not
>>>> with the hardware. But it's fundamental to programming (at least in
>>>> areas affected by the software crisis, i.e., not supercomputers), so
>>>> it has to be solved at the system level (i.e., hardware, compiler,
>>>> etc.).
>>>
>>> It /IS/ a problem with the programmers. The average "developer" now
>>> has no CS, engineering, or (advanced) mathematics education, and their
>>> programming skills are pitiful - only slightly above "script kiddie".
>>> This is an unfortunate fact of life that I think too often is lost on
>>> some denizens of this group.
>>
>> One could have an interesting discussion about that, but that's
>> besides the point wrt the parallelization problem. Even if the
>> developers have all the education one could wish for, if they have to
>> produce a maintainable program for a big problem (resulting in a big
>> program) with the minimal development effort, they will divide the
>> problem into subproblems and divide the program into parts for dealing
>> with the subproblems etc. But parallelization with the current cost
>> structure has to be done for the whole program and cannot be
>> subdivided in the same way.
>>
>>> Given the ability to create "parallel" tasks, an /average/ programmer
>>> is very likely to naively create large numbers of new tasks regardless
>>> of resources being available to actually execute them.
>>
>> Yes, if you tell them to create parallel tasks. And good programmers
>> will do so, too, unless you tell them that efficient parallelization
>> is more important than maintainability.
>>
>>> Which maybe is fine if the number of tasks (relatively) is small, or
>>> if many of them are I/O bound and the use is for /concurrency/. But
>>> most programmers do not understand the difference between "parallel"
>>> and "concurrent", and too many don't understand why spawning large
>>> numbers of tasks can slow down the program.
>>
>> Sure. That's the way to write parallel programs that is in line with
>> the divide-and-conquer approach we have established for writing
>> programs for big problems. So if it slows down programs, the solution
>> is not to tell the programmers not to do that, but to make systems
>> that run such programs efficiently. E.g., have hardware where having
>> many more tasks than hardware threads does not slow down the program.
>> Or have a compiler and run-time system that combines the many tasks
>> written by the programmer into so few intermediate tasks that the
>> overheads of having more tasks than threads play little role. Or
>> both.
>>
>>>> Why is it fundamental? Because we build maintainable software by
>>>> splitting it into mostly-independent parts. Deciding how much to
>>>> parallelize on current hardware needs a global view of the program,
>>>> which programmers usually do not have; and even when they have it,
>>>> their decisions will probably be outdated after a while of maintaining
>>>> the program.
>>>>
>>>> We have similar problems with explicitly managed fast memory, which is
>>>> why we don't see that in general-purpose computers; instead, we see
>>>> caches (a software-crisis-compatible variant of fast memory).
>>>
>>> We have similar problems with programmer managed dynamic allocation.
>>> All the modern languages use GC /because/ repeated studies have shown
>>> that average programmers largely are incapable of writing leak-proof
>>> code without it.
>>
>> Good example. Garbage collection is a good solution to the dynamic
>> memory allocation problem, including for good programmers. Now we
>> need such a solution for the parallelization problem.
> [...]
>
> I remember way back when somebody was having a performance issue in a
> GC'ed environment when the system was under a great deal of sustained
> load. Memory would grow and grow, and the GC was spending a lot of time
> trying to handle all of it. So, I suggested using distributed lock-free
> node caches, it sped things up by orders of magnitude. However,
> pushing/popping from the node cache is a form of manual memory
> management. They did not like it because of that, but ended up using it
> anyway. So, manual memory management can "help" a GC under a large
> amount of stress.
Rust had GC in early versions. They ditched in in favor of reference count
because of performance problems. Swift, which is derived from Rust,
never had GC :P
Simply put GC is hassle in concurrent loads...

--
bmaxa now listens Boys by Robots in disguise from Robots in disguise

On Tuesday, July 20, 2021 at 1:17:57 PM UTC-6, Branimir Maksimovic wrote:

> Parallel and concurrent is same thing :P
> Someone told me that depends on definition, but it is dim :P

"Concurrent" refers to tasks which _could_ be done in parallel, but becaue
you only have one serial processor available, it just does them one at a time,
switching back and forth between them.

So now the distinction is no longer dim, but glowing as brightly as the
noonday sun!

John Savard

On 7/20/2021 3:07 PM, Quadibloc wrote:
> On Tuesday, July 20, 2021 at 1:17:57 PM UTC-6, Branimir Maksimovic wrote:
>
>> Parallel and concurrent is same thing :P
>> Someone told me that depends on definition, but it is dim :P
>
> "Concurrent" refers to tasks which _could_ be done in parallel, but becaue
> you only have one serial processor available, it just does them one at a time,
> switching back and forth between them.
>
> So now the distinction is no longer dim, but glowing as brightly as the
> noonday sun!

Now, one "difference" can be that several parallel computations can
never possibly interfere with each other as they run at the same time.
Several concurrent computations might mean that they can interfere with
one other as they run at the same time.

On 2021-07-20, Quadibloc <jsavard@ecn.ab.ca> wrote:
> On Tuesday, July 20, 2021 at 1:17:57 PM UTC-6, Branimir Maksimovic wrote:
>
>> Parallel and concurrent is same thing :P
>> Someone told me that depends on definition, but it is dim :P
>
> "Concurrent" refers to tasks which _could_ be done in parallel, but becaue
> you only have one serial processor available, it just does them one at a time,
> switching back and forth between them.
>
> So now the distinction is no longer dim, but glowing as brightly as the
> noonday sun!

That's your defnition. Such tasks are in no way concurrent.
What you describing is coroutines that must yield for other
tasks to work :p

>
> John Savard

--
bmaxa now listens Woman In Disguise by Angelic Upstarts from The Independent Punk Singles Collection

On 2021-07-20, Chris M. Thomasson <chris.m.thomasson.1@gmail.com> wrote:
> On 7/20/2021 3:07 PM, Quadibloc wrote:
>> On Tuesday, July 20, 2021 at 1:17:57 PM UTC-6, Branimir Maksimovic wrote:
>>
>>> Parallel and concurrent is same thing :P
>>> Someone told me that depends on definition, but it is dim :P
>>
>> "Concurrent" refers to tasks which _could_ be done in parallel, but becaue
>> you only have one serial processor available, it just does them one at a time,
>> switching back and forth between them.
>>
>> So now the distinction is no longer dim, but glowing as brightly as the
>> noonday sun!
>
> Now, one "difference" can be that several parallel computations can
> never possibly interfere with each other as they run at the same time.
> Several concurrent computations might mean that they can interfere with
> one other as they run at the same time.
That is another definition, which is another interpretation. In reallity
no body made clear definition that will all follow :P
My attempt is this: Parallel execution can be done on several different
machines, like MPI, andr concurrent means on single computer. I think that
this was original definition and distinction.

--
bmaxa now listens Woman In Disguise by Angelic Upstarts from The Independent Punk Singles Collection

Quadibloc [2021-07-20 15:07:31] wrote:
> On Tuesday, July 20, 2021 at 1:17:57 PM UTC-6, Branimir Maksimovic wrote:
>> Parallel and concurrent is same thing :P
>> Someone told me that depends on definition, but it is dim :P
> "Concurrent" refers to tasks which _could_ be done in parallel, but
> becaue you only have one serial processor available, it just does them
> one at a time, switching back and forth between them.

That's definitely not my understanding of the term.

To me the difference between the two is that parallelism is concerned
with dividing a task into subtasks that can be performed concurrently so
as to reduce the latency of its execution. Concurrency OTOH starts with
concurrent tasks and is concerned with how to schedule and synchronize
them such that the result is correct and to obey various other
timing constraints like fairness.

Stefan

On 2021-07-20, Stefan Monnier <monnier@iro.umontreal.ca> wrote:
> Quadibloc [2021-07-20 15:07:31] wrote:
>> On Tuesday, July 20, 2021 at 1:17:57 PM UTC-6, Branimir Maksimovic wrote:
>>> Parallel and concurrent is same thing :P
>>> Someone told me that depends on definition, but it is dim :P
>> "Concurrent" refers to tasks which _could_ be done in parallel, but
>> becaue you only have one serial processor available, it just does them
>> one at a time, switching back and forth between them.
>
> That's definitely not my understanding of the term.
>
> To me the difference between the two is that parallelism is concerned
> with dividing a task into subtasks that can be performed concurrently so
> as to reduce the latency of its execution. Concurrency OTOH starts with
> concurrent tasks and is concerned with how to schedule and synchronize
> them such that the result is correct and to obey various other
> timing constraints like fairness.
>
>
> Stefan
Well parrallel computation (several computers), concurrent execution (single computer)

--
bmaxa now listens Solidarity by Angelic Upstarts from The Independent Punk Singles Collection

On 20 Jul 2021, Thomas Koenig wrote
(in article <sd62ts$19o$1@newsreader4.netcologne.de>):

> Diophantine equations are generally much harder to solve than
> equations that involve real numbers that can be solved approximately
> using floating point values.

It's worse than that, Jim ...
The roots of Diophantine equations are not computable
(in the same sense as the TM halting problem).

--
Bill Findlay

wtorek, 20 lipca 2021 o 10:53:19 UTC+2 Thomas Koenig napisał(a):

> I'm not sure what you calculated here.
The point is to have a good starting point.
> However, as stated, this is a Diophantine equation (integer solutions
> only), so approximate solutions are not valid.
> Diophantine equations are generally much harder to solve than
> equations that involve real numbers that can be solved approximately
> using floating point values.
It is not a Diophantine equation.
The numbers are decimals with fixed point arithmetic.
Numerical analysis guarantees that fixed point product can not be too far from the real one, so you can dramatically restrict the search space: approximately +-0.03 around every value but we need to consider all permutations of values (multiplication with rounding is not connective).

Branimir Maksimovic [2021-07-20 22:36:55] wrote:
> On 2021-07-20, Stefan Monnier <monnier@iro.umontreal.ca> wrote:
>> Quadibloc [2021-07-20 15:07:31] wrote:
>>> On Tuesday, July 20, 2021 at 1:17:57 PM UTC-6, Branimir Maksimovic wrote:
>>>> Parallel and concurrent is same thing :P
>>>> Someone told me that depends on definition, but it is dim :P
>>> "Concurrent" refers to tasks which _could_ be done in parallel, but
>>> becaue you only have one serial processor available, it just does them
>>> one at a time, switching back and forth between them.
>>
>> That's definitely not my understanding of the term.
>>
>> To me the difference between the two is that parallelism is concerned
>> with dividing a task into subtasks that can be performed concurrently so
>> as to reduce the latency of its execution. Concurrency OTOH starts with
>> concurrent tasks and is concerned with how to schedule and synchronize
>> them such that the result is correct and to obey various other
>> timing constraints like fairness.
> Well parrallel computation (several computers), concurrent execution
> (single computer)

I don't see where my description made you think concurrency was limited
to the "single computer" case. But of course, parallel computation is
generally a losing proposition if you only have a single compute element
(tho a "single computer" can contain several CPUs, and a single CPU can
also have several concurrent compute elements, e.g. via superscalar
execution, SIMD, you name it).

Stefan

On 2021-07-21, Stefan Monnier <monnier@iro.umontreal.ca> wrote:
> Branimir Maksimovic [2021-07-20 22:36:55] wrote:
>> On 2021-07-20, Stefan Monnier <monnier@iro.umontreal.ca> wrote:
>>> Quadibloc [2021-07-20 15:07:31] wrote:
>>>> On Tuesday, July 20, 2021 at 1:17:57 PM UTC-6, Branimir Maksimovic wrote:
>>>>> Parallel and concurrent is same thing :P
>>>>> Someone told me that depends on definition, but it is dim :P
>>>> "Concurrent" refers to tasks which _could_ be done in parallel, but
>>>> becaue you only have one serial processor available, it just does them
>>>> one at a time, switching back and forth between them.
>>>
>>> That's definitely not my understanding of the term.
>>>
>>> To me the difference between the two is that parallelism is concerned
>>> with dividing a task into subtasks that can be performed concurrently so
>>> as to reduce the latency of its execution. Concurrency OTOH starts with
>>> concurrent tasks and is concerned with how to schedule and synchronize
>>> them such that the result is correct and to obey various other
>>> timing constraints like fairness.
>> Well parrallel computation (several computers), concurrent execution
>> (single computer)
>
> I don't see where my description made you think concurrency was limited
> to the "single computer" case. But of course, parallel computation is
> generally a losing proposition if you only have a single compute element
> (tho a "single computer" can contain several CPUs, and a single CPU can
> also have several concurrent compute elements, e.g. via superscalar
> execution, SIMD, you name it).

That was original defitibition. Parallel was distributed computing via MPI eg,
while concurrent ment via threads on single computer.
Just sain' :P

i

>
>
> Stefan

--
bmaxa now listens MARTHA & THE MUFFINS - ECHO BEACH.ogg

On Tuesday, July 20, 2021 at 5:04:49 PM UTC-6, Bill Findlay wrote:
> On 20 Jul 2021, Thomas Koenig wrote
> (in article <sd62ts$19o$1...@newsreader4.netcologne.de>):
> > Diophantine equations are generally much harder to solve than
> > equations that involve real numbers that can be solved approximately
> > using floating point values.

> It's worse than that, Jim ...
> The roots of Diophantine equations are not computable
> (in the same sense as the TM halting problem).

But that only means that _some_ Diophantine equations can't be solved.

Many of them can still be solved, but with difficulty.

John Savard

On 2021-07-20 21:17, Branimir Maksimovic wrote:
> On 2021-07-20, Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
>> George Neuner <gneuner2@comcast.net> writes:
>>> On Sun, 18 Jul 2021 15:55:24 GMT, anton@mips.complang.tuwien.ac.at
>>> (Anton Ertl) wrote:
>>>

[snip]

>>>> We have similar problems with explicitly managed fast memory, which is
>>>> why we don't see that in general-purpose computers; instead, we see
>>>> caches (a software-crisis-compatible variant of fast memory).
>>>
>>> We have similar problems with programmer managed dynamic allocation.
>>> All the modern languages use GC /because/ repeated studies have shown
>>> that average programmers largely are incapable of writing leak-proof
>>> code without it.
>>
>> Good example. Garbage collection is a good solution to the dynamic
>> memory allocation problem, including for good programmers. Now we
>> need such a solution for the parallelization problem.
>
> C++, Rust , Swift all does not have GC...
> They use RAII and reference counting (shared_ptr and such)
>

I've never liked GC. I find that when languages try to hide things from
the programmer (e.g. when, how and what memory gets freed) it gets
harder for me to reason about the code and its behavior. I also believe
that it generally lures programmers into making poorer SW architecture.

RAII and reference counting are much more controlled methods with
predictable performance / overhead, so me likes.

It is /possible/ to write C++ code that never leaks, /if/ you use the
right constructs. Rust took this to the next level and simply excluded
the bad constructs from the language.

....but I agree that we need language support for parallelization. For
instance order-independent loops and similar constructs should be the
goto solution (no pun intended) rather than explicit iteration logic.
Likewise pure functions should be the norm (object orientation really
screwed that up). And of course good support for async primitives.

Then we can start designing hardware that can spawn lightweight threads
as easily as they can call subroutines. But as long as everyone uses
old-school C and stdc functionality there's little use in trying.

/Marcus

Quadibloc <jsavard@ecn.ab.ca> writes:
>On Tuesday, July 20, 2021 at 1:17:57 PM UTC-6, Branimir Maksimovic wrote:
>
>> Parallel and concurrent is same thing :P
>> Someone told me that depends on definition, but it is dim :P
>
>"Concurrent" refers to tasks which _could_ be done in parallel, but becaue
>you only have one serial processor available, it just does them one at a time,
>switching back and forth between them.

Reference needed.

en.wikipedia.org says:

|Concurrent computing is a form of computing in which several
|computations are executed concurrently-during overlapping time
|periods-instead of sequentially-with one completing before the next
|starts.

My impression is that "concurrent" is used when discussing concurrent
access to a data structure common between the tasks, and the
synchronization mechanisms for that, while "parallel" is used when
discussing parallel execution where such issues play no role or are
outside or at the fringes of the scope of the discussion.

So these are basically complementary concepts.

- anton
--
'Anyone trying for "industrial quality" ISA should avoid undefined behavior.'
Mitch Alsup, <c17fcd89-f024-40e7-a594-88a85ac10d20o@googlegroups.com>