C++ for embedded: how to learn it in 2021?

[DiTBho]

so, I have to stand up and admit: I don't know how to program in C++, because when I write something I think it in C.

I do spend a lot of time programming in ErLang, C, and assembly (PowerPC and MIPS), and this for sure ads some kind of bias to my "C++ thinking".

Therefore, I want to forget everything, and go back as beginner for a new fresh start.

But: how to learn C++ in the correct way? In 2021? I don't need enterprise knowledge, my focus of interest is only Embedded stuff.

Let me know about books, courses, etc.

(Don't take it offensive, but for me Arduino is not a good reference about C++ ... I do find their libraries clunky and confusing)

[Nominal Animal]

The core problem with embedded C++ is that exceptions (try, catch, throw) are not supported, but in standard (hosted) C++ environments they are the standard mechanism for error propagation.  That is the major one, but there are additional minor problems like static object initialization order, and so on.

It is my opinion that because of those differences, standard C++ programming guides are not suitable as-is.  I suppose one can pick-and-choose what to adopt, but the paradigm, approaching problems "in a C++ way", is different in embedded C++ than in standard hosted C++.

I've looked at the sources of many different embedded C/C++ open source projects, from SmoothieBoards to Arduino/PlatformIO libraries, and to me it seems that problems are approached from the "C way" (with respect to abstractions and how they are used), with freestanding C++ facilities like objects, templates, and atomics used rather like an extension to C.  Note that my experience is limited to open source projects, and therefore is likely skewed; I too would be interested in the opinion of whether this applies to proprietary projects as well, by those who have used C++ in embedded environments in many proprietary projects.

If one were to assume a similar opinion to mine, then it might help to list some of the most useful features of freestanding C++ used in embedded environments.  (I hope others will pipe up, because these are just the most important ones I've noted.)

• Objects, classes, and inheritance
  
  While one can implement plain objects as structures in C, the class hierarchy and inheritance means you can move common functionality and properties to parent classes.  For example, if you drive an ILI9341-controlled display, the commands and data stay the same, but the underlying bus can be 9-bit SPI, 8-bit SPI with a separate command/data output line, or one of multiple parallel bus types.  If you implement a class for the display controller, and a class for each of the bus types, you can use multiple inheritance to create a class that inherits from both, and only contains the needed "glue" code.
  
  If the class interfaces are well designed, the classes can be refactored (implementation rewritten without changing the interface) if needed, and overall the code can be easier to maintain and to port to different architectures.
  
  
• Function overloading
  
  In C++, you can implement "versions" of the same function that only differ by the parameters they take.  The compiler will then choose the correct one (at compile time), depending on the parameters passed.  This simplifies the interfaces and reduces programmer cognitive load, because they then only need to remember that say send() object member or function is used to send data in various forms, instead of say send_string() for strings, send_data() for arrays with specified length, and so on.
  
  
• Templates
  
  Basically, when you define a class or a function, you can leave out the types of certain parameters.  When instantiated (used), the compiler will make sure that there is an implementation with the types specified at that point.  This can be extremely useful, for example if one wants to implement say fixed-point arithmetic; but the downside is that each unique combination of the types usually requires a completely new machine code implementation, so the compiled binary size can grow unexpectedly large with careless use of templates.
  

Again, those are just the ones that have been obvious to me.  I wonder if I should include atomics in there.. I didn't, because I've only ever used the GCC atomic built-ins and only after verifying they don't compile to function calls (i.e., emulation via some kind of locking facility).

I don't remember seeing operator overloading used in a useful manner, and personally do not except when implementing an arithmetic class (say, fixed-point arithmetic, or range arithmetic).  A lot of code (especially those targeted at AVR and ARM architectures) also happily use variable and function attributes provided by GCC and LLVM/Clang as extensions to C and C++.  I don't know how much those are frowned upon in the proprietary world using non-GCC, non-Clang toolchains.

If one wants to be cruel, they could say I myself write embedded/freestanding C++ pretty much as I'd write in a language that was a bastard mix of Python and C.  So take that into account when considering my opinions here.

Hopefully others will pipe up with their opinions and experiences.  I might be completely wrong, and need a restart in C++ myself, too.

[DiTBho]

well, for the sewing industrial machine, I wrote a polymorphic b*tree algorithm in C because I was unable to use C++, and also because I tend to use C++ like if it was C, and this is very very bad!

The resulting code has to handle different kinds of keys
- uint32
- string
- rect(x,y)
and since C has neither templates nor operator-overloading I had to implement this stuff manually
- cmp { is_eq(a,b), is_ne(a,b), is_lt(a,b), is_le(a,b), is_gt(a,b), is_ge(a,b) }
- let { copy(a,b), show(a) }
- check keys and coherence, react to errors, and propagate it to the high layers
for each kind of keys ... and load them as function-pointers in every function of the library, plus a trick to convert a "key" into an array of byte in order to "pass" it to the low-level algorithms (storage, load and save from/to file).

A further problem is ... the code must be MISRA compliant (otherwise I cannot sell the software), so you cannot use too ugly tricks, and your code needs to look "polished" enough for those who care to read it.

Now it's clean and it also works solid as a rock, I can even define and manage an abstract "key", but the whole development-and-testing-process was a very unpleasant, rather masochistic experience, and it took three weeks just to debug and verify the polymorphic stuff, which is really too much time.

Proper use of C ++ could reduce the effort by several orders of magnitude I think, that's why I worry about learning it the right way

[Kalvin]

Just select a subset of C++, and stick with that. C++ has a lots of nice features, but typically you can get things done using a small subset of well understood language features. Even if you were a C++ guru, the next person may not be.

Edit: It is always useful to check the compiler's assembly output, so that you really can see what kind of code is generated from the actual C++ source code. Especially in memory-limited devices, seeing the compiler's output has proven very useful to be able to keep track of device's memory usage.

[SiliconWizard]

But: how to learn C++ in the correct way? In 2021?

Probably by reading Stroustrup's book itself: https://www.stroustrup.com/4th.html
You'll get C++ as it was meant to be used, instead of the fantasy some people have about it.

As to C++ for embedded development, this is an endless source of discussion. There virtually is NO "correct way" of using C++ for embedded development, because this is undefined territory, so everyone is pretty much doing their own thing while being dead convinced it's the right way of doing it. There's been an official attempt at defining a subset of C++ for embedded development: https://en.wikipedia.org/wiki/Embedded_C%2B%2B , but it failed miserably in the end. That did not prevent people from doing exactly the same, as I just said, each in their own way, while thinking it's better than the EC++ attempt.

Here is what Stroustrup thinks about this: https://www.stroustrup.com/bs_faq.html#EC++

One question comes to mind - what is your motivation here for learning C++? This may in itself help guiding you.

[Nominal Animal]

well, for the sewing industrial machine, I wrote a polymorphic b*tree algorithm in C because I was unable to use C++, and also because I tend to use C++ like if it was C, and this is very very bad!

That's a good example of where the OO approach would likely have saved some work for sure.

However, other than object encapsulation and using the class structure to separate the algorithm from the three data types you needed it with, I don't really see a major difference in a freestanding C and a freestanding C++ implementations.  If you agree, then you need to concentrate on learning the aforementioned C++ features, and how to use them in your own embedded code.

A further problem is ... the code must be MISRA compliant (otherwise I cannot sell the software)

AFAIK MISRA C++ has its own list of C++ features it forbids.  AUTOSAR AP 18-10 for C++14 forbids malloc(), free(), goto, casts (except static_cast), multiple inheritance (other than one base class and any number of interface classes), friend, dynamic exceptions, function try blocks, and #pragma.

It is basically its own set of recommended and forbidden patterns and rules, that you need to abide by.  Perhaps "MISRA C++ in an embedded environment" might be a good key phrase?

[AntiProtonBoy]

But: how to learn C++ in the correct way? In 2021? I don't need enterprise knowledge, my focus of interest is only Embedded stuff.

Let me know about books, courses, etc.

Focus on learning the language first, then worry about the embedded stuff later.

Bjarne's books are a good start, as others have suggested, but you also look into books published by Scott Meyers, Andrei Alexandrescu, Sean Parent, Kate Gregory, Herb Sutter.

[westfw]

First, define what "embedded" means for you.  Are you talking itty bitty microcontrollers like an Arduino, significantly capable single board computers like a raspberry pi, or maybe even x86 PC compatibles without a keyboard ("kiosk", "set top boxes", etc.)  I've seen people call each of those "embedded", with not-unreasonable justifications.
I agree with Nominal Animal - most "embedded C++" looks a lot like C code with some additions, while many C++ "experts" will try to convince you to make your C++ look as little like C as possible :-(  That can make the many books, tutorials, libraries, and fora about C++ relatively useless for embedded programmers.  I mean, objects are swell, I guess, but that doesn't mean that EVERYTHING has to be an object.  And to be honest, I think a lot of C++ is like Python and Arduino - it's not so much that the language itself is so great, but that you can find libraries already written that implement SOME things quite elegantly, within a C++ framework.  That's great if you have libraries that are useful to you, but only vaguely interesting if you're writing from scratch.

[DiTBho]

what is your motivation here for learning C++?

I'm full of embedded examples where OO approach would likely have saved some work.
I can do OO in pure C, but it's ... rather masochistic and I'd like to save time and effort.

[DiTBho]

@AntiProtonBoy
added to list!

• Scott Meyers
• Andrei Alexandrescu
• Sean Parent
• Kate Gregory
• Herb Sutter

Thanks!

[DiTBho]

First, define what "embedded" means for you

I quoted sewing machine is the typical scenario where I usually work!
- not Linux, and not even close to RPI
- one/two RISC CPUs coupled with a lot of ASIC stuff

and I have to write the firmware from scratch:
- built-in tests -> C + assembly are perfect here
- bootloader -> C is perfect here
- application layers -> it usually better suites OO approach, therefore C++ ... mumble ?!?

[DiTBho]

I agree with Nominal Animal - most "embedded C++" looks a lot like C code with some additions

That's precisely what I'd like to understand and master: which additions, where to use, where to not abuse, and how to use them the right way.

In 2022 I will for sure write a new firmware for the new sewing machines (bigger and more complex machines): maybe gain pure C with manual OO, maybe "embedded C++ that looks a lot like C code but with some addictions" 

[Kalvin]

Here are two or three things that may come as a surprise for the beginning [embedded] C++ users:

1. The compiler is generating default constructors if not provided explicitly by the programmer.

This may not be what you want, because the default constructors created by the compiler may allocate the objects dynamically from the heap. The default constructor will be called if a programmer accidentally declares the object but doesn't specifically provide the constructor to be used. Been there, done that.

In order to prevent this, declare the default constructor for each and every class as private. This will effectively hide the default constructor, and prevent accidental invocation of the default constructor by creating a compile-time error.

2. The objects declared at global scope level, file static level, or as a static function member will be constructed before the main() is called.

This may not be what you want, and may cause confusion because the objects may be constructed in an order you did not expect.

This can be handled quite easily by creating an init()-function for each module,  and calling the modules' init()-functions from the main() in the order you want. Make these modules' init()-functions to allocate and construct the objects as required, and you are in control again.

3. Declare all destructors as virtual, unless you really want to do otherwise.

[magic]

You should delete implicit constructors which you really don't want to be called under any circumstances.
Marking them private still leaves the possibility of accidental use inside a class method.

That being said, the implicit default constructor only calls the default constructors of all base classes and member objects.
It doesn't allocate memory unless one of the bases/members do.

[rpiloverbd]

I think getting enrolled in an AVR microcontroller course will be helpful. I personally was benefited, worked on Atmega4809.

[DiTBho]

I think getting enrolled in an AVR microcontroller course will be helpful. I personally was benefited.

Anyone specifically? Public (say, promoted by universities)? Commercial?

[gf]

You should delete implicit constructors which you really don't want to be called under any circumstances.

And of course, if the default constructor is deleted, then the class needs at least one other constructor (different from the copy constructor) otherwise you can't create an object of the class type.

Marking them private still leaves the possibility of accidental use inside a class method.

Private was rather used with older c++ versions, where deleted constructors were not yet supported, and private was the only opportunity to hide it at least to the outside.

3. Declare all destructors as virtual, unless you really want to do otherwise.

Non-polymorphic classes don't need a virtual destructor at all (a virtual destructor rather increases the object size unnecessarily, as it implies a vtable).

A virtual destructor is basically only required for a polymorphic base class, if the polymorphic object is supposed to be deleted via a pointer to the base class.

[westfw]

As a training exercise, you could do a lot worse than looking at a swath of Arduino code, and analyzing it to see where you think C++ mechanisms were useful, where they they were obnoxious, where they maybe SHOULD have been used, but weren't (why aren't "pins" objects?), where there are unexpected performance issues (Serial.peek() included even if never used, etc.)
(Note that this is entirely different from actually USING, much less LIKING, the Arduino code/framework/tools.  Arguably, one learns as much from their mistakes as from their good points.  (that'd be true of any C++ program, but "real" embedded C++ programs of moderate size, that are Open Source, seem to be relatively rare.)

[emece67]

.

[DiTBho]

"real" embedded C++ programs of moderate size, that are Open Source, seem to be relatively rare

That's why I am looking for a pay-course, or something.

[emece67]

.

[tggzzz]

I do spend a lot of time programming in ErLang, C, and assembly (PowerPC and MIPS), and this for sure ads some kind of bias to my "C++ thinking".

Lucky you, and good respectively

Therefore, I want to forget everything, and go back as beginner for a new fresh start.

Bad idea. You want to build on your good experience, not "pollute it" with concepts that seem nice but actually aren't.

But: how to learn C++ in the correct way? In 2021? I don't need enterprise knowledge, my focus of interest is only Embedded stuff.

Learn Rust; it looks like it will become good for your career. Understand the restrictions relative to C++ and why they are there. Only then flip to C++ and choose your own subset that doesn't throw away the lessons learned and encapsulated in modern languages like Rust, Go,and xC.

Everybody else chooses their own subset of C++, so why shouldn't you! Good luck ensuring they all play nicely together.

[DiTBho]

Learn Rust; it looks like it will become good for your career.

Umm, I did not think about it, excellent idea 

[AntiProtonBoy]

Here are two or three things that may come as a surprise for the beginning [embedded] C++ users:

1. The compiler is generating default constructors if not provided explicitly by the programmer.

This may not be what you want, because the default constructors created by the compiler may allocate the objects dynamically from the heap. The default constructor will be called if a programmer accidentally declares the object but doesn't specifically provide the constructor to be used. Been there, done that.

In order to prevent this, declare the default constructor for each and every class as private. This will effectively hide the default constructor, and prevent accidental invocation of the default constructor by creating a compile-time error.

2. The objects declared at global scope level, file static level, or as a static function member will be constructed before the main() is called.

This may not be what you want, and may cause confusion because the objects may be constructed in an order you did not expect.

This can be handled quite easily by creating an init()-function for each module,  and calling the modules' init()-functions from the main() in the order you want. Make these modules' init()-functions to allocate and construct the objects as required, and you are in control again.

3. Declare all destructors as virtual, unless you really want to do otherwise.

I have to respectfully disagree with some of these points. Here is why:

1. While the language standards stipulates that conceptually default constructors is called for every new object created, the C++ language also mandates that compilers should generate code with zero cost abstraction. What this means, default constructors will have no run-time cost if they don't need to do work (see code examples below). Furthermore, if you delete default constructors (as per your suggestion), then you disable your ability to create objects, which doesn't make sense at all.

Code: [Select]

// Default constructor will have no runtime cost as there is nothing to do.
struct Foo
{
int a, b, c;
};

// Compiler will generate a default constructor that initializes member variables.
struct Foo2
{
int a = 0, b = 0, c = 0;
};

// This deletes the default constructor, but then it also renders the class useless as you cant construct  it any more.
struct Foo3
{
int a, b, c;

Foo3() = delete;
};

2. Be careful with static initialisation. The order of static initialisation is undefined across different implementation files (or translation units).  See static order initialization fiasco. Also avoid using static global objects unless there is a real good reason to use one.

3. Adding virtual destructors to every object is superfluous for several reasons. First, you only need virtual destructor, if the class is participates in an inheritance hierarchy and engages in polymorphism. Second, if you add a custom destructor to your object, then you also need to implement the class constructor(s) and assignment operator(s) to conform with the rule of three/five/zero convention, which again is superfluous unless you really need to manually track internal state.

I highly recommend to reading through the C++ Core Guidelines for best practices. It's maintained by Bjarne Stroustrup and Herb Sutter. I always refer to it, to make sure I don't do anything silly in C++, because it's very easy to do.

[tggzzz]

I highly recommend to reading through the C++ Core Guidelines for best practices. It's maintained by Bjarne Stroustrup and Herb Sutter. I always refer to it, to make sure I don't do anything silly in C++, because it's very easy to do.

I highly recommend reading the C++ FQA; I'm partial to the section on const correctness. It is a good introduction to the difficulties you must inevitably encounter when trying to use C++.

For advanced readers, develop the arguments for and against it being (a) mandatory (b) forbidden to be able to "cast away constness". Since there are very good use cases why both are desirable, it exercised the C++ committees for about a year in the early 90s. At that point it becomes apparent that the language is becoming part of the problem, not part of the solution.

And when covid prevents you from going to work, create a valid C++ program that never finishes compiling - because the compiler spits out the sequence of prime numbers during compilation. The C++ language design committee refused to believe that was possible, until Erwin Unruh rubbed the committee's nose in it!

[westfw]

arguments for and against

Heh.  In C, you can do powerful but dangerous things because the language is "lightweight"and doesn't stop you.
In C++, they keep complexifying the language to allow similar things to be done.

I don't know for sure which is better.

[magic]

1. While the language standards stipulates that conceptually default constructors is called for every new object created, the C++ language also mandates that compilers should generate code with zero cost abstraction. What this means, default constructors will have no run-time cost if they don't need to do work (see code examples below). Furthermore, if you delete default constructors (as per your suggestion), then you disable your ability to create objects, which doesn't make sense at all.

Yes, it does, because you can define your own constructors.
(That being said, I don't understand what the original issue with implicit constructors allocating memory was supposed to be, I suspect an XY problem).

And when covid prevents you from going to work, create a valid C++ program that never finishes compiling - because the compiler spits out the sequence of prime numbers during compilation. The C++ language design committee refused to believe that was possible, until Erwin Unruh rubbed the committee's nose in it!

It's not possible.
Compilers won't let you get past about 1000

[tggzzz]

And when covid prevents you from going to work, create a valid C++ program that never finishes compiling - because the compiler spits out the sequence of prime numbers during compilation. The C++ language design committee refused to believe that was possible, until Erwin Unruh rubbed the committee's nose in it!

It's not possible.
Compilers won't let you get past about 1000

I've read that is correct.

That magic number would have been added to compilers after their "capability" was demonstrated. ISTR that exceeding the magic number is defined to turn an otherwise valid C++ program into an invalid one.

Does anybody think that is anything other than ridiculous? Yes, it is amusing and demonstrates the "power" of the language, but that can be achieved using brainfuck!

[DiTBho]

At the moment, I need the language to help me with polymorphic things.

[SiliconWizard]

arguments for and against

Heh.  In C, you can do powerful but dangerous things because the language is "lightweight"and doesn't stop you.
In C++, they keep complexifying the language to allow similar things to be done.

I don't know for sure which is better.

I have an idea about this.

[SiliconWizard]

At the moment, I need the language to help me with polymorphic things.

Could you give examples of what you'd like to achieve?

[Nominal Animal]

At the moment, I need the language to help me with polymorphic things.

Could you give examples of what you'd like to achieve?

DiTBho already mentioned a practical one in #2: a B*tree for three different types of keys: unsigned 32-bit integers, strings, and points (or axis-aligned rectangles).  Each tree only has one type of key, of course; so basically three "different" B*trees needed.

As emece pointed out, I should have included constexpr in my list.

[SiliconWizard]

At the moment, I need the language to help me with polymorphic things.

Could you give examples of what you'd like to achieve?

DiTBho already mentioned a practical one in #2: a B*tree for three different types of keys: unsigned 32-bit integers, strings, and points (or axis-aligned rectangles).  Each tree only has one type of key, of course; so basically three "different" B*trees needed.

There's a number of ways to do this in C, just like there's a number of ways to do it in C++.

In C, the typical approach would be to use pointers to "keys". The keys could be objects defined as structures holding either directly the information needed for the key, or a pointer to it, and then one or more functions acting on the key.

This might look like a pretty "manual" way of doing OO, but in practice, when done properly, it's not that much different nor even that many more lines of code. I see practically no difference in the number of lines of code needed for either approach. The C one even possibly takes fewer. The assumption that using C++ would take "orders of magnitude" less effort is not just exaggerated, it's not even backed by reality.

Of course, one benefit of C++ is that it will do more typechecking - sure polymorphic stuff in C is not without risks - and will be potentially more efficient at run time, but even that remains to be checked in practice.

Another approach is to use the preprocessor. Oh yeah, that's so bad, I know.
One thing that would make it easier IMO with the preprocessor is if we could write multi-line macros without having to put a backslash at the end of every line. That's pretty annoying and looks terrible. A simple addition to the preprocessor would allow this. (That could be an opening "[[" and closing "]]", which is used in other languages for writing multi-line strings, for instance...)

But yeah, better generic programming is a good feature. I'm not sure C++ templates and/or a mess of inherited objects is really what we could call good generic programming though. But that's of course a discussion that could last for years.

[magic]

Start with figuring out the requirements because there are many ways to skin the cat.
Speed?
Code size?
Structure size?

Dumb OO approach a'la Java or "C with classes": equip each key object with a pointer to a list of pointers to functions implementing overloaded operators for that key type. Automatic in OO languages, or you could code this in vanilla C if you feel masochistic.

A smarter approach to the above: recognize that it's the same pointer for each key and store it only once in the root of the tree. You can code this in C with little effort: pass the key operators pointer as an argument to internal tree traversal functions, API entry points read the pointer from the root.
BONUS:
Type safety in vanilla C. Don't store the pointer in the root. Take it as an argument to tree_insert(), tree_lookup(), etc and hide those functions from users. For API entry points, create wrappers:

Code: [Select]

struct {some_function_pointer; other_function_pointer;} int_key_ops;
struct int_tree {struct tree tree;};
xxx int_tree_insert(struct int_tree *it, yyy) {return tree_insert(int_key_ops, it.tree, yyy);}
Speed/size tradeoff: separate version of code for each key type, possibly inlined comparison operators. Easily and cleanly solved with C++ templates, maybe doable in C if you compile the same .c file to different .o files with different #defines set by command line.

[AntiProtonBoy]

1. While the language standards stipulates that conceptually default constructors is called for every new object created, the C++ language also mandates that compilers should generate code with zero cost abstraction. What this means, default constructors will have no run-time cost if they don't need to do work (see code examples below). Furthermore, if you delete default constructors (as per your suggestion), then you disable your ability to create objects, which doesn't make sense at all.

Yes, it does, because you can define your own constructors.

Sure, if you want to make your own custom constructors, that's another issue all together. But deleting default constructors on its own doesn't make sense.

[DiTBho]

In C, the typical approach would be to use pointers to "keys". The keys could be objects defined as structures holding either directly the information needed for the key, or a pointer to it, and then one or more functions acting on the key.

This might look like a pretty "manual" way of doing OO, but in practice, when done properly, it's not that much different nor even that many more lines of code. I see practically no difference in the number of lines of code needed for either approach.

I did it in C for production and it works very well, but its backstage was a pretty masochistic experience, I am somehow proud of my code because it also looks shiny and nice, but not so happy because it took me 3 months from the draft to the official commit.

[DiTBho]

pass the key operators pointer as an argument to internal tree traversal functions, API entry points read the pointer from the root.

yes, I did something similar.
Not tricky to design, not difficult to implement, but it requires a lot of effort and it's a bit tricky to test.

[tggzzz]

pass the key operators pointer as an argument to internal tree traversal functions, API entry points read the pointer from the root.

yes, I did something similar.
Not tricky to design, not difficult to implement, but it requires a lot of effort and it's a bit tricky to test.

Do you think it will be easier in C++? If so, why?

[DiTBho]

axis-aligned rectangles

yup! precisely.

planned for the new firmware, also complex numbers in Euler form (r, theta) --> r * e^ (i * theta)

[DiTBho]

Do you think it will be easier in C++? If so, why?

you don't have to care about inner details to make things working OO.
Also, you can overload operators, therefore you have less functions to test, and less testcases.

[brucehoult]

And when covid prevents you from going to work, create a valid C++ program that never finishes compiling - because the compiler spits out the sequence of prime numbers during compilation. The C++ language design committee refused to believe that was possible, until Erwin Unruh rubbed the committee's nose in it!

It's not possible.
Compilers won't let you get past about 1000

I've read that is correct.

That magic number would have been added to compilers after their "capability" was demonstrated. ISTR that exceeding the magic number is defined to turn an otherwise valid C++ program into an invalid one.

Does anybody think that is anything other than ridiculous? Yes, it is amusing and demonstrates the "power" of the language, but that can be achieved using brainfuck!

I have no objections to a language enabling you to compute prime numbers at compile-time -- in fact I desire it highly.

I do, however, want it to be as easy to express and to run as quickly as if I wrote a small stand-alone program to do that, and this program was compiled and run as part of the build process.

[magic]

Do you think it will be easier in C++? If so, why?

you don't have to care about inner details to make things working OO.
Also, you can overload operators, therefore you have less functions to test, and less testcases.

I'm with tggzzz here; I can't see how this solution written in C++ could be anything other than exactly the same code as in C.
Only the duplicated type safety wrappers could be easier (templates).

You can't use overloads in generic code unless they are virtual methods/operators, in which case you are doing the "dumb OO" solution and might as well go for J*va - "compile once, hog memory everywhere". And if you use templates, you are duplicating this code, which is again not the same thing anymore. Maybe you don't care, fair enough.

Not sure how testing with a bunch of different overloads is simpler than with a bunch of ordinary functions. It's basically same thing

[tggzzz]

And when covid prevents you from going to work, create a valid C++ program that never finishes compiling - because the compiler spits out the sequence of prime numbers during compilation. The C++ language design committee refused to believe that was possible, until Erwin Unruh rubbed the committee's nose in it!

It's not possible.
Compilers won't let you get past about 1000

I've read that is correct.

That magic number would have been added to compilers after their "capability" was demonstrated. ISTR that exceeding the magic number is defined to turn an otherwise valid C++ program into an invalid one.

Does anybody think that is anything other than ridiculous? Yes, it is amusing and demonstrates the "power" of the language, but that can be achieved using brainfuck!

I have no objections to a language enabling you to compute prime numbers at compile-time -- in fact I desire it highly.

I do, however, want it to be as easy to express and to run as quickly as if I wrote a small stand-alone program to do that, and this program was compiled and run as part of the build process.

Why is it so valuable?
Isn't there a simpler alternative to achieve the same ends?
Why is there a magic number in the compiler; how can you be sure your application won't exceed it sometime in the future?

Note that the language designers initially denied it was possible, only conceding the point when Erwin Unruh demonstrated it. The template language unexpectedly turned out to be Turing complete.

If the language is so complex the designers don't understand what they have created, what chance do ordinary developers stand?

[magic]

Why is it so valuable?
Isn't there a simpler alternative to achieve the same ends?

Is there?
Like it or not, C++ is the only language which makes generating and using duplicated code that easy.
Templates are perhaps its most appealing aspect - everybody has some "objects" stuff nowadays.

Why is there a magic number in the compiler; how can you be sure your application won't exceed it sometime in the future?

The minimum number specified by C++11 is greater than 640 so it should be enough for everyone.
A sane application probably won't need more than 100 and you know how much it is when writing the code.
GCC has a command line switch if you need more, but they warn that it may run out of stack (perhaps ulimit could help).

If the language is so complex the designers don't understand what they have created, what chance do ordinary developers stand?

Could say the same about almost anything.
Just consider the amount of security bugs everywhere.

[tggzzz]

Why is it so valuable?
Isn't there a simpler alternative to achieve the same ends?

Is there?
Like it or not, C++ is the only language which makes generating and using duplicated code that easy.

Complete nonsense. Many languages have that capability; the first of many was designed in the 1950s!

Templates are perhaps its most appealing aspect - everybody has some "objects" stuff nowadays.

Yes, C++ is a "little bit of this" and a "little bit of that" - none done well. I prefer things that do one thing well, not many things poorly.

If you need objects, use a decent OOP, not a language with them bolted on as an afterthought.

[tggzzz]

If the language is so complex the designers don't understand what they have created, what chance do ordinary developers stand?

Could say the same about almost anything.
Just consider the amount of security bugs everywhere.

Don't confuse language mis-design with poorly designed things written in the language. Don't build castles on sand.

People are moving away from C++ for reasons of security, amongst things. Even the Linux kernel will soon have Rust in it for those and other reasons.

[magic]

Complete nonsense. Many languages have that capability; the first of many was designed in the 1950s!

Fine, the only low level one.
Lisp or whatever other brainfsck don't count

People are moving away from C++ for reasons of security, amongst things. Even the Linux kernel will soon have Rust in it for those and other reasons.

If you can move off of C++ you probably didn't need it in the first place.

Regarding it being a mess, no disagreement.

[DiTBho]

People are moving away from C++ for reasons of security, amongst things. Even the Linux kernel will soon have Rust in it for those and other reasons.

So, are you suggesting learning Rust instead of C++?

Do you think it will be reasonable to try to design an implementation of the next sewing machine firmware in Rust (at least as a "real" learning exercise)?

[brucehoult]

And when covid prevents you from going to work, create a valid C++ program that never finishes compiling - because the compiler spits out the sequence of prime numbers during compilation. The C++ language design committee refused to believe that was possible, until Erwin Unruh rubbed the committee's nose in it!

It's not possible.
Compilers won't let you get past about 1000

I've read that is correct.

That magic number would have been added to compilers after their "capability" was demonstrated. ISTR that exceeding the magic number is defined to turn an otherwise valid C++ program into an invalid one.

Does anybody think that is anything other than ridiculous? Yes, it is amusing and demonstrates the "power" of the language, but that can be achieved using brainfuck!

I have no objections to a language enabling you to compute prime numbers at compile-time -- in fact I desire it highly.

I do, however, want it to be as easy to express and to run as quickly as if I wrote a small stand-alone program to do that, and this program was compiled and run as part of the build process.

Why is it so valuable?
Isn't there a simpler alternative to achieve the same ends?
Why is there a magic number in the compiler; how can you be sure your application won't exceed it sometime in the future?

Note that the language designers initially denied it was possible, only conceding the point when Erwin Unruh demonstrated it. The template language unexpectedly turned out to be Turing complete.

If the language is so complex the designers don't understand what they have created, what chance do ordinary developers stand?

You apparently are talking about C++. I am not.

C++ doesn't make compile time computation as easy to express as runtime computation.

C++ doesn't execute compile time computation as efficiently as runtime computation -- it is orders of magnitude slower. And it has stupidly low arbitrary limits on it.

I want something much much better than C++. And it has existed for many decades in the form, for example, of Common Lisp. FORTH also has similar abilities.

[magic]

So, are you suggesting learning Rust instead of C++?

It's tggzzz, not me. And has indeed already done exactly that yesterday.

I'm not familiar with Rust but what I can say is that I haven't seen them produce a decent migration guide for C/C++ developers and trying to learn the language from their "tutorials" is pain because they are written with little explanation of how the various constructs are implemented and how they relate to established languages.

[tggzzz]

Complete nonsense. Many languages have that capability; the first of many was designed in the 1950s!

Fine, the only low level one.
Lisp or whatever other brainfsck don't count

How about Python? Anything containing a REPL or reflection can do it, e.g. Smalltalk, Java, Forth, Perl, Ruby, many special purpose languages, and apparently C#.

People are moving away from C++ for reasons of security, amongst things. Even the Linux kernel will soon have Rust in it for those and other reasons.

If you can move off of C++ you probably didn't need it in the first place.

Regarding it being a mess, no disagreement.

Indeed, which is why there is little value to learning C++ if you already know C. Better to choose a clean/modern language.

[tggzzz]

So, are you suggesting learning Rust instead of C++?

It's tggzzz, not me. And has indeed already done exactly that yesterday.

I'm not familiar with Rust but what I can say is that I haven't seen them produce a decent migration guide for C/C++ developers and trying to learn the language from their "tutorials" is pain because they are written with little explanation of how the various constructs are implemented and how they relate to established languages.

There isn't any need for a C++->Rust migration guide. Nobody would migrate C++ to Rust!

I don't recognise your point about the tutorials. I don't understand "how the constructs are implemented", and their relationship to other languages is either obvious or is irrelevant.

Having said that, Gosling's original Java Whitepaper was wonderful: it explained why each capability had been chosen, its pedigree, and why they all fitted together harmoniously. (The last would be impossible for C++ because its objective was to be all things to all people.)

The Rust tutorials aren't as good, but they are good enough for any programmer whose mind hasn't been crippled by only learning C++ (with a nod to Dijkstra and COBOL!).

[magic]

Python is not low level and doesn't generate machine code

VM languages with reflection are a more interesting example because they provide something that cannot be replicated in C without a 3rd party JIT library.
But using reflection to generate and compile a few functions ahead of time wouldn't be as convenient as templates.

There isn't any need for a C++->Rust migration guide. Nobody would migrate C++ to Rust!

I mean migrating C and C++ developers, not code. That's something they just can't stop talking about.

You ask about relevance, so let's look at something related to this thread, generics and traits.
https://doc.rust-lang.org/book/ch10-00-generics.html

Simple question: are they static dispatch like C++ templates or dynamic dispatch like Java interfaces? How much code is generated when I define trait Comparable, implement it for a few types and write a generic btree_insert working with that?
Answer: the word dispatch doesn't even appear in this chapter, but the word "tweet" does and we also get to learn how to find the largest number in a vector.

That's what I'm talking about.

And the true answer is: I found some blog post somewhere explaining that Rust generics use static dispatch but there are ways to get dynamic dispatch with traits as well.

[tggzzz]

Python is not low level and doesn't generate machine code

Neither does C/C++! In superscalar processors the output of the compilers is internally converted into many instructions. Yes, in effect "add ax, bx" is interpreted by the hardware.

The processor manufacturers keep that internal instruction set a closely guarded secret, and it changes over time.

VM languages with reflection are a more interesting example because they provide something that cannot be replicated in C without a 3rd party JIT library.
But using reflection to generate and compile a few functions ahead of time wouldn't be as convenient as templates.

Reflection is a dangerous tool, and too many people will use it where there are simpler and better alternatives.

One example of the danger is that in Java it is possible to cause the rest of the VM to "think" that Integer(2) has the same numerical value as int 3, so Integer(2)+Integer(10)=Integer(13). Let's see if the unit tests detect that, ho ho ho

There isn't any need for a C++->Rust migration guide. Nobody would migrate C++ to Rust!

I mean migrating C and C++ developers, not code. That's something they just can't stop talking about.

That seems more sensible

You ask about relevance, so let's look at something related to this thread, generics and traits.
https://doc.rust-lang.org/book/ch10-00-generics.html

Simple question: are they static dispatch like C++ templates or dynamic dispatch like Java interfaces? How much code is generated when I define trait Comparable, implement it for a few types and write a generic btree_insert working with that?
Answer: the word dispatch doesn't even appear in this chapter, but the word "tweet" does and we also get to learn how to find the largest number in a vector.

That's what I'm talking about.

And the true answer is: I found some blog post somewhere explaining that Rust generics use static dispatch but there are ways to get dynamic dispatch with traits as well.

Any programmer that isn't familiar with multiple languages is not an engineer, by definition! I would expect that it would be relatively simple for a C++ programmer with basic competence to migrate themselves to Rust - certainly easier than the reverse.

I wouldn't expect a language tutorial to go into that level of depth because it could well be implementation dependent.

Given that it is probable that Rust will be in the linux kernel (probably drivers initially), I would presume there are no major inefficiencies compared with C. Indeed, the clarifications/simplifications inherent in Rust can be expected to enable the compiler to avoid having to make pessimistic assumptions.

Short term the biggest issue appears to be that Rust compiler is based on LLVM, not gcc. But that's true of many new languages, for reasons that bore me

[DiTBho]

This is the previous cpu-board of the sewing machine.
The new one is based on PowerPC e500.

[SiliconWizard]

In C, the typical approach would be to use pointers to "keys". The keys could be objects defined as structures holding either directly the information needed for the key, or a pointer to it, and then one or more functions acting on the key.

This might look like a pretty "manual" way of doing OO, but in practice, when done properly, it's not that much different nor even that many more lines of code. I see practically no difference in the number of lines of code needed for either approach.

I did it in C for production and it works very well, but its backstage was a pretty masochistic experience, I am somehow proud of my code because it also looks shiny and nice, but not so happy because it took me 3 months from the draft to the official commit.

Sure, but again, what makes you think it would have taken less time using C++? Actually, since you do not master C++ as far as I've understood, between learning it and using it efficiently to implement this, I bet it would have taken you more time.

But do not take my word for it. Since you seem to be willing to give it a try, just do it! Try reimplementing this in C++ and see what you get.

[SiliconWizard]

Oh uh, I usually agree with tggzzz on programming topics. Except about Rust. But hey, let's not pollute this thread!

[tggzzz]

Oh uh, I usually agree with tggzzz on programming topics. Except about Rust. But hey, let's not pollute this thread!

FWIW I'm not a Rust fanbois; I haven't yet seriously "kicked its tyres".

Competent people that have "kicked its tyres" seem to believe that it has sufficient characteristics to be a useful improvement on the existing languages/tools. That makes it worthy of attention.

The same can be said for a few other languages for different application domains.

[ve7xen]

C++ doesn't make compile time computation as easy to express as runtime computation.

I would argue that with the advent of constexpr, it actually does, at least since C++14's improvements.

[SiliconWizard]

Oh uh, I usually agree with tggzzz on programming topics. Except about Rust. But hey, let's not pollute this thread!

FWIW I'm not a Rust fanbois; I haven't yet seriously "kicked its tyres".

Oh, I didn't imply you were. But yes, if you're interested, you should definitely try using it and see what you like and what you don't like in practice.

Competent people that have "kicked its tyres" seem to believe that it has sufficient characteristics to be a useful improvement on the existing languages/tools. That makes it worthy of attention.

I agree it is. But after taking a closer look at it for a while, I've also seen a number of points that were IMHO not so good. That would certainly warrant a completely separate thread though.

[magic]

Neither does C/C++! In superscalar processors the output of the compilers is internally converted into many instructions. Yes, in effect "add ax, bx" is interpreted by the hardware.

The processor manufacturers keep that internal instruction set a closely guarded secret, and it changes over time.

Which makes the whole remark irrelevant - writing or generating assembly is as close to metal as it gets. C takes me there, Python doesn't come close.

Besides, I don't know about "add ax, bx", but "add eax, ebx" surely translates to a single µOP. The do release enough to know that much. And it has nothing to do with superscalar - i8086 was microcoded and single issue and you could make some trivial RISC like MIPS run superscalar on bare metal.

I wouldn't expect a language tutorial to go into that level of depth because it could well be implementation dependent.

If I suspected something like that about a language I would be more cautious recommending it to embedded developers.

BTW, I will have to dig how they handle multiple (conflicting or not) instantiations of the same generic in different modules and linking this clusterfuck together. C++ loves such things.

Given that it is probable that Rust will be in the linux kernel (probably drivers initially), I would presume there are no major inefficiencies compared with C. Indeed, the clarifications/simplifications inherent in Rust can be expected to enable the compiler to avoid having to make pessimistic assumptions.

Well, this cuts both ways. They fell for hype and rewrote the whole thing in C++ at one point and Linus curses that language to this day

[brucehoult]

Python is not low level and doesn't generate machine code

Neither does C/C++! In superscalar processors the output of the compilers is internally converted into many instructions. Yes, in effect "add ax, bx" is interpreted by the hardware.

That's nothing to do with superscalar (running multiple machine language instructions in parallel). You're talking about CISC, such as x86.

CPUs running true RISC instruction sets such as RISC-V or MIPS or Alpha don't have secret internal instructions. The instruction you see is the instruction that goes down the pipeline.

ARM is somewhere in the middle. Most instructions are like any other RISC. The load/store multiple are expanded internally into the obvious series of single-register transfers. Complex addressing modes and on some implementations also ALU operations that combine shift/rotate with something else might be broken down into a couple of uops.

Even on x86, an instruction like "add ax, bx" will be ONE uop. Multiple uops is for instructions that use memory, especially with complex addressing modes, or operations that involve reading and writing memory in the same instruction e.g. adding a register to a memory location.

[brucehoult]

C++ doesn't make compile time computation as easy to express as runtime computation.

I would argue that with the advent of constexpr, it actually does, at least since C++14's improvements.

That does help a lot, yes.

I'm not sure it's fast. I guess I could do an experiment...

[tggzzz]

Neither does C/C++! In superscalar processors the output of the compilers is internally converted into many instructions. Yes, in effect "add ax, bx" is interpreted by the hardware.

The processor manufacturers keep that internal instruction set a closely guarded secret, and it changes over time.

Which makes the whole remark irrelevant - writing or generating assembly is as close to metal as it gets. C takes me there, Python doesn't come close.

Clearly incorrect; you can't access lower levels, but other people can and do. They even change the internal instructions in processors operating in customers' premises - that's how all the recent slew of security breaches are mitigated.

Besides, I don't know about "add ax, bx", but "add eax, ebx" surely translates to a single µOP. The do release enough to know that much. And it has nothing to do with superscalar - i8086 was microcoded and single issue and you could make some trivial RISC like MIPS run superscalar on bare metal.

You are almost certainly correct about the specific (pseudo!) instruction I used. But if different instructions and/or addressing modes that touch memory are used, then the instructions output by  the C compiler will be interpreted.

I wouldn't expect a language tutorial to go into that level of depth because it could well be implementation dependent.

If I suspected something like that about a language I would be more cautious recommending it to embedded developers.

Then you shouldn't be recommending C for that purpose!

The original C tutorials (i.e. K&R and The C Puzzle Book) certainly didn't discuss anything like that. For good reasons they don't even mention stacks, even though all implementations will be based around stacks.

Having said that, C has finally got around to specifying a memory model - quarter of a century after other mainstream languages did it, and a decade after Boehm had to forcibly remind people that threads couldn't be implemented as a library in C.

BTW, I will have to dig how they handle multiple (conflicting or not) instantiations of the same generic in different modules and linking this clusterfuck together. C++ loves such things.

Given that it is probable that Rust will be in the linux kernel (probably drivers initially), I would presume there are no major inefficiencies compared with C. Indeed, the clarifications/simplifications inherent in Rust can be expected to enable the compiler to avoid having to make pessimistic assumptions.

Well, this cuts both ways. They fell for hype and rewrote the whole thing in C++ at one point and Linus curses that language to this day

That cuts both ways: given Torvald's "sub-optimal" experiences that you mention, his not objecting to Rust in the kernel is indicative.

[magic]

But if different instructions and/or addressing modes that touch memory are used, then the instructions output by  the C compiler will be interpreted.

It changes nothing about the fact that C prepares those architectural instructions in advance and some languages don't.
And "interpretation" is a rather melodramatic way to describe what happens to most instructions.

Then you shouldn't be recommending C for that purpose!

The original C tutorials (i.e. K&R and The C Puzzle Book) certainly didn't discuss anything like that. For good reasons they don't even mention stacks, even though all implementations will be based around stacks.

Because C has no generics.

But if it had generics, and if it were implementation defined whether they blow up into many variants during compilation, and if the reference implementation were silent about what it can promise in this regard, then yes, I would think twice before using C for anything memory constrained.

BTW, I found that the book does actually explain the implementation of generic function. In the subchapter on generic data types

[tggzzz]

If you included the context in which I made my statements, you would see that you are making strawman points.

In this context, generics are a complete red herring.

[magic]

The whole exchange started with my rant about generics and poor documentation of low level aspects of the language. To which you said:  maybe it's not documented because it's implementation defined. I assumed that to be the context

[SiliconWizard]

I'm not sure what exactly you guys were discussing after reading your exchange. I think you were not talking about the same thing exactly though, hence the discussion running in circles.
As to generic programming, it's an entire topic in itself, there are many ways of tackling it and I don't think C++ is the best at this either. But that using generics would potentially "blow up" code size is pretty much a given in the general case, at least if you want it to be implemented statically at compile time. From the POV of code size, the typical C approach (very textbook example with the qsort() function and siblings) with pointers and function pointers is usually still the winner, except possibly in very particular cases with *very small* functions.

There is probably room for optimization and code reuse from the compiler's side - for C++ templates for example - but I will never expect this to be particularly impressive in the general case.

[brucehoult]

C++ doesn't make compile time computation as easy to express as runtime computation.

I would argue that with the advent of constexpr, it actually does, at least since C++14's improvements.

That does help a lot, yes.

I'm not sure it's fast. I guess I could do an experiment...

OK, given this code:

Code: [Select]

#include <stdio.h>

constexpr long fib(long n) {
  return n < 2 ? n : fib(n - 1) + fib(n - 2);
}

int main(){
  printf("%ld\n", fib(36));
  return 0;
}

... gcc -O takes 1.58 seconds to compile it, then the compiled program takes 0.01 seconds to run (basically, helloworld).

If I change the 36 to 37 then gcc takes 1.99 seconds to compile it, then the compiled program takes 0.130 seconds to run.

Basically, with 37 gcc hits a time limit and gives up on evaluating it at compile time.

If I do it for 36 but disable the compile-time evaluation then it takes 0.100 seconds to run.

So compile-time evaluation takes around 15 times as long as running compiled code. And there is a definite and fairly low upper limit to how much computation is permitted.


Clang refuses to compile-time evaluate this function for any argument except 0 or 1, no matter the optimisation level. Clang will compile-time evaluate a singly-recursive function such as factorial.

[westfw]

a B*tree for three different types of keys: unsigned 32-bit integers, strings, and points (or axis-aligned rectangles).

OK, I'm curious.  Why did you need a B*Tree(s)?  One of my observations has been that much "embedded" software rarely needs the sort of performance one gets from "advanced" algorithms, just because "N" is rarely very large...

Do you think it will be easier in C++? If so, why?

Convince me that in C++, they would not have wrapped some polymorphism around std::map (RB trees by default, I think?  Or one of the other tree-type implementations designed to replace map) and called it done...
(No, you probably couldn't run std::map on your Arduino-class hardware.  But you wouldn't have needed to, either.  OP's system was significantly bigger.)
Call in one month to search, figure out, and add the polymorphism, instead of 3M to implement from scratch.
(quicker it it was already part of your toolbook, of course.)

It's vaguely how I feel about Python.  As an ASM/C coder I "hate" programming in an interpreted language with no clear idea how any particular library is implemented, or how "fast" or "efficient" it is.  But I put it together cause I don't want to write a GUI, or an XML or JSON parser in C or ASM, and when I'm done the python code runs ... plenty fast enough, for the cases I'm using.
(Or for that matter, CircuitPython vs Arduino vs Bare C - all zippier (on current hardware) than a BASIC Stamp.  And people did all sorts of neat things with BASIC Stamps.)

[Nominal Animal]

So, I did some crude code experimentation with a binary search tree, with the aim of being MISRA C++ compliant (except that I don't have the actual spec, so I'm guessing) for use in an embedded (freestanding C/C++) environment while maximising maintainability, readability, and verifiability, without compromising performance too much; all just to see what I would end up with.

Here's how I went about it.

At the very core, I defined a key comparison function that we define for each key type we need.  For example,

Code: [Select]

enum class compares_as { below, equal, above };

template <class T>
compares_as key_compare(T key1, T key2)
{
    return (key1 < key2) ? compares_as::below :
           (key1 > key2) ? compares_as::above :
                           compares_as::equal ;
}

template <>
compares_as key_compare<const char *>(const char *key1, const char *key2)
{
    const int  rc = strcmp((key1) ? key1 : "", (key2) ? key2 : "");
    return (rc < 0) ? compares_as::below :
           (rc > 0) ? compares_as::above :
                      compares_as::equal ;
}
The above implements key_compare() for all numeric types, and for strings using strcmp().  For a 2D point (or complex number) type, something like

Code: [Select]

template <>
compares_as key_compare<vec2>(vec2 key1, vec2 key2)
{
    return (key1.y < key2.y) ? compares_as::below :
           (key1.y > key2.y) ? compares_as::above :
           (key1.x < key2.x) ? compares_as::below :
           (key1.x > key2.x) ? compares_as::above :
                               compares_as::equal ;
}
should work, sorting points in ascending y coordinates, and points with the same y coordinate in ascending x coordinates.

The binary search tree node template class heavily relies on the compares_as enumeration logic above.  Omitting sensible destructors, I initially came up with

Code: [Select]

template <class K, class V>
class node {
    private:
        K          key;
        V          val;
        node<K,V> *lt;
        node<K,V> *gt;

    public:
        node(K key, V val): key(key), val(val), lt(nullptr), gt(nullptr) { }

        K get_key(void) { return key; }
        V get_val(void) { return val; }

        compares_as towards_key(K otherkey) { return key_compare(otherkey, key); }

        node<K,V> *get_child(compares_as direction) {
            return (direction == compares_as::below) ? lt :
                   (direction == compares_as::above) ? gt :
                                                       nullptr;
        }

        bool add_child(compares_as cmp, K newkey, V newval) {
            if (cmp == compares_as::below) {
                if (!lt) {
                    lt = new node<K,V>(newkey, newval);
                    return true;
                }
            } else
            if (cmp == compares_as::above) {
                if (!gt) {
                    gt = new node<K,V>(newkey, newval);
                    return true;
                }
            }
            return false;
        }

        int in_order(node<K,V> *parent, compares_as descent, int (*callback)(node<K,V> *, node<K,V> *, compares_as)) {
            int rc;

            if (lt) {
                rc = lt->in_order(this, compares_as::below, callback);
                if (rc) {
                    return rc;
                }
            }

            rc = callback(this, parent, descent);
            if (rc) {
                return rc;
            }

            if (gt) {
                rc = gt->in_order(this, compares_as::above, callback);
                if (rc) {
                    return rc;
                }
            }

            return 0;
        }
};
The node::in_order() member function is a recursive function that traverses the tree, calling the callback function for each visited node in order.  I used it to output the trees generated in Graphviz DOT format, for simple visual verification.  (EDIT: It is not supposed to be included in actual used code, and is not MISRA compliant; I included it only because it lets us verify test trees very easily, with just one helper call back function per tree/node type.)

The "trick" is the node::towards_key() member function, which compares the specified key to the key in the current node.  It simply calls the key_compare() function we defined earlier.  This way, to add new key types, one only needs to define a template specialization for key_compare().

The actual tree template class:

Code: [Select]

template <class K, class V>
class tree {
    private:
        node<K,V> *root;
    public:
        tree(): root(nullptr) { }

        bool add(K newkey, V newval) {
            if (root) {
                node<K,V>   *next = root;
                node<K,V>   *curr;
                compares_as  direction;

                do {
                    curr = next;
                    direction = curr->towards_key(newkey);
                    next = curr->get_child(direction);
                } while (next);

                return curr->add_child(direction, newkey, newval);

            } else {
                root = new node<K,V>(newkey, newval);
                return true;
            }
        }

        bool find(K thekey, V* oldval) {
            if (root) {
                node<K,V>   *curr = root;
                compares_as  direction;

                do {
                    direction = curr->towards_key(thekey);
                    if (direction == compares_as::equal) {
                        if (oldval) {
                            *oldval = curr->get_val();
                        }
                        return true;
                    }
                    curr = curr->get_child(direction);
                } while (curr);
            }

            return false;
        }

        V get(K thekey, V notfound) {
            if (root) {
                node<K,V>   *curr = root;
                compares_as  direction;

                do {
                    direction = curr->towards_key(thekey);
                    if (direction == compares_as::equal) {
                        return curr->get_val();
                    }
                    curr = curr->get_child(direction);
                } while (curr);
            }

            return notfound;
        }

        int in_order(int (*callback)(node<K,V> *, node<K,V> *, compares_as)) {
            if (root) {
                return root->in_order(nullptr, compares_as::equal, callback);
            } else {
                return 0;
            }
        }
};
To instantiate a tree with integer keys and integer values, I used

Code: [Select]

    tree<int, int> itree;
    itree.add(4, 1);
    itree.add(2, 2);
    itree.add(6, 2);
    itree.add(1, 3);
    itree.add(3, 3);
    itree.add(5, 3);
    itree.add(7, 3);
and another with C string keys and values with

Code: [Select]

    tree<const char *, const char *> stree;
    stree.add("one", "1");
    stree.add("two", "2");
    stree.add("three", "3");
    stree.add("four", "4");
    stree.add("five", "5");
    stree.add("six", "6");
It seems to work.

Because this was the first go at it, I omitted all comments, and the code is quite crude.  Remember, first sketch.  Here are my observations on this exercise:

• Adding new key types using this scheme is very easy, as it only requires a new template specialization for the key_compare() function.
  The only requirement is that the key set is totally ordered with respect to key_compare(), without conflicts.
• Names matter. compares_as seemed a good name while I wrote the key_compare() function, but it is a poor name for the use cases.  order would be a more descriptive name.
• The root node is created in tree::add(), but all subsequent ones in node::add_child().  This needs documenting, and probably a comment in both places for maintenance purposes.
• I completely omitted destructors and deleteing the nodes created with new.
• I avoided virtual methods, to keep any overhead (when compiled with optimizations enabled) to a minimum.
  I do not claim this code is efficient, though.
• Since the tree class only cares about the keys in their ordinal sense, an unit test with say integer keys suffices for the tree template class verification.
  All key types should be carefully verified, so that each key type forms a totally ordered set.  But since that is just one function, it should be easy to do.
• I do think the code is a lot more compact, readable, and maintainable than the C (or GNU C) version I might write, assuming – as we are in this thread – that multiple key types are actually needed.

At this point, I'm very interested in what others think of the approach (given the aims stated at the beginning of this post), and whether DiTBho believes this kind of approach would have helped with their B*tree implementation.  The code itself is just crude first sketch; and I apologise for the lack of comments.

[DiTBho]

I'm curious.  Why did you need a B*Tree(s)?  One of my observations has been that much "embedded" software rarely needs the sort of performance one gets from "advanced" algorithms, just because "N" is rarely very large...

I call it "sewing machine" but it's an "embroidery machine" with 400 sewing needles per line, and there is a very complex motion engine in order to process embroidery on silk, microfiber, in addition to the fact that it also works curtains and tablecloths.

You can also partition the tasks and allocate one line to embroider sexy lace panties for women, and the other line to embroider napkins.

The number of items (especially when n = patterns) to search for is very large, k0 * log(n) << k1 * n , and the engine requires fast search to satisfy deadlines in the motion engine in order to drive each 400 sewing needles line.

[DiTBho]

The old board (in the pic) runs VxWorks v5.3.

[DiTBho]

The current toolchain, ICE and BSP don't support C++, only C ... so, in any case, I have to pay for a new package-set (ah, Windriver ...      )

[DiTBho]

So, I did some crude code experimentation with a binary search tree
[...]

thank you a lot! I will for sure study this draft 

Code: [Select]

void btree_methods_string_init
(
    p_btree_t p_btree
)
{
    p_btree->context.coin.method.cmp.isle = cmp_isle; /* A <= B */
    p_btree->context.coin.method.cmp.islt = cmp_islt; /* A < B */
    p_btree->context.coin.method.cmp.isge = cmp_isge; /* A >= B */
    p_btree->context.coin.method.cmp.isgt = cmp_isgt; /* A > B */
    p_btree->context.coin.method.cmp.iseq = cmp_iseq; /* A == B */
    p_btree->context.coin.method.let.show = let_show;
    p_btree->context.coin.method.let.copy = let_copy; /* A = B */
}

That's what I need to define for each key-type.

To compare strings, I use lexicographic ordering. To compare rect(x,y) and cplx numbers in Euler form, I only consider the module, unless the two modules are equal, in that case, I also consider the angle.

in rect(x,y): { x,y } are a pair of uint32
in cplx(r,theta): { r , theta} are a pair of fixedpoint

Code: [Select]

/*
 * finds and returns the record to which a coin refers
 */
btree_ans_t btree_coin_find
(
    p_btree_t p_btree,
    btree_coin_t coin
)
{
    p_btree_node_t       p_root;
    p_btree_node_t       p_node;
    btree_coin_t         penny;
    btree_item_method2_t cmp_iseq;
    btree_item_method2_t let_copy;
...
    p_root   = p_btree->context.p_root;
...
    cmp_iseq = p_btree->context.coin.method.cmp.iseq;
    let_copy = p_btree->context.coin.method.let.copy;
...
        while (...)
        {
            let_copy(p_btree, penny, p_node->as.leaf.coin[i0]);
            is_found = cmp_iseq(p_btree, penny, coin);
            if (is_found)
            {
...
That's how the code looks like with function-methods to copy and compare.

Code: [Select]

LG__ ________________ c:0002 d:01 lib_btree_z_v1.btree_coins_show
____ ________________ c:0001 d:01 lib_btree_z_v1.btree_height_get
LG__ _123456_________ c:0616 d:01 lib_btree_z_v1.btree_coin_insert
LG__ _1234___________ c:7708 d:01 lib_btree_z_v1.btree_coin_find
____ ________________ c:0139 d:01 lib_btree_z_v1.record_make
L___ ________________ c:0005 d:01 lib_btree_z_v1.btree_start_new
L___ ________________ c:0081 d:01 lib_btree_z_v1.node_make_leaf
_G__ ________________ c:0106 d:01 lib_btree_z_v1.node_make
LG__ __2_____________ c:7837 d:01 lib_btree_z_v1.node_leaf_get
L___ _12_____________ c:0059 d:02 lib_btree_z_v1.node_insert_leaf
LG__ ________________ c:0077 d:02 lib_btree_z_v1.node_insert_leaf_after_splitting
____ _12_____________ c:0183 d:01 lib_btree_z_v1.node_cutpoint_get
LG__ _123____________ c:0092 d:03 lib_btree_z_v1.node_insert_parent
LG__ ________________ c:0011 d:02 lib_btree_z_v1.node_insert_new_root
_G__ ________________ c:0081 d:01 lib_btree_z_v1.node_iLP_get
LG__ ________________ c:0067 d:02 lib_btree_z_v1.node_insert
_G__ ________________ c:0015 d:01 lib_btree_z_v1.node_insert_after_splitting
_G__ ________________ c:0005 d:02 lib_btree_z_v1.destroy_tree
LG__ _12_____________ c:0046 d:04 lib_btree_z_v1.nodes_destroy
_G__ ________________ c:0053 d:02 lib_btree_z_v1.btree_coin_delete
LG__ _1234___________ c:0099 d:04 lib_btree_z_v1.node_entry_delete
LG__ ________________ c:0099 d:02 lib_btree_z_v1.node_entry_remove
LG__ ________________ c:0051 d:04 lib_btree_z_v1.node_iNG_get
LG__ ________________ c:0047 d:03 lib_btree_z_v1.nodes_coalesce
_G__ ________________ c:0007 d:02 lib_btree_z_v1.node_root_adjust
LG__ ________________ c:0005 d:02 lib_btree_z_v1.nodes_redistribute

This is a shot with minimal coverage, considering a minimum test with
- start a new tree
- fill 20 keys
- random delete and check
- check global consistency
- check local consistency
- delete everything (tree destroy + check for memory leakage)
- fill the tree again
- fill it again with special keys to force nodes_redistribute
- selective delete and check for consistency (forces nodes_redistribute)
- fill it again with special keys to force nodes_coalesce

The most of the functions have to work with both "glue" (internal node) and "leaf" nodes.

I also need to check the maximal stack deep because the code is not "recursion free".

[SiliconWizard]

A quick glance showed that it uses new to allocate nodes, is that really MISRA C++ compliant? (Sorry I only know MISRA C, and dynamic allocation is frowned upon.)

[Nominal Animal]

The in_order() function is definitely not MISRA compliant, and not intended to be; I only included it because it helps testing the generated tree structures quickly and visually.  (I use Graphviz DOT language output, with the third parameter to the callback, compares_as, providing the flag for the directed graph tail label (< or >).)  I edited my post to make that clearer; one should not need it in final code.

I vaguely recall that there is a way to traverse trees without recursion or stack, with just fixed amount of storage (some sort of direction cookie or something, with checking which side one came from when going towards the root), but it requires a parent pointer in each node.  If tree traversal is needed, then I'd modify the node structure accordingly, and implement that.

A quick glance showed that it uses new to allocate nodes, is that really MISRA C++ compliant?

I don't know, I don't have MISRA C++ either.

If it matters, AUTOSAR AP Release 18-10 for C++14, which targets C++14 but builds upon MISRA C++ 2008, forbids malloc()/free() but allows new/delete in section 6.1.

If the tree nodes are of fixed size, I could change the code to use a template parameter for statically allocating the tree nodes, with a secondary tree as a singly-linked list holding the unused nodes for quick reuse.  Populating the next tree node would move from node::add_child() to tree::add(), but the populated node would only be removed from the free list if the node::add_child() call succeeded.  So, I don't think it matters that much here, both dynamic and static allocation patterns are easily achieved with very minimal changes.  It is why I didn't include any delete operators or destructors.

Code: [Select]

    p_btree->context.coin.method.cmp.isle = cmp_isle; /* A <= B */
    p_btree->context.coin.method.cmp.islt = cmp_islt; /* A < B */
    p_btree->context.coin.method.cmp.isge = cmp_isge; /* A >= B */
    p_btree->context.coin.method.cmp.isgt = cmp_isgt; /* A > B */
    p_btree->context.coin.method.cmp.iseq = cmp_iseq; /* A == B */


Why separate comparison functions, instead of just one that returns less/below, equal, greater/above?

If cmp(x,y) returns 0 if equal, -1 if less/below, or 1 if greater/above, then
      logic │ expression
    ────────┼────────────────
     x == y │ cmp(x, y) == 0
     x != y │ cmp(x, y) != 0
     x <= y │ cmp(x, y) <= 0
     x >= y │ cmp(x, y) >= 0
      x < y │ cmp(x, y) < 0
      x > y | cmp(x, y) > 0

Is there something in MISRA that forbids this?

You see, it is of crucial importance that the key set is totally ordered, meaning that if x < y and y <= z, then z > x or the data structure will fail because the keys are not properly ordered.

Another option is to use a bit mask, so that 0 denotes "not comparable" or "unknown order" (which the unit tests would try to look for, since it should not happen).  Then, say

Code: [Select]

/* Bit 0: Equal, Bit 1: Less/Below, Bit 2: Greater/Above */
enum order_bits {
    MASK_EQ = 1,
    MASK_LT = 2,
    MASK_LE = 3,
    MASK_GT = 4,
    MASK_GE = 5,
    MASK_NE = 6,
};
in which case we'd have
      logic │ expression
    ────────┼───────────────────────────
     x == y │ (cmpmask(x, y) & MASK_EQ)
     x != y │ (cmpmask(x, y) & MASK_NE)
     x <= y │ (cmpmask(x, y) & MASK_LE)
     x >= y │ (cmpmask(x, y) & MASK_GE)
      x < y │ (cmpmask(x, y) & MASK_LT)
      x > y | (cmpmask(x, y) & MASK_GT)
and the unit test would ensure that for all possible keys, cmpmask(x, y) returns a value between 1 and 6, inclusive.

[DiTBho]

Why separate comparison functions, instead of just one that returns less/below, equal, greater/above?

It's a development choice, it facilitates the automatic debugging with ICE.

[Nominal Animal]

I see.  I do see the ordering of the keys absolutely crucial here; risk of bugs in the comparison functions that cause violations in the ordering are very, VERY dangerous, in my opinion.  (They lead to "Heisenbug" type of bugs, where the bug occurs for the same data only if the tree structure is similar enough.)

I am also not at all sure B*trees are the best option, but I do see that you have tight timing constraints, and any suggestions for alternate solutions would require in-depth detailed knowledge of the data stored, accesses needed, et cetera; something you probably do not want to discuss on an open forum, considering it is a proprietary product. 

[SiliconWizard]

I see.  I do see the ordering of the keys absolutely crucial here; risk of bugs in the comparison functions that cause violations in the ordering are very, VERY dangerous, in my opinion.  (They lead to "Heisenbug" type of bugs, where the bug occurs for the same data only if the tree structure is similar enough.)

Yes absolutely!

[ve7xen]

So compile-time evaluation takes around 15 times as long as running compiled code. And there is a definite and fairly low upper limit to how much computation is permitted.


Clang refuses to compile-time evaluate this function for any argument except 0 or 1, no matter the optimisation level. Clang will compile-time evaluate a singly-recursive function such as factorial.

Aligns reasonably well with my experience, I would have estimated 50x slower. For testing, it's useful to use -std=c++20 and the consteval specifier on the function instead, which forces compile-time evaluation. Otherwise the compiler is permitted to fall back to runtime evaluation, and both gcc and clang will do so if compile time evaluation fails - and both have limits on execution length and depth in compile-time context. With clang, this is controlled with -fconstexpr-steps and -fconstexpr-depth gcc uses -fconstexpr-ops-limit and -fconstexpr-loop-limit so you can override it if needed.

With consteval and the tunables, clang 13 will compile your code at n=36 in (!!) 83s on my machine and microseconds of runtime. With consteval elided, it uses 33ms in compile time and 68ms in runtime. So a factor of over 1000 . gcc 11.1 does a much more efficient job taking 2.93s of compile time vs 50ms compile + 86ms run (~34x). Both required the tunables to do compile-time execution at n=36 on my system. I believe the performance difference might be due to the fact that gcc seems to cache constexpr function calls, and clang may not, which in this particular test case is catastrophic, but probably not that relevant on 'real' code. OTOH, executing without the cache is I guess closer to what the runtime code is doing.

In embedded use I have found it useful for computing things like filter constants, PLL divisors, baud divisors, LUTs and such like in a much more elegant manner that supports most of C++ features (loops, arrays), unlike C macros, and without wasting code space on functions that will be called once at initialization. For these kinds of uses you're not really going to run into the computation limits. Much of the standard math library is not constexpr though, so you may find gcem useful for this purpose to get constexpr math functions.

I wonder how performance compares to wanton abuse of C macros... though they may be too limited for such a test, lacking loops and recursion.

In general though I think 'modern' c++ (11, 14, 17) brings a lot to the table, if all you know of is C++03 or earlier and didn't bother with that. constexpr & related and template parameters in particular are very nice for containing code size. type deduction, binary literals, and range-for are nice conveniences. lambdas... That 8-year hiatus really brought a lot of major improvements, and they keep coming.

[DiTBho]

I am also not at all sure B*trees are the best option

Yup, for certain reasons, and considering rect(x,y), R-tree should be better than b*tree.

[westfw]

Quote from: DiTBho on December 12, 2021, 05:43:47 am

But: how to learn C++ in the correct way? In 2021? I don't need enterprise knowledge, my focus of interest is only Embedded stuff.
Let me know about books, courses, etc.

But also:

This is the previous cpu-board of the sewing machine.
runs VxWorks v5.3.
[Dual CPUs, massive amounts of RAM...]
   :
The new one is based on PowerPC e500.
   :
400 sewing needles per line, and there is a very complex motion engine

I'm going to jump back to the original question, and perhaps go out on a limb, and say that with your environment and experience, "standard, full, C++" classes and books would do fine for learning C++.  You have the power and OS to be able to use (at least theoretically) all of the language features, and the experience to be able to analyze pieces that might not make sense and accept/reject them as appropriate.

The next question is whether there are good C++ books/classes/etc for people who are already experienced programmers.  :-(
I took https://www.coursera.org/learn/c-plus-plus-a which seemed to have reasonable content, but ... was pretty awful as a class.  (slow, droning prof, assignments whose difficulty was far beyond the class material, etc.)  It might have improved since then; IIRC his downloadable book was OK.  (but then, I haven't really jumped on C++ afterward, anyway.)

[DiTBho]

Dual CPUs, massive amounts of RAM

256Mbyte of ram on the old board (32bit hardware pointers, 32bit CPU)
8Gbyte of ram on the new board (64bit hardware pointers, 64bit CPU)

The next question is whether there are good C++ books/classes/etc for people who are already experienced programmers.  :-(

Yup, precisely!

I took https://www.coursera.org/learn/c-plus-plus-a which seemed to have reasonable content, but ... was pretty awful as a class.  (slow, droning prof, assignments whose difficulty was far beyond the class material, etc.)  It might have improved since then; IIRC his downloadable book was OK.  (but then, I haven't really jumped on C++ afterward, anyway.)

Coursera has a pay-courses, 1 week for free, then 40 USD/month.
I think I'll sign up