Wednesday, June 26, 2019

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

ram@zedat.fu-berlin.de (Stefan Ram): Jun 26 05:32PM

>"Effects: Determines the lowest position xpos, if possible, such that
>both of the following conditions
 
C++ and boost now use the "Effects: " label, which is good,
because it makes clear which effects a call has.
 
OTOH, it is sad to see this used incorrectly by authors
writing for both boost and C++.
 
The whole process of the determination of a result should
be described either without a label or under the label
"Returns: ", because this has nothing to do with an effect.
 
An effect is everything that is /changed/ by the call,
excluding internal operations that only can be observed
indirectly via the value (result) of the call.
 
A /correct/ example (written by me for this post):
 
//! <b>Effects</b>: prints "example".
//! <b>Returns</b>: the value of pi, determined by
//! evaluating atan2( 1, 1 ) and multiplying it by 4.
double f()
{ ::std::cout << "example";
return 4 * atan2( 1, 1 ); }
 
But it is even better not to talk about implementation
details as much as possible:
 
//! <b>Effects</b>: prints "example".
//! <b>Returns</b>: the value of pi
double f()
{ ::std::cout << "example";
return 4 * atan2( 1, 1 ); }
 
.
James Kuyper <jameskuyper@alumni.caltech.edu>: Jun 25 04:37PM -0700

On Saturday, June 22, 2019 at 6:56:25 AM UTC-4, David Brown wrote:
> individual using them (they work far better when combined with "kill
> thread" or "kill sub-thread" features). But they are totally
> ineffective at keeping bad posts, or bad posters, out of the group.
 
You shouldn't criticize something as ineffectual without taking into
consideration what effect it was intended to achieve. Not seeing Rick's
posts is an achievable goal. As you yourself admit above, keeping bad
posts out of the group is not. Keith set his goal accordingly, and his
killfile is fairly effective at achieving that goal.
Keith Thompson <kst-u@mib.org>: Jun 25 05:38PM -0700

> posts is an achievable goal. As you yourself admit above, keeping bad
> posts out of the group is not. Keith set his goal accordingly, and his
> killfile is fairly effective at achieving that goal.
 
Exactly. But its effectiveness is limited by people who insist on
replying to, and quoting, Rick's spam.
 
--
Keith Thompson (The_Other_Keith) kst-u@mib.org <http://www.ghoti.net/~kst>
Will write code for food.
void Void(void) { Void(); } /* The recursive call of the void */
rick.c.hodgin@gmail.com: Jun 25 05:46PM -0700

On Tuesday, June 25, 2019 at 8:38:56 PM UTC-4, Keith Thompson wrote:
> Exactly. But its effectiveness is limited by people who insist on
> replying to, and quoting, Rick's spam.
 
 
It wouldn't be hard to add a filter based on content. Anywhere
you see "Rick C. Hodgin" or "Hodgin" even, delete the entire post.
It doesn't have to come from me. It could just mention me any-
where and be deleted.
 
Thunderbird's email/news client has this ability.
 
--
Rick C. Hodgin
David Brown <david.brown@hesbynett.no>: Jun 26 06:33PM +0200

On 26/06/2019 01:37, James Kuyper wrote:
> posts is an achievable goal. As you yourself admit above, keeping bad
> posts out of the group is not. Keith set his goal accordingly, and his
> killfile is fairly effective at achieving that goal.
 
Yes, I agree - which was the point of my post. I had said Keith's
methods were ineffectual, but I had been thinking about different goals
- my post explained that. Keith's method is reasonable effective for
his goals, though not quite as good as he would like. They would work
better when combined with "kill sub-thread" features, but I assume he
has good reason for not using such tools. His methods would work
reasonably if everyone followed them, but I don't think that is a
realistic prospect.
 
This is an open group. Posters and posts that people don't like is the
cost of that. If we are able to minimise that cost, either for the
group as a whole or for individuals, great.
David Brown <david.brown@hesbynett.no>: Jun 26 06:26PM +0200

On 25/06/2019 21:53, Scott Lurndal wrote:
 
> In order to make a limit register work, you need a dedicated instruction to adjust
> the stack pointer - you can't use the ADD instruction as we do today (unless you
> generate code to test against the limit, like Microsoft does).
 
I was suggesting it as a feature in the hardware, in the cpu ISA. Then
you could make it a dedicated instruction or a special feature of add
instructions targeting the dedicated SP register.
 
James Kuyper <jameskuyper@alumni.caltech.edu>: Jun 25 09:58PM -0400

On 6/25/19 4:05 AM, Ralf Goertz wrote:
...
> As an aside: What find algorithm does basic_string::find() use? Does it
> do something more sophisticated than the naïve way?
 
As it normally is, the standard is silent on the algorithm used,
defining only the results. There's many different overloads for find(),
and several variant of find, but they are all specified in a fashion
similar, in this regard, to the first one:
 
"Effects: Determines the lowest position xpos, if possible, such that
both of the following conditions
obtain:
— pos <= xpos and xpos + str.size() <= size();
— traits::eq(at(xpos+I), str.at(I)) for all elements I of the string
controlled by str." (21.4.7.2p1).
 
The algorithm used is chosen by the implementor, and therefore depends
upon which implementation you are using.
Ralf Goertz <me@myprovider.invalid>: Jun 26 10:41AM +0200

Am Tue, 25 Jun 2019 17:39:58 +0200
> cout << tester << endl;
> }
 
> However, since it's UB it's not /guaranteed/ to produce garbage.
 
Okay, but shouldn't the compiler warn about that? I mean it's fairly
obvious (at least after having read how string_view is constructed).
 
> https://en.cppreference.com/w/cpp/algorithm/search>. But this
> newfangled stuff isn't necessarily available with any particular
> compiler yet.
 
Thanks, I changed to std::boyer_moore_searcher. That indeed sped up the
program considerably (after interchanging corpus and pattern). Now I
could also use vector<char> instead of string which also had a very
noticable effect. Together, the "9 9" case is 1 second compared to the
2.5 seconds before.
Juha Nieminen <nospam@thanks.invalid>: Jun 26 12:11PM

> string const tester=permuter+permuter.substr(0,permuter.size()-1); //*
 
If you are aiming for the utmost extreme speed and optimization, lines
like this should *immediately* ring alarm bells in your head.
 
std::string uses dynamic memory allocation, and lines like that are
doing them in droves. This is especially problematic when you are
just dealing with byte arrays of fixed sizes (with the size being
determined before the algorithm even begins), which usually means
you can get away with just one or a handful of allocations, and no
dynamic allocations of any kind during the execution of the algorithm
(other than, possibly, adding the result to some dynamic data
container, which usually isn't a problem).
 
Dynamic memory allocation is notoriously inefficient for many reasons,
and using pre-allocated non-size-changing buffers over and over is
often the best approach. Doing dynamic allocations in the inner loops
of your computationally heavy algorithms is going to kill the efficiency.
(There are situations where it simply can't be avoided, but if you can
avoid it, you should.)
Ralf Goertz <me@myprovider.invalid>: Jun 26 02:42PM +0200

Am Wed, 26 Jun 2019 12:11:57 -0000 (UTC)
> of your computationally heavy algorithms is going to kill the
> efficiency. (There are situations where it simply can't be avoided,
> but if you can avoid it, you should.)
 
That's what I did now. (See also my answer to Alf.) The relevant changes
are the following:
 
size_t const size=permuter.size();
vector<char> tester(size*2-2);
do {
bool found(false);
boyer_moore_searcher b(permuter.begin(),permuter.end());
for (int i=0;i<result.size();++i) {
copy(result[i].begin()+1,result[i].end(), tester.begin());
copy(result[i].begin() ,result[i].end()-1,tester.begin()+size-1);
if (b(tester.begin(),tester.end()).first!=tester.end()) {
found=true;
break;
}
}
if (!found) {
result.push_back(permuter);
if (result.size()==bin) {
cout<<bin<<endl;
bin<<=1;
}
}
} while (next_permutation(permuter.begin()+1,permuter.end()));
Tim Rentsch <tr.17687@z991.linuxsc.com>: Jun 25 11:15PM -0700

> also others might learn something or at least be guided to think
> about something if you explain the practical utility of the
> distinction.
 
Ah, this is a good comment. I should explain the difference
between the two categories of errors. I hadn't thought of it
in just those terms before.
 
To identify the two categories let's use the terms "program
error" and "execution error". A "program error" is one that
depends only on the state of the abstract machine, and includes
things like dereferencing a null pointer and other similar items
like those listed in Annex J.2 of the C standard. (The C++
standard doesn't have a list like J.2 in the C standard AFAICT.)
The term "program error" corresponds to what I believe is meant
by the term "undefined behavior" in the C and C++ standards, if
we gloss over the cases of compile-time error that don't ever get
to the abstract machine (for example, a source file not ending in
a newline).
 
An "execution error" is one that depends in some way on the state
of the actual machine during execution (perhaps in addition to
depending on the state of the abstract machine, but the key
element is some dependence on the state of the actual machine).
"Execution errors" include things like stack overflow, running
out of swap space, or a failing logic path in the CPU. In all
cases of "execution error" there is (by definition) some aspect
that is not addressed by the language definition. I don't mean
not /defined/ by the standard, but not referred to at all in any
normative text. For example, many computer systems have ECC
memory chips, but the standards don't consider such things at
all. An uncorrected two-bit memory error is an "execution
error", because it depends on stuff outside what the language
definition talks about.
 
Probably the most important difference between "program errors"
and "execution errors" is this: for "program errors", we know
what they depend on and in all cases can revise the program
source to avoid any actual or potential "program errors". For
example, before dereferencing a pointer value the program
could check to see if the value is a null pointer (and not do
the dereference, obviously). In contrast, for "execution errors"
we may not know what they depend on, and worse, /whatever/ they
depend on is outside what the C or C++ standards address; hence
there is no guarantee about whether or what program change might
fix it, or for which systems the fix would apply. In this sense
we could say that "execution errors" are _worse_ than undefined
behavior, because unlike "program errors" there are no guarantees
(and certainly no portable guarantees) about what program changes
will alleviate the problem.
 
 
> mostly at run time and sometimes detectable in at least global
> view of things at build time, one wouldn't be able to draw the
> same conclusion?
 
Almost any program that runs reliably might be a good example
here. To give a concrete example, consider the following
trivial program:
 
int
main( int argc, char *argv[] ){
char a[4096] = { 0 };
return a[ 4000 ];
}
 
Assuming I haven't made any stupid mistakes, the program has no
"program errors". It has well-defined behavior and is portable
to all conforming hosted C implementations (and probably C++ also
but I'm not as familiar with the C++ standard as I am with the C
standard). But these statements don't apply to "execution
errors". If run, for example, after setting the stack space
limit to 1K, it might fail. If we run the program today on an
unloaded system and tomorrow on a very heavily loaded system it
might work today and not work tomorrow. Or it might work on
system X but not work on system Y, even if they have exactly the
same hardware but perhaps different versions of the OS (ubuntu 16
and ubuntu 18, let's say). The problem is we don't know, and
nothing in the language standards will help us, because (by
definition) "execution errors" are things that depend on aspects
outside of what the C and C++ standards address.
 
Does this help clarify what I'm trying to get at?
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)