Friday, December 7, 2018

Digest for comp.lang.c++@googlegroups.com - 20 updates in 5 topics

"Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com>: Dec 07 08:36AM +0100

On 07.12.2018 00:23, Paul wrote:
> MaxHeap() : Heap(new int[MAX_HEAP_SIZE], &Greater) { }
 
The use of `Greater` versus `Smaller` seems to be the only difference
between the two classes `MaxHeap` and `MinHeap`.
 
You can make that a parameter in at least three ways:
 
* As a template parameter.
* As a function object constructor argument.
* As a virtual function to be overridden in each class.
 
 
Cheers & hth.,
 
- Alf
Paul <pepstein5@gmail.com>: Dec 07 12:19AM -0800

On Friday, December 7, 2018 at 7:36:56 AM UTC, Alf P. Steinbach wrote:
> * As a virtual function to be overridden in each class.
 
> Cheers & hth.,
 
> - Alf
 
Thanks, but is the code duplication approach, as originally posted considered
bad, or is it a fine example to emulate?
 
Paul
"Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com>: Dec 07 10:20AM +0100

On 07.12.2018 09:19, Paul wrote:
 
>> - Alf
 
> Thanks, but is the code duplication approach, as originally posted considered
> bad, or is it a fine example to emulate?
 
Generally code duplication is frowned on, regarded as ungood, hence the
common advice to keep it DRY (Don't Repeat Yourself).
 
A main reason why it's ungood in the ideal, is that roughly 80% of
development is maintenance, and maintenance can easily introduce
unintenteded differences in a set of code duplications. This then
increases work involved in further maintenance and bug-hunting.
 
However, especially (in my experience) in the defense industry, code
like whole files is very often duplicated, and then some minor changes
are made. It's in practice necessary because the original code is at a
low level of abstraction with no support for e.g. overriding behavior.
And it generates a source of income for the developer, a kind of job
security, as well making the developer seem productive in terms of
number of lines produced per time period, the infamous SLOC metric.
 
Job security: it would cost much more to let some other developer try to
make sense of the spaghetti.
 
Productivity: defense industry people are a very conservative lot in
peace time. During WWII this industry invented the whole field of
logistics and the underlying math of what's now dynamic programming, and
the ideas now underlying ISO certification (as I recall that originated
with ungood quality of bombs made in English factories with mostly
female workers), and much else. But since then it's not progressed
beyond e.g. counting lines of code as a metric of productivity.
 
Of course the defense industry thing is a /management issue/, that it's
too easy for a manager to benefit from taking the short view and passing
the cost on to someone who later gets responsibility for this, and
ultimately it's an issue of people being paid just to conform. But. In
practice it means that for what's "best practice" in C++ one should
better consider the outer context, like who pays, very carefully.
 
 
Cheers!,
 
- Alf
Vir Campestris <vir.campestris@invalid.invalid>: Dec 07 09:17PM

On 07/12/2018 08:19, Paul wrote:
> Thanks, but is the code duplication approach, as originally posted considered
> bad, or is it a fine example to emulate?
 
I've just spent a few days removing some duplication, and I expect to be
doing some more. I'm having to untangle the spaghetti before I dare add
anything new.
 
I found at least one case where some bugs had been fixed in one of the
copies, but not in the other.
 
Then on further examination I found that none of the build
configurations could actually access the second copy. So I've deleted it.
 
Andy
Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk>: Dec 07 08:11PM

Hi!
 
Website for neoGFX side project neoTUI now up at https://neotui.com
 
/Flibble
 
--
"You won't burn in hell. But be nice anyway." – Ricky Gervais
 
"I see Atheists are fighting and killing each other again, over who
doesn't believe in any God the most. Oh, no..wait.. that never happens." –
Ricky Gervais
 
"Suppose it's all true, and you walk up to the pearly gates, and are
confronted by God," Bryne asked on his show The Meaning of Life. "What
will Stephen Fry say to him, her, or it?"
"I'd say, bone cancer in children? What's that about?" Fry replied.
"How dare you? How dare you create a world to which there is such misery
that is not our fault. It's not right, it's utterly, utterly evil."
"Why should I respect a capricious, mean-minded, stupid God who creates a
world that is so full of injustice and pain. That's what I would say."
woodbrian77@gmail.com: Dec 06 06:45PM -0800

> stop using #import now. That will also reduce the amount of rush
> re-writing you'll have to do once they do come out with a version that
> no longer supports it.
 
From what I can tell it has been deprecated for decades:
 
Here:
https://stackoverflow.com/questions/5301019/what-is-the-difference-between-import-and-include-in-c
 
Sylvain Defresne writes:
"It is best to avoid #import (sadly) if you want to write
code portable to multiple compilers."
 
Notice the "sadly". He acknowledges it's helpful, but that
portability considerations limit it's usefulness. And Intel's
ICC, for example, doesn't support #import. But who cares?
 
I don't have Gcc 9 installed. Maybe someone with Gcc 9
could tell if #import support has been preserved.
 
 
Brian
Ebenezer Enterprises
http://webEbenezer.net
David Brown <david.brown@hesbynett.no>: Dec 07 08:08AM +0100

> code portable to multiple compilers."
 
> Notice the "sadly". He acknowledges it's helpful, but that
> portability considerations limit it's usefulness.
 
Stack Overflow can be a useful source of help and information, but
quoting some random person does not have the level of authority you are
implying here. Nobody is going to be influenced by this person's
feelings about #import.
 
> ICC, for example, doesn't support #import. But who cares?
 
> I don't have Gcc 9 installed. Maybe someone with Gcc 9
> could tell if #import support has been preserved.
 
It is highly unlikely to be removed - simply because no one would
prioritise making the change. That does not mean it is a good idea to
use it.
Juha Nieminen <nospam@thanks.invalid>: Dec 07 11:34AM

> I added -Wno-deprecated to get a warning to turn off.
 
I think that you should only turn off that one particular warning
(IIRC gcc supports turning off individual warnings), rather than
*all* warnings of that type. Else you may be missing some other,
more important warnings.
Juha Nieminen <nospam@thanks.invalid>: Dec 07 11:38AM

> include guards. The time saving from #import compared to include guards
> is /tiny/ - and if you have a decent OS and a decent compiler, /really/
> tiny.
 
Clearly you haven't been using for extensive periods of time.
 
You could write that exact same paragraph for tons of other things
(such as range-bosed for loops, for instance). That doesn't mean
those things aren't handy.
 
It's the small things that reduce boilerplate that make programming
more comfortable.
David Brown <david.brown@hesbynett.no>: Dec 07 03:02PM +0100

On 07/12/18 12:38, Juha Nieminen wrote:
>> is /tiny/ - and if you have a decent OS and a decent compiler, /really/
>> tiny.
 
> Clearly you haven't been using for extensive periods of time.
 
Correct. I have not used #import.
 
> those things aren't handy.
 
> It's the small things that reduce boilerplate that make programming
> more comfortable.
 
I agree that the small things are vital. I don't agree that #import is
such a useful small thing.
 
Good compilers will handle include guards as fast as #import. And
include guards are standard, will work correctly in awkward cases (such
as accessing the same file from different filesystem paths), will work
correctly no matter how the file is included (even if someone uses
#import), and make it clear in the header file that this is a once-only
include.
 
So for safe and portable code, you want include guards anyway - and then
#import gives you no benefits. Using #import just gives you bad habits
as you have to change methods when writing code that other people or
other compilers will see.
 
(Once we get proper modules in C++, and a proper "import" mechanism, it
will be a different matter.)
woodbrian77@gmail.com: Dec 07 10:41AM -0800

On Friday, December 7, 2018 at 5:35:00 AM UTC-6, Juha Nieminen wrote:
> (IIRC gcc supports turning off individual warnings), rather than
> *all* warnings of that type. Else you maFy be missing some other,
> more important warnings.
 
Wno-deprecated is the only way I know of to turn it
off. I tried -Wno-import but that didn't turn it off.
scott@slp53.sl.home (Scott Lurndal): Dec 07 07:12PM

>> more important warnings.
 
>Wno-deprecated is the only way I know of to turn it
>off. I tried -Wno-import but that didn't turn it off.
 
#pragma GCC diagnostic push
#pragma GCC diagnostic warning -Wno-deprecated
#import "xyz.h" /* Shouldn't be using #import anyway */
#pragma GCC diagnostic pop
woodbrian77@gmail.com: Dec 07 11:14AM -0800

On Friday, December 7, 2018 at 8:02:52 AM UTC-6, David Brown wrote:
> correctly no matter how the file is included (even if someone uses
> #import), and make it clear in the header file that this is a once-only
> include.
 
If you need to do something like that, then use
#includes. You can mix #import and #include.
 
 
> So for safe and portable code, you want include guards anyway - and then
> #import gives you no benefits.
 
No one is advocating for #import for portable code.
 
> Using #import just gives you bad habits
> as you have to change methods when writing code that other people or
> other compilers will see.
 
"There are rules behind the rules and a unity that is
deeper than uniformity." C.S. Lewis
 
It seems there is some envy of the freedoms that are
afforded closed-source developers.
 
 
Brian
Ebenezer Enterprises
https://github.com/Ebenezer-group/onwards
David Brown <david.brown@hesbynett.no>: Dec 07 08:39PM +0100

> deeper than uniformity." C.S. Lewis
 
> It seems there is some envy of the freedoms that are
> afforded closed-source developers.
 
Your imagination knows no bounds. I write almost exclusively closed
source software. It rarely has to be portable, and I regularly use
compiler extensions or compiler-specific features. That does not mean I
would use a pointless extension which adds nothing to the functionality,
efficiency, elegance, legibility, or correctness of code.
 
You seem to be basing your use of #import on "I /can/ use it, therefore
I /will/ use it", without the slightest indication of any benefit.
 
That, of course, is your own choice for your own code. But please stop
pretending that you have discovered something marvellous that you alone
can use to make better code than anyone else.
scott@slp53.sl.home (Scott Lurndal): Dec 07 08:06PM

>deeper than uniformity." C.S. Lewis
 
>It seems there is some envy of the freedoms that are
>afforded closed-source developers.
 
I'm sorry, but you're wrong. There's no envy involved at all.
 
I primarily work on closed source, and we'd _NEVER_ use a
known deprecated feature. It would be pretty stupid to
do that and find in a year or two that everything is broken
because deprecated feature was removed in the next release
of the compiler.
Paul <pepstein5@gmail.com>: Dec 07 06:57AM -0800

When I think of brace initialization I think of things like
std::vector<int> v {3, 1, 2};
 
I didn't realise though that this could be used with expressions.
When I coded the below, I thought a compile error was likely but it worked fine. It seems that in the context of a definition which is also a declaration,
the braces can replace the = sign. Is this correct? I've never seen it
explained that way.
For example, instead of const int sum = f(a, b, c);
I can now write const int sum{f(a,b,c)};
// Assume f is a function (int, int, int) -> int and that a, b, c
// ints which are defined elsewhere.
 
Thanks,
 
Paul
 
#include <numeric>
#include <cmath>
#include <climits>
 
 
//// Online compiler must be using #include <vector> and namespace std;
// behind the scenes
 
int solution(vector<int> &A) {
// write your code in C++14 (g++ 6.2.0)
const int sum{std::accumulate(A.begin(), A.end(), 0)};

int minDiff = INT_MAX;
int left = A[0];
for(int i = 1; i < A.size(); ++i)
{
const int right = sum - left;
const int diff = std::abs(right - left);
if(diff < minDiff)
minDiff = diff;

left += A[i];
}

return minDiff;
}
"Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com>: Dec 07 05:41PM +0100

On 07.12.2018 15:57, Paul wrote:
> I can now write const int sum{f(a,b,c)};
> // Assume f is a function (int, int, int) -> int and that a, b, c
> // ints which are defined elsewhere.
 
You can also write
 
const int sum( f( a, b, c ) );
 
… but that form is more likely to attract the attention of the Most
Vexing Parse monster.
 
The Most Vexing Parse, disregarding Scott Meyers' original more limited
special case definition, is the rule that anything that /can/ be parsed
as a function declaration will be parsed as a function declaration.
 
---
 
The form
 
T v( args );
 
or
 
T v{ args };
 
is called /direct initialization/, and the form with `=`,
 
T v = something;
 
is called /copy initialization/.
 
---
 
Up till C++17 copy initialization required that a copy or move
constructor was accessible. With C++17 there is some pretty much
impenetrable formal language that requires the elision of actual copy or
move constructor calls in many cases, so that copy initialization can be
used even when the type is not copyable...
 
In C++03 there was no support for defining a class with constructor that
could be initialized with braces syntax.
 
When this support was added in C++11, via the `std::initializer_list`
type, the brace notation from old C was extended to usage also in direct
initialization syntax. Bjarne's goal or vision was that the braces
notation, the original notation from old C, should become a universal
initialization notation also in C++ (e.g., no more Most Vexing Parse, as
long as people just used the new universal notation). However, the
committee, or maybe he, anyway "They"™, bungled it with rules that mean
a constructor with `std::initializer_list` wins overload resolution,
unlike the more practical rules for other stuff where most specific
wins, e.g. `string{ 42, 'x' }` does not equal `string( 42, 'x' )`…
 
 
Cheers & hth.,
 
- Alf
"Chris M. Thomasson" <invalid_chris_thomasson@invalid.invalid>: Dec 06 04:35PM -0800

On 12/5/2018 11:55 PM, Marcel Mueller wrote:
>> scheme? Seqlocks can be pretty nice at getting a fast snapshot:
 
>> https://en.wikipedia.org/wiki/Seqlock
 
> Eh, no, the snapshots require no locking at all.
 
Seqlocks do not necessarily need writers to use locks. They just need to
update the version counts in the proper order. However, readers will
spin if they do not obtain a coherent view of all the memory locations
they are reading from. There is a distributed seqlock over here:
 
http://www.1024cores.net/home/lock-free-algorithms/reader-writer-problem/improved-lock-free-seqlock
 
A lot of pressure is taken off the readers.
 
 
> an older snapshot. All operations act on snapshots. So any object in the
> snapshot is /immutable/ from the readers point of view, again no locking
> required.
 
Kind of sounds something like:
 
https://pdfs.semanticscholar.org/f2c4/05920a129aa8df38ec7cb3d5135283498684.pdf
 
https://ieeexplore.ieee.org/document/4709153
 
Are you use a global version count to derive all of the revision numbers?
 
 
> risk of a deadlock. And of course blocking on I/O when requesting
> entities is not lock free. But the in memory approach avoids this most
> of the time, and no risk of deadlock either.
 
Need to think some more on this. Read it more carefully. Thanks.
 
 
 
> value types. In fact the above application rarely takes more than 0.5
> CPU cores when used by about 100 concurrent users. No need to struggle
> with C++.
 
.NET can work perfectly fine. Although, I would personally use C++ to
build a scalable server that had to handle tens of thousands of
concurrent connections.
 
 
> would avoid such elementary compromises and require adequate hardware.
> This is no big deal nowadays. In general hardware is almost always
> cheaper than workers (for a more flexible solution).
 
Well, the multex is just an example of how it can be done.
 
 
> And in between there might be other options. E.g. packing the two words
> of a DCAS into a single one.
 
How can we do that when DCAS operates on two separate memory locations
that are not contiguous? They can be on completely separate cache lines.
 
 
> safety. The performance impact of the required push of the (small) outer
> reference count to the inner one after each acquire access is
> neglectable, in particular compared to simulated DCAS.
 
I think you might be confusing DWCAS with DCAS.
 
DWCAS operates on a memory location that contains two contiguous words.
DW is double-word.
 
A DCAS operates on two separate memory locations that are not contiguous.
 
Wrt the stolen bits overflowing, well, they certainly can. I can think
of several scenarios. It basically depends on what the stolen bits are
"used for". A reference count? An version count to avoid ABA? Ect...
 
 
 
>>> Dark chapter. Who needs atomics that /might/ be lock free?
 
>> Very dark.
 
> Again a compromise to avoid to drop platforms.
 
;^)
 
 
>> the performance might not be up to par... ;^o
 
> Hmm, a static assertion comes into my mind. C++ might support all
> platforms, a certain application might have minimum requirements.
 
Sounds okay. :^)
Pavel <pauldontspamtolk@removeyourself.dontspam.yahoo>: Dec 06 11:51PM -0500

Chris M. Thomasson wrote:
 
>> Which variation did you solve?
 
> I did one a while back for fun where each diner was a different creature that
> could have more than two hands.
And all n had to be busy to eat? :-)
 
I guess my real question is then: is there still any incidence between
philosophers and chopsticks? In classic problem, a philosopher should grab the
one from his left or his right but cannot get just any across the table I guess
i.e. chopsticks are not fungible. With more than 2 hands, what would be the
"table topology"? :)
 
 
>> Any requirements on fairness / starvation avoidance?
 
> It shall not deadlock. It shall provide forward progress.
Yes, so no restriction on starvation (i.e. the correct solution can end up with
2 philosophers eating intermittently and the 3rd starving to death). This is an
easier problem then.
>> statement, but a chopstick does not have to have a mutex).
 
> It depends on how fine of a grain one uses with the locking scheme. You can lock
> the table. Lock each diner. Lock each chopstick.
 
Because in most real-life tasks every thread has to do more than one thing (in
other words, handle more than one type of event -- let's say, in this problem,
the "main event" is a random time at which a philosopher gets hungry; but still
there should be some "service events" such as "we are out of food (for body or
brain)" i.e. "terminate orderly" or "how are you" i.e. some diagnostics; etc), I
prefer an event loop model. In this case, a philosopher would serve its queue of
events, for the purpose of our example, guarded by a mutex (it actually does not
have to be a mutex; a semaphore would probably be better and in a non-kernel app
where the events are usually inspired by i/o it would be some
wait-for-multiple-event/select/poll/epoll/kqueue). Only one mutex is required to
get locked at the time: to post or receive a message from a thread's queue.
 
I wrote down one solution (also, allowing starvation, resolving conflicts by
always yielding to a peer with lesser id) using a per-philosopher
mutex-protected event queues. Tried to illustrate how I usually design without
locking multiple resources (this is a slight diversion, actually, as usually
there is some I/O so I would not use mutices at all but instead use some select;
but philosophers could still be fed from an eventfd- driven queue (on Linux) so
the principle is same). No simultaneous locking of mutices is required and
achieved parallelism seems quite good: on old Linux machine with 4 very old CPU
cores (1.6 Ghz), 5 philosophers, it takes 3.2 times less real time than total
CPU time. A large chunk is spent in system calls; but this is because actual
meal does nothing at all of substance.
 
$ egrep 'processor\>|cpu MHz' /proc/cpuinfo
processor : 0
cpu MHz : 1600.195
processor : 1
cpu MHz : 1610.742
processor : 2
cpu MHz : 1613.554
processor : 3
cpu MHz : 1599.960
$ time ./dp.fast 10000000
idx:0 nPostponedMeals:0 nEatenMeals:1998464
idx:1 nPostponedMeals:0 nEatenMeals:1999544
idx:2 nPostponedMeals:0 nEatenMeals:1999008
idx:3 nPostponedMeals:0 nEatenMeals:2001252
idx:4 nPostponedMeals:0 nEatenMeals:2001732
TOTAL_N_MEALS:10000000 nEatenMeals:10000000
 
real 0m6.380s
user 0m7.628s
sys 0m12.884s
pavel@bahus:~/probes/DiningPhilosophers$ python -c 'print((7.628+12.884)/6.380)'
3.21504702194
 
The code and makefile are below:
 
--------------- code ------------------
#include <algorithm>
#include <cassert>
#include <chrono>
#include <condition_variable>
#include <cstdlib>
#include <functional>
#include <iostream>
#include <iterator>
#include <mutex>
#include <queue>
#include <thread>
 
using namespace std;
using namespace std::chrono;
 
static constexpr int N_PHILOSOPHERS = 5;
static constexpr int MAX_IDX = N_PHILOSOPHERS - 1;
 
enum Event {
NoEvent,
GetHungry,
YieldToLeftPeer,
YieldToRightPeer,
LeftPeerYielded,
RightPeerYielded,
ReportWhenNotHungry,
NotHungry,
Stop
};
 
class Philosopher;
 
class EventQueue {
public:
EventQueue():
condVar_(),
mutex_(),
queue_() {}
Event getEvent() {
Event event(NoEvent);
unique_lock<mutex> queueUniqueLock(mutex_);
if(queue_.empty())
condVar_.wait(queueUniqueLock);
assert(!queue_.empty());
event = queue_.front();
assert(event != NoEvent);
queue_.pop();
return event;
}
void postEvent(Event event) {
lock_guard<mutex> queueGuard(mutex_);
condVar_.notify_one();
queue_.push(event);
}
private:
condition_variable condVar_;
mutex mutex_;
queue<Event> queue_;
};
 
class Peer {
public:
explicit Peer(bool ownsChopstick):
eventQueue_(nullptr),
knowsToYield_(false),
ownsChopstick_(ownsChopstick) {}
void clearKnowsToYield() { knowsToYield_ = false; }
void clearOwnsChopstick() { ownsChopstick_ = false; }
Event getEvent() { return eventQueue_->getEvent(); }
int idx() const { return idx_; }
void init(EventQueue& eventQueue, int idx) {
eventQueue_ = &eventQueue;
idx_ = idx;
}
bool knowsToYield() const { return knowsToYield_; }
bool ownsChopstick() const { return ownsChopstick_; }
void postEvent(Event event) { eventQueue_->postEvent(event); }
void setKnowsToYield() { knowsToYield_ = true; }
void setOwnsChopstick() { ownsChopstick_ = true; }
private:
EventQueue* eventQueue_;
int idx_;
bool knowsToYield_;
bool ownsChopstick_;
};
 
class Philosopher {
public:
Philosopher():
eventQueue_(),
greaterPeerIsHungry_(false),
idx_(-1),
leftPeer_(false),
mainEventQueue_(nullptr),
nEatenMeals_(0),
needToReportNotHungry_(false),
nPostponedMeals_(0),
rightPeer_(true),
workerThread_(Work, ref(*this)) {}
void dump(ostream& os) const {
os << " idx:" << idx_ << " nPostponedMeals:" << nPostponedMeals_ <<
" nEatenMeals:" << nEatenMeals_;
}
void init(int idx, const Philosopher *peers, EventQueue& mainEventQueue);
void join() { workerThread_.join(); }
int nEatenMeals() const { return nEatenMeals_; }
void postEvent(Event event) { eventQueue_.postEvent(event); }
Event getEvent() { return eventQueue_.getEvent(); }
static void Work(Philosopher& philosopher) { philosopher.work(); }
void work();
private:
bool askPeerToYieldIfNeeded(Peer& peer, Event yieldEvent);
EventQueue& eventQueue() const { return eventQueue_; }
void eatPostponedMeals();
void eatTheOnlyMeal();
void grabChopstick(Peer& peer);
void handlePeerYielded(Peer& yieldedPeer, Peer& otherPeer,
Event otherPeerYieldEvent);
bool hungry() const { return !!nPostponedMeals_; }
bool lessThanPeer(const Peer& peer) { return idx_ < peer.idx(); }
void reportNotHungry();
void resetGreaterPeerIsHungry();
void yieldIfNeeded(Peer &peer, Event yieldedEvent);
void yieldToGreaterPeerIfNeeded();
 
mutable EventQueue eventQueue_;
bool greaterPeerIsHungry_;
int idx_;
Peer leftPeer_;
EventQueue* mainEventQueue_;
int nEatenMeals_;
bool needToReportNotHungry_;
int nPostponedMeals_;
Peer rightPeer_;
thread workerThread_;
};
 
ostream&
operator<<(ostream& os, const Philosopher& p)
{
p.dump(os);
return os;
}
 
int
main(int argc, char *argv[])
{
EventQueue mainEventQueue;
Philosopher philosophers[N_PHILOSOPHERS];
for (int i = 0; i < N_PHILOSOPHERS; ++i)
philosophers[i].init(i, philosophers, mainEventQueue);
 
constexpr int TOTAL_N_MEALS_DFLT = 1000 * 1000;
const int TOTAL_N_MEALS = argc == 1 ? TOTAL_N_MEALS_DFLT : atoi(argv[1]);
 
for(int nTestsLeft = TOTAL_N_MEALS; nTestsLeft--;) {
const int idx = rand() % N_PHILOSOPHERS;
Philosopher& philosopher = philosophers[idx];
philosopher.postEvent(GetHungry);
}
 
for(auto& philosopher: philosophers)
philosopher.postEvent(ReportWhenNotHungry);
 
for(int nToReport = N_PHILOSOPHERS; nToReport > 0; --nToReport) {
Event e = mainEventQueue.getEvent(); // wait for all to get not hungry
assert(e == NotHungry);
}
 
for(auto& philosopher: philosophers)
philosopher.postEvent(Stop);
 
for(auto& philosopher: philosophers)
philosopher.join();
 
for(auto& philosopher: philosophers) // print philosophers
cout << philosopher << endl;
 
const int nEatenMeals = accumulate(begin(philosophers), end(philosophers), 0,
[](int a, const Philosopher& p) { return a + p.nEatenMeals(); });
 
cout << "TOTAL_N_MEALS:" << TOTAL_N_MEALS << " nEatenMeals:" << nEatenMeals <<
endl;
 
 
return 0;
}
 
bool
Philosopher::askPeerToYieldIfNeeded(Peer& peer, Event yieldEvent)
{
if (!peer.ownsChopstick())
return false;
if (peer.knowsToYield())
return false;
peer.postEvent(yieldEvent);
peer.setKnowsToYield();
return true;
}
 
void
Philosopher::eatPostponedMeals()
{
assert(!!nPostponedMeals_);
nEatenMeals_ += nPostponedMeals_;
nPostponedMeals_ = 0;
if(needToReportNotHungry_) {
reportNotHungry();
needToReportNotHungry_ = false;
}
}
 
void
Philosopher::eatTheOnlyMeal()
{
assert(!nPostponedMeals_);
++nEatenMeals_;
}
 
void
Philosopher::grabChopstick(Peer& peer)
{
assert(hungry());
peer.clearOwnsChopstick();
}
 
void
Philosopher::handlePeerYielded(Peer& yieldedPeer, Peer& otherPeer,
Event otherPeerYieldEvent)
{
yieldedPeer.clearKnowsToYield();
grabChopstick(yieldedPeer);
if (askPeerToYieldIfNeeded(otherPeer, otherPeerYieldEvent)) {
assert(otherPeer.ownsChopstick());
return;
}
if (otherPeer.ownsChopstick())
return;
eatPostponedMeals();
yieldToGreaterPeerIfNeeded();
}
 
void
Philosopher::init(int idx, const Philosopher *peers, EventQueue& mainEventQueue)
{
assert(idx >= 0);
assert(idx <= MAX_IDX);
idx_ = idx;
leftPeer_.init(peers[idx == 0 ? MAX_IDX : idx - 1].eventQueue(), idx);
rightPeer_.init(peers[idx == MAX_IDX ? 0 : idx + 1].eventQueue(), idx);
mainEventQueue_ = &mainEventQueue;
}
 
void
Philosopher::work()
{
for(Event event = getEvent(); ; event = getEvent()) {
assert(event != NoEvent);
switch(event) {
case GetHungry:
if (askPeerToYieldIfNeeded(leftPeer_, YieldToRightPeer) ||
askPeerToYieldIfNeeded(rightPeer_, YieldToLeftPeer)) {
++nPostponedMeals_;
break;
}
if (rightPeer_.ownsChopstick() || leftPeer_.ownsChopstick()) {
++nPostponedMeals_;
break;
}
eatTheOnlyMeal();
yieldToGreaterPeerIfNeeded();
break;
case YieldToLeftPeer:
yieldIfNeeded(leftPeer_, RightPeerYielded);
break;
case YieldToRightPeer:
yieldIfNeeded(rightPeer_, LeftPeerYielded);
break;
case LeftPeerYielded:
handlePeerYielded(leftPeer_, rightPeer_, YieldToLeftPeer);
break;
case RightPeerYielded:
handlePeerYielded(rightPeer_, leftPeer_, YieldToRightPeer);
break;
case ReportWhenNotHungry:
if(!hungry())
reportNotHungry();
else
needToReportNotHungry_ = true;
break;
case Stop:
return;
default:
assert(false);
}
}
}
 
void
Philosopher::reportNotHungry()
{
mainEventQueue_->postEvent(NotHungry);
}
 
void
Philosopher::resetGreaterPeerIsHungry()
{
greaterPeerIsHungry_ = false;
}
 
void
Philosopher::yieldIfNeeded(Peer &peer, Event yieldedEvent)
{
if(lessThanPeer(peer)) {
if(hungry()) {
if(!greaterPeerIsHungry_)
greaterPeerIsHungry_ = true;
return; // don't yield
}
if(greaterPeerIsHungry_) {
resetGreaterPeerIsHungry();
}
}
if(peer.ownsChopstick()) // we yielded it before, after eating
return;
peer.setOwnsChopstick();
peer.postEvent(yieldedEvent);
}
 
void
Philosopher::yieldToGreaterPeerIfNeeded()
{
if(!greaterPeerIsHungry_)
return;
resetGreaterPeerIsHungry();
const bool leftPeerIsGreater = lessThanPeer(leftPeer_);
Peer& greaterPeer = leftPeerIsGreater ? leftPeer_ : rightPeer_;
const Event yieldedEvent = leftPeerIsGreater ? RightPeerYielded :
LeftPeerYielded;
greaterPeer.setOwnsChopstick();
greaterPeer.postEvent(yieldedEvent);
}
 
/* TODO:
* - could cache lessThanPeer for both peers;
*/
 
---------------------- makefile: -------------------
dp: dp.cpp
g++ -g -pthread -std=c++11 $< -o $@
 
dp.fast: dp.cpp
g++ -O3 -funroll-loops -g -pthread -std=c++11 $< -o $@
"Chris M. Thomasson" <invalid_chris_thomasson@invalid.invalid>: Dec 06 09:08PM -0800

On 12/6/2018 8:51 PM, Pavel wrote:
 
>> I did one a while back for fun where each diner was a different creature that
>> could have more than two hands.
> And all n had to be busy to eat? :-)
 
Big time... For stress testing, yes... :^)
 
 
> one from his left or his right but cannot get just any across the table I guess
> i.e. chopsticks are not fungible. With more than 2 hands, what would be the
> "table topology"? :)
 
Imagine a field line of the following rendering being a fractal hand as
it approaches the unit circle, which represents the table:
 
https://plus.google.com/101799841244447089430/posts/457Kzv21gFp
 
n-ary diners at a table:
 
https://plus.google.com/101799841244447089430/posts/gYcUXTN5zBb
 
Now, we can create a little network here. Tangents are sync points?
 
 
 
> Yes, so no restriction on starvation (i.e. the correct solution can end up with
> 2 philosophers eating intermittently and the 3rd starving to death). This is an
> easier problem then.
 
Every diner shall complete their transaction without deadlock, or
livelock. It will complete. This basically handles starvation by
default. Each diner always gains forward progress. A diner starving to
death means it never got to participate in the forward progress, thus
violating the property.
 
 
>> the table. Lock each diner. Lock each chopstick.
 
> Because in most real-life tasks every thread has to do more than one thing (in
> other words, handle more than one type of event
 
Agreed. This is a simple example of a lock-based sync primitive that be
used.
 
 
> there should be some "service events" such as "we are out of food (for body or
> brain)" i.e. "terminate orderly" or "how are you" i.e. some diagnostics; etc), I
> prefer an event loop model.
 
[...]
 
Event driven is a fun solution as well. Fwiw, check this out for a fast
MPMC queue:
 
https://groups.google.com/d/topic/lock-free/acjQ3-89abE/discussion
(read all...)
 
It is mod based, so, nice for a unitary angle formation of diners.
You received this digest because you're subscribed to updates for this group. You can change your settings on the group membership page.
To unsubscribe from this group and stop receiving emails from it send an email to comp.lang.c+++unsubscribe@googlegroups.com.
Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)