Re: Multi Threading Options

See below...
On Wed, 1 Jun 2005 18:46:26 +0100, "Mark Randall" <markyr@xxxxxxxxxxxxxxxxxxxxxxxxxxx>
wrote:

>class CAwAvatar
>{
> int x, y, z, messages_to, session;
****
AVOID ALL USE OF COMMAS IN VARIABLE DECLARATIONS. I see what should be five separate lines
of code lumped into one unreadable line above
*****
>
> void SendMsg(LPCTSTR text)
> {
> aw_whisper(session, text) << External C API
> messages_to++;
> }
****
messages_to apparently does not participate in any of the logic dealing with messaging (is
it only for doing performance analysis?)
****
>
> void Kill(LPCTSTR reason)
> {
> FOR_EACH_OF_AVATARS << Linked List Enumerator
> pUser->SendMsg(reason);
> END_FOR_EACH << aka '}'
> }
>}
*****
Presumably this is shutting down the avatar threads?
****
>
>class CAwAvatars
>{
> CTypedPtrList<CPtrList, CAwAvatar*> vCol;
>
> CAwAvatar* create( ); << adds new user to vCol
> void Delete(CAwAvatar*) << removes from vCol
> CAwAvatar* find(int session); << loops through, finds session match
>}
>
>extern CAwAvatars avatars; << defined globally in stdafx
******
NEVER, EVER, UNDER ANY CIRCUMSTANCES IMAGINABLE, SHOULD YOU PUT ANYTHING IN STDAFX.H OTHER
THAN #include <> STATEMENTS FOR STANDARD LIBRARIES AND THEIR SURROUNDING CONDITIONALS AND
POSSIBLY #define DECLARATIONS THAT CONFIGURE THE STANDARD LIBRARY INCLUDES. NEVER, EVER
PUT A VARIABLE DECLARATION FOR ANYTHING OF YOUR OWN IN STDAFX.H. NEVER PUT ONE OF YOUR OWN
#include REQUESTS IN STDAFX.H. IT IS SOLELY AND EXCLUSIVELY, WITHOUT ANY EXCEPTION, FOR
THE PURPOSE OF PRECOMPILED STANDARD LIBRARY HEADERS. NEVER, EVER, UNDER ANY CIRCUMSTANCES
IMAGINABLE, FOR ANY REASON WHATSOEVER, EDIT STDAFX.CPP.

Code that does this is unmaintainable. If you need an extern, you will put it, in the
best case, in a totally separate file which contains that one line of declaration. I
cannot emphasize strongly enough that abuse of the purpose of the stdafx files leads to
unmaintainable disasters. MFC/C++ is *not* "C programming". Abysmal habits such as lumping
everything into a single #include file were poor programming in C, and unacceptable in
C++. Using stdafx files for any purpose other than the one they were designed for is
unforgiveable. Even the concept that there is a single global header file for your private
variables is a mistake. Adding #include directives is never a mistake. Splitting is good.
Lumping is bad. Always. (One of my Ph.D. students did her dissertation and has the numbers
to prove that this is always a mistake! This is not just my opinion, it is substantiated
by carefully measured evidence). You include the files you need ONLY in the modules that
use them! (For example, when I subclass, the FIRST thing I do is remove that asinine
#include that Microsoft puts into every derived class, which includes the app class. There
is absolutely no excuse for this to have been done, and it is always a mistake to leave it
in. At best, you may need resource.h, and should include only that. The last major app I
delivered had close to 200 source files, and exactly TWO of them included the project.h
file, and they were the project.cpp and the mainfrm.cpp files).
*****
>
>[could be any thread #2]
>void some_externally_triggered_func(int session, int x, int y, int z, [...])
>{
> CAwAvatar* pUser = avatars.find(session);
> if (pUser)
> {
> pUser->x = x;
> pUser->y = y;
> [...]
> }
>}
****
If the avatars struct could be modified by any other thread, it *must* be synchronized. At
that point, your modifications are so short that releasing the main lock and locking just
the individual struct doesn't pay off, unless that stuff inside the conditional has on the
order of a thousand lines of code, or could block. It looks like neither would apply to
your case, so you only need a single lock to modify it)
****
>
>[could be any thread except #2]
>void another_external_func(int session, LPCTSTR msg)
>{
> CAwAvatar* pUser = avatars.find(session);
> if (!strcmp(msg, "bad word"))
> pUser->Kill("User said something... regrettable");
>}
****
basically the same problem. SInce you have to actually lock the avatars list in its
entirety, unless your lstrcmp represents a long computational loop looking things up from
a massive dictionary, the single lock will suffice.

Note that if performance is an issue, you might consider a CMap instead of a CList <OOPS,
Hit the send sequence by accident...keyboard is flaky> if you have a lot of atavars. The
linear lookup time may become the dominant performance problem.
*****
>
>[ --- thread #2 --- ]
>void MyDlg::OnTimer( )
>{
> FOR_EACH_OF_AVATARS
> DoDrawingOf(pUser);
> END_FOR_EACH
>}
****
Given that the refresh is timer=based, you could probably eliminate all synchronization
just by at this point sending a draw notification to the thread that handles the avatars.
That is, the avatar struct, intead of being a global variable, is actually a thread-local
variable of a CWinThread class. Nobody can even touch it without contacting that thread.
If it is a UI thread, then while the drawing is happening, the Post[Thread]Message
requests to the thread just pile up waiting for the drawing to finish, but don't block the
sending threads (a lock would force blocking of those threads to do the update), and every
once in a while, the main thread, on the OnTimer handler, posts a message to redraw. This
message will queue up behind all the pending update requests. If the pending queue can get
long enough to block updating, you might want to consider my earlier suggestion of a mix
of a message pump and an I/O Completion Port (a bad name since it is really a
general-purpose queuing mechanism which happens to have a nice interface to the I/O
system. The way I do this in MFC, by the way, is described in my essay; I handle it in the
OnIdle handler of the CWinThread.
*****
>
>void MyDlg::DoDrawingOf(CAwAvatar* pUser)
>{
> >> rather large drawing code here based on variables in pUser <<
> >> also some methods of pUser may be called here that change its data <<
>}
>
>Thats the bread and butter of it, of course there are over 100 methods and
>properties associated with the AwAvatar class, all are set directly via
>pUser->x = x and the like (somehow setting and getting vars through
>functions sounds like a good way to add extra overhead, is this going to
>come back and bite me in the back side now?)
****
Only if you believe that set/get functions actually generate function calls. If you create
them in the class itself, you will discover in the optimized code that they generate no
real function calls, just inline automatically.

void SetSomeValue(int n) { somevalue = n; }
int GetSomeValue() { return somevalue; }

But never judge what generated code looks like unless you have generated the code using
compiler optimizations on. Debug code always looks crappy in this regard.

The problem is that if you have to synchronize accesses, the cost of the function call is
undetectable (even if it were a full function call) compared with synchronization
overhead, which is why it is a good idea to avoid the need for synchronization overhead.

What are the expected update rates? Tens, hundreds, thousands per second? If thousands,
you may need to rethink what you are doing, because synchronizaiton overhead is going to
kill your performance by orders of magnitude over what subroutine calls would have cost.
****
>
>So really, I dont want CAwAvatar to be added or removed while I am looping
>through them, and I do not want the AwAvatar object to be changed by
>anything else while I am actually reading from it, but while I am reading
>from it I need to call functions inside it that change things - even if
>those variables are shielded from obvious view by the class
*****
That's where I'd tend to use queueing models. The painting thread would either be painting
or processing update requests. While it was in its painting loop, it wouldn't be seeing
update requests, so there would be no problem. The risk is that as soon as you have
cycles in the structures, deadlock becomes inevitable if both threads can access the
structure from different roots in the structure. Canonical ordering constraints would
readily be violated.

Another approach I used, when draw performance was an issue, was to "compile" the updated
list into an array of draw requests. I could then draw from the "compiled" array at high
speed while letting alternate threads update the "source" structure. But my update rate
was fairly low, although disruptive to the drawing logic.

Another approach I took was to segment the drawing list, so I could be adding to
"inactive" segments without requiring synchronization overhead in them. I didn't have
cycles to deal with, so it was easy to partition. Since there was only one drawing thread,
and it only locked one segment at a time, I had no deadlock issues to address. If you
could partition the drawing list into logically disjoint segments, then high-performance
synchronization using CRITICAL_SECTION would work pretty well. The only time you would
block the update thread is while a segment was being drawn, and if you make the segments
small enough, this puts an upper bound on the amount of time the insertion thread would be
delayed.

If you are at the tens of items per second, PostMessage/PostThreadMessage should work
fine.

It is unfortunate that the kernel resource known as an "Executive Resource" which allows
multiple readers and a single writer is not exported to user space. It could be done using
a device driver, but at that point, you are into potentially fairly large overheads.

I found two articles on the mutliple-reader-single-writer problem. One uses my earlier
suggestion of a file system lock as the locking primitive; the other refers to a .NET
feature of a multiple-reader-single-writer lock, which is described as the
ReaderWriterLock class. It has a C++ interface, but it would require using .NET
components.
*****
>
>So in summary:
>
>- Looping and Adding to linked list must be mutally exclusive
>- Any data from the avatar should be readable at any time, but should wait
>until all data has finished being updated;
>- Any thread needs to be able to call methods in the avatar class without
>fear of half-way-changing other things in it for something else thats
>reading.
****
The issue is one of "priority". If you need to do an update, RIGHT NOW, then you can
simply use my two-tier approach to allow drawing to get priority over updates. But this
delays the updates. Using Post[Thread]Message or PostQueuedEventStatus (to an I/O
completion port) means the sending threads don't have to block during the drawing, even
though the updates are delayed. The delay could be seen by the user, but not by the
threads generating the update requests.
****
>
>I hope that allows you to suggest anything else you may be able to think of.

Joseph M. Newcomer [MVP]
email: newcomer@xxxxxxxxxxxx
Web: http://www.flounder.com
MVP Tips: http://www.flounder.com/mvp_tips.htm
.

Relevant Pages

  • Re: Multi Threading Options
    ... > If the avatars struct could be modified by any other thread, ... The avatars are handled in the main thread - its the drawing a map of them ... > That is, the avatar struct, intead of being a global variable, is actually ...
    (microsoft.public.vc.mfc)
  • Re: [-mm][PATCH 4/4] Add memrlimit controller accounting and control (v4)
    ... Assuming that we're holding a write lock on mm->mmap_sem here, ... Seems good to minimize additional synchronization on the fast path. ... static struct cgroup_subsys_state * ... goto out_assign; ...
    (Linux-Kernel)
  • Re: threading - Monitor.Wait/Pulse
    ... thread synchronization is considered a "Bad Thing" since there is no way ... WaitOne/WaitAny/WaitAllmethods of the WaitHandle indicates whether ... don't get with WaitHandles is that it releases the Lock on the Object ... RendezvousDemo demo = new RendezvousDemo; ...
    (microsoft.public.dotnet.general)
  • Re: Why "lock" functionality is introduced for all the objects?
    ... very nature of objects in Java. ... synchronization, well, simple. ... can use it as a lock (strictly speaking, a Hoare monitor). ...
    (comp.lang.java.programmer)
  • Re: synchronization demo
    ... two "for" loops at the bottom. ... the Locker struct and BransMonitor class. ... this pattern for synchronization really isn't very useful anyway. ...
    (microsoft.public.dotnet.languages.csharp)