Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #138704 > unrolled thread

Multithreading

Back to article view | Back to comp.lang.c

Contents

  Multithreading nobody@example.org (Scott) - 2018-12-16 21:48 +0000
    Re: Multithreading Joey Pabalinas <joeypabalinas@gmail.com> - 2018-12-16 17:11 -1000
    Re: Multithreading rbowman <bowman@montana.com> - 2018-12-16 21:00 -0700
    Re: Multithreading Jorgen Grahn <grahn+nntp@snipabacken.se> - 2018-12-17 22:19 +0000
      Re: Multithreading Joey Pabalinas <joeypabalinas@gmail.com> - 2018-12-17 12:45 -1000
      Re: Multithreading nobody@example.org (Scott) - 2018-12-19 19:48 +0000
        Re: Multithreading fir <profesor.fir@gmail.com> - 2018-12-19 11:58 -0800
        Re: Multithreading Jorgen Grahn <grahn+nntp@snipabacken.se> - 2018-12-19 23:17 +0000
          Re: Multithreading "Chris M. Thomasson" <invalid_chris_thomasson@invalid.invalid> - 2018-12-19 15:31 -0800
            Re: Multithreading "Chris M. Thomasson" <invalid_chris_thomasson@invalid.invalid> - 2018-12-19 15:34 -0800
          Re: Multithreading nobody@example.org (Scott) - 2018-12-22 10:43 +0000
            Re: Multithreading fir <profesor.fir@gmail.com> - 2018-12-22 03:41 -0800
              Re: Multithreading fir <profesor.fir@gmail.com> - 2018-12-22 03:46 -0800
            Re: Multithreading Thiago Adams <thiago.adams@gmail.com> - 2018-12-22 07:14 -0800
            Re: Multithreading rbowman <bowman@montana.com> - 2018-12-22 11:41 -0700
              Re: Multithreading "Chris M. Thomasson" <invalid_chris_thomasson@invalid.invalid> - 2018-12-22 16:09 -0800
            Re: Multithreading scott@slp53.sl.home (Scott Lurndal) - 2018-12-22 19:52 +0000
              Re: Multithreading "Chris M. Thomasson" <invalid_chris_thomasson@invalid.invalid> - 2018-12-22 16:10 -0800
              Re: Multithreading nobody@example.org (Scott) - 2018-12-23 23:11 +0000
                Re: Multithreading "Chris M. Thomasson" <invalid_chris_thomasson@invalid.invalid> - 2018-12-23 15:24 -0800
                  Re: Multithreading "Chris M. Thomasson" <invalid_chris_thomasson@invalid.invalid> - 2018-12-23 15:25 -0800
                  Re: Multithreading fir <profesor.fir@gmail.com> - 2018-12-24 02:05 -0800
                Re: Multithreading fir <profesor.fir@gmail.com> - 2018-12-24 02:08 -0800
    Re: Multithreading fir <profesor.fir@gmail.com> - 2018-12-18 07:18 -0800
      Re: Multithreading fir <profesor.fir@gmail.com> - 2018-12-18 07:51 -0800
        Re: Multithreading fir <profesor.fir@gmail.com> - 2018-12-19 09:24 -0800
          Re: Multithreading fir <profesor.fir@gmail.com> - 2018-12-19 09:55 -0800
            Re: Multithreading fir <profesor.fir@gmail.com> - 2018-12-19 11:02 -0800
              Re: Multithreading fir <profesor.fir@gmail.com> - 2018-12-19 11:16 -0800
                Re: Multithreading fir <profesor.fir@gmail.com> - 2018-12-19 11:25 -0800
            Re: Multithreading "Chris M. Thomasson" <invalid_chris_thomasson@invalid.invalid> - 2018-12-19 15:37 -0800
              Re: Multithreading fir <profesor.fir@gmail.com> - 2018-12-19 16:03 -0800
                Re: Multithreading fir <profesor.fir@gmail.com> - 2018-12-20 08:02 -0800

Page 1 of 2  [1] 2  Next page →

#138704 — Multithreading

Well, not specifically a C matter, but as I've made a project of
converting an older program to leverage modern multi-core processors,
it just happens to be in C and I just happen to have opted for
pthreads since that works on all the platforms I use.

What I'd like to ask for are recommendations on resources for learning
about the principles and pitfalls of threaded programming, in a
general way, not tied to any specific implementation. I'm muddling my
way through this exercise, but I have this feeling that I'm taking a
Sunday stroll through a live minefield and just haven't managed to
walk into anything really interesting yet.

As always, thanks very much for your help.

[toc] | [next] | [standalone]

#138707

[Multipart message — attachments visible in raw view] — view raw

On Sun, Dec 16, 2018 at 09:48:48PM +0000, Scott wrote:
> Well, not specifically a C matter, but as I've made a project of
> converting an older program to leverage modern multi-core processors,
> it just happens to be in C and I just happen to have opted for
> pthreads since that works on all the platforms I use.
> 
> What I'd like to ask for are recommendations on resources for learning
> about the principles and pitfalls of threaded programming, in a
> general way, not tied to any specific implementation. I'm muddling my
> way through this exercise, but I have this feeling that I'm taking a
> Sunday stroll through a live minefield and just haven't managed to
> walk into anything really interesting yet.
> 
> As always, thanks very much for your help.

The gold standard for beginners is probably the Butenhof book [1].

Very friendly even if you've never heard of threads at all before, and
even if you aren't programming on an OS with POSIX threads it is still a
great introduction to the major concepts needed for concurrent programming
in my opinion.

[1] https://www.amazon.com/Programming-POSIX-Threads-David-Butenhof/dp/0201633922

-- 
Cheers,
Joey Pabalinas

[toc] | [prev] | [next] | [standalone]

#138710

On 12/16/2018 02:48 PM, Scott wrote:
> What I'd like to ask for are recommendations on resources for learning
> about the principles and pitfalls of threaded programming, in a
> general way, not tied to any specific implementation. I'm muddling my
> way through this exercise, but I have this feeling that I'm taking a
> Sunday stroll through a live minefield and just haven't managed to
> walk into anything really interesting yet.

Oh, there are definitely mines...

https://www.thegeekstuff.com/2012/05/c-mutex-examples/?refcom

That's one of the first pages I hit. There may be better examples but it 
does discuss one of the major minefields. Logically threads can simplify 
the code. For example, you can thread off something to read from a 
socket. It can block, no big deal, so you don't have to go to a 
non-blocking socket, select statements, and all that good stuff to keep 
the ball rolling.

Where it gets tricky is when it has read data from a socket and now has 
to pass it to another thread. Lets say you want to insert it into a 
linked list to be consumed by the other thread. The other thread is 
blissfully unaware of the socket reader and is happily processing the 
list and doing something with the data. Somebody has to say 'hey, I'm 
modifying the list' with the other thread waiting for its turn.

You need to watch out for deadlocks or both threads wind up politely 
waiting on each other.

It can bite you at odd moments. I'm old school and like to salt the code 
with fprintf's to a log file while I developing so I can construct a 
narrative of what's supposed to be happening. Even that needs to be set 
up with a mutex so the threads aren't simultaneously trying to write to 
the same log.

It's really not that complicated and you just need to think about where 
each thread will interact with a common object and keep them playing 
nicely together.

[toc] | [prev] | [next] | [standalone]

#138720

On Sun, 2018-12-16, Scott wrote:
> Well, not specifically a C matter, but as I've made a project of
> converting an older program to leverage modern multi-core processors,
> it just happens to be in C and I just happen to have opted for
> pthreads since that works on all the platforms I use.
>
> What I'd like to ask for are recommendations on resources for learning
> about the principles and pitfalls of threaded programming, in a
> general way, not tied to any specific implementation. I'm muddling my
> way through this exercise, but I have this feeling that I'm taking a
> Sunday stroll through a live minefield and just haven't managed to
> walk into anything really interesting yet.
>
> As always, thanks very much for your help.

In what way would this program benefit from being threaded?

The main thing I've learned about threading is to avoid it if
possible.  Or, to know why you're using it.

Sorry if that sounded negative.  Put differently, if you can describe
the task and people can help you with the high-level threading design
for that particular task, that's better than any pthreads-specific
help.

/Jorgen

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

[toc] | [prev] | [next] | [standalone]

#138721

[Multipart message — attachments visible in raw view] — view raw

On Mon, Dec 17, 2018 at 10:19:02PM +0000, Jorgen Grahn wrote:
> On Sun, 2018-12-16, Scott wrote:
> > Well, not specifically a C matter, but as I've made a project of
> > converting an older program to leverage modern multi-core processors,
> > it just happens to be in C and I just happen to have opted for
> > pthreads since that works on all the platforms I use.
> >
> > What I'd like to ask for are recommendations on resources for learning
> > about the principles and pitfalls of threaded programming, in a
> > general way, not tied to any specific implementation. I'm muddling my
> > way through this exercise, but I have this feeling that I'm taking a
> > Sunday stroll through a live minefield and just haven't managed to
> > walk into anything really interesting yet.
> >
> > As always, thanks very much for your help.
> 
> In what way would this program benefit from being threaded?
> 
> The main thing I've learned about threading is to avoid it if
> possible.  Or, to know why you're using it.
> 
> Sorry if that sounded negative.  Put differently, if you can describe
> the task and people can help you with the high-level threading design
> for that particular task, that's better than any pthreads-specific
> help.

As negative as it may sound, I agree that it's one of the most important
considerations to keep in mind when planning a threaded program.

Synchronization (locking, memory barriers, etc.) is far from free. Even
if you ignore the complexity cost they add (not trivial to put it lightly),
it's easier than you think to end up with a program which multi-threaded is
now _slower_ than single, solely because of subtle interactions between
caches, CPU schedulers, and other hard-to-reason-about factors.

This isn't to say it is never a good idea; in many cases it makes sense to
have multiple threads of execution in today's workloads. Just think long and
hard before you commit to that road, and when you do decide on it make sure
you do it right. Your sanity will thank you later.

-- 
Cheers,
Joey Pabalinas

[toc] | [prev] | [next] | [standalone]

#138747

On 17 Dec 2018 22:19:02 GMT, Jorgen Grahn <grahn+nntp@snipabacken.se>
wrote:

>In what way would this program benefit from being threaded?

Well, this program does a lot of related but independent computations
and tends to be CPU-bound rather than I/O-bound. Kind of like a ray
tracer. Experiments with multiprocessing show that it *can* benefit
from more CPUs, it's just not written to do so by itself. Then
consider the difficulty of evenly distributing a workload across
multiple processes and the significant expense of forking them.
Threading seems to offer better flexibility and lower cost, at the
expense of having to implement it correctly in the first place.

More generally, modern computing is definitely well on its way to more
CPUs rather than faster CPUs. Developing some skill in this area
doesn't seem like a bad idea.

>The main thing I've learned about threading is to avoid it if
>possible.  Or, to know why you're using it.
>
>Sorry if that sounded negative.

Oh, not at all. I understand exactly where you're coming from.

[toc] | [prev] | [next] | [standalone]

#138748

W dniu środa, 19 grudnia 2018 20:48:06 UTC+1 użytkownik Scott napisał:
> On 17 Dec 2018 22:19:02 GMT, Jorgen Grahn <grahn+nntp@snipabacken.se>
> wrote:
> 
> >In what way would this program benefit from being threaded?
> 
> Well, this program does a lot of related but independent computations
> and tends to be CPU-bound rather than I/O-bound. Kind of like a ray
> tracer. Experiments with multiprocessing show that it *can* benefit
> from more CPUs, it's just not written to do so by itself. Then
> consider the difficulty of evenly distributing a workload across
> multiple processes and the significant expense of forking them.
> Threading seems to offer better flexibility and lower cost, at the
> expense of having to implement it correctly in the first place.
> 
> More generally, modern computing is definitely well on its way to more
> CPUs rather than faster CPUs. Developing some skill in this area
> doesn't seem like a bad idea.
> 
> >The main thing I've learned about threading is to avoid it if
> >possible.  Or, to know why you're using it.
> >
> >Sorry if that sounded negative.
> 
> Oh, not at all. I understand exactly where you're coming from.

you probably wont need much theory behind it

do it as i said - few 'async talls' and then barrrier and thats it

(the theory behind it is that that are atoms you could build nearly everything on them - and not you dont even need no
lock/any synchronisation in pure form of it

i once discovered it to myslelf, (and wrote on tis nearly 10 years ago) when doing multithreaded prgraming you in facy dont need locks you dont even need atomic accesses)

you may provide info what exactly it 
is then someone could almost exactly tell you what can you use

[toc] | [prev] | [next] | [standalone]

#138754

On Wed, 2018-12-19, Scott wrote:
> On 17 Dec 2018 22:19:02 GMT, Jorgen Grahn <grahn+nntp@snipabacken.se>
> wrote:
>
>>In what way would this program benefit from being threaded?
>
> Well, this program does a lot of related but independent computations
> and tends to be CPU-bound rather than I/O-bound. Kind of like a ray
> tracer.

That's a fairly good reason.  My experience is very limited, but I'd
start by looking for ways to split this particular problem across N
threads, without them having to fight each other for some silly shared
resource.  And the best ways to feed work to a thread, and for a
thread to say it's done.  Queues?

I think this group can help with that last part.

> Experiments with multiprocessing show that it *can* benefit
> from more CPUs, it's just not written to do so by itself. Then
> consider the difficulty of evenly distributing a workload across
> multiple processes and the significant expense of forking them.
> Threading seems to offer better flexibility and lower cost, at the
> expense of having to implement it correctly in the first place.

Forking in itself isn't that expensive.  I think the limited ways a
process can do I/O is the biggest problem.  Also an asset maybe, if
you can fit your problem into the pipeline pattern.

> More generally, modern computing is definitely well on its way to more
> CPUs rather than faster CPUs.

On the other hand, microservices split the workload across multiple
processes again, and often these come in their own VMs or Docker
containers ... that's in some sense a trend in the other direction.

> Developing some skill in this area doesn't seem like a bad idea.

True.

>>The main thing I've learned about threading is to avoid it if
>>possible.  Or, to know why you're using it.
>>
>>Sorry if that sounded negative.
>
> Oh, not at all. I understand exactly where you're coming from.

/Jorgen

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

[toc] | [prev] | [next] | [standalone]

#138755

On 12/19/2018 3:17 PM, Jorgen Grahn wrote:
> On Wed, 2018-12-19, Scott wrote:
>> On 17 Dec 2018 22:19:02 GMT, Jorgen Grahn <grahn+nntp@snipabacken.se>
>> wrote:
>>
>>> In what way would this program benefit from being threaded?
>>
>> Well, this program does a lot of related but independent computations
>> and tends to be CPU-bound rather than I/O-bound. Kind of like a ray
>> tracer.
> 
> That's a fairly good reason.  My experience is very limited, but I'd
> start by looking for ways to split this particular problem across N
> threads, without them having to fight each other for some silly shared
> resource.  And the best ways to feed work to a thread, and for a
> thread to say it's done.  Queues?

Queues between threads _are_ a shared resource. There are different 
types of queues. The most efficient is a simple Single Producer, Single 
Producer (SPSC) Queue. It uses simple atomic loads, stores and memory 
barriers. No atomic RMW!

However, there are MPMC, multi producer consumer, or single producer 
multi consumer sync setups, ect...

SPSC, MPSC, MPMC, SPMC

Fwiw, here is one of the fastest bakery style MPMC queues out there wrt 
using a single XADD for producer and consumer threads:

https://groups.google.com/d/topic/lock-free/acjQ3-89abE/discussion
(please read all...)

[...]

[toc] | [prev] | [next] | [standalone]

#138756

On 12/19/2018 3:31 PM, Chris M. Thomasson wrote:
> On 12/19/2018 3:17 PM, Jorgen Grahn wrote:
>> On Wed, 2018-12-19, Scott wrote:
>>> On 17 Dec 2018 22:19:02 GMT, Jorgen Grahn <grahn+nntp@snipabacken.se>
>>> wrote:
>>>
>>>> In what way would this program benefit from being threaded?
>>>
>>> Well, this program does a lot of related but independent computations
>>> and tends to be CPU-bound rather than I/O-bound. Kind of like a ray
>>> tracer.
>>
>> That's a fairly good reason.  My experience is very limited, but I'd
>> start by looking for ways to split this particular problem across N
>> threads, without them having to fight each other for some silly shared
>> resource.  And the best ways to feed work to a thread, and for a
>> thread to say it's done.  Queues?
> 
> Queues between threads _are_ a shared resource. There are different 
> types of queues. The most efficient is a simple Single Producer, Single 
> Producer (SPSC) Queue. 

Ummm, that is Single Producer, Single Consumer (SPSC) Queue.

Sorry about that typo.



> It uses simple atomic loads, stores and memory 
> barriers. No atomic RMW!
> 
> However, there are MPMC, multi producer consumer, or single producer 
> multi consumer sync setups, ect...
> 
> SPSC, MPSC, MPMC, SPMC
> 
> Fwiw, here is one of the fastest bakery style MPMC queues out there wrt 
> using a single XADD for producer and consumer threads:
> 
> https://groups.google.com/d/topic/lock-free/acjQ3-89abE/discussion
> (please read all...)
> 
> [...]

[toc] | [prev] | [next] | [standalone]

#138901

On 19 Dec 2018 23:17:07 GMT, Jorgen Grahn <grahn+nntp@snipabacken.se>
wrote:

>On Wed, 2018-12-19, Scott wrote:
>> Well, this program does a lot of related but independent computations
>> and tends to be CPU-bound rather than I/O-bound. Kind of like a ray
>> tracer.
>
>That's a fairly good reason.  My experience is very limited, but I'd
>start by looking for ways to split this particular problem across N
>threads, without them having to fight each other for some silly shared
>resource.  And the best ways to feed work to a thread, and for a
>thread to say it's done.  Queues?
>
>I think this group can help with that last part.

Well, let's see. I've made some progress and hit a few snags.

For feeding the threads, a shared job queue seems right. I made a
simple queue with mutex locking, since it's not a big player in the
overall process. The way it's laid out, a few thousand jobs can
account for many minutes of run time. On the output side there's no
contention to worry about.

What I'm running into now is irritating. I added the thread management
bits, it works, it produces correct results, but the performance is
perverse - the more threads I run, the slower it gets. Based on clues
popping up while chasing other bugs, am I right in thinking that
multiple threads calling malloc and friends could be a source of pain?
If so, I think I have a remedy for that. If not...well, I'll be stuck
looking for some other excuse.

[toc] | [prev] | [next] | [standalone]

#138903

W dniu sobota, 22 grudnia 2018 11:42:49 UTC+1 użytkownik Scott napisał:
> On 19 Dec 2018 23:17:07 GMT, Jorgen Grahn <grahn+nntp@snipabacken.se>
> wrote:
> 
> >On Wed, 2018-12-19, Scott wrote:
> >> Well, this program does a lot of related but independent computations
> >> and tends to be CPU-bound rather than I/O-bound. Kind of like a ray
> >> tracer.
> >
> >That's a fairly good reason.  My experience is very limited, but I'd
> >start by looking for ways to split this particular problem across N
> >threads, without them having to fight each other for some silly shared
> >resource.  And the best ways to feed work to a thread, and for a
> >thread to say it's done.  Queues?
> >
> >I think this group can help with that last part.
> 
> Well, let's see. I've made some progress and hit a few snags.
> 
> For feeding the threads, a shared job queue seems right. I made a
> simple queue with mutex locking, since it's not a big player in the
> overall process. The way it's laid out, a few thousand jobs can
> account for many minutes of run time. On the output side there's no
> contention to worry about.
> 
> What I'm running into now is irritating. I added the thread management
> bits, it works, it produces correct results, but the performance is
> perverse - the more threads I run, the slower it gets. Based on clues
> popping up while chasing other bugs, am I right in thinking that
> multiple threads calling malloc and friends could be a source of pain?
> If so, I think I have a remedy for that. If not...well, I'll be stuck
> looking for some other excuse.

you should state what this code exactly do, aksing such general questions to specific problem which is unknown is so stupid that is kind of group abuse

[toc] | [prev] | [next] | [standalone]

#138904

W dniu sobota, 22 grudnia 2018 12:41:20 UTC+1 użytkownik fir napisał:
> W dniu sobota, 22 grudnia 2018 11:42:49 UTC+1 użytkownik Scott napisał:
> > On 19 Dec 2018 23:17:07 GMT, Jorgen Grahn <grahn+nntp@snipabacken.se>
> > wrote:
> > 
> > >On Wed, 2018-12-19, Scott wrote:
> > >> Well, this program does a lot of related but independent computations
> > >> and tends to be CPU-bound rather than I/O-bound. Kind of like a ray
> > >> tracer.
> > >
> > >That's a fairly good reason.  My experience is very limited, but I'd
> > >start by looking for ways to split this particular problem across N
> > >threads, without them having to fight each other for some silly shared
> > >resource.  And the best ways to feed work to a thread, and for a
> > >thread to say it's done.  Queues?
> > >
> > >I think this group can help with that last part.
> > 
> > Well, let's see. I've made some progress and hit a few snags.
> > 
> > For feeding the threads, a shared job queue seems right. I made a
> > simple queue with mutex locking, since it's not a big player in the
> > overall process. The way it's laid out, a few thousand jobs can
> > account for many minutes of run time. On the output side there's no
> > contention to worry about.
> > 
> > What I'm running into now is irritating. I added the thread management
> > bits, it works, it produces correct results, but the performance is
> > perverse - the more threads I run, the slower it gets. Based on clues
> > popping up while chasing other bugs, am I right in thinking that
> > multiple threads calling malloc and friends could be a source of pain?
> > If so, I think I have a remedy for that. If not...well, I'll be stuck
> > looking for some other excuse.
> 
> you should state what this code exactly do, aksing such general questions to specific problem which is unknown is so stupid that is kind of group abuse

i may assure you that properly written mt code like in the scheme i was talking about (n async calls + barrier) bring good results, if i got frame time like 60 ms on  one thread, on four i would get it like 16 maybe 17 if this is properly done

[toc] | [prev] | [next] | [standalone]

#138906

On Saturday, December 22, 2018 at 8:42:49 AM UTC-2, Scott wrote:
> On 19 Dec 2018 23:17:07 GMT, Jorgen Grahn 
> wrote:
> 
> >On Wed, 2018-12-19, Scott wrote:
> >> Well, this program does a lot of related but independent computations
> >> and tends to be CPU-bound rather than I/O-bound. Kind of like a ray
> >> tracer.
> >
> >That's a fairly good reason.  My experience is very limited, but I'd
> >start by looking for ways to split this particular problem across N
> >threads, without them having to fight each other for some silly shared
> >resource.  And the best ways to feed work to a thread, and for a
> >thread to say it's done.  Queues?
> >
> >I think this group can help with that last part.
> 
> Well, let's see. I've made some progress and hit a few snags.
> 
> For feeding the threads, a shared job queue seems right. I made a
> simple queue with mutex locking, since it's not a big player in the
> overall process. The way it's laid out, a few thousand jobs can
> account for many minutes of run time. On the output side there's no
> contention to worry about.
> 
> What I'm running into now is irritating. I added the thread management
> bits, it works, it produces correct results, but the performance is
> perverse - the more threads I run, the slower it gets. Based on clues
> popping up while chasing other bugs, am I right in thinking that
> multiple threads calling malloc and friends could be a source of pain?
> If so, I think I have a remedy for that. If not...well, I'll be stuck
> looking for some other excuse.

Why do you think more threads makes the program faster?
After you reach the number of cores there is no magic.

One way to avoid malloc for jobs (I usually call Tasks) is
to have a fixed-size circular queue of jobs.

[toc] | [prev] | [next] | [standalone]

#138911

On 12/22/2018 03:43 AM, Scott wrote:
> For feeding the threads, a shared job queue seems right. I made a
> simple queue with mutex locking, since it's not a big player in the
> overall process. The way it's laid out, a few thousand jobs can
> account for many minutes of run time. On the output side there's no
> contention to worry about.

Is there any i/o involved, disk accesses for example? What does the CPU 
usage look like on each of the cores? If you are on Linux gprof is easy 
to use and might give you some hints. There are commercial tools like 
TotalView that are shinier.

On Windows VS has some capability. Rational's Purify is not cheap and 
it's also painful enough that we used it very rarely.

Do the threads ever come up for air? You may need to throw sched_yield() 
in some strategic places to allow the other threads to run. Context 
switching is expensive however.

Keep the TANSTAAFL principle in mind. N cpu intensive threads on one 
core aren't going to have any magical way to get more cycles than there 
are.

[toc] | [prev] | [next] | [standalone]

#138924

On 12/22/2018 10:41 AM, rbowman wrote:
> On 12/22/2018 03:43 AM, Scott wrote:
>> For feeding the threads, a shared job queue seems right. I made a
>> simple queue with mutex locking, since it's not a big player in the
>> overall process. The way it's laid out, a few thousand jobs can
>> account for many minutes of run time. On the output side there's no
>> contention to worry about.
> 
> Is there any i/o involved, disk accesses for example? What does the CPU 
> usage look like on each of the cores? If you are on Linux gprof is easy 
> to use and might give you some hints. There are commercial tools like 
> TotalView that are shinier.
> 
> On Windows VS has some capability. Rational's Purify is not cheap and 
> it's also painful enough that we used it very rarely.
> 
> Do the threads ever come up for air? You may need to throw sched_yield() 
> in some strategic places to allow the other threads to run. Context 
> switching is expensive however.

Generally, one should never use sched_yield() just to get "other threads 
to run". Threads should run full steam ahead doing work.  However, 
sched_yield() and hardware specific yields (e.g., x86 PAUSE) can be used 
in some spinlock backoff schemes. A nice example is the adaptive version 
of a mutex is where a thread can spin a few times before finally 
blocking on a kernel waitset.


> Keep the TANSTAAFL principle in mind. N cpu intensive threads on one 
> core aren't going to have any magical way to get more cycles than there 
> are.

You usually want each thread to represent an independent unit of 
execution. 4 CPUS, you can create 4 threads. Even use affinity masks to 
bind them. Or, you can "oversubscribe" with 8 threads, 2-per core.

[toc] | [prev] | [next] | [standalone]

#138917

nobody@example.org (Scott) writes:
>On 19 Dec 2018 23:17:07 GMT, Jorgen Grahn <grahn+nntp@snipabacken.se>
>wrote:

>What I'm running into now is irritating. I added the thread management
>bits, it works, it produces correct results, but the performance is
>perverse - the more threads I run, the slower it gets. Based on clues
>popping up while chasing other bugs, am I right in thinking that
>multiple threads calling malloc and friends could be a source of pain?
>If so, I think I have a remedy for that. If not...well, I'll be stuck
>looking for some other excuse.
>

It generally doesn't make sense to have more _active_[*] threads than
cores/hardware threads.

Certainly malloc/free must be thread-safe, which implies some level
of serialization of those calls - which for performance reasons, one
should disfavor.   Pool based allocators (using atomics to manage the
lookaside list) may be less expensive, but you'll still be contending
for the cache lines that hold the pool metadata; for that reason, per-thread
pool allocators may be more efficent.

Best case, you allocate everything you need up front.

[*] e.g. cpu-bound activities with little or no I/O

[toc] | [prev] | [next] | [standalone]

#138925

On 12/22/2018 11:52 AM, Scott Lurndal wrote:
> nobody@example.org (Scott) writes:
>> On 19 Dec 2018 23:17:07 GMT, Jorgen Grahn <grahn+nntp@snipabacken.se>
>> wrote:
> 
>> What I'm running into now is irritating. I added the thread management
>> bits, it works, it produces correct results, but the performance is
>> perverse - the more threads I run, the slower it gets. Based on clues
>> popping up while chasing other bugs, am I right in thinking that
>> multiple threads calling malloc and friends could be a source of pain?
>> If so, I think I have a remedy for that. If not...well, I'll be stuck
>> looking for some other excuse.
>>
> 
> It generally doesn't make sense to have more _active_[*] threads than
> cores/hardware threads.
> 
> Certainly malloc/free must be thread-safe, which implies some level
> of serialization of those calls - which for performance reasons, one
> should disfavor.   Pool based allocators (using atomics to manage the
> lookaside list) may be less expensive, but you'll still be contending
> for the cache lines that hold the pool metadata; for that reason, per-thread
> pool allocators may be more efficent.
> 
> Best case, you allocate everything you need up front.

Hard to disagree with that! :^)

> 
> [*] e.g. cpu-bound activities with little or no I/O
> 

[toc] | [prev] | [next] | [standalone]

#139003

On Sat, 22 Dec 2018 19:52:01 GMT, scott@slp53.sl.home (Scott Lurndal)
wrote:

>nobody@example.org (Scott) writes:
>>On 19 Dec 2018 23:17:07 GMT, Jorgen Grahn <grahn+nntp@snipabacken.se>
>>wrote:
>
>>What I'm running into now is irritating. I added the thread management
>>bits, it works, it produces correct results, but the performance is
>>perverse - the more threads I run, the slower it gets. Based on clues
>>popping up while chasing other bugs, am I right in thinking that
>>multiple threads calling malloc and friends could be a source of pain?
>>If so, I think I have a remedy for that. If not...well, I'll be stuck
>>looking for some other excuse.
>>
>
>It generally doesn't make sense to have more _active_[*] threads than
>cores/hardware threads.

Indeed. For fun (after I fixed the malloc problem) I tried pushing the
thread count up and up. Once I had more threads than cores (6),
performance was pretty flat, and started to slow down again at around
400 threads. No surprises there.

>Certainly malloc/free must be thread-safe, which implies some level
>of serialization of those calls - which for performance reasons, one
>should disfavor.   Pool based allocators (using atomics to manage the
>lookaside list) may be less expensive, but you'll still be contending
>for the cache lines that hold the pool metadata; for that reason, per-thread
>pool allocators may be more efficent.
>
>Best case, you allocate everything you need up front.

I wish. Being a ray tracer, the complexity and therefore memory
demands vary wildly with the input data. My test data set, which isn't
even very complex, ends up causing over 17 million malloc calls. The
resulting performance looks like this:

threads	time
1	0:22
2	0:23
3	1:18
4	1:27
5	1:29
6	1:42

Easy to see where the threads start fighting each other.

But lacking pre-allocation, as you said, a per-thread allocator is the
next best thing here. I did that with some #defines to redirect the
threaded malloc calls into my own thread pool allocator. It's not very
elegant since it has to search a list to find the thread context for
every call, but this can be done without mutex locks and that already
saves a lot of overhead. Point is, by making this change I was able to
reduce the number of actual malloc calls from 17 million to four
thousand (!), and the new performance tests look like this:

threads	time
1	0:21
2	0:11
3	0:08
4	0:06
5	0:05
6	0:05

And that is exactly the kind of performance gains I expected to see
when I first began this exercise. In fact the diminishing returns with
more cores is a clear effect of my program getting washed out by
system overhead - time to load the initial data, time to write the
results, the fact that the computer has other jobs than mine to keep
running. But I'm pleased with these results.

[toc] | [prev] | [next] | [standalone]

#139004

On 12/23/2018 3:11 PM, Scott wrote:
> On Sat, 22 Dec 2018 19:52:01 GMT, scott@slp53.sl.home (Scott Lurndal)
> wrote:
> 
>> nobody@example.org (Scott) writes:
>>> On 19 Dec 2018 23:17:07 GMT, Jorgen Grahn <grahn+nntp@snipabacken.se>
>>> wrote:
>>
>>> What I'm running into now is irritating. I added the thread management
>>> bits, it works, it produces correct results, but the performance is
>>> perverse - the more threads I run, the slower it gets. Based on clues
>>> popping up while chasing other bugs, am I right in thinking that
>>> multiple threads calling malloc and friends could be a source of pain?
>>> If so, I think I have a remedy for that. If not...well, I'll be stuck
>>> looking for some other excuse.
>>>
>>
>> It generally doesn't make sense to have more _active_[*] threads than
>> cores/hardware threads.
> 
> Indeed. For fun (after I fixed the malloc problem) I tried pushing the
> thread count up and up. Once I had more threads than cores (6),
> performance was pretty flat, and started to slow down again at around
> 400 threads. No surprises there.
> 
>> Certainly malloc/free must be thread-safe, which implies some level
>> of serialization of those calls - which for performance reasons, one
>> should disfavor.   Pool based allocators (using atomics to manage the
>> lookaside list) may be less expensive, but you'll still be contending
>> for the cache lines that hold the pool metadata; for that reason, per-thread
>> pool allocators may be more efficent.
>>
>> Best case, you allocate everything you need up front.
> 
> I wish. Being a ray tracer, the complexity and therefore memory
> demands vary wildly with the input data. My test data set, which isn't
> even very complex, ends up causing over 17 million malloc calls. The
> resulting performance looks like this:
[...]

There are ways to trace some fairly complex scenes without using dynamic 
memory:

https://www.shadertoy.com/view/XdB3Dw

https://www.shadertoy.com/view/4dSGW1

https://www.shadertoy.com/view/XdsGDB

https://www.shadertoy.com/view/llj3Rz

https://www.shadertoy.com/view/MdXSWn

;^)

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | comp.lang.c

csiph-web