To the question of sets
Alice: Why is this place a VERY weird place?
Dodo: But because all the other places are not very strange. There must be at least one VERY strange place.
So, let’s take a look at the text of the template class BitSet with the aim of adapting it to the requirements of MK, the main areas of optimization were defined earlier. You can, of course, write your own class from scratch, but let's not neglect the opportunity to get acquainted with good solutions, because the STL library (not to be confused with spl) has been known for a long time and is used everywhere. First you need to find the source code, after a short trip on the Internet, I just opened the directory with my MinGW and looked for the required file, which I intend to discuss further.
At the beginning we see a little more than a page with copyright and the text of the license, as well as a variety of warnings - well, you can skip this, this is for lawyers. Next up are includes and I thank the authors - each one is accompanied by a comment about what we want to get from each file - everyone would do that, the work of
And here light misunderstandings begin - at first they define the template auxiliary structure struct _Base_bitset (why exactly the structure, and not the class, since they are interchangeable), in which they determine the type for data storage and it is again specified directly - we change it to our own. Next, two instances of this auxiliary structure are determined - for one storage unit (well, this is understandable, to increase the efficiency of the code) and for a degenerate example without storage at all (probably for error handling), until we touch this code.
Next, we find the main class class bitset (now the class), derived from the template structure (yes, in C it is possible, it is not clear why to do this, but it is possible), in which the storage type is again determined and changed to ours again. But here I wondered - why the type was not inherited from the parent structure and was amazed to find (yes with amazement, template classes - this is not what I do in everyday life) that the inheritance of template classes is somewhat different from ordinary ones. That is, the inheritance is just the same and all the entities of the parent are available in the daughter class (I hope no one will take me for a gender chauvinist) class, but they must be indicated with a full name. Well, this can still be understood, otherwise the compiler will not guess which of the instantiated options to apply, but if you use types defined in the class, you must also add the typename keyword. This is not an obvious solution, I was especially pleased with the compiler’s diagnostics, which means “maybe you had a type from the parent class” - yes, thanks, captain, that’s what I meant, I'm glad that we understand each other, but it doesn't get any easier for me. However, such a diagnosis takes place in the old version of GCC, in the current message it becomes more clear "you may have forgotten the typename keyword." Understanding the compiler’s diagnostic messages for template classes is generally a topic for a separate song, and this song is by no means joyful. thank you captain, that was what I had in mind, I’m glad that we understand each other, but it doesn’t get any easier for me. However, such a diagnosis takes place in the old version of GCC, in the current message it becomes more clear "you may have forgotten the typename keyword." Understanding the compiler’s diagnostic messages for template classes is generally a topic for a separate song, and this song is by no means joyful. thank you captain, that was what I had in mind, I’m glad that we understand each other, but it doesn’t get any easier for me. However, such a diagnosis takes place in the old version of GCC, in the current message it becomes more clear "you may have forgotten the typename keyword." Understanding the compiler’s diagnostic messages for template classes is generally a topic for a separate song, and this song is by no means joyful.
So if we don’t want to constantly use the construct in the child class
std::_Base_bitset::_WordT (and we don’t want, neg?) then we have three ways
1) trivial
#define _WordT typename _Base_bitset<_Nb>::_WordT2) obvious - type determination on a global level and I liked more
3) for fans of the weird
typedef typename _Base_bitset<_Nb>::_WordT _WordT;(persistent feeling of a magnificent chrome crutch). Personally, in all three cases I am not happy with the direct indication of the parent class, because the implementation should not take into account the inheritance chain, but maybe I don’t understand something.
There is also a method 4)
using _WordT = std::_Base_bitset::_WordT; but in my version of the compiler it does not work, so it is not.
Note in the margins (PNP) - in the wonderful book “C ++ for real programmers” (I downloaded it by mistake at the time, deciding that it was devoted to C ++ in real-time systems) it says about the language “Its elegance is not in simplicity (the words C ++ and simplicity cut the ear with its apparent contradiction), but in its potential capabilities. Behind every ugly problem is hidden some kind of clever idiom, an elegant linguistic feint, thanks to which the problem melts right before our eyes. ”Since the book is really wonderful, it means that the above quote is correct (I understand that there is a certain logical stretch here), but I personally Unfortunately, I see the problem, but with a smart idiom, stress.
Despite the remaining feeling of slight bewilderment, the problem is solved and you can enjoy the result - but it wasn’t there. When resizing the test set from 15 to 5, a compilation error occurred completely unexpectedly. No, everything is clear, an unmodified instantiation with template parameter 1 worked, but from the outside it looks very strange - we change the constant and the program stops compiling.
You can, of course, modify this implementation and another, but such an approach looks like a gross violation of the DRY principle. There are possible solutions, and there are more than one of them 1) the obvious - again the define and 2) the trivial - again the type definition at the global level, but in this case it will get outside the module, which, however, it does in the implementation under consideration, protruding from the basic structure , but also the qualifier will not need to be written.
Therefore, I am inclined to option 3) the base class for determining the type and the inheritance of all instances from it. Moreover, the entities of the parent class are protected, again, so that they do not stick out. Next, I find a funny property, probably C ++ should be praised for its flexibility - for a variant with no storage, the type is not needed, and the language allows the implementation to be used without inheritance, although this is not particularly necessary in this particular case. Immediately I discover one more drawback of the library - in all three cases, operations for calculating the number of storage units are set each time
static size_t _S_whichwordand the bit masks in it _S_maskbit and they are completely identical - we also move them to the base class. In this case, a "dead" code is detected - the _S_whichbyte method, I don’t even know what to do - on the one hand, good tone rules require its removal, on the other hand - in the case of a template, this does not affect the resulting code. I will use the rule - “do not understand something - do not touch” and leave this method.
In principle, the modifications in terms of the type of storage are completed and you can begin testing. And immediately I find a lack of implementation - for the MSP430 architecture, for some reason, two-byte words are allocated instead of bytes. Of course, not double words, as before, but still we are fighting for the minimum (in every sense) code. It turns out that the compiler is sure that in this architecture the type uint_fast8_t has a size of 2, although the command system has operations with bytes and the compiler itself uses them completely. The idea of using this type is compromised and you have to set the data type uint8_t directly. Well, if there is an architecture in which work with bytes is unsuccessful and the size of the uint_fast8_t type is different from 1 (none of those available in the compiler), it will have to suffer for the speed of all the others.
Testing the corrected version shows its correct operation on various architectures and with different parameters, but there still remains the issue of calculating bit masks for MK without developed shifts, in our case it is MSP430 and AVR. In principle, you can simply make reading the bitmask from the array a method for all cases, regardless of MK architecture. The solution is quite working, in developed architectures with indexing everything is fine, but there will still be a time loss compared to quick shifts, and I would not want to poke my fingers with the words “the class will be faster, he said, we are optimizing he said. "
Therefore, we need a different implementation for our two weak architectures, which differ from all others in the size of the uint_fast16_t type - it is 2 versus 4, or 8 in 64 bit versions. Conditional compilation will not help us, but setting the condition in the hope of optimization is not the way of the samurai, there remain patterns. I am trying to create a template method of the class, but partial specialization is not available for it - it turns out that it should be so and even find an article that says why this is a good solution. Honestly, I did not understand why this decision is good, most likely, this is due to religious considerations. Nevertheless, we were not asked, and what remains to be done - you can make a friendly template function (it turned out that it is impossible, and for the same reason - partial specialization is prohibited), there is one more solution, It looks funny - a partial specialization of the method outside the class body. You can even create a separate template function and access it from the class methods, I don’t know which method is more correct, I chose this one. Yes, she does not have access to the internal entities of the class, but in this particular case it is not necessary, what to do if necessary, I don’t know yet, “we will solve problems as they arise”.
Now we have everything we need, we collect the tested fragments together and get the code that solves the initial optimization problem. At the same time, we made the code more compact (and therefore more understandable, although the latter is debatable), removed numerous repetitions and eliminated redundant entities sticking out. The only thing that has not been fixed is a mixture of structures and classes, but here I do not understand the reasons for such an implementation, therefore, just in case, I will not touch this part.
A second post will be devoted to the implementation of the second version of the set, and without that something has worked out a lot.