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

Groups > comp.unix.programmer > #1059 > unrolled thread

Non-deterministic behavior of multithreaded software

Back to article view | Back to comp.unix.programmer

Contents

  Non-deterministic behavior of multithreaded software itt ium <ittium@gmail.com> - 2011-08-05 02:38 -0700
    Re: Non-deterministic behavior of multithreaded software Rainer Weikusat <rweikusat@mssgmbh.com> - 2011-08-05 15:41 +0100
    Re: Non-deterministic behavior of multithreaded software BGB <cr88192@hotmail.com> - 2011-08-05 14:46 -0700
      Re: Non-deterministic behavior of multithreaded software Rainer Weikusat <rweikusat@mssgmbh.com> - 2011-08-05 23:04 +0100
        Re: Non-deterministic behavior of multithreaded software BGB <cr88192@hotmail.com> - 2011-08-05 18:54 -0700
          Re: Non-deterministic behavior of multithreaded software Rainer Weikusat <rweikusat@mssgmbh.com> - 2011-08-06 14:59 +0100
            Re: Non-deterministic behavior of multithreaded software BGB <cr88192@hotmail.com> - 2011-08-06 20:29 -0700
              Re: Non-deterministic behavior of multithreaded software Rainer Weikusat <rweikusat@mssgmbh.com> - 2011-08-07 20:02 +0100
                Re: Non-deterministic behavior of multithreaded software BGB <cr88192@hotmail.com> - 2011-08-07 18:09 -0700
                  Re: Non-deterministic behavior of multithreaded software ittium <ittium@gmail.com> - 2011-08-09 09:48 +0530

#1059 — Non-deterministic behavior of multithreaded software

Group,
I have recently modified a software from single threaded to
multithreaded design. In single threaded version, a connection fd was
read by single thread, so event were always delivered in order. Now
since multiple threads handle different events (on the same fd), the
events are sometimes delivered out of order. Please note, on the
connection fd, events are received in proper order and this non-
deterministic behavior is introduced by my software only.

Following are my doubt

1. How to handle such a situation

2. Is it a bad idea to have multiple threads for the same fd. If yes
than how to increase capacity of a software that receives large amount
of data on a single fd only.

Because of the relevance I am posting the message to following groups.

comp.unix.programmer

comp.programming.threads

thanks
Ittium

[toc] | [next] | [standalone]

#1060

itt ium <ittium@gmail.com> writes:
> I have recently modified a software from single threaded to
> multithreaded design. In single threaded version, a connection fd was
> read by single thread, so event were always delivered in order. Now
> since multiple threads handle different events (on the same fd), the
> events are sometimes delivered out of order. Please note, on the
> connection fd, events are received in proper order and this non-
> deterministic behavior is introduced by my software only.
>
> Following are my doubt
>
> 1. How to handle such a situation

If you need such an ordering and it isn't implicitly guaranteed
anymore because it is now possible to work an several requests in
parallel, the intended order needs to be restored after the parts of
the task which are parallelizable have completed. A simple idea how
this could be done would be to include a 'ticket number' in the
request that can later be used to determine the ordering which was
lost in between again.

> 2. Is it a bad idea to have multiple threads for the same fd. If yes
> than how to increase capacity of a software that receives large amount
> of data on a single fd only.

'Multiple threads' can only be of help if at least some parts of the
work some program is supposed to do can be performed indepedently of
each other in parallell. Otherwise, if you cannot used more than one
CPU/ 'execution unit' and need to increase the capacity, you need to
get a faster execution unit or reduce the resource-intensity of
request processing so that the same 'execution unit' can process more
requests during some time interval.

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

#1062

On 8/5/2011 2:38 AM, itt ium wrote:
> Group,
> I have recently modified a software from single threaded to
> multithreaded design. In single threaded version, a connection fd was
> read by single thread, so event were always delivered in order. Now
> since multiple threads handle different events (on the same fd), the
> events are sometimes delivered out of order. Please note, on the
> connection fd, events are received in proper order and this non-
> deterministic behavior is introduced by my software only.
>

this is just what threads do...

realize that threads introduce a very large number of fairly subtle 
behaviors, which may totally "own" apps which are not really designed to 
deal effectively with them.

when multiple threads are involved, not even adding or removing things 
from linked lists are safe. this is why there are mutexes...


> Following are my doubt
>
> 1. How to handle such a situation
>

which part?...

for most cases, a simple answer is:
don't assume that the input and output will come in the same order;
if ordering is important, provide some means to re-order the results 
after the fact.

> 2. Is it a bad idea to have multiple threads for the same fd. If yes
> than how to increase capacity of a software that receives large amount
> of data on a single fd only.
>

2A. yes, all sorts of nasty things can happen when sharing fd's/... 
between threads. IMO, it is better to only have a single thread manage 
each resource.

2B. if it is a CPU bound operation, then one can try message-passing. in 
this case, a single thread manages IO, passing input to worker threads 
via job-queues or similar, and receiving results either in the job-queue 
objects, or via an output queue.

if the operation is IO bound, then there isn't really much of anything 
that can be done (multiple threads will not make IO go any faster...).


> Because of the relevance I am posting the message to following groups.
>
> comp.unix.programmer
>
> comp.programming.threads
>
> thanks
> Ittium

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

#1063

BGB <cr88192@hotmail.com> writes:

[...]

>> 2. Is it a bad idea to have multiple threads for the same fd. If yes
>> than how to increase capacity of a software that receives large amount
>> of data on a single fd only.
>>
>
> 2A. yes, all sorts of nasty things can happen when sharing
> fd's/... between threads.

Generally, 'all sorts of nasty things can happen' when code doesn't
work as it would need to. And your statement means little more than
that especially as file descriptors referring to different kind of
resources (eg, a listening stream socket, a connected accepted on such
a socket or a datagram socket) have wildly different behaviour.

[...]

> 2B. if it is a CPU bound operation, then one can try
> message-passing. in this case, a single thread manages IO, passing
> input to worker threads via job-queues or similar, and receiving
> results either in the job-queue objects, or via an output queue.

A nice quote on this:

	The simplest conceptual model of a multi-threaded event-driven
	server has a queue at its center; requests are read by one or
	more "listener" threads and put on queues, from which one or
	more "worker" threads will remove and process
	them. Conceptually, this is a good model, but all too often
	people actually implement their code this way. Why is this
	wrong? Because the #2 cause of context switches is
	transferring work from one thread to another. Some people even
	compound the error by requiring that the response to a request
	be sent by the original thread - guaranteeing not one but two
	context switches per request. It's very important to use a
	"symmetric" approach in which a given thread can go from being
	a listener to a worker to a listener again without ever
	changing context. Whether this involves partitioning
	connections between threads or having all threads take turns
	being listener for the entire set of connections seems to
	matter a lot less.
	http://pl.atyp.us/content/tech/servers.html

This is, of course, only 'wrong' when request processing performance
aka request-to-response-latency is actually the most important
concern.

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

#1065

On 8/5/2011 3:04 PM, Rainer Weikusat wrote:
> BGB<cr88192@hotmail.com>  writes:
>
> [...]
>
>>> 2. Is it a bad idea to have multiple threads for the same fd. If yes
>>> than how to increase capacity of a software that receives large amount
>>> of data on a single fd only.
>>>
>>
>> 2A. yes, all sorts of nasty things can happen when sharing
>> fd's/... between threads.
>
> Generally, 'all sorts of nasty things can happen' when code doesn't
> work as it would need to. And your statement means little more than
> that especially as file descriptors referring to different kind of
> resources (eg, a listening stream socket, a connected accepted on such
> a socket or a datagram socket) have wildly different behaviour.
>

the particular issue with fd's though is that when being shared between 
threads, one can end up with "slice-and-dice" input or output, as each 
read-request or write-request ends up interspersed with those from other 
threads.

or, if they are shared, one may end up using a mutex or similar as a 
transaction lock, which if combined with the potential for blocking, 
makes this a much bigger problem (threads backing up waiting for IO, 
...). with non-blocking IO, then one may also face the risk of truncated 
input or output messages, but still with an inability to safely unlock 
until the transaction can complete.

so, IMO, best practice is to not share them.


> [...]
>
>> 2B. if it is a CPU bound operation, then one can try
>> message-passing. in this case, a single thread manages IO, passing
>> input to worker threads via job-queues or similar, and receiving
>> results either in the job-queue objects, or via an output queue.
>
> A nice quote on this:
>
> 	The simplest conceptual model of a multi-threaded event-driven
> 	server has a queue at its center; requests are read by one or
> 	more "listener" threads and put on queues, from which one or
> 	more "worker" threads will remove and process
> 	them. Conceptually, this is a good model, but all too often
> 	people actually implement their code this way. Why is this
> 	wrong? Because the #2 cause of context switches is
> 	transferring work from one thread to another. Some people even
> 	compound the error by requiring that the response to a request
> 	be sent by the original thread - guaranteeing not one but two
> 	context switches per request. It's very important to use a
> 	"symmetric" approach in which a given thread can go from being
> 	a listener to a worker to a listener again without ever
> 	changing context. Whether this involves partitioning
> 	connections between threads or having all threads take turns
> 	being listener for the entire set of connections seems to
> 	matter a lot less.
> 	http://pl.atyp.us/content/tech/servers.html
>
> This is, of course, only 'wrong' when request processing performance
> aka request-to-response-latency is actually the most important
> concern.

yeah.

another thing is:
if request/response latency and context-switches actually become a 
performance issue, then the level of granularity is likely far too 
small, and likely better would have been to just use a single thread.

also, I was assuming that the operations would be queued up and handled 
asynchronously. if synchronous handling is needed, well then, there is 
no good reason to be using multiple threads in this case, as multiple 
threads will not improve performance in this case (one thread will 
simply end up sitting idly waiting for the other to complete).

also, given that OS-level threads are typically fairly expensive, 
fine-grained thread creation is itself generally a bad idea.

...

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

#1066

BGB <cr88192@hotmail.com> writes:
> On 8/5/2011 3:04 PM, Rainer Weikusat wrote:
>> BGB<cr88192@hotmail.com>  writes:
>>
>> [...]
>>
>>>> 2. Is it a bad idea to have multiple threads for the same fd. If yes
>>>> than how to increase capacity of a software that receives large amount
>>>> of data on a single fd only.
>>>>
>>>
>>> 2A. yes, all sorts of nasty things can happen when sharing
>>> fd's/... between threads.
>>
>> Generally, 'all sorts of nasty things can happen' when code doesn't
>> work as it would need to. And your statement means little more than
>> that especially as file descriptors referring to different kind of
>> resources (eg, a listening stream socket, a connected accepted on such
>> a socket or a datagram socket) have wildly different behaviour.
>>
>
> the particular issue with fd's though is that when being shared
> between threads, one can end up with "slice-and-dice" input or output,
> as each read-request or write-request ends up interspersed with those
> from other threads.

I intentionally gave three examples with two of them being immune to this
problem: Any number of threads can block in accept, as soon as a
thread returns, it will have a file descriptor for an accepted
connection, not 2/3 of such a file descriptor. The same is true for
receive operations on 'I/O channels' which preserve message boundaries
(and I strongly suspsect that the OP is doing this): A thread
returning from such a receive call will always have read a complete
message.

Your statement about 'file descriptors' is way too general to make
sense. Actually, the only thing it applies to is 'I/O channels with
bytestream semantics', eg, stream sockets, pipes, FIFOs and regular
files. And it basically just means 'multiple independent "executable
things" need to coordinate accesses to shared ressources'. In some
cases, this coordination happens inside the kernel, in some other
cases, it needs to be coded into the application.

[...]

>>> 2B. if it is a CPU bound operation, then one can try
>>> message-passing. in this case, a single thread manages IO, passing
>>> input to worker threads via job-queues or similar, and receiving
>>> results either in the job-queue objects, or via an output queue.
>>
>> A nice quote on this:
>>
>> 	The simplest conceptual model of a multi-threaded event-driven
>> 	server has a queue at its center; requests are read by one or
>> 	more "listener" threads and put on queues, from which one or
>> 	more "worker" threads will remove and process
>> 	them. Conceptually, this is a good model, but all too often
>> 	people actually implement their code this way. Why is this
>> 	wrong? Because the #2 cause of context switches is
>> 	transferring work from one thread to another. Some people even
>> 	compound the error by requiring that the response to a request
>> 	be sent by the original thread - guaranteeing not one but two
>> 	context switches per request. It's very important to use a
>> 	"symmetric" approach in which a given thread can go from being
>> 	a listener to a worker to a listener again without ever
>> 	changing context. Whether this involves partitioning
>> 	connections between threads or having all threads take turns
>> 	being listener for the entire set of connections seems to
>> 	matter a lot less.
>> 	http://pl.atyp.us/content/tech/servers.html
>>
>> This is, of course, only 'wrong' when request processing performance
>> aka request-to-response-latency is actually the most important
>> concern.
>
> yeah.
>
> another thing is:
> if request/response latency and context-switches actually become a
> performance issue, then the level of granularity is likely far too
> small, and likely better would have been to just use a single
> thread.

I assume that you are convinced that this makes sense because you were
thinking about something specific while typing this 'reminder to self'
note but the words, as they are written down, are pretty much total
nonsense: Average/ medium request/response latency is 'the
performance' (of some server) expressed as a number
(simplified). Context switches are a specific kind of operation taking
place when one thread 'passes work' to some other thread: Assuming the
server isn't already overloaded and actually buffering requests on the
queue because they arrive faster than the responses can be generated,
it means that a currently running thread needs to be put to sleep
despite it has all the information ('the request') necessary to
continue processing available while a currently sleeping thread that
doesn't have this information available needs to be awoken in order to
receive it so that it can do the processing. Technically, that's just a
nonsense operation because it is pure overhead. The advantage is that
the design becomes simpler when threads are used as 'specialized
execution units' as if they were independent parts of a real machine
design to perform a specific function and incapable of doing anything
else. But this limitation of physical things doesn't really exist for
threads: They are all created equal in the sense that every thread can
run all of the code any other thread can also run which implies that
the transport overhead implicit in the 'geographically distant
funtional units with different purposes' model can be avoided.

> also, I was assuming that the operations would be queued up and
> handled asynchronously. if synchronous handling is needed, well then,
> there is no good reason to be using multiple threads in this case, as
> multiple threads will not improve performance in this case (one thread
> will simply end up sitting idly waiting for the other to complete).

Multiple threads can handle multiple requests 'synchronously' in
parallell if such parallell request handling is possible.

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

#1068

On 8/6/2011 6:59 AM, Rainer Weikusat wrote:
> BGB<cr88192@hotmail.com>  writes:
>> On 8/5/2011 3:04 PM, Rainer Weikusat wrote:
>>> BGB<cr88192@hotmail.com>   writes:
>>>
>>> [...]
>>>
>>>>> 2. Is it a bad idea to have multiple threads for the same fd. If yes
>>>>> than how to increase capacity of a software that receives large amount
>>>>> of data on a single fd only.
>>>>>
>>>>
>>>> 2A. yes, all sorts of nasty things can happen when sharing
>>>> fd's/... between threads.
>>>
>>> Generally, 'all sorts of nasty things can happen' when code doesn't
>>> work as it would need to. And your statement means little more than
>>> that especially as file descriptors referring to different kind of
>>> resources (eg, a listening stream socket, a connected accepted on such
>>> a socket or a datagram socket) have wildly different behaviour.
>>>
>>
>> the particular issue with fd's though is that when being shared
>> between threads, one can end up with "slice-and-dice" input or output,
>> as each read-request or write-request ends up interspersed with those
>> from other threads.
>
> I intentionally gave three examples with two of them being immune to this
> problem: Any number of threads can block in accept, as soon as a
> thread returns, it will have a file descriptor for an accepted
> connection, not 2/3 of such a file descriptor. The same is true for
> receive operations on 'I/O channels' which preserve message boundaries
> (and I strongly suspsect that the OP is doing this): A thread
> returning from such a receive call will always have read a complete
> message.
>
> Your statement about 'file descriptors' is way too general to make
> sense. Actually, the only thing it applies to is 'I/O channels with
> bytestream semantics', eg, stream sockets, pipes, FIFOs and regular
> files. And it basically just means 'multiple independent "executable
> things" need to coordinate accesses to shared ressources'. In some
> cases, this coordination happens inside the kernel, in some other
> cases, it needs to be coded into the application.
>

bytestream IO is the main use of file-descriptors though:
one is reading/writing a file or block device;
or it is the console;
or it is a TCP connection;
...

granted, yes, listening sockets or datagram sockets could be shared, I 
had overlooked this case.


> [...]
>
>>>> 2B. if it is a CPU bound operation, then one can try
>>>> message-passing. in this case, a single thread manages IO, passing
>>>> input to worker threads via job-queues or similar, and receiving
>>>> results either in the job-queue objects, or via an output queue.
>>>
>>> A nice quote on this:
>>>
>>> 	The simplest conceptual model of a multi-threaded event-driven
>>> 	server has a queue at its center; requests are read by one or
>>> 	more "listener" threads and put on queues, from which one or
>>> 	more "worker" threads will remove and process
>>> 	them. Conceptually, this is a good model, but all too often
>>> 	people actually implement their code this way. Why is this
>>> 	wrong? Because the #2 cause of context switches is
>>> 	transferring work from one thread to another. Some people even
>>> 	compound the error by requiring that the response to a request
>>> 	be sent by the original thread - guaranteeing not one but two
>>> 	context switches per request. It's very important to use a
>>> 	"symmetric" approach in which a given thread can go from being
>>> 	a listener to a worker to a listener again without ever
>>> 	changing context. Whether this involves partitioning
>>> 	connections between threads or having all threads take turns
>>> 	being listener for the entire set of connections seems to
>>> 	matter a lot less.
>>> 	http://pl.atyp.us/content/tech/servers.html
>>>
>>> This is, of course, only 'wrong' when request processing performance
>>> aka request-to-response-latency is actually the most important
>>> concern.
>>
>> yeah.
>>
>> another thing is:
>> if request/response latency and context-switches actually become a
>> performance issue, then the level of granularity is likely far too
>> small, and likely better would have been to just use a single
>> thread.
>
> I assume that you are convinced that this makes sense because you were
> thinking about something specific while typing this 'reminder to self'
> note but the words, as they are written down, are pretty much total
> nonsense: Average/ medium request/response latency is 'the
> performance' (of some server) expressed as a number
> (simplified). Context switches are a specific kind of operation taking
> place when one thread 'passes work' to some other thread: Assuming the
> server isn't already overloaded and actually buffering requests on the
> queue because they arrive faster than the responses can be generated,
> it means that a currently running thread needs to be put to sleep
> despite it has all the information ('the request') necessary to
> continue processing available while a currently sleeping thread that
> doesn't have this information available needs to be awoken in order to
> receive it so that it can do the processing. Technically, that's just a
> nonsense operation because it is pure overhead. The advantage is that
> the design becomes simpler when threads are used as 'specialized
> execution units' as if they were independent parts of a real machine
> design to perform a specific function and incapable of doing anything
> else. But this limitation of physical things doesn't really exist for
> threads: They are all created equal in the sense that every thread can
> run all of the code any other thread can also run which implies that
> the transport overhead implicit in the 'geographically distant
> funtional units with different purposes' model can be avoided.
>

I have before measured the time to go to sleep, switch threads, and get 
control back, to typically be about 50-100ns or so on modern systems 
(granted, this was in the case of multi-threaded programs on Windows).

(the above is in contrast to the 1-2us needed to lock a mutex object, 
for whatever reason it takes this long...).

if the operation itself is something which takes, say, < 10us or so, 
then likely the granularity was too small, and a single thread (or 
multiple independent/parallel threads) would probably have made more sense.


for example, one could use multiple threads for rendering frames of 
video, or run a physics-simulator frame-step, ...

but, say, cross-thread function-calls, ... would be terribly wasteful.


>> also, I was assuming that the operations would be queued up and
>> handled asynchronously. if synchronous handling is needed, well then,
>> there is no good reason to be using multiple threads in this case, as
>> multiple threads will not improve performance in this case (one thread
>> will simply end up sitting idly waiting for the other to complete).
>
> Multiple threads can handle multiple requests 'synchronously' in
> parallell if such parallell request handling is possible.

potentially.

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

#1069

BGB <cr88192@hotmail.com> writes:
> On 8/6/2011 6:59 AM, Rainer Weikusat wrote:

[...]

>> Context switches are a specific kind of operation taking
>> place when one thread 'passes work' to some other thread: Assuming the
>> server isn't already overloaded and actually buffering requests on the
>> queue because they arrive faster than the responses can be generated,
>> it means that a currently running thread needs to be put to sleep
>> despite it has all the information ('the request') necessary to
>> continue processing available while a currently sleeping thread that
>> doesn't have this information available needs to be awoken in order to
>> receive it so that it can do the processing. Technically, that's just a
>> nonsense operation because it is pure overhead. The advantage is that
>> the design becomes simpler when threads are used as 'specialized
>> execution units' as if they were independent parts of a real machine
>> design to perform a specific function and incapable of doing anything
>> else. But this limitation of physical things doesn't really exist for
>> threads: They are all created equal in the sense that every thread can
>> run all of the code any other thread can also run which implies that
>> the transport overhead implicit in the 'geographically distant
>> funtional units with different purposes' model can be avoided.
>
> I have before measured the time to go to sleep, switch threads, and
> get control back, to typically be about 50-100ns or so on modern
> systems (granted, this was in the case of multi-threaded programs on
> Windows).
>
> (the above is in contrast to the 1-2us needed to lock a mutex object,
> for whatever reason it takes this long...).

According to a very simplistic experiment I just made, namely,

----------
#include <pthread.h>

unsigned a;

int main(void)
{
    pthread_mutex_t lock;
    unsigned b;

    b = 0xfffffff;
    while (--b) {
    	pthread_mutex_lock(&lock);
	nop(++a);
    	pthread_mutex_unlock(&lock);
    }

    return a;
}
----------

with 'nop' being

void nop(unsigned x) { }

defined in another file in order to 'fool' the gcc optimizer, locking
and unlocking an uncontended mutex takes about 11.6ns on an Intel Core
i3 3.2Ghz-using computer. This means assuming your numbers are
accurate, the operation is an about an order of magnitude faster than
'go to sleep, switch threads ...'. However, I don't quite understand
what you're up to, especially since passing a data item from one
thread to another 'fast' (ie, without copying it through the kernel)
will usually involve operations on a mutex and a condition variable on
both ends.
 
> if the operation itself is something which takes, say, < 10us or so,
> then likely the granularity was too small, and a single thread (or
> multiple independent/parallel threads) would probably have made more
> sense.

Also, I still don't understand what 'granularity' is supposed to mean
here. 

[...]

>>> also, I was assuming that the operations would be queued up and
>>> handled asynchronously. if synchronous handling is needed, well then,
>>> there is no good reason to be using multiple threads in this case, as
>>> multiple threads will not improve performance in this case (one thread
>>> will simply end up sitting idly waiting for the other to complete).
>>
>> Multiple threads can handle multiple requests 'synchronously' in
>> parallell if such parallell request handling is possible.
>
> potentially.

Provided that multiple threads can run in parallell (because more than
a single 'execution unit' exists), they will be able to do parallell
request processing.

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

#1070

On 8/7/2011 12:02 PM, Rainer Weikusat wrote:
> BGB<cr88192@hotmail.com>  writes:
>> On 8/6/2011 6:59 AM, Rainer Weikusat wrote:
>
> [...]
>
>>> Context switches are a specific kind of operation taking
>>> place when one thread 'passes work' to some other thread: Assuming the
>>> server isn't already overloaded and actually buffering requests on the
>>> queue because they arrive faster than the responses can be generated,
>>> it means that a currently running thread needs to be put to sleep
>>> despite it has all the information ('the request') necessary to
>>> continue processing available while a currently sleeping thread that
>>> doesn't have this information available needs to be awoken in order to
>>> receive it so that it can do the processing. Technically, that's just a
>>> nonsense operation because it is pure overhead. The advantage is that
>>> the design becomes simpler when threads are used as 'specialized
>>> execution units' as if they were independent parts of a real machine
>>> design to perform a specific function and incapable of doing anything
>>> else. But this limitation of physical things doesn't really exist for
>>> threads: They are all created equal in the sense that every thread can
>>> run all of the code any other thread can also run which implies that
>>> the transport overhead implicit in the 'geographically distant
>>> funtional units with different purposes' model can be avoided.
>>
>> I have before measured the time to go to sleep, switch threads, and
>> get control back, to typically be about 50-100ns or so on modern
>> systems (granted, this was in the case of multi-threaded programs on
>> Windows).
>>
>> (the above is in contrast to the 1-2us needed to lock a mutex object,
>> for whatever reason it takes this long...).
>
> According to a very simplistic experiment I just made, namely,
>
> ----------
> #include<pthread.h>
>
> unsigned a;
>
> int main(void)
> {
>      pthread_mutex_t lock;
>      unsigned b;
>
>      b = 0xfffffff;
>      while (--b) {
>      	pthread_mutex_lock(&lock);
> 	nop(++a);
>      	pthread_mutex_unlock(&lock);
>      }
>
>      return a;
> }
> ----------
>
> with 'nop' being
>
> void nop(unsigned x) { }
>
> defined in another file in order to 'fool' the gcc optimizer, locking
> and unlocking an uncontended mutex takes about 11.6ns on an Intel Core
> i3 3.2Ghz-using computer. This means assuming your numbers are
> accurate, the operation is an about an order of magnitude faster than
> 'go to sleep, switch threads ...'. However, I don't quite understand
> what you're up to, especially since passing a data item from one
> thread to another 'fast' (ie, without copying it through the kernel)
> will usually involve operations on a mutex and a condition variable on
> both ends.
>

I should have written this more clearly (the context was assumed because 
the prior statement mentioned Windows and the following statement had 
parenthesis, and so was a side-note related to the former).

I was talking at the moment about the "mutex object" on Windows (handled 
with "CreateMutex()" and "WaitForSingleObject()" API calls), which is, 
generally, *absurdly* slow... (why?... who knows...). it is well 
documented as being slow though (I guess the usual answer is because it 
does multiple-process synchronization or similar, but it is a mystery 
why this itself takes as long as it does).

OTOH, Windows offers "critical section" support which is a good deal 
faster, but still not terribly fast (it is single process, but I have 
read that it tries to be "fair" by granting locks in a FIFO order, ...).


the fastest option was generally to roll ones' own mutex support (in my 
case, essentially a spin-lock with sleeping), which gets performance 
fairly similar to your pthread-based example (on a 2.8GHz AthlonII).


>> if the operation itself is something which takes, say,<  10us or so,
>> then likely the granularity was too small, and a single thread (or
>> multiple independent/parallel threads) would probably have made more
>> sense.
>
> Also, I still don't understand what 'granularity' is supposed to mean
> here.
>

the the size as the amount of time needed to complete a request.

smaller granularity would mean a larger number of smaller requests.
larger granularity would mean a smaller number of much larger requests.

the relative cost of scheduling overhead/... would likely depend 
somewhat on the number, type, and size of the requests (scheduling 
overhead is much lower if the requests are relatively few but take a 
reasonably large amount of time to process).


> [...]
>
>>>> also, I was assuming that the operations would be queued up and
>>>> handled asynchronously. if synchronous handling is needed, well then,
>>>> there is no good reason to be using multiple threads in this case, as
>>>> multiple threads will not improve performance in this case (one thread
>>>> will simply end up sitting idly waiting for the other to complete).
>>>
>>> Multiple threads can handle multiple requests 'synchronously' in
>>> parallell if such parallell request handling is possible.
>>
>> potentially.
>
> Provided that multiple threads can run in parallell (because more than
> a single 'execution unit' exists), they will be able to do parallell
> request processing.

yep.


this is one case where using threads makes sense, but typically threads 
would be used in a more-or-less asynchronous manner (pass a bunch of 
requests and wait for them to start finishing), since if one does a 
synchronous operation (pass request, wait for it to complete, pass next 
request, ...), more time is wasted with one thread waiting for another 
thread to go do its thing, essentially eliminating much of the possible 
speedup (since time spent sleeping is not time spent doing something).


or such...

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

#1091

On 08-08-2011 AM 06:39, BGB wrote:
> On 8/7/2011 12:02 PM, Rainer Weikusat wrote:
>> BGB<cr88192@hotmail.com> writes:
>>> On 8/6/2011 6:59 AM, Rainer Weikusat wrote:
>>
>> [...]
>>
>>>> Context switches are a specific kind of operation taking
>>>> place when one thread 'passes work' to some other thread: Assuming the
>>>> server isn't already overloaded and actually buffering requests on the
>>>> queue because they arrive faster than the responses can be generated,
>>>> it means that a currently running thread needs to be put to sleep
>>>> despite it has all the information ('the request') necessary to
>>>> continue processing available while a currently sleeping thread that
>>>> doesn't have this information available needs to be awoken in order to
>>>> receive it so that it can do the processing. Technically, that's just a
>>>> nonsense operation because it is pure overhead. The advantage is that
>>>> the design becomes simpler when threads are used as 'specialized
>>>> execution units' as if they were independent parts of a real machine
>>>> design to perform a specific function and incapable of doing anything
>>>> else. But this limitation of physical things doesn't really exist for
>>>> threads: They are all created equal in the sense that every thread can
>>>> run all of the code any other thread can also run which implies that
>>>> the transport overhead implicit in the 'geographically distant
>>>> funtional units with different purposes' model can be avoided.
>>>
>>> I have before measured the time to go to sleep, switch threads, and
>>> get control back, to typically be about 50-100ns or so on modern
>>> systems (granted, this was in the case of multi-threaded programs on
>>> Windows).
>>>
>>> (the above is in contrast to the 1-2us needed to lock a mutex object,
>>> for whatever reason it takes this long...).
>>
>> According to a very simplistic experiment I just made, namely,
>>
>> ----------
>> #include<pthread.h>
>>
>> unsigned a;
>>
>> int main(void)
>> {
>> pthread_mutex_t lock;
>> unsigned b;
>>
>> b = 0xfffffff;
>> while (--b) {
>> pthread_mutex_lock(&lock);
>> nop(++a);
>> pthread_mutex_unlock(&lock);
>> }
>>
>> return a;
>> }
>> ----------
>>
>> with 'nop' being
>>
>> void nop(unsigned x) { }
>>
>> defined in another file in order to 'fool' the gcc optimizer, locking
>> and unlocking an uncontended mutex takes about 11.6ns on an Intel Core
>> i3 3.2Ghz-using computer. This means assuming your numbers are
>> accurate, the operation is an about an order of magnitude faster than
>> 'go to sleep, switch threads ...'. However, I don't quite understand
>> what you're up to, especially since passing a data item from one
>> thread to another 'fast' (ie, without copying it through the kernel)
>> will usually involve operations on a mutex and a condition variable on
>> both ends.
>>
>
> I should have written this more clearly (the context was assumed because
> the prior statement mentioned Windows and the following statement had
> parenthesis, and so was a side-note related to the former).
>
> I was talking at the moment about the "mutex object" on Windows (handled
> with "CreateMutex()" and "WaitForSingleObject()" API calls), which is,
> generally, *absurdly* slow... (why?... who knows...). it is well
> documented as being slow though (I guess the usual answer is because it
> does multiple-process synchronization or similar, but it is a mystery
> why this itself takes as long as it does).
>
> OTOH, Windows offers "critical section" support which is a good deal
> faster, but still not terribly fast (it is single process, but I have
> read that it tries to be "fair" by granting locks in a FIFO order, ...).
>
>
> the fastest option was generally to roll ones' own mutex support (in my
> case, essentially a spin-lock with sleeping), which gets performance
> fairly similar to your pthread-based example (on a 2.8GHz AthlonII).
>
>
>>> if the operation itself is something which takes, say,< 10us or so,
>>> then likely the granularity was too small, and a single thread (or
>>> multiple independent/parallel threads) would probably have made more
>>> sense.
>>
>> Also, I still don't understand what 'granularity' is supposed to mean
>> here.
>>
>
> the the size as the amount of time needed to complete a request.
>
> smaller granularity would mean a larger number of smaller requests.
> larger granularity would mean a smaller number of much larger requests.
>
> the relative cost of scheduling overhead/... would likely depend
> somewhat on the number, type, and size of the requests (scheduling
> overhead is much lower if the requests are relatively few but take a
> reasonably large amount of time to process).
>
>
>> [...]
>>
>>>>> also, I was assuming that the operations would be queued up and
>>>>> handled asynchronously. if synchronous handling is needed, well then,
>>>>> there is no good reason to be using multiple threads in this case, as
>>>>> multiple threads will not improve performance in this case (one thread
>>>>> will simply end up sitting idly waiting for the other to complete).
>>>>
>>>> Multiple threads can handle multiple requests 'synchronously' in
>>>> parallell if such parallell request handling is possible.
>>>
>>> potentially.
>>
>> Provided that multiple threads can run in parallell (because more than
>> a single 'execution unit' exists), they will be able to do parallell
>> request processing.
>
> yep.
>
>
> this is one case where using threads makes sense, but typically threads
> would be used in a more-or-less asynchronous manner (pass a bunch of
> requests and wait for them to start finishing), since if one does a
> synchronous operation (pass request, wait for it to complete, pass next
> request, ...), more time is wasted with one thread waiting for another
> thread to go do its thing, essentially eliminating much of the possible
> speedup (since time spent sleeping is not time spent doing something).
>
>
> or such...

Thanks BGB  and Rainer, for detailed discussion on this. I went through 
the whole threads, I think some more information will help in 
understanding my system better

We are finding out readyness of the fd through edge-triggered mechanism 
(epoll). All threads are equally likely to read the message using 
non-blocking call. We are currently targeting message based 
prototocol(sctp/udp) so no locks are needed. In future we might add 
support for byte stream protocol (like TCP), we might need mutex then. 
There is zero context switching in this model.

My software is handing the call session. The problem occur, if event for 
a call are delivered out of order. I have modified the software such 
that message belonging to a call are processed by same thread, in this 
way ordering of events for the call state machine is maintained. But 
this has introduced a pinner thread that assign the messages to 
different worker threads based on a a hash function that take input as 
call ID.

1. Thread ID may not be uniformly distributed, any logic of work 
division might load few thread.

2. A context switch is introduced because of pinner. Earlier a single 
thread was doing all the work (from reading from socket to delivering it 
to other modules.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.unix.programmer

csiph-web