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

[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