Different people have different needs from C++, and use different
features. If I were programming on a PC, I'd happily use std::map<>
and the like. But I don't program on PC's, and I don't use
std::map<>. If I needed something like that, I'd make my own class
that fitted my requirements tightly - a factor of 10 inefficiency is
often fine on big systems, but not on the devices I work with.
But that's all fine - use whatever you find useful from the language.
On Sun, 7 Apr 2024 16:06:02 +0200
David Brown <david.brown@hesbynett.no> wrote:
Different people have different needs from C++, and use different
features. If I were programming on a PC, I'd happily use std::map<>
and the like. But I don't program on PC's, and I don't use
std::map<>. If I needed something like that, I'd make my own class
that fitted my requirements tightly - a factor of 10 inefficiency is
often fine on big systems, but not on the devices I work with.
But that's all fine - use whatever you find useful from the language.
Factor of 5-10 (mentioned in my other post) is quite rare and mostly
applies not to std::map vs custom implementation of RB or AVL tree, but
to std::map vs some form of hash, esp. when the nature of the key is
such that relatively simple hash function happens to have good
collision avoidance properties and when the database is huge, so O(1)
vs O(logN) starts to be significant.
Also pay attention that in situations where you do a lot of insertions
and deletions, and especially of deletions followed by insertions, std::map::extract() could be of great help in reducing a cost of memory allocation/delallocation to necessary minimum. It's relatively new
addition to std::map (C++17) and I'd guess that many C++ programmers
are not aware of its existence.
In my recent experience (I was implementing median filter over window
of few 1000s values), a use of extract() made clean and simple
std::map-based solution (well, actually std::multiset in this
particular case, but the same principles applies to std::set/multiset/amp/multymap) faster than relatively more complicated
code based on boost:intrusive:map.
In this case I happened to have enough time to rewrite it in C with
my own implementation of AVL tree. My own code was only some 10 or
15% faster than std container's. And it took more than a day (may be
more than two days? I don't remember) to write and to debug. And that's
for me, who knows the algorithm (from TAoCP) for more than 40 years.
For somebody else it could easily take a weak.
In short, std::map and relatives is quite good piece of work.
Highly recommended. Consider me fan.
At the end in particular case of my unusually long median filter, it
turned out that AVL or RB tree is not the best structure for the job. A couple of other structures (heap and tournament tree) work better. But
they don't work much better, only by factor of ~2.5. However both heap
and tournament tree are far less generically applicable data structures
than AVL/RB tree. They just happened to be better in this quite
special case.
On Sun, 7 Apr 2024 16:06:02 +0200
David Brown <david.brown@hesbynett.no> wrote:
Different people have different needs from C++, and use different
features. If I were programming on a PC, I'd happily use std::map<>
and the like. But I don't program on PC's, and I don't use
std::map<>. If I needed something like that, I'd make my own class
that fitted my requirements tightly - a factor of 10 inefficiency is
often fine on big systems, but not on the devices I work with.
But that's all fine - use whatever you find useful from the language.
Factor of 5-10 (mentioned in my other post) is quite rare and mostly
applies not to std::map vs custom implementation of RB or AVL tree, but
to std::map vs some form of hash, esp. when the nature of the key is
such that relatively simple hash function happens to have good
collision avoidance properties and when the database is huge, so O(1)
vs O(logN) starts to be significant.
On 07/04/2024 17:38, Michael S wrote:
On Sun, 7 Apr 2024 16:06:02 +0200
David Brown <david.brown@hesbynett.no> wrote:
Different people have different needs from C++, and use different
features. If I were programming on a PC, I'd happily use
std::map<> and the like. But I don't program on PC's, and I don't
use std::map<>. If I needed something like that, I'd make my own
class that fitted my requirements tightly - a factor of 10
inefficiency is often fine on big systems, but not on the devices
I work with.
But that's all fine - use whatever you find useful from the
language.
Factor of 5-10 (mentioned in my other post) is quite rare and mostly applies not to std::map vs custom implementation of RB or AVL tree,
but to std::map vs some form of hash, esp. when the nature of the
key is such that relatively simple hash function happens to have
good collision avoidance properties and when the database is huge,
so O(1) vs O(logN) starts to be significant.
Sure.
But remember, for small embedded systems you don't have dynamic
memory - or if you do, you use it in limited and tightly controlled
manner. And in a real-time system, it is the worst-case time that
matters, unlike PC's where you are generally looking for average or
amortized times. So a data structure which allocates and deallocates
memory unpredictably, can use complex tree structures with little
control of their worst-case times - no thanks!
(And again, that does not mean these containers are not great choices
for all kinds of other uses.)
Michael S <already5chosen@yahoo.com> writes:
On Sun, 7 Apr 2024 16:06:02 +0200
David Brown <david.brown@hesbynett.no> wrote:
Different people have different needs from C++, and use different
features. If I were programming on a PC, I'd happily use
std::map<> and the like. But I don't program on PC's, and I don't
use std::map<>. If I needed something like that, I'd make my own
class that fitted my requirements tightly - a factor of 10
inefficiency is often fine on big systems, but not on the devices
I work with.
But that's all fine - use whatever you find useful from the
language.
Factor of 5-10 (mentioned in my other post) is quite rare and mostly >applies not to std::map vs custom implementation of RB or AVL tree,
but to std::map vs some form of hash, esp. when the nature of the
key is such that relatively simple hash function happens to have good >collision avoidance properties and when the database is huge, so O(1)
vs O(logN) starts to be significant.
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.
Factor of 5-10 (mentioned in my other post) is quite rare and mostly
applies not to std::map vs custom implementation of RB or AVL tree, ...
In this case I happened to have enough time to rewrite it in C with
my own implementation of AVL tree. My own code was only some 10 or
15% faster than std container's. ...
If you have the case where good hash function does not exist (which
is extremely rare) then in your scenario simple sorted vector + binary
search will likely be 1.5-2 times faster than std::map. Also when both
key and payload are small, vector can be non-trivially more
compact than map.
Am 07.04.2024 um 17:38 schrieb Michael S:
Factor of 5-10 (mentioned in my other post) is quite rare and mostly applies not to std::map vs custom implementation of RB or AVL tree,
...
That's nonsense. If the tree type is the same the performance is the
same. The high overhead of a tree comes from the pointer chasing while looking up a certain node. The issue is the same for manual implemen- tations.
What could make a map slow is the memory allocation part, but you
could either chose a fast allocator like mimalloc or use a C++23
flat_map, where insertion or removal is as fast as possible.
In this case I happened to have enough time to rewrite it in C with
my own implementation of AVL tree. My own code was only some 10 or
15% faster than std container's. ...
I also prefer AVL-trees over RB-trees for the faster lookup,
but if
the type of tree is the same and the memory allocation part is the
same there should be no performance difference between a manual C -implementation and a std::map.
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.
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.
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.
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.I would say that maybe you don't know how to use C++ effectively.
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.
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.
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.
What exactly is nonsense?
You are saying approximately the same that I said above.
On x86-64 with MSVC/gcc/clang each std::set/multiset node occupies 32
bytes even when key is only 32 bits. ...
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.
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.
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.
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.
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.
I would say that maybe you don't know how to use C++ effectively.
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.
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.
Even under restrictions of std API, parent link is not strictly
necessary.
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.
BTW, I *don't* use C++ on small embedded targets.
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.
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.
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, 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.
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.
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.)
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.
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.
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.
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?
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.
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:
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.
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 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?
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.
On Tue, 9 Apr 2024 15:13:54 +0200...
David Brown <david.brown@hesbynett.no> wrote:
...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.
You continue to argue about unimportant theoretical possibilities.
On 4/9/24 11:12, Michael S wrote:
On Tue, 9 Apr 2024 15:13:54 +0200...
David Brown <david.brown@hesbynett.no> wrote:
...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.
You continue to argue about unimportant theoretical possibilities.
He's doing the exact opposite of worrying about theorectical
possibilities. He's saying that what the implementation he's using
actually does is more important than your instance that it can only be
doing something else.
On Wed, 10 Apr 2024 02:24:59 -0400
James Kuyper <jameskuyper@alumni.caltech.edu> wrote:
On 4/9/24 11:12, Michael S wrote:
On Tue, 9 Apr 2024 15:13:54 +0200...
David Brown <david.brown@hesbynett.no> wrote:
...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.
You continue to argue about unimportant theoretical possibilities.
He's doing the exact opposite of worrying about theorectical
possibilities. He's saying that what the implementation he's using
actually does is more important than your instance that it can only be
doing something else.
He can check and see by himself that all toolsets that he uses have
std::map implemented on top of red-black tree. It's easy, sources are
here. But it seems arguing is more fun.
And one of the the posibilities that he mentiond (wider nodes) does not
look like even theoretically possible for C++17 and later, because it
would mess with extract() and the rest of node-based APIs.
On 10/04/2024 23:07, Michael S wrote:
On Wed, 10 Apr 2024 02:24:59 -0400
James Kuyper <jameskuyper@alumni.caltech.edu> wrote:
On 4/9/24 11:12, Michael S wrote:
On Tue, 9 Apr 2024 15:13:54 +0200...
David Brown <david.brown@hesbynett.no> wrote:
...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.
You continue to argue about unimportant theoretical possibilities.
He's doing the exact opposite of worrying about theorectical possibilities. He's saying that what the implementation he's using actually does is more important than your instance that it can only be doing something else.
He can check and see by himself that all toolsets that he uses have std::map implemented on top of red-black tree. It's easy, sources are
here. But it seems arguing is more fun.
No, it is /not/ easy - sources for big C++ standard libraries are far
from simple to understand. (That is in no way a criticism - I
understand why they are written the way they are.) I could look up
sources and see identifiers or comments saying they use red-black trees,
but as I have already explained several times, knowing that does not
give me anywhere close to the guarantees that are needed before the code
is useable for hard real-time systems. Of course I could study the code for long enough, and do enough analysis and testing to establish timing guarantees - but it would be vastly simpler and faster to write my own
data structures from scratch to fulfil real-time requirements. I would
not expect my implementations to be faster on average for general usage
- indeed, I'd expect them to be a lot slower. But /knowing/ the limits
is the important point, not the speed.
If you don't know what real-time requirements are - what the phrase "real-time" means - that's fine. Most people don't need to know about it. Even most people who work with small embedded systems as a
profession don't really understand it - most embedded systems don't have serious real-time requirements. But some do, and the more advanced C++ standard library features are not something that could be considered for them.
If you are interesting it knowing what real-time means, I can try to explain. If you'd rather continue playing salesman for C++ standard library containers, then we'll just have to leave it.
And one of the the posibilities that he mentiond (wider nodes) does not look like even theoretically possible for C++17 and later, because it
would mess with extract() and the rest of node-based APIs.
Yup, the good point of std::list/set/map/... is that users can use it nearly blindingly. But when you calculate the gains/losses, things are different than
what is usually thought.
Yes, most C++ users can use these standard library containers "blindly".
And for others that have special requirements, things like custom allocators and other flexibilities can help.
Yup, the good point of std::list/set/map/... is that users can use it
nearly blindingly. But when you calculate the gains/losses, things
are different than what is usually thought.
Am 11.04.2024 um 13:47 schrieb David Brown:
Yes, most C++ users can use these standard library containers
"blindly". And for others that have special requirements, things
like custom allocators and other flexibilities can help.
Custom allocators only make sense with a vector. With all other con-
tainers the standars library does a
allocator_traits<X>::rebind_alloc<Y> to have a different allocator
type. F.e. a map never uses the supplied allocator since the nodes
also contain the links. For me the whole allocator-concept mostly
doesn't make sense because of that.
On Thu, 11 Apr 2024 14:04:47 +0200
Bonita Montero <Bonita.Montero@gmail.com> wrote:
Am 11.04.2024 um 13:47 schrieb David Brown:
Yes, most C++ users can use these standard library containers
"blindly". And for others that have special requirements, things
like custom allocators and other flexibilities can help.
Custom allocators only make sense with a vector. With all other con-
tainers the standars library does a
allocator_traits<X>::rebind_alloc<Y> to have a different allocator
type. F.e. a map never uses the supplied allocator since the nodes
also contain the links. For me the whole allocator-concept mostly
doesn't make sense because of that.
I tried to implement custom allocator for std::multiset and actually
succeed. But it was too hard and too ugly. So I happily forgot how to
do it 2 hours later.
Am 11.04.2024 um 15:18 schrieb Michael S:
On Thu, 11 Apr 2024 14:04:47 +0200
Bonita Montero <Bonita.Montero@gmail.com> wrote:
Am 11.04.2024 um 13:47 schrieb David Brown:
Yes, most C++ users can use these standard library containers
"blindly". And for others that have special requirements, things
like custom allocators and other flexibilities can help.
Custom allocators only make sense with a vector. With all other
con- tainers the standars library does a
allocator_traits<X>::rebind_alloc<Y> to have a different allocator
type. F.e. a map never uses the supplied allocator since the nodes
also contain the links. For me the whole allocator-concept mostly
doesn't make sense because of that.
I tried to implement custom allocator for std::multiset and actually succeed. But it was too hard and too ugly. So I happily forgot how
to do it 2 hours later.
To make this work a custom allocator should be rebind<>-able to any
type, thereby having a typed malloc()-like allocator for all types
and sizes.
On Thu, 11 Apr 2024 15:31:21 +0200
Bonita Montero <Bonita.Montero@gmail.com> wrote:
Am 11.04.2024 um 15:18 schrieb Michael S:
On Thu, 11 Apr 2024 14:04:47 +0200
Bonita Montero <Bonita.Montero@gmail.com> wrote:
Am 11.04.2024 um 13:47 schrieb David Brown:
Yes, most C++ users can use these standard library containers
"blindly". And for others that have special requirements, things
like custom allocators and other flexibilities can help.
Custom allocators only make sense with a vector. With all other
con- tainers the standars library does a
allocator_traits<X>::rebind_alloc<Y> to have a different allocator
type. F.e. a map never uses the supplied allocator since the nodes
also contain the links. For me the whole allocator-concept mostly
doesn't make sense because of that.
I tried to implement custom allocator for std::multiset and actually
succeed. But it was too hard and too ugly. So I happily forgot how
to do it 2 hours later.
To make this work a custom allocator should be rebind<>-able to any
type, thereby having a typed malloc()-like allocator for all types
and sizes.
The point is to not be more generic than absolutely necessary for
particular application.
On 11/04/2024 13:25, wij wrote:
Yup, the good point of std::list/set/map/... is that users can use it nearly
blindingly. But when you calculate the gains/losses, things are different than
what is usually thought.
Yes, most C++ users can use these standard library containers "blindly".
And for others that have special requirements, things like custom allocators and other flexibilities can help.
But people working on real-time systems, high-reliability systems, safety-related systems, or very resource-constrained systems can't do /anything/ blindly.
On Thu, 2024-04-11 at 13:47 +0200, David Brown wrote:
On 11/04/2024 13:25, wij wrote:
Yup, the good point of std::list/set/map/... is that users can use it nearlyYes, most C++ users can use these standard library containers "blindly".
blindingly. But when you calculate the gains/losses, things are different than
what is usually thought.
And for others that have special requirements, things like custom
allocators and other flexibilities can help.
But people working on real-time systems, high-reliability systems,
safety-related systems, or very resource-constrained systems can't do
/anything/ blindly.
Understand. People here seemingly do not program hard-wares (thus don't really
understand C, IMO). I quit hard-ware things (and C) for a long time. But, for embedded systems, esp. real real-time systems, my first choice was Assembly. I am not aware whether C++ is suitable for real real-time systems or not.
I had encountered programming for buggy hardwares (sound efffect chips, and some
badly designed hard-wares, because the company wanted to save money) where some pins had to be read/written in a peculiar way (language optimization will
be a problem here).
And, an embedded system that had to simulate UART where
timeing is really critical in order to communicate with other devices (every machine tick counts). And a system that uses two DOS machines to work as one machine where COM1 is set to the highest priority to provide basic synchronization mechanism...
And, for embedded systems, RAM/pins is money, related to survival of product. Average people don't understand this.
High-level languages normally involves more supporting tools, all these need update and learning, not necessarily good.
I can not see a single reason to use std::list. It brings nothing to the table relatively to my own lists and just reduces flexibility and transparency.
| Sysop: | DaiTengu |
|---|---|
| Location: | Appleton, WI |
| Users: | 915 |
| Nodes: | 10 (1 / 9) |
| Uptime: | 20:58:51 |
| Calls: | 12,168 |
| Files: | 186,520 |
| Messages: | 2,233,937 |