Designing Critical Algorithms: Implementation

  1. Design
  2. Implementation
  3. Integration


When I was just starting my career in professional development, I did not understand why open source was needed. I didn't understand side projects either, for that matter. After all, why give valuable work for free? Over the years, through working on open source projects, as well as working with Apex.AI, ROS 2 and Autoware.Auto, I have come to some understanding of open-source.



Engineers love to create. People want recognition and gratitude.



When you combine these factors together, you have the path to open source. If I'm building something to meet my creative needs, why not let everyone else appreciate my work and find practical use and value in it? After all, I'm not doing this for the money.



As for side projects, I realized their charm only after I began to develop professionally and more carefully approach various aspects of my work. To create a reliable product that people will pay for, it is often necessary to artificially restrict workflows. Design analysis. Code review. Coding standards, style guides, test coverage metrics, and so on and so forth. Don't get me wrong - these are all good things that are most likely necessary to develop a quality product. It's just that sometimes a developer wants a little freedom. A developer may want to create what he wants, how he wants, and when he wants. No meetings, reviews, or business cases.



So how do you combine these aspects when it comes to developing safe or high quality algorithms? A large part of the allure of the open source world is freedom, and practices that help ensure more reliable code is developed limit that freedom.



The answer I found is to follow an open and consistent discipline, and to liberally use a lot of cool tools that have come from the open source world.



Planning open source projects



Engineers need a specific skill set to address these issues. Engineers need to be focused, they need good problem solving skills. Engineers also need to be able to separate concerns and have the solid basic skills required to gain knowledge of all of the above.



This particular skill set can lead us engineers to be somewhat overwhelmed.



For all the technical abilities that engineers have, they are ultimately limited in their capabilities. I would argue that most developers are unable to keep the entire project in mind while writing individual lines of code. Moreover, I would argue that most developers cannot program and keep a broader project in their head without forgetting about general business goals.



This is where the black magic of project management comes into play.



While we developers may have somewhat controversial relationships with HR, technical, or project managers, it should be recognized that all of these people are doing important work. The best representatives of the management profession make sure that developers don't lose sight of important tasks, and annoying irritants don't stop us from shooting problems with all weapons.



And while we understand the importance of different managers, people with these skills usually don't get involved in a typical open-source project whose goal is to have fun.



So what should we do then?



Well, we developers can get our hands dirty and spend a little time planning ahead.



I will not go into these conversations, as in the previous post I went into detail about the design and development planning stages. The bottom line is that taking into account the design and architecture, for which, as a rule, consist of many components, and form some dependencies, in your own project you form the design yourself, and collect its components separately.



Coming back to the aspect of project planning, I like to start with the components with the least dependencies (think a minute!) and then continue working, adding implementation stubs where necessary to keep development going. With this order of work, you can usually create many tickets (with some dependencies in them corresponding to your architectural dependencies - if your task tracker has such functionality). These tickets may contain some general notes that are useful to keep in mind before you dive into any task in more detail. Tickets should be as small and specific as possible. Let's face it - our focus and ability to hold context are limited. The more granularly the development tasks are broken down, the easier - so why not try to make difficult tasks as simple as possible?



As your project evolves, your job will be to take tickets in order of priority and complete the tasks assigned to them.



Obviously, this is a vastly simplified version of project management. There are many other aspects to true project management such as resources, planning, competing business cases, and so on. Project management in open-source can be simpler and freer. Perhaps in the world of open source development there are cases of full-fledged project management.



Open development



Having typed a stack of tickets, having formed a work plan, and having understood all the details, we can proceed to development.



However, many of the freedom factors present in the wild west of open development should not be in the development of secure code. You can avoid a lot of pitfalls by using open source tools and with some discipline (and having friends).



I am a big proponent of discipline as a means of improving work quality (after all, discipline is in 6th place in my rating on StrengthsFinder). With enough discipline to use open source tools, listen to others, act on results, and stick to workflows, we can overcome many of the flaws that creep in with the cowboy approaches of the open source world.



In short, the use of the following tools and practices (which, with some caveats, can be easily applied in any project) helps to improve the quality of the code:



  1. Tests (or better yet, test driven development)
  2. Static analysis
  3. Continuous Integration (CI / CD)
  4. Code Review


I will also give a number of principles that I adhere to when writing code directly:



  1. DRY
  2. Full use of language and libraries
  3. The code should be readable and blindingly obvious.


I will try to relate this text to the actual implementation of the NDT localization algorithm , which was completed in 10 merge requests by my good colleague Yunus . He is too busy with direct work, so I can hang on myself some imaginary medals by writing about his work.



In addition, to illustrate some of the processes and practices, I will give an example of developing an open-source algorithm for the MPC controller . It was developed in a slightly looser (cowboy) style in about 30+ merge requests , not counting additional edits and improvements made after the main work was completed.



Testing



Let's talk about testing.



I had a long and difficult (by my standards) relationship with testing. When I first got a position as a developer and took on the first project, I absolutely did not believe that my code worked, and therefore I was the first on the team who started writing at least some meaningful unit tests. However, I was absolutely right that my code didn't work.



Since then, my tumultuous relationship with testing has gone through many twists and turns worthy of overnight films. Sometimes I liked it. Sometimes I hated it all. I've written too many tests. Too much copy-paste, too many redundant tests. Then testing became a routine work, another part of development. First I wrote the code, and then I wrote tests for it, this was the order of things.



Now I have a normal relationship with testing. It is an integral part of my workflow, no matter what application I work on.



What has changed for me is the test-driven development techniques that I started using in my mpc project.



I briefly talked about test-driven development in the previous text, but here's another description of the process:



  1. Develop a specification (use cases, requirements, etc.).
  2. Implement the API / architecture
  3. Write tests based on API and design specification; they must fail.
  4. Implement logic; tests must pass


There is some iteration in this process (tests don't fail on stubs, implementation fails tests, API can be awkward, etc.), but overall, I think it can be extremely useful.



I've talked a lot about planning before implementation, and test-driven development gives you that opportunity. The first point was noted. Then you think about architecture and APIs, and map them to use cases. This gives you a great opportunity to get closer to the code, but still think about the problem more broadly. The second point was noted.



Then we move on to writing tests. There are several reasons for the benefits of writing tests before implementation, and I think they are all important:



  1. Tests should be written as first priority objects, not as add-ons.
  2. , โ€“ .
  3. API , .
  4. , , , , .


Overall, I think the benefits of test driven development are enormous, and once again I highly recommend everyone to at least give it a try.



Let's go back to Autoware.Auto. Yunus, while not sticking to test-driven development methods, wrote tests for each merge request during NDT development. At the same time, the amount of test code was equal to (and sometimes even exceeded) the amount of implementation code, which is good. In comparison, SQLite , which is probably the benchmark for testing (not just by the standards of open source projects), has 662 times more test code than implementation code. At Autoware.Auto we are not quite at this stage yet, but if you look at the history of merge requests related to NDT, you will notice that the volume of test code slowly crawled up until it reached 90% coverage (although it has since dropped due to other designs and external code).



And that's cool.



Likewise, my mpc project has tests for everything, including the tests themselves . Moreover, I always carefully conduct regression testing to make sure that the bug is fixed and does not show up again.



I'm fine fellow.



Static analysis



Many concepts are curious in that the definitions included in them can be significantly stretched. For example, testing goes far beyond hand-written functional tests. In fact, style checking or bug hunting can also be considered a form of testing (it is essentially an inspection, but if you stretch the definition, it can be called testing).



Such "tests" are somewhat painful and laborious to work with. After all, validation, validation for tabs / spaces in alignment? No thanks.



But one of the most enjoyable and valuable things about programming is the ability to automate painful and time-consuming processes. At the same time, the code can achieve results faster and more accurately than any person. What if we can do the same with bugs and problematic or error-prone constructs in our code?



Well, we can - with static analysis tools.



I wrote about static analysis long enough in a previous blog post , so I won't go deep into its benefits and the tools you can use.



In Autoware.Auto we use a slightly smaller version of the ament_lint setfrom our close friends at ROS 2. These tools do us a lot of good, but perhaps the most important thing is that our code auto-formatting to eliminate style disputes - impartial tools tell us what is right and what is wrong. If you're interested, I'll note that clang-format is stricter than uncrustify .



In the mpc project, I went a little further. In it, I used the Weverything flag of the Clang compiler, in addition to all the warnings from clang-tidy and the Clang static analyzer . Surprisingly, commercial development required several options to be disabled (due to redundant warnings and conceptual confusion) When interacting with external code, I had to disable many checks - they led to unnecessary noise.



Ultimately, I realized that using extensive static analysis does not greatly interfere with normal development (in the case of writing new code and after passing a certain point on the learning curve)



It is difficult to quantify the value of static analysis, especially if you use it from the beginning. The point is that it is difficult to guess whether the error existed before the introduction of static analysis or not.



However, I believe that using warnings and static analysis is one of those things where, even when used correctly, one cannot be sure that they did anything at all.... In other words, you can't be sure about the value of a static analyzer when it's on, but heck, you'll notice it's not there right away.



CI / CD



As much as I love rigorous testing and static / dynamic code analysis, all tests and checks are worthless if not run. CI can meet these challenges with minimal overhead.



I think everyone agrees that having a CI / CD infrastructure is an essential part of modern development, as well as using a version control system and having development standards (at least style guides). However, the value of a good CI / CD pipeline is that its operations must be reproducible.



The CI / CD pipeline should, at a minimum, build code and run tests before pushing the code into your repository. After all, no one wants to be that guy (or girl, or persona) who broke an assembly or some kind of test and has to fix everything quickly and shamefully. CIs (and therefore your dear DevOps engineers) protect you from this shame.



But CI can do a lot more for you.



With a robust CI pipeline, you can test any number of combinations of operating systems, compilers, and architectures (with some limitations, considering combination testing ). You can also perform builds, run tests, and other operations that can be too resource intensive or cumbersome for a developer to manually perform. You can't jump over your head.



Going back to the original statement, having a CI / CD pipeline (which we use at Autoware.Auto ) in your open-source project will help ride the unmanageable development. The code will not be able to get into the project if it does not build or pass tests. If you adhere to strict testing discipline, you can always be sure that the code works.



In Autoware.Auto, CI:



  1. Collects code
  2. Runs tests (style, linter checks, functional tests).
  3. Measures test coverage
  4. Checks that the code is documented




In turn, my hastily compiled CI in the mpc project:



  1. Collects code
  2. Performs a scan (Clang static analysis)
  3. Runs tests (but doesn't stop CI if tests fail).


A CI pipeline put together by an experienced DevOps engineer (like our J.P. Samper or Hao Peng !) Can do much more. So cherish your DevOps engineers. They make our life (as developers) much easier.



Code Review



Benchmarks, analyzers and CI are great. You can run tests, analyze everything, and make sure that these tests are done using CI, right?



Unfortunately no.



Again, all tests in the world are worthless if they are bad. So how do you make sure your tests are good?



Unfortunately, I have no magic answers. In fact, I'm going back to the old engineering technique, peer review. In particular, to the code review.



It is generally believed that two heads are better than one. In fact, I would argue that this concept is supported not only by literature, but also by theory.



Ensemble of methodsin machine learning illustrates this theory. It is believed that using an ensemble of methods is a quick and easy way to improve the performance of statistical models (the well-known boosting method is an example ). Similarly, from a purely statistical point of view, the variance is lower (with assumptions) the more samples you have. In other words, you are more likely to be closer to the truth if you connect more employees.



You can try this technique out with a live example by doing a team building exercise . A less fun version might involve guessing random statistics individually and in a group.



Theory and team building aside, code review is an important and powerful tool. Unsurprisingly, code review is an integral part of any professional development process, and even recommended by the ISO 26262 standard.



All this suggests that there is always a danger that one child will have seven nannies. Moreover, sometimes code review can cause certain difficulties.



However, I think code reviews can be enjoyable and painless if both the reviewer and the peer-reviewed remember the following:



  1. You are not your code.
  2. You are talking to another person.
  3. Be polite
  4. Everyone is working towards the same goal; code review does not represent any competition (although sometimes it happens in programming )


Many smarter and nicer people than me have written about how to do code reviews properly, and I invite you to take a look at their work . The last thing I can say is that you should do code reviews if you want your code to be more reliable.



DRY



I went into detail about the processes and tools that can be used to create a development environment: checks and tools that conduct checks and make sure that the code is good enough.



Next, I'd like to move on to a quick talk about programming prowess and share some thoughts on the processes and intent behind writing individual lines of code.



There are a couple of concepts that have helped me greatly improve my code. One of those concepts was the ability to remember intent, semantics, and readability, which I'll talk about a little later. Another is an understanding of OOP and separation of concerns . The last important idea is DRY ( Don't Repeat Yourself ) or the principle "Do not repeat yourself."



DRY is what is taught in school and, as with many other things, we put this thought on the far shelf and do not attach much importance to it outside of exams (at least for me). But, as is the case with many other things in school, we do not learn anything just like that. In fact, this is good practice.



To put it simply, if you find yourself frequently copying and pasting code, or writing very similar code frequently, this is a very good indication that repeatable code should become a function or part of some abstraction.



But DRY goes further than checking that some code should be moved into a function. This concept can also serve as a basis for some architectural decisions.



Although this approach intersects with some architectural concepts (such as aliasing, connectivity, and separation of concerns), an example of how DRY is applied to architecture can be seen in my mpc project. During the development of the mpc controller, I noticed that I would have to duplicate some code if I ever write another controller. It's about boilerplate code for tracking state, posts, subscriptions, conversions, and the like. In other words, it seemed that it was a separate task from the mpc controller.



This was a good indication that I should separate the general designs and functionality into a separate class . The payback was twofold: the mpc controller is 100% focused on the code related to mpc, and withthe module associated with it is just a configuration template. In other words, due to architectural abstractions, I don't have to rewrite everything when working with a different controller.



The world is made up of shades of gray, so these design decisions should be delved into with care and the right mindset. Otherwise, you can go too far and start creating abstractions where they are not needed. However, if the developer is mindful of the concepts that these abstractions model, DRY is a powerful tool for shaping architectural decisions. In my opinion DRY is the main concept for keeping your code clean and dense.



After all, one of the key benefits of code is its ability to perform repetitive tasks, so why not shift repetition to well-designed functions and classes?



Full use of language and library



DRY, in my opinion, is such an important and pervasive concept that this point is really just a continuation of the DRY conversation.



If your language supports something, then you should generally use the inline implementation, unless you have very good reason to opt out. And C ++ has a lot of things built in .



Programming is a skill and there is a big difference in skill levels. I only caught a glimpse of how high the mountain of this skill is, and in general I find that the people who create standards are better at implementing common patterns than I am.



A similar argument can be made for the functionality of the libraries (although perhaps not so categorically). Someone else has already done the same, and probably at a good level, so there is no reason to reinvent the wheel.



Nevertheless, this, like many others, this paragraph is a recommendation, and not a rigid and urgent rule to apply. While it's not worth reinventing the wheel, and while standard implementations are generally very good, there is no point in trying to squeeze a square piece into a round hole. Think with your head.



Readable code



The last concept that helped me improve my programming skill was that programming is not so much about writing code as it is about communication. If not communication with other developers, then communication with yourself from the future. Of course, you need to think about memory, math, and the complexity of the Big O, but once you get that done, you need to start thinking about intent, semantics and clarity.



There is a very famous and widely recommended book on this topic, Clean Code , so there is not much I can add on this topic. Here are some general information that I refer to when writing code and doing code reviews:



  1. Try to keep your classes clear and focused:

    • Minimize snagging
    • ()



      • const, noexcept? ? (, )




    • , (, , ).
    • (, )
    • .
  2. -



    • ยซยป, , .
    • (, ).
    • ( ) ().
  3. ? ()



    • , ().
    • , , , (, ).


Another great resource that addresses this kind of problem is the ISO C ++ Core Guidelines .



I will reiterate that none of these principles are revolutionary, new or unique, but if the writing of the principles has value (or someone will say โ€œahaโ€ upon reading it ), then I did not waste the bits and traffic to write this post. ...



Looking back



These were some of the tools, principles and processes that we used in developing and implementing the NDT localization algorithm, as well as when working on the MPC controller. A lot of work was done, it was fun, it is not so interesting to talk about it.



Overall, we made great use of the tools and practices I mentioned, but we weren't perfect.



So, for example, when working on the NDT, we did not follow the idioms of test-driven development (although we have everything perfectly tested!). In turn, I did follow test-driven development techniques on MPC, but this project did not benefit from the more powerful CI built into Autoware.Auto. Moreover, the MPC project was not public and therefore did not receive the benefits of a code review.



Both projects could benefit from the introduction of static analysis, more detailed testing, and more feedback. However, we are talking about projects created by one person, so I think that the testing done and the feedback received is enough. When it comes to static analysis, better and closer forms generally fall into the realm of product development interests and move away from the open-source developer community (although interesting ideas may appear on the horizon ).



I have nothing to say about the simultaneous development of two algorithms - we worked to the best of our ability, adhering to the principles that I outlined above.



I think we have done an excellent job of decomposing large problems into smaller pieces (although the MR component in the NDT algorithm could be smaller), and have done extensive testing. I think the preliminary results speak for themselves.



Forward movement



After implementation, it's time for integration. It is necessary to connect to a larger system with its own complex components. This system will take your input, digest it, and produce the results of your algorithm. Integration is perhaps the most difficult part of developing an algorithm, as you need to keep track of the overall system plan and fix low-level problems. Any mistake in any of your many lines of code can prevent your algorithm from integrating.



I'll cover this in the third and final post of this series.



As a preview, I will say that during the development process, not a single big error was found during the use and integration of the mpc controller. True, there were some problems with writing scripts , assembling,tests , input data validation was skipped , and there were also problems with incompatibility of QoS settings , but there was nothing terrible in the code.



In fact, it was able to run (bypassing QoS incompatibilities and setting options) almost out of the box .



The same applies to the NDT algorithm, which ran into a number of minor problems like instability of covariance , error in searching for strings in existing code, and incorrectly aligned maps. Regardless, it was also capable of working out of the box .



Not bad for products designed for everyone to see.



Subscribe to channels:

@TeslaHackers โ€” Tesla-, Tesla

@AutomotiveRu โ€” ,







image



- automotive . 2500 , 650 .



, , . ( 30, ), -, -, - (DSP-) .



, . , , , . , automotive. , , .


:






All Articles