Am 07.04.2024 um 15:00 schrieb Michael S:

> $ gcc -c -Wall -O2 foo.cpp raii-foo.cpp
> $ size *.o
> text data bss dec hex filename
> 136 0 0 136 88 foo.o
> 172 0 0 172 ac raii-foo.o
>

That's because of the unrolling code for exceptions. But this
unrolling code is separate and usually not executed. The code
path for the non-exceptional case should have the same perfor-
mance.

07.04.2024 16:00 Michael S kirjutas:
> On Sat, 6 Apr 2024 17:29:45 +0300
> Paavo Helde <eesnimi@osa.pri.ee> wrote:
>>
>> run-time performance hits. But iostreams do not make up most of C++.
>>
>> Still, the best feature of C++ is RAII (zero run-time performance
>> hit).
>>
>
> RAII has low run-time cost, although I doubt that it's really zero.
> RAII has non-trivial code size cost, esp. when used a lot. See below.

The last time when I had to worry about code size was in year 1992, with
an Intel 80186 processor. But I understand it might be a concern in some
applications.

> But my main objection with RAII is that I feel like loosing track.

It's the opposite for me. I feel myself at ease and having control only
after I put a resource release properly under RAII.

On Sun, 7 Apr 2024 16:06:02 +0200
David Brown <david.brown@hesbynett.no> wrote:

> On 07/04/2024 15:00, Michael S wrote:
> > On Sat, 6 Apr 2024 17:29:45 +0300
> > Paavo Helde <eesnimi@osa.pri.ee> wrote:
> >>
> >> run-time performance hits. But iostreams do not make up most of
> >> C++.
> >>
> >> Still, the best feature of C++ is RAII (zero run-time performance
> >> hit).
> >>
> >
> > RAII has low run-time cost, although I doubt that it's really zero.
> > RAII has non-trivial code size cost, esp. when used a lot. See
> > below. But my main objection with RAII is that I feel like loosing
> > track.
>
> > $ gcc -c -Wall -O2 foo.cpp raii-foo.cpp
> > $ size *.o
> > text data bss dec hex filename
> > 136 0 0 136 88 foo.o
> > 172 0 0 172 ac raii-foo.o
> >
>
> You will almost certainly find that the overhead here is due to
> exception handling and/or RTTI. Add the flag "-fno-execptions
> -fno-rtti", and you'll see the same code generated using
> <https://godbolt.org>.

Of course, it is due to exception!
But isn't exception safety the main point behind RAII?

RTTI plays no role here.
Is not RTTI supported only for classes with virtual functions?

>
> For some kinds of code (such as the stuff Scott does, and the stuff I
> do), exceptions are an unacceptable overhead, cost and complication
> in a language. Many other features of C++ - including RAII,
> templates, classes, namespaces, strong enums, overloading, concepts,
> constexpr, inline variables, smart pointers, and countless other bits
> and pieces can be used to get better source code (clearer, simpler,
> more flexible, safer, etc.) without inefficiency overheads compared
> to similar solutions in C.
>

I am not a fan of smart pointers.
The other thing you mentioned can help sometimes, but also can make
a mess of your codebase. And I had seen the later more often than the
former.
In particular, classes with big number of members are used by lazy
programmers to have what is in effect global variables without feeling
guilty.

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:39:02 +0200
Bonita Montero <Bonita.Montero@gmail.com> wrote:

> Am 07.04.2024 um 15:00 schrieb Michael S:
>
> > $ gcc -c -Wall -O2 foo.cpp raii-foo.cpp
> > $ size *.o
> > text data bss dec hex filename
> > 136 0 0 136 88 foo.o
> > 172 0 0 172 ac raii-foo.o
> >
>
> That's because of the unrolling code for exceptions. But this
> unrolling code is separate and usually not executed. The code
> path for the non-exceptional case should have the same perfor-
> mance.
>

Didn't I say it myself about low runtime cost?

Bonita Montero <Bonita.Montero@gmail.com> writes:
>Am 07.04.2024 um 00:55 schrieb Chris M. Thomasson:
>> On 4/5/2024 9:04 AM, Bonita Montero wrote:
>>> Am 05.04.2024 um 17:37 schrieb Michael S:
>>>
>>>> However I know enough to know that Win32 is defined in terms of C.
>>>> So I don't quite understand how XHANDLE can be part of it.
>>>
>>> It's obvious.
>>>
>>
>> Where is XHANDLE defined wrt any Microsoft documentation? Its not:
>
>It's obvious that XHANDE is some kind of RAII-wrapper.

https://www.logicallyfallacious.com/logicalfallacies/Appeal-to-Self-evident-Truth

Michael S <already5chosen@yahoo.com> writes:
>On Sun, 7 Apr 2024 16:06:02 +0200
>David Brown <david.brown@hesbynett.no> wrote:
>
>> On 07/04/2024 15:00, Michael S wrote:
>> > On Sat, 6 Apr 2024 17:29:45 +0300
>> > Paavo Helde <eesnimi@osa.pri.ee> wrote:
>> >>

>> > RAII has low run-time cost, although I doubt that it's really zero.
>> > RAII has non-trivial code size cost, esp. when used a lot. See
>> > below. But my main objection with RAII is that I feel like loosing
>> > track.
>>
>> > $ gcc -c -Wall -O2 foo.cpp raii-foo.cpp
>> > $ size *.o
>> > text data bss dec hex filename
>> > 136 0 0 136 88 foo.o
>> > 172 0 0 172 ac raii-foo.o
>> >
>>
>> You will almost certainly find that the overhead here is due to
>> exception handling and/or RTTI. Add the flag "-fno-execptions
>> -fno-rtti", and you'll see the same code generated using
>> <https://godbolt.org>.
>
>Of course, it is due to exception!
>But isn't exception safety the main point behind RAII?

Not necessarily. We used RAII (perhaps before it was called
such) in 1989, in cfront 2.1 (exceptions didn't appear until 3.0)
as a way to bail (return) from a long function (a kernel implementation
of fork) and automatically deallocate various system resources
(assigned credentials, memory map/pt, new process attributes,
process-id, session/process group associations, etc) that
had been allocated before the fork failure was detected.

>
>RTTI plays no role here.
>Is not RTTI supported only for classes with virtual functions?

dynamic_cast requires RTTI.

>
>>
>> For some kinds of code (such as the stuff Scott does, and the stuff I
>> do), exceptions are an unacceptable overhead, cost and complication
>> in a language. Many other features of C++ - including RAII,
>> templates, classes, namespaces, strong enums, overloading, concepts,
>> constexpr, inline variables, smart pointers, and countless other bits
>> and pieces can be used to get better source code (clearer, simpler,
>> more flexible, safer, etc.) without inefficiency overheads compared
>> to similar solutions in C.
>>
>
>I am not a fan of smart pointers.

Concur.

On 07/04/2024 17:37, Michael S wrote:
> On Sun, 7 Apr 2024 16:06:02 +0200
> David Brown <david.brown@hesbynett.no> wrote:
>
>> On 07/04/2024 15:00, Michael S wrote:
>>> On Sat, 6 Apr 2024 17:29:45 +0300
>>> Paavo Helde <eesnimi@osa.pri.ee> wrote:
>>>>
>>>> run-time performance hits. But iostreams do not make up most of
>>>> C++.
>>>>
>>>> Still, the best feature of C++ is RAII (zero run-time performance
>>>> hit).
>>>>
>>>
>>> RAII has low run-time cost, although I doubt that it's really zero.
>>> RAII has non-trivial code size cost, esp. when used a lot. See
>>> below. But my main objection with RAII is that I feel like loosing
>>> track.
>>
>>> $ gcc -c -Wall -O2 foo.cpp raii-foo.cpp
>>> $ size *.o
>>> text data bss dec hex filename
>>> 136 0 0 136 88 foo.o
>>> 172 0 0 172 ac raii-foo.o
>>>
>>
>> You will almost certainly find that the overhead here is due to
>> exception handling and/or RTTI. Add the flag "-fno-execptions
>> -fno-rtti", and you'll see the same code generated using
>> <https://godbolt.org>.
>
> Of course, it is due to exception!
> But isn't exception safety the main point behind RAII?
>

Not at all!

RAII is about encapsulating an acquire-release pair in a manner that
makes it easy to get right, and hard to get wrong, while minimising the
boiler-plate code needed at the time of use. It's convenience for use
with exceptions is almost completely incidental - as demonstrated by its
usefulness when exceptions are not used (many C++ users don't use
exceptions, and for a lot of use-cases, particularly embedded uses or
safety or reliability critical code, exceptions are totally banned), and
also by languages that have exceptions but not RAII.

RAII is neither sufficient nor necessary for exception safety, but it
certainly makes exception safety easier.

> RTTI plays no role here.

True - but RTTI goes along with exceptions as being a part of C++ that
adds overhead. If you don't use the information, it is generally just
wasted code space, rather than run time inefficiency, but for resource
limited systems, that's a relevant issue.

> Is not RTTI supported only for classes with virtual functions?

No, it gets used for dynamic casts, and for identifying the class of a
thrown exception. (At least, I think that's true - wait for others to
either correct me or confirm this before believing it!)

>
>>
>> For some kinds of code (such as the stuff Scott does, and the stuff I
>> do), exceptions are an unacceptable overhead, cost and complication
>> in a language. Many other features of C++ - including RAII,
>> templates, classes, namespaces, strong enums, overloading, concepts,
>> constexpr, inline variables, smart pointers, and countless other bits
>> and pieces can be used to get better source code (clearer, simpler,
>> more flexible, safer, etc.) without inefficiency overheads compared
>> to similar solutions in C.
>>
>
> I am not a fan of smart pointers.

Nobody likes /everything/ in C++ !

> The other thing you mentioned can help sometimes, but also can make
> a mess of your codebase. And I had seen the later more often than the
> former.

With great power, comes great responsibility - that's why we fear it :-)

Useful tools for writing better code can also be used to mess things up
in new and imaginative ways.

> In particular, classes with big number of members are used by lazy
> programmers to have what is in effect global variables without feeling
> guilty.
>

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.)

> 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.
>
>

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.

On Sun, 7 Apr 2024 18:06:29 +0200
David Brown <david.brown@hesbynett.no> wrote:

> 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!

As said in post above, in C++17 when the max size of map is known
during initialization, allocation and de-allocation can be solved by
std::map:extract in the same manner you do it for simpler containers:
you push the required number of nodes into std::map then immediately
extract and store in the simple structure, typically managed like a
stack, but probably not using std::stack. Then during main runtime,
in very typical "embedded" manner, you pop nodes that you want to
insert from stack and push extracted nodes back to stack. No malloc, no
free.
It was possibly to achieve similar effect before C++17 as well, but it
required use of custom allocators which are, IMHO, too hard to use.

>
> (And again, that does not mean these containers are not great choices
> for all kinds of other uses.)
>

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 Sun, 07 Apr 2024 16:09:04 GMT
scott@slp53.sl.home (Scott Lurndal) wrote:

> 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.
>

std::map is known to not be the best data structure for static search.
Not too bad, but not the best.

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.

Nowadays the best structures probably have to take into account cache
hierarchy, so fat nodes are somewhat better than simple binary search,
but that level of advancement should be used only when speed is VERY
important.

Am 07.04.2024 um 17:51 schrieb Scott Lurndal:
> Bonita Montero <Bonita.Montero@gmail.com> writes:
>> Am 07.04.2024 um 00:55 schrieb Chris M. Thomasson:
>>> On 4/5/2024 9:04 AM, Bonita Montero wrote:
>>>> Am 05.04.2024 um 17:37 schrieb Michael S:
>>>>
>>>>> However I know enough to know that Win32 is defined in terms of C.
>>>>> So I don't quite understand how XHANDLE can be part of it.
>>>>
>>>> It's obvious.
>>>>
>>>
>>> Where is XHANDLE defined wrt any Microsoft documentation? Its not:
>>
>> It's obvious that XHANDE is some kind of RAII-wrapper.
>
> https://www.logicallyfallacious.com/logicalfallacies/Appeal-to-Self-evident-Truth
>

My XHANDLE has nearly the same name like a HANDLE and takes a HANDLE
as its constructor parameter, so this is obvious.

Am 07.04.2024 um 17:41 schrieb Michael S:
> On Sun, 7 Apr 2024 16:39:02 +0200
> Bonita Montero <Bonita.Montero@gmail.com> wrote:
>
>> Am 07.04.2024 um 15:00 schrieb Michael S:
>>
>>> $ gcc -c -Wall -O2 foo.cpp raii-foo.cpp
>>> $ size *.o
>>> text data bss dec hex filename
>>> 136 0 0 136 88 foo.o
>>> 172 0 0 172 ac raii-foo.o
>>>
>>
>> That's because of the unrolling code for exceptions. But this
>> unrolling code is separate and usually not executed. The code
>> path for the non-exceptional case should have the same perfor-
>> mance.
>>
>
> Didn't I say it myself about low runtime cost?
>
>

I think there's no additional runtime cost over manual releases
at all if no exception is thrown.

Am 07.04.2024 um 17:37 schrieb Michael S:

> RTTI plays no role here.
> Is not RTTI supported only for classes with virtual functions?

Destructors may be virutal but while unwinding the type of the
destructed object is known so ther's no need to call the destructor
virtually.

> In particular, classes with big number of members are used by lazy
> programmers to have what is in effect global variables without feeling
> guilty.

This may apply to static methods only.

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.

Am 07.04.2024 um 18:48 schrieb Michael 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.

Use a flat_map and you'll get near to the lookup performance of a sorted
vector but you'll have superior insertion or removal performance.

On 4/7/2024 10:35 AM, Bonita Montero wrote:
> Am 07.04.2024 um 17:51 schrieb Scott Lurndal:
>> Bonita Montero <Bonita.Montero@gmail.com> writes:
>>> Am 07.04.2024 um 00:55 schrieb Chris M. Thomasson:
>>>> On 4/5/2024 9:04 AM, Bonita Montero wrote:
>>>>> Am 05.04.2024 um 17:37 schrieb Michael S:
>>>>>
>>>>>> However I know enough to know that Win32 is defined in terms of C.
>>>>>> So I don't quite understand how XHANDLE can be part of it.
>>>>>
>>>>> It's obvious.
>>>>>
>>>>
>>>> Where is XHANDLE defined wrt any Microsoft documentation? Its not:
>>>
>>> It's obvious that XHANDE is some kind of RAII-wrapper.
>>
>> https://www.logicallyfallacious.com/logicalfallacies/Appeal-to-Self-evident-Truth
>>
>
> My XHANDLE has nearly the same name like a HANDLE and takes a HANDLE
> as its constructor parameter, so this is obvious.

I was just wondering if it was actually a CHandle, or what.

On Sun, 2024-04-07 at 08:28 +0200, Bonita Montero wrote:
> Am 06.04.2024 um 21:00 schrieb wij:
> > On Sat, 2024-04-06 at 18:34 +0200, Bonita Montero wrote:
> > > Am 06.04.2024 um 16:56 schrieb Scott Lurndal:
> > >
> > > > For the most part true of std::vector.   Not necessarily for
> > > > std::map.
> > >
> > I estimate ::hsearch(...) is about 20 times faster than std::map, that says it all,
> > although the key is limited to c-string.
>
>
> A tree is slow, but if you need to iterate with key order there's
> nothing faster. Hash-maps are O(1) are faster but you can't traverse
> the KVs in key-order.
>
> >
> > > Show me a better key-value data structure when you
> > > also need to iterate through the KVs in sorting order.
> > >
> > > > Poorly used, templates increase the code footprint, ...
> > >
> > > They're fast and the code-foooprint may not be tolerable only on very
> > > small systems.
> > >
> >
> > One of the worst part of C++ is memory consumption, compared with C.
>
> C++ is not known for its bad memory consumption.
>
> > Let's say C program can solve problems of size X, C++ normally solves of size X/2.
> > This is equivalent to time performance in larger size.
> >
> > > > There is a definite run-time cost to using exceptions.  And some
> > > > C++ code (operating systems, hypervisors) don't have the
> > > > run-time infrastructure to support exception handling and stack
> > > > unwinding.
> > >
> > > Then don't throw exceptions through that foreign code. I'm often using
> > > lambdas without captures as callbacks to C-interfaces with Win32. With
> > > these callback's I can't use exceptions but that's not a problem.
> > >
> >
> > The problem of 'throw' is context-loss and time cost. For context-loss, you generally
> > won't be able to have library-level reusable codes. 'Throw' is normally one thousand
> > times slower than return, this part is, generally speaking, doomed.
>
> Exceptions are only thrown in exceptional cases like I/O-errors or a
> memory collapse. That happens very rarely and performance of thrown
> exceptions doens't count.
>

Don't be that exclusive. Throwing error is not that bad. Throwing error is like
setting global errno and executing 'soft' assertion failure.

> >
> > The problem of std::exception family is simply unnecessarily complex.
> >
> > > > Useful, but can easily be abused (e.g. for locking).
> > >
> > > Ok, "can be abused", then drop it ! ;-)
> > >
> > >
> >
> >
>

On Sun, 7 Apr 2024 19:44:18 +0200
Bonita Montero <Bonita.Montero@gmail.com> wrote:

> 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 exactly is nonsense?
You are saying approximately the same that I said above.

> 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.
>

I didn't look at flat_map yet. I hate to leave leading edge of the
language.
In the case that I described in the other post allocation was solved by
extract() and pool of nodes. Worked great because in this particular
application there were a lot of insertions and deletions, but they
perfectly balanced each other and total size of multiset remained
constant (+-1) for majority of its life time.

> > 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,

Since my application was very modification-intensive, from algorithmic
perspective AVL is probably slightly worse than RB. I did AVL not
because of algorithmic superiority, but because I understand it better.

> 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.
>

In my particular case of 2K to 10K nodes it was indeed almost the
same. But for bigger size, e.g. 1M to 10M, manual implementation could
be significantly faster, because nodes could be made significantly
smaller, improving cache hit rates.
That applies to set/multiset more than to map/multimap and to small
keys more than to big keys.

On x86-64 with MSVC/gcc/clang each std::set/multiset node occupies 32
bytes even when key is only 32 bits. With manual code+custom allocator+
knowledge that size of set never exceeds 4G nodes, the size of node
could be reduced to 16 bytes, still with 2 or 3 bytes to spare. Whether
it makes significant difference in speed or not, depends on exact size
of your set, on your hardware, on your access pattern, etc... But it
surely *could* make a difference.

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.
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.

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.

On Mon, 2024-04-08 at 13:34 +0300, 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.

I would say that maybe you don't know how to use C++ effectively.
Ex1: I use my own C++ library (based on Clib), burden (learning, remembering,...) is super low.
all that user need to know are very reusable (c++ std-library has lots of things to learn that
are only meaningful in that library). E.g. my 'filesystem' is based on file descriptor, I don't
think what in the std c++ lib can beat mine (except it considers lots more usage environments).
Ex2: Qt is the software I admired since learn C++. It does not use std c++ library.

> 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.
>
>
>
>

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.