On Mon, 8 Apr 2024 14:09:32 +0200
Bonita Montero <Bonita.Montero@gmail.com> wrote:

> Am 08.04.2024 um 10:15 schrieb Michael S:
>
> > What exactly is nonsense?
> > You are saying approximately the same that I said above.
>
> You said that a cusom implementation of a RB- or AVL-tree is multiple
> times faster. I said that this depends on the tree's properties
> because you've got pointer chasing with trees; and you can't improve
> that with a custom implementation.
>

I never said what you think I said.
In fact, I said an opposite - that bigger factors could happen only when
competing structure/algorithm is *not* a balanced binary tree of any
sort.

> > On x86-64 with MSVC/gcc/clang each std::set/multiset node occupies
> > 32 bytes even when key is only 32 bits. ...
>
> There ar three pointers: to the parent and to the children and if a
> RB-tree is used there's a flag that determines the colour of the node.
> There's nothing to get around that.

There is little (not nothing, see below) to do about it under
restrictions of std API. In the absence of restrictions several thing
possible.

Even under restrictions of std API, parent link is not strictly
necessary. In absence of knowledge about expected usage, it's probably
wise to have it. But when the usage is known there are cases where one
would do better without it. Such cases are not even too rare.

And if you wonder, no, I don't think that taken in isolation removal
of parent link could provide measurable gain. It's just one example of
what could be done when you are determined to shrink the size of the
node.

On 08/04/2024 12:34, Michael S wrote:
> On Mon, 8 Apr 2024 11:29:11 +0200
> David Brown <david.brown@hesbynett.no> wrote:
>
>> On 07/04/2024 18:35, Michael S wrote:
>>
>>> Partially balanced binary trees, like those used by std::map and by
>>> its relatives, are among the most predictable data structures out
>>> here. Certainly they are far more predictable than generic hash
>>> that in the worst case degenerates into O(N).
>>> OTOH, in std::map of given size the difference in worst access time
>>> between perfectly balanced case and most unbalanced case is only
>>> 2x. And that applies not just for lookup, but for insertion and
>>> deletion as well.
>>>
>>
>> As far as I know, details of how containers such as std::map are
>> implemented are left to the implementation - they are not guaranteed
>> by the standards.
>>
>> Different types of systems have different needs. C++ supports a huge
>> range of uses, and for some of them, many parts of the standard
>> library are simply out of the question. The point was just that
>> claims such as Bonita's that "it is impossible to use C++ without
>> exception[s]", or that if you don't use the standard library you are
>> "missing most of C++", are just ignorant nonsense. People can choose
>> what they need based on a range of requirements and preferences, and
>> that's exactly what we want from a general-purpose language.
>>
>
> My opinion about standard library is very close to that Bonita, even if
> possibly possibly for the opposite reasons.
> IMHO, if you can't make good use of either C++ Standard library or of
> the other key feature of the language - virtual functions, then it is
> wiser to avoid C++ altogether.

Sorry to say, but I think that is an absurd attitude.

There is a cost to using C++, rather than C. You lose a couple of
features (such as compound literals), and there are few very minor cases
where the same code is valid as C and C++ but has slightly different
semantics. You need a C++ compiler (rarely an issue these days). You
lose the clear match between HLL identifiers and generated code identifiers.

Perhaps the biggest cost risk is that it opens doors for some people in
a team to write code that others in the team don't understand. But that
is a development process issue that can apply regardless of language choice.

So often, the cost of using C++ rather than C is small. That means you
only need minor benefits before it is worth making the change. And
there are a /lot/ of features of C++ that can be used to benefit the
code, even when the style is basically C.

This means it can be wise to move to C++ merely to get better type
checking for enumerated types, nicer "const", and fewer uses of "typedef".

In my last embedded C++ project, some of the C++ features I have made
heavy use of include :

* classes
* template classes (on classes and non-class template parameters)
* CRTP (compile-time polymorphism)
* class inheritance, including multiple inheritance for methods, but
without run-time polymorphism
* namespaces
* strong enumerations
* RAII
* std::optional<> and std::variant<>
* references
* constexpr functions
* inline variables
* function overloads
* std::array<>
* lambdas
* auto

Some things I have not used include :

* virtual functions
* "big" standard library features such as iostreams or containers (other
than std::array)
* exceptions
* rtti
* new, delete, or other allocations

Should I not have used C++ ? Should I have stuck to C because some
people think that feature X is the be-all and end-all of C++ ?

> BTW, I *don't* use C++ on small embedded targets. More so, I don't use
> it on moderately-sized embedded targets, say, 8-16 MB of RAM, 100-200
> MHz CPU, but without protected memory and without full-featured OS.

I don't have a lower bound for use of C++.

It certainly used to be the case that C++ was unsuitable for very small
systems - indeed, there was a time when C was unsuitable for very small
systems. But C++ and C++ tools have improved greatly, and the power of
"very small" embedded systems has gone up. In the past decade at least,
I've only used C for continuing work on existing programs or working
with other people's C projects (though of course that's a large part of
the job).

> My reasons are more psychological/managerial than technical - to keep
> away developers with wrong mindsets and to prevent those that I can't
> keep away from turning wrongest parts of their mindsets to full volume.
>

Those reasons I can understand. Developers with the wrong mindset can
do harm faster with C++ than with C.

On Mon, 08 Apr 2024 19:18:06 +0800
wij <wyniijj5@gmail.com> wrote:

>
> I would say that maybe you don't know how to use C++ effectively.
>

It is possible.
But more likely that relatively to you I have longer experience in C++
and better understanding of both advantages and disadvantages.

07.04.2024 19:09 Scott Lurndal kirjutas:
>
> The biggest problem I have with std::map is that you cannot
> define a compile time map. For the application where we use
> map, the maps can be quite large (hundreds or thousands of entries)
> and initialization of those maps impacts application startup time
> significantly (several hundred distinct maps).
>
> We're planning on replacing std::map with a custom class optimized
> to efficiently handle the data (mmap'd disk file generated by
> a python script). A binary search on the primary key is the likely
> search algorithm. The maps don't change during application execution.

If the map does not change during run, then there is no need to use any
map-like data structures or mmap files, a pre-sorted static array should
be fine for most cases. I am having multiple such "compile-time maps",
as they are not so large (tens and hundreds of entries) and do not
change often, I am maintaining them just by hand, no pre-processing
complications needed. I do not really trust my sorting abilities, so I
always also have a small function which is checking the array order (in
the Debug build, or in a unit test). A bare-bone demo:

struct A {
int x;
double y;
};

struct Entry {
std::string_view key;
A a;
};

static constexpr const Entry gLookup[] = {
{ "alpha", {1, 10.0}},
{ "beta", {2, 20.0}},
{ "gamma", {3, 30.0}}
};

#ifdef _DEBUG
// Check that I have pre-sorted my array correctly.
static struct CheckLookupTable {
CheckLookupTable() {
for (size_t i = 1; i < std::size(gLookup); ++i) {
assert(gLookup[i].key > gLookup[i - 1].key);
}
}
} gCheck;
#endif

const A* Lookup(std::string_view searchKey) {
auto it = std::lower_bound(
std::begin(gLookup),
std::end(gLookup),
searchKey,
[](const Entry& a, std::string_view b) {return a.key < b; });

return ((it != std::end(gLookup) && it->key == searchKey) ?
&(it->a):
nullptr);
}

On 08/04/2024 13:10, Richard Damon wrote:
> On 4/8/24 5:29 AM, David Brown wrote:
>> On 07/04/2024 18:35, Michael S wrote:
>>
>>> Partially balanced binary trees, like those used by std::map and by its
>>> relatives, are among the most predictable data structures out here.
>>> Certainly they are far more predictable than generic hash that in the
>>> worst case degenerates into O(N).
>>> OTOH, in std::map of given size the difference in worst access time
>>> between perfectly balanced case and most unbalanced case is only
>>> 2x. And that applies not just for lookup, but for insertion and
>>> deletion as well.
>>>
>>
>> As far as I know, details of how containers such as std::map are
>> implemented are left to the implementation - they are not guaranteed
>> by the standards.
>>
>> Different types of systems have different needs.  C++ supports a huge
>> range of uses, and for some of them, many parts of the standard
>> library are simply out of the question.  The point was just that
>> claims such as Bonita's that "it is impossible to use C++ without
>> exception[s]", or that if you don't use the standard library you are
>> "missing most of C++", are just ignorant nonsense.  People can choose
>> what they need based on a range of requirements and preferences, and
>> that's exactly what we want from a general-purpose language.
>>
>
> The Standard gives complexity guarantees for some operations on most
> containers which largely limit what sort of method can be used by each
> of them.

The complexity guarantees in the standard are vague - they are given as
an indication of "time and/or space complexity", and I assume they mean
the average or amortized complexity. That's fine for general use, but
not for real-time systems. (Some people distinguish between "hard
real-time" and "soft real-time" - the C++ standard guarantees /might/ be
acceptable for some "soft real-time" uses.)

Am 08.04.2024 um 15:26 schrieb Michael S:

> Even under restrictions of std API, parent link is not strictly
> necessary.

This would make iterators large since they's have to carry a stack
ov parent nodes.

Michael S <already5chosen@yahoo.com> writes:
>On Mon, 8 Apr 2024 11:29:11 +0200
>David Brown <david.brown@hesbynett.no> wrote:
>
>> On 07/04/2024 18:35, Michael S wrote:
>>
>> > Partially balanced binary trees, like those used by std::map and by
>> > its relatives, are among the most predictable data structures out
>> > here. Certainly they are far more predictable than generic hash
>> > that in the worst case degenerates into O(N).
>> > OTOH, in std::map of given size the difference in worst access time
>> > between perfectly balanced case and most unbalanced case is only
>> > 2x. And that applies not just for lookup, but for insertion and
>> > deletion as well.
>> >
>>
>> As far as I know, details of how containers such as std::map are
>> implemented are left to the implementation - they are not guaranteed
>> by the standards.
>>
>> Different types of systems have different needs. C++ supports a huge
>> range of uses, and for some of them, many parts of the standard
>> library are simply out of the question. The point was just that
>> claims such as Bonita's that "it is impossible to use C++ without
>> exception[s]", or that if you don't use the standard library you are
>> "missing most of C++", are just ignorant nonsense. People can choose
>> what they need based on a range of requirements and preferences, and
>> that's exactly what we want from a general-purpose language.
>>
>
>My opinion about standard library is very close to that Bonita, even if
>possibly possibly for the opposite reasons.
>IMHO, if you can't make good use of either C++ Standard library or of
>the other key feature of the language - virtual functions, then it is
>wiser to avoid C++ altogether.

Now that's just as silly as Bonita's position

>BTW, I *don't* use C++ on small embedded targets.

I do, and have. Two operating commercial operating
systems, a hypervisor, and SoC microcode; all in C++ (with some legacy
C device drivers loaded dynamically). Using a rational
subset of C++ (with little run-time overhead) makes perfect
sense for such an application given the data hiding and
interface advantages of C++ over say, C.

Because _you_ don't do something doesn't generalize.

On Mon, 8 Apr 2024 16:54:02 +0200
Bonita Montero <Bonita.Montero@gmail.com> wrote:

> Am 08.04.2024 um 15:26 schrieb Michael S:
>
> > Even under restrictions of std API, parent link is not strictly
> > necessary.
>
> This would make iterators large since they's have to carry a stack
> ov parent nodes.
>
>

For modifications, yes. But that's still only LogN, but in time and in
size of temporary storage. And search from root which in majority of
workloads is the most common operation by far, is not affected.

On Mon, 8 Apr 2024 20:52:53 +0300
Michael S <already5chosen@yahoo.com> wrote:

> On Mon, 8 Apr 2024 16:54:02 +0200
> Bonita Montero <Bonita.Montero@gmail.com> wrote:
>
> > Am 08.04.2024 um 15:26 schrieb Michael S:
> >
> > > Even under restrictions of std API, parent link is not strictly
> > > necessary.
> >
> > This would make iterators large since they's have to carry a stack
> > ov parent nodes.
> >
> >
>
> For modifications, yes. But that's still only LogN, but in time and in
> size of temporary storage. And search from root which in majority of
> workloads is the most common operation by far, is not affected.
>

I meant to write "both in time and etc..."

On Mon, 08 Apr 2024 17:19:19 GMT
scott@slp53.sl.home (Scott Lurndal) wrote:

> Michael S <already5chosen@yahoo.com> writes:
> >On Mon, 8 Apr 2024 11:29:11 +0200
> >David Brown <david.brown@hesbynett.no> wrote:
> >
> >> On 07/04/2024 18:35, Michael S wrote:
> >>
> >> > Partially balanced binary trees, like those used by std::map and
> >> > by its relatives, are among the most predictable data structures
> >> > out here. Certainly they are far more predictable than generic
> >> > hash that in the worst case degenerates into O(N).
> >> > OTOH, in std::map of given size the difference in worst access
> >> > time between perfectly balanced case and most unbalanced case is
> >> > only 2x. And that applies not just for lookup, but for insertion
> >> > and deletion as well.
> >> >
> >>
> >> As far as I know, details of how containers such as std::map are
> >> implemented are left to the implementation - they are not
> >> guaranteed by the standards.
> >>
> >> Different types of systems have different needs. C++ supports a
> >> huge range of uses, and for some of them, many parts of the
> >> standard library are simply out of the question. The point was
> >> just that claims such as Bonita's that "it is impossible to use
> >> C++ without exception[s]", or that if you don't use the standard
> >> library you are "missing most of C++", are just ignorant nonsense.
> >> People can choose what they need based on a range of requirements
> >> and preferences, and that's exactly what we want from a
> >> general-purpose language.
> >
> >My opinion about standard library is very close to that Bonita, even
> >if possibly possibly for the opposite reasons.
> >IMHO, if you can't make good use of either C++ Standard library or of
> >the other key feature of the language - virtual functions, then it is
> >wiser to avoid C++ altogether.
>
> Now that's just as silly as Bonita's position
>
> >BTW, I *don't* use C++ on small embedded targets.
>
> I do, and have. Two operating commercial operating
> systems, a hypervisor, and SoC microcode; all in C++ (with some legacy
> C device drivers loaded dynamically). Using a rational
> subset of C++ (with little run-time overhead) makes perfect
> sense for such an application given the data hiding and
> interface advantages of C++ over say, C.
>

What proof do you have that C++ was an advantage for your projects
rather than handicap?
Unlike standard library, the things you mention don't sound like
something that directly improves productivity.
In particular, is there really a productivity gain from sort of data
hiding available in C++ vs disciplined C with systematic documentation
and project-wide naming conventions? I am pretty sure that even if gain
exists it is below noise.

One "free" C++ feature that on paper could improve productivity in the
sort of project that you mention is constant expressions. I have
no experience with it, so can't say whether the gain is real or its
just my wrong impression.
This feature is relatively new, at least in form that no longer looks
like a toy, so I would guess that you didn't use it in at least 2 out of
3 project that you mention as success stories.

>
> Because _you_ don't do something doesn't generalize.

Didn't I wrote IMHO ? I think I did.

BTW, in 90s and early 00s I held opinion similar to yours. Since than I
certainly gained weight and hopefully gained wisdom.

Michael S <already5chosen@yahoo.com> writes:
>On Mon, 08 Apr 2024 17:19:19 GMT
>scott@slp53.sl.home (Scott Lurndal) wrote:
>
>> Michael S <already5chosen@yahoo.com> writes:
>> >On Mon, 8 Apr 2024 11:29:11 +0200
>> >David Brown <david.brown@hesbynett.no> wrote:
>> >
>> >> On 07/04/2024 18:35, Michael S wrote:
>> >>
>> >> > Partially balanced binary trees, like those used by std::map and
>> >> > by its relatives, are among the most predictable data structures
>> >> > out here. Certainly they are far more predictable than generic
>> >> > hash that in the worst case degenerates into O(N).
>> >> > OTOH, in std::map of given size the difference in worst access
>> >> > time between perfectly balanced case and most unbalanced case is
>> >> > only 2x. And that applies not just for lookup, but for insertion
>> >> > and deletion as well.
>> >> >
>> >>
>> >> As far as I know, details of how containers such as std::map are
>> >> implemented are left to the implementation - they are not
>> >> guaranteed by the standards.
>> >>
>> >> Different types of systems have different needs. C++ supports a
>> >> huge range of uses, and for some of them, many parts of the
>> >> standard library are simply out of the question. The point was
>> >> just that claims such as Bonita's that "it is impossible to use
>> >> C++ without exception[s]", or that if you don't use the standard
>> >> library you are "missing most of C++", are just ignorant nonsense.
>> >> People can choose what they need based on a range of requirements
>> >> and preferences, and that's exactly what we want from a
>> >> general-purpose language.
>> >
>> >My opinion about standard library is very close to that Bonita, even
>> >if possibly possibly for the opposite reasons.
>> >IMHO, if you can't make good use of either C++ Standard library or of
>> >the other key feature of the language - virtual functions, then it is
>> >wiser to avoid C++ altogether.
>>
>> Now that's just as silly as Bonita's position
>>
>> >BTW, I *don't* use C++ on small embedded targets.
>>
>> I do, and have. Two operating commercial operating
>> systems, a hypervisor, and SoC microcode; all in C++ (with some legacy
>> C device drivers loaded dynamically). Using a rational
>> subset of C++ (with little run-time overhead) makes perfect
>> sense for such an application given the data hiding and
>> interface advantages of C++ over say, C.
>>
>
>What proof do you have that C++ was an advantage for your projects
>rather than handicap?

What proof would you except? What makes you think proof is necessary?

>Unlike standard library, the things you mention don't sound like
>something that directly improves productivity.

Inheritance, pure-virtual (interface) classes leading to clean
interfaces, improved type safety, destructors, for starters. There's nothing
preventing one from developing equivalent facililties as one might
find in the soi disant standard library as part of the project and
re-use those "classes" throughout multiple projects.

In any case, the first C++ OS project I worked on ran from 1989 to 1997,
and there was no standard C++ library available. The first hypervisor
project was 1998-1999 (skunk works at SGI - coincidentally, an early
standardish C++ library originated at SGI) and the second hypervisor project
was from 2004-2010.

On Mon, 08 Apr 2024 23:00:47 GMT
scott@slp53.sl.home (Scott Lurndal) wrote:

> Michael S <already5chosen@yahoo.com> writes:
> >On Mon, 08 Apr 2024 17:19:19 GMT
> >scott@slp53.sl.home (Scott Lurndal) wrote:
> >
> >> Michael S <already5chosen@yahoo.com> writes:
> >> >On Mon, 8 Apr 2024 11:29:11 +0200
> >> >David Brown <david.brown@hesbynett.no> wrote:
> >> >
> >> >> On 07/04/2024 18:35, Michael S wrote:
> >> >>
> >> >> > Partially balanced binary trees, like those used by std::map
> >> >> > and by its relatives, are among the most predictable data
> >> >> > structures out here. Certainly they are far more predictable
> >> >> > than generic hash that in the worst case degenerates into
> >> >> > O(N). OTOH, in std::map of given size the difference in worst
> >> >> > access time between perfectly balanced case and most
> >> >> > unbalanced case is only 2x. And that applies not just for
> >> >> > lookup, but for insertion and deletion as well.
> >> >> >
> >> >>
> >> >> As far as I know, details of how containers such as std::map
> >> >> are implemented are left to the implementation - they are not
> >> >> guaranteed by the standards.
> >> >>
> >> >> Different types of systems have different needs. C++ supports a
> >> >> huge range of uses, and for some of them, many parts of the
> >> >> standard library are simply out of the question. The point was
> >> >> just that claims such as Bonita's that "it is impossible to use
> >> >> C++ without exception[s]", or that if you don't use the standard
> >> >> library you are "missing most of C++", are just ignorant
> >> >> nonsense. People can choose what they need based on a range of
> >> >> requirements and preferences, and that's exactly what we want
> >> >> from a general-purpose language.
> >> >
> >> >My opinion about standard library is very close to that Bonita,
> >> >even if possibly possibly for the opposite reasons.
> >> >IMHO, if you can't make good use of either C++ Standard library
> >> >or of the other key feature of the language - virtual functions,
> >> >then it is wiser to avoid C++ altogether.
> >>
> >> Now that's just as silly as Bonita's position
> >>
> >> >BTW, I *don't* use C++ on small embedded targets.
> >>
> >> I do, and have. Two operating commercial operating
> >> systems, a hypervisor, and SoC microcode; all in C++ (with some
> >> legacy C device drivers loaded dynamically). Using a rational
> >> subset of C++ (with little run-time overhead) makes perfect
> >> sense for such an application given the data hiding and
> >> interface advantages of C++ over say, C.
> >>
> >
> >What proof do you have that C++ was an advantage for your projects
> >rather than handicap?
>
> What proof would you except? What makes you think proof is necessary?
>
> >Unlike standard library, the things you mention don't sound like
> >something that directly improves productivity.
>
> Inheritance, pure-virtual (interface) classes leading to clean
> interfaces, improved type safety,

Sounds like you misread my original post.
I wrote that use of virtual function is a sufficient justification for
choice of C++ over C.
What I didn't wrote, but had in mind was "when inheritence used to
implement interfaces, preferably with abstract base classes and *not*
used for anything else."

> destructors, for starters.

I'd rather avoid destructors in that types of system.

> There's nothing preventing one from developing equivalent facililties
> as one might find in the soi disant standard library as part of the
> project and re-use those "classes" throughout multiple projects.
>

Everything can be developed from scratch. Not doing it improves
productivity. At least most of the time.

> In any case, the first C++ OS project I worked on ran from 1989 to
> 1997, and there was no standard C++ library available. The first
> hypervisor project was 1998-1999 (skunk works at SGI -
> coincidentally, an early standardish C++ library originated at SGI)
> and the second hypervisor project was from 2004-2010.
>
>

Used until scrapped or scrapped before used?

On 4/8/24 09:45, David Brown wrote:
....
> The complexity guarantees in the standard are vague - they are given as
> an indication of "time and/or space complexity", and I assume they mean
> the average or amortized complexity.

I don't think they are that vague. Some of them are explicitly described
as amortized - virtually all of which are "amortized constant time", I
would presume that any complexity guarantee not explicitly described as
amortized, isn't.

> That's fine for general use, but
> not for real-time systems. (Some people distinguish between "hard
> real-time" and "soft real-time" - the C++ standard guarantees /might/ be
> acceptable for some "soft real-time" uses.)

The standard's guarantees about complexity are meant to be what
developers can portably rely upon. Code that doesn't need to be portable
can rely upon more precise specifications of the complexity provided by
a particular implementation of C.

On Mon, 2024-04-08 at 16:32 +0300, Michael S wrote:
> On Mon, 08 Apr 2024 19:18:06 +0800
> wij <wyniijj5@gmail.com> wrote:
>
> >
> > I would say that maybe you don't know how to use C++ effectively.
> >
>
> It is possible.
> But more likely that relatively to you I have longer experience in C++
> and better understanding of both advantages and disadvantages.
>
>
>
>

Any works of yours on the internet that I can understand better what you mean?

Am 08.04.2024 um 19:52 schrieb Michael S:

> For modifications, yes. But that's still only LogN, but in time and
> in size of temporary storage. And search from root which in majority
> of workloads is the most common operation by far, is not affected.

If you've got a large number of nodes this only would be a "problem"
if an additional cacheline would be loaded for a node.

On 08/04/2024 23:47, Michael S wrote:

(I am speaking for myself, and my own projects - and my uses of C++
might differ a lot from those of Scott.)

>
> What proof do you have that C++ was an advantage for your projects
> rather than handicap?
> Unlike standard library, the things you mention don't sound like
> something that directly improves productivity.
> In particular, is there really a productivity gain from sort of data
> hiding available in C++ vs disciplined C with systematic documentation
> and project-wide naming conventions? I am pretty sure that even if gain
> exists it is below noise.

Seriously? Are you suggesting that documentation of requirements,
restrictions and features is just as good as expressing them in code? I
assume that your own coding and documentation is flawless, but have you
never seen code written by anyone else where the source code and the
comments or documentation are out of sync or directly contradictory?

The more you can express your requirements and the features of the
program in code itself, the better. It gives vastly better checking
than asking someone to read through the documentation. It keeps
everything in sync. It gives the compiler more knowledge - for better
checking, and for more efficient code generation (which often matters a
lot in embedded systems).

Tell me, is it better to document that users must call "flubar_init()"
on their "flubar" objects before calling "flubar_bar()" on them, or is
it better to make a "flubar" class with a constructor to do the "init"
automatically and guaranteed by the language? Is it more productive to
have developers check each other's code for accidental mixups between
two enum types, or to have the compiler throw a hard compile-time error?

>
> One "free" C++ feature that on paper could improve productivity in the
> sort of project that you mention is constant expressions. I have
> no experience with it, so can't say whether the gain is real or its
> just my wrong impression. > This feature is relatively new, at least in form that no longer looks
> like a toy, so I would guess that you didn't use it in at least 2 out of
> 3 project that you mention as success stories.
>

It's only been around for a decade or so, and thus is relatively young.
And it certainly has improved since its introduction in C++11. Yes, it
can be extremely useful.

But it's only one of the dozen or more features of C++ that I use to be
more productive and write safer and more efficient code for small
embedded systems.

On 09/04/2024 01:42, James Kuyper wrote:
> On 4/8/24 09:45, David Brown wrote:
> ...
>> The complexity guarantees in the standard are vague - they are given as
>> an indication of "time and/or space complexity", and I assume they mean
>> the average or amortized complexity.
>
> I don't think they are that vague. Some of them are explicitly described
> as amortized - virtually all of which are "amortized constant time", I
> would presume that any complexity guarantee not explicitly described as
> amortized, isn't.

I only saw "amortized" used in the context of "amortized constant"
complexity. (I have not read the standards here very thoroughly, so I
might have missed something.) I think it is fair to assume that
something marked "constant" complexity, without "amortized", really is
constant - and that will obviously also apply to the worst case.

Everything else is vague. That's good enough for most uses, and
stricter guarantees would limit implementations too much. But it is not
suitable for real-time systems or systems with tight constraints on time
or space.

>
>> That's fine for general use, but
>> not for real-time systems. (Some people distinguish between "hard
>> real-time" and "soft real-time" - the C++ standard guarantees /might/ be
>> acceptable for some "soft real-time" uses.)
>
> The standard's guarantees about complexity are meant to be what
> developers can portably rely upon. Code that doesn't need to be portable
> can rely upon more precise specifications of the complexity provided by
> a particular implementation of C.

Sure. However, I don't think any of the big C++ standard library
implementations provide tighter guarantees. Other implementations of
standard library containers, such as the EASTL, might have worst-case
guarantees - or they might at least have simple enough source code that
it is practical to determine the complexity by reading the code.

Typically, however, small embedded systems and hard real-time systems
have little need for things like std::map<> or std::vector<>, so it is
not much of an issue in practice. But it is one of the reasons why I
rule out such containers for use in the code I write.

On Tue, 09 Apr 2024 08:40:34 +0800
wij <wyniijj5@gmail.com> wrote:

> On Mon, 2024-04-08 at 16:32 +0300, Michael S wrote:
> > On Mon, 08 Apr 2024 19:18:06 +0800
> > wij <wyniijj5@gmail.com> wrote:
> >
> > >
> > > I would say that maybe you don't know how to use C++ effectively.
> > >
> >
> > It is possible.
> > But more likely that relatively to you I have longer experience in
> > C++ and better understanding of both advantages and disadvantages.
> >
> >
> >
> >
>
> Any works of yours on the internet that I can understand better what
> you mean?
>

All my code on Internet is for fun and either unrelated or very
remotely related to my professional work.
The conservative approach I am preaching in this thread is all about
pro and is not necessarily applicable to hobby coding.
Besides, all my code that you can seen on Internet is written by a
single person whose judgment I tend to trust, possibly mistakenly,
i.e. by me.
That is very different even from small work group, yet more different
from medium-sized group. Tight control is far less important in one
man shop.
However even looking at my public github repository you probably can
see gradual shift from C++ to C, with remaining uses of C++ almost
exclusively due to productivity gains provided by C++ Standard Library.

On Tue, 9 Apr 2024 09:11:16 +0200
David Brown <david.brown@hesbynett.no> wrote:

> On 08/04/2024 23:47, Michael S wrote:
>
> (I am speaking for myself, and my own projects - and my uses of C++
> might differ a lot from those of Scott.)
>
> >
> > What proof do you have that C++ was an advantage for your projects
> > rather than handicap?
> > Unlike standard library, the things you mention don't sound like
> > something that directly improves productivity.
> > In particular, is there really a productivity gain from sort of data
> > hiding available in C++ vs disciplined C with systematic
> > documentation and project-wide naming conventions? I am pretty sure
> > that even if gain exists it is below noise.
>
> Seriously? Are you suggesting that documentation of requirements,
> restrictions and features is just as good as expressing them in code?

Naming conventions are expressed in code.
E.g. if you systematically prefix all you private data members then I
would think that it's not just as good for productivity as C++ access
control, but better than it.

> I assume that your own coding and documentation is flawless, but
> have you never seen code written by anyone else where the source code
> and the comments or documentation are out of sync or directly
> contradictory?
>

There is no language solution to problem of undisciplined co-worker.

> The more you can express your requirements and the features of the
> program in code itself, the better. It gives vastly better checking
> than asking someone to read through the documentation. It keeps
> everything in sync. It gives the compiler more knowledge - for
> better checking, and for more efficient code generation (which often
> matters a lot in embedded systems).
>

I can't see of any C++ feature except templates that can lead to more
efficient code generation vs C. And I probably wouldn't want templates
written by ourselves (as opposed to std and saner parts of boost) in my
embedded project for reasons mostly unrelated to efficiency.

> Tell me, is it better to document that users must call
> "flubar_init()" on their "flubar" objects before calling
> "flubar_bar()" on them, or is it better to make a "flubar" class with
> a constructor to do the "init" automatically and guaranteed by the
> language?

It depends.
For trivial initialization constructor is a little better. For
non-trivial initialization init function is better, sometimes
significantly.
Overall, gain from sane use of constructors is smaller than harm caused
even by relatively minor misuse of constructors.

> Is it more productive to have developers check each
> other's code for accidental mixups between two enum types, or to have
> the compiler throw a hard compile-time error?
>

It's not like C++ enum classes are convenient. It's not like people
that use them tend to cast left, right and center.
And its not like even in ideal scenario they can improve productivity.

> >
> > One "free" C++ feature that on paper could improve productivity in
> > the sort of project that you mention is constant expressions. I have
> > no experience with it, so can't say whether the gain is real or its
> > just my wrong impression. > This feature is relatively new, at
> > least in form that no longer looks like a toy, so I would guess
> > that you didn't use it in at least 2 out of 3 project that you
> > mention as success stories.
>
> It's only been around for a decade or so, and thus is relatively
> young. And it certainly has improved since its introduction in C++11.
> Yes, it can be extremely useful.
>

In theory, or you have positive first hand experience?
I mean, something that warrants an epithet "extremely"?

> But it's only one of the dozen or more features of C++ that I use to
> be more productive and write safer and more efficient code for small
> embedded systems.
>

Try one day to start your next project in C. You will likely find out
that productivity is the same if not improved.

On Tue, 9 Apr 2024 09:45:08 +0200
David Brown <david.brown@hesbynett.no> wrote:

> On 09/04/2024 01:42, James Kuyper wrote:
> > On 4/8/24 09:45, David Brown wrote:
> > ...
> >> The complexity guarantees in the standard are vague - they are
> >> given as an indication of "time and/or space complexity", and I
> >> assume they mean the average or amortized complexity.
> >
> > I don't think they are that vague. Some of them are explicitly
> > described as amortized - virtually all of which are "amortized
> > constant time", I would presume that any complexity guarantee not
> > explicitly described as amortized, isn't.
>
> I only saw "amortized" used in the context of "amortized constant"
> complexity. (I have not read the standards here very thoroughly, so
> I might have missed something.) I think it is fair to assume that
> something marked "constant" complexity, without "amortized", really
> is constant - and that will obviously also apply to the worst case.
>
> Everything else is vague. That's good enough for most uses, and
> stricter guarantees would limit implementations too much. But it is
> not suitable for real-time systems or systems with tight constraints
> on time or space.
>
> >
> >> That's fine for general use, but
> >> not for real-time systems. (Some people distinguish between "hard
> >> real-time" and "soft real-time" - the C++ standard guarantees
> >> /might/ be acceptable for some "soft real-time" uses.)
> >
> > The standard's guarantees about complexity are meant to be what
> > developers can portably rely upon. Code that doesn't need to be
> > portable can rely upon more precise specifications of the
> > complexity provided by a particular implementation of C.
>
> Sure. However, I don't think any of the big C++ standard library
> implementations provide tighter guarantees. Other implementations of
> standard library containers, such as the EASTL, might have worst-case
> guarantees - or they might at least have simple enough source code
> that it is practical to determine the complexity by reading the code.
>
> Typically, however, small embedded systems and hard real-time systems
> have little need for things like std::map<> or std::vector<>, so it
> is not much of an issue in practice. But it is one of the reasons
> why I rule out such containers for use in the code I write.
>

You're arguing about unimportant theoretical possibilities.

In practice 95% of std::map implementations that you will ever
encounter will be Red-Black Tree and the remaining 5% will be AVL Tree.
All of them will have lookup, insertion and deletion in O(logN), not
amortized, but honest worst case. If you want all three major ops and
if your keys have no special properties than nothing more real-time
friendly than partially balanced binary tree does not exist. Or at least
I never heard about it and I tend to keep my ears open to that sort of
gossips.

All above not considering memory allocation part, but for robustness of
the later there exist several solutions mentioned by several posters in
this sub-thread.

Am 09.04.2024 um 11:48 schrieb Michael S:

> However even looking at my public github repository you probably can
> see gradual shift from C++ to C, with remaining uses of C++ almost
> exclusively due to productivity gains provided by C++ Standard Library.

With C you've got at least five times the code as in C++.

On 09/04/2024 12:12, Michael S wrote:
> On Tue, 9 Apr 2024 09:11:16 +0200
> David Brown <david.brown@hesbynett.no> wrote:
>
>> On 08/04/2024 23:47, Michael S wrote:
>>
>> (I am speaking for myself, and my own projects - and my uses of C++
>> might differ a lot from those of Scott.)
>>
>>>
>>> What proof do you have that C++ was an advantage for your projects
>>> rather than handicap?
>>> Unlike standard library, the things you mention don't sound like
>>> something that directly improves productivity.
>>> In particular, is there really a productivity gain from sort of data
>>> hiding available in C++ vs disciplined C with systematic
>>> documentation and project-wide naming conventions? I am pretty sure
>>> that even if gain exists it is below noise.
>>
>> Seriously? Are you suggesting that documentation of requirements,
>> restrictions and features is just as good as expressing them in code?
>
> Naming conventions are expressed in code.
> E.g. if you systematically prefix all you private data members then I
> would think that it's not just as good for productivity as C++ access
> control, but better than it.

I would strongly disagree. If you prefer having your private data
members named in a particular way, that's fine - do that in /addition/
to making them "private" class/struct members. But express it in code
first, documentation or comments as a secondary point.

I think, as a general point, there is nothing that you can do with your
coding conventions, discipline and documentation in C that you cannot
also equally well with C++. Using C++ features to promote safe and
correct coding, and turn at least some kinds of mistakes into
compile-time errors, does not in any way preclude non-coding procedures.

>
>> I assume that your own coding and documentation is flawless, but
>> have you never seen code written by anyone else where the source code
>> and the comments or documentation are out of sync or directly
>> contradictory?
>>
>
> There is no language solution to problem of undisciplined co-worker.

No, indeed - no language can protect you from a determined fool. But
the strength of a programming language comes not just from the features
it provides, but from the limitations it enforces. C++ is more powerful
than C partly because it provides more ways to restrict incorrect code
by accident.

Computer time is free - developer time is not, and the further down the
development process a mistake gets, the more costly it is. Any tool
that makes it easier to find errors earlier, and in a more automated
fashion, is likely to be a useful choice. So you use a language and
language features that help here - references instead of pointers, const
where possible (within reason, of course), small scopes, strong typing,
strong enums, etc. Mistakes found by your editor/IDE are the cheapest
and easiest to fix. You run your compiler (or linter) with strong
warnings, preferably flagged as errors rather than warnings, to help
enforce coding rules and styles as well as violations of the language's
type system. You use all the safety-related tools your language and
your compiler give you - including compiler extensions, to the extent
possible within portability requirements.

You can't stop all mistakes through choice of language and use of tools.
But you can certainly stop many types of error, and it would be silly
not to do that.

>
>> The more you can express your requirements and the features of the
>> program in code itself, the better. It gives vastly better checking
>> than asking someone to read through the documentation. It keeps
>> everything in sync. It gives the compiler more knowledge - for
>> better checking, and for more efficient code generation (which often
>> matters a lot in embedded systems).
>>
>
> I can't see of any C++ feature except templates that can lead to more
> efficient code generation vs C.

I agree that templates can often be important in improving efficiency.
constexpr can save run-time effort. References can occasionally be more
efficient because the compiler knows more about them than pointers - and
more compiler knowledge can lead to better error checking and better
optimisations. inline variables have made it easier to put more stuff
in headers, leading to more compiler optimisations (LTO is an
alternative here). Once modules mature, they will help keep this all
neat and modular.

But I was being more general than the language choice here - the more
you write in code, the better. You don't write a comment saying the
size of struct X is 32 bytes - you write static_assert(sizeof(X) == 32).
You don't write a comment saying "we can assume x is not negative",
you write [[assume(x >= 0)]];". You don't write "x /should/ be
none-negative", you use some kind of assertion - perhaps with run-time
checking during testing and debugging, and an assume attribute when it
is thoroughly confirmed correct.

> And I probably wouldn't want templates
> written by ourselves (as opposed to std and saner parts of boost) in my
> embedded project for reasons mostly unrelated to efficiency.

I use templates regularly. Now that concepts are part of the language I
have available (embedded toolchains are usually a version or two behind
the mainstream releases), I have started to use them to make templates
neater.

I don't know why people worry so much about using templates. They can
make some kinds of debugging a lot harder. But they can make things
safer and more efficient by carrying around details as part of their
type, rather than as run-time information. I use templates for GPIO pin
instances, for example - every GPIO pin is an inline variable of a
unique type that encapsulates things like the port and pin number,
active high or low, interrupt support, and so on, as part of the type.
These types inherit from base template classes with methods for reading
or setting pins, and other features - a GPIO_In_Out class will inherit
from both GPIO_In and GPIO_Out template classes. And it all cooks down
to absolute minimal run-time code with the neatest possible usage in the
source code.

>
>> Tell me, is it better to document that users must call
>> "flubar_init()" on their "flubar" objects before calling
>> "flubar_bar()" on them, or is it better to make a "flubar" class with
>> a constructor to do the "init" automatically and guaranteed by the
>> language?
>
> It depends.
> For trivial initialization constructor is a little better. For
> non-trivial initialization init function is better, sometimes
> significantly.
> Overall, gain from sane use of constructors is smaller than harm caused
> even by relatively minor misuse of constructors.
>

You believe you can make safe code in C by telling developers to be
disciplined and follow rules. Tell them not to misuse constructors, and
now your C++ is safe for trivial and non-trivial cases.

>> Is it more productive to have developers check each
>> other's code for accidental mixups between two enum types, or to have
>> the compiler throw a hard compile-time error?
>>
>
> It's not like C++ enum classes are convenient. It's not like people
> that use them tend to cast left, right and center.
> And its not like even in ideal scenario they can improve productivity.
>

They are not /quite/ as convenient as I'd like (though "using enum" in
C++20 helps). But they are pretty good for many purposes. They
increase productivity by being harder to get wrong than non-scoped
enums. (And enums in general, combined with compiler checks, are much
nicer and safer than arbitrary lists of constants.)

>>>
>>> One "free" C++ feature that on paper could improve productivity in
>>> the sort of project that you mention is constant expressions. I have
>>> no experience with it, so can't say whether the gain is real or its
>>> just my wrong impression. > This feature is relatively new, at
>>> least in form that no longer looks like a toy, so I would guess
>>> that you didn't use it in at least 2 out of 3 project that you
>>> mention as success stories.
>>
>> It's only been around for a decade or so, and thus is relatively
>> young. And it certainly has improved since its introduction in C++11.
>> Yes, it can be extremely useful.
>>
>
> In theory, or you have positive first hand experience?
> I mean, something that warrants an epithet "extremely"?

I use constexpr constants all the time, though in many (or even most)
cases a "const" would work too. But probably the most advanced uses of
constexpr I have had would be compile-time calculation of a CRC
acceleration table, and a case where I needed a reversible mapping
between byte orderings for a data package that my code received and
transmitted. I had one constexpr std::array initiated with the mapping
in one direction (based on external documentation), then the reverse
constexpr std::array was calculated at compile time. That gave me top
efficiency in use, and only one array to change if the ordering changed.

On 09/04/2024 12:27, Michael S wrote:
> On Tue, 9 Apr 2024 09:45:08 +0200
> David Brown <david.brown@hesbynett.no> wrote:
>

>> Typically, however, small embedded systems and hard real-time systems
>> have little need for things like std::map<> or std::vector<>, so it
>> is not much of an issue in practice. But it is one of the reasons
>> why I rule out such containers for use in the code I write.
>>
>
> You're arguing about unimportant theoretical possibilities.
>

Perhaps you don't understand about what "real-time" means. Real-time
development does not care about theoretical possibilities of different
implementations, because you fix your system at /one/ implementation.
But it /does/ care about theoretical possibilities of what could happen
in that one system. I don't care if some implementation uses Pink-Green
trees to get O(1) average speed, or another one uses Purple-Brown trees
to get O(n ^ 27) space complexity. I only care about the implementation
I am using. And I don't care about its average speed, I only care about
its worst-case spaces and times.

I don't care if it does 99.999% of its operations within 1µs, I care if
I can /guarantee/ that /every/ case is completed with 1 second.

Sometimes in real-time systems you will prefer a linear search through a
list, because it is easier to be sure of your limits and the correctness
of the code in all cases - with the simpler code, it's likely that your
worst case times are better than many kinds of tree.

And the same applies to space considerations - the worst case is the
only relevant case.

On Tue, 9 Apr 2024 15:13:54 +0200
David Brown <david.brown@hesbynett.no> wrote:

> On 09/04/2024 12:27, Michael S wrote:
> > On Tue, 9 Apr 2024 09:45:08 +0200
> > David Brown <david.brown@hesbynett.no> wrote:
> >
>
> >> Typically, however, small embedded systems and hard real-time
> >> systems have little need for things like std::map<> or
> >> std::vector<>, so it is not much of an issue in practice. But it
> >> is one of the reasons why I rule out such containers for use in
> >> the code I write.
> >
> > You're arguing about unimportant theoretical possibilities.
> >
>
> Perhaps you don't understand about what "real-time" means. Real-time
> development does not care about theoretical possibilities of
> different implementations, because you fix your system at /one/
> implementation. But it /does/ care about theoretical possibilities of
> what could happen in that one system. I don't care if some
> implementation uses Pink-Green trees to get O(1) average speed, or
> another one uses Purple-Brown trees to get O(n ^ 27) space
> complexity. I only care about the implementation I am using. And I
> don't care about its average speed, I only care about its worst-case
> spaces and times.
>
> I don't care if it does 99.999% of its operations within 1µs, I care
> if I can /guarantee/ that /every/ case is completed with 1 second.
>
> Sometimes in real-time systems you will prefer a linear search
> through a list, because it is easier to be sure of your limits and
> the correctness of the code in all cases - with the simpler code,
> it's likely that your worst case times are better than many kinds of
> tree.
>
> And the same applies to space considerations - the worst case is the
> only relevant case.
>

You continue to argue about unimportant theoretical possibilities.
std::map is *never* Pink-Green or Purple-Brown, It is either
Guibas-Sedgewick, better known as red-black or, very rarely,
Adelson-Velsky-Landis.
The only Brown connection that I can think about is that Sedgewick got
his Master degree from Brown University.

Michael S <already5chosen@yahoo.com> writes:
>On Mon, 08 Apr 2024 23:00:47 GMT
>scott@slp53.sl.home (Scott Lurndal) wrote:
>

>> In any case, the first C++ OS project I worked on ran from 1989 to
>> 1997, and there was no standard C++ library available. The first
>> hypervisor project was 1998-1999 (skunk works at SGI -
>> coincidentally, an early standardish C++ library originated at SGI)
>> and the second hypervisor project was from 2004-2010.
>>
>>
>
>Used until scrapped or scrapped before used?

The former, in all cases except the skunk works project.