Follow our illustrated blog on Embedded Software Architecture

How to build a hybrid solar/wind energy harvester?

Vector, list and tree

VN:F [1.9.22_1171]
Rating: 0.0/10 (0 votes cast)

Choice of containers

Information technology, even embedded devices, is about information gathering, processing or calculation, and control. Input and data needs to be juggled around and maybe sorted. In this article, we want to point out some fundamental implications in the choice of a data container.

Vector

The first container is the array or “vector”. If the data is not be sorted, adding data at the end is simple. Except at the moment when the reserved size of the array is exceeded, then a new bigger memory region needs to be made available and the data from the old array, needs to be copied (depending on the memory configuration). Indexed access or picking a random element from the vector is very fast. If the data is to be sorted, insertion sort becomes much slower as – depending on the size of the array – potentially lots of data elements needs to be copied to make room for the new element at the correct index. But, searching for a specific element via the binary search method is more scalable and time efficient for larger values of n. Moreover, for real-time systems, we are interested in worst case performance: Algoritms that are time deterministic and timing predictable, and more specifically that always take the same time to come up with the requested answer (depending on the number of elements in the container), are preferred. This in contrast with some other applications and algorithms that are optimized for providing the solution in the shortest average time.

List

A second possible container is the linked list. Two variations; the single and the double linked list. For the first one, one always needs the head to start since there is only forward navigation: Each element only has a link or pointer to the next element. For the double linked list, we can navigate forward (to the next element) and backward (to the previous element). Adding an element, is simply a matter of unlinking, insert and linking to the previous and the next element. Removing an element is just as simple. On the other hand, sorting and searching in a linked list is less efficient when compared with the binary search method on a sorted vector (depending on the number of elements in the container).

Tree

A (sorted) binary tree is a further evolution of the data container concept. While the double linked list has links to its previous and next element, the binary tree element has 3 links: a root element, a left and a right element. A binary tree is sorted when starting from the root (the binary tree root element is the element which has no root or where the root is null), an element –
that is smaller – is linked to by the “left”, and an element – that is bigger – is linked to by the “right”.

When the binary tree is “balanced”, the search operations could be made time deterministic and timing predictable (i.e. again to always take the same time depending on the number of elements in the container) :

A balanced binary tree is commonly defined as a binary tree in which the depth of the left and right subtrees of every node differ by 1 or less.

Advantages and disadvantages

To recapitulate:

The unsorted vector

+ indexed access
+ fast iteration
+ fast adding except when exceeding reserved memory
- slower removing
Use when indexed access is important, when insert and remove is less important, and sorting is not needed.

The sorted vector

+ indexed access
+ fast iteration
+ time deterministic and timing predictable element searching
- slower adding (binary search for insert position, make room for element by copying elements)
- slower removing
Use when sorting, indexed access and searching is important, when insert and remove is less important.

The linked list

+ fast forward (and also backward for double linked list) iteration
+ fast adding
+ fast removing
- slow indexed access
- slower searching
Use when insert/remove must be fast, when sorting and searching is less important.

The binary tree

+ iteration is slower than compared with a vector
+ time deterministic element searching (for a balanced tree)
+ faster removing
- slower adding (first one needs to determine the insert position)
- (offline) re-balancing could be required
Use when insert/remove may take longer, but where sorting and searching (on bigger sets) is more important, and the implementation must remain simple.

The even more advanced container we look at later is the red-black tree and the hash table…

Important

In order to take a look at and to compare the different algorithms and how they provide their solution in a time deterministic way, refer to e.g. http://bigocheatsheet.com/
In real-time systems we must adhere to strict timeline, and thus worst case performance of an algorithm is most important. Again to evaluate worst case timings, cache must always be ‘cold’. For applications that do not have this limitation, the concept of data locality begins to play a big role: Linear searching an array of objects might become much faster in practice because the cache is more optimally used when compared with a binary tree e.g. that has to jump from object address to object address. All depends on platform architecture, number of elements and the specific application, of course.

Conclusion

Vectors and lists are simple, do not have much overhead, and are used extensively for small embedded programs. In that case, the maximum number of elements (and thus the allocated memory) are usually pre-determined resulting in fast adding, removing and searching on limited data sets.
If one considers using a binary tree, we will discuss better solutions in a next article.

 

VN:F [1.9.22_1171]
Rating: 0.0/10 (0 votes cast)
Share

Priority inversion

I found the inspiration for this article while working on a consultancy job: Priority inversion. In computer science, priority inversion is a (potential) problematic scenario in scheduling in which a high priority task is indirectly preempted by a … [Continue reading]

Progress update

Time for another update. The Green4 project is progressing steadily. In the last few months, we have been busy preparing the Green4 prototypes. Test software has been developed which is already very usable, but it is still in a state of flux as we … [Continue reading]

Embedding a Basic interpreter

The green4 stm32 cortex m3 microprocessor we selected is - according to today's standards - a rather small microprocessor in Flash (128KB) and RAM (8KB). why an interpreter The Green4 device is running control software on top of FreeRTOS, with a … [Continue reading]

Green4 charge controller: wiring diagrams part 2

Wiring diagram: wind turbine to dump load In contrast to solar panels, a wind turbine can't be disconnected in case it generates too much power. We need to brake it by attaching a load to it. However, wind power can't always flow through the charge … [Continue reading]

Green4 charge controller: wiring diagrams part 1

charge controller wiring batteries to external device

Introduction Instead of endlessly listing requirements and specifications, we prefer to demonstrate the architecture of our Green4 charge controller by means of wiring diagrams and other illustrations. The Green4 is designed to be a versatile … [Continue reading]

Open source implementations of malloc

On (very) small embedded systems without a full OS (e.g. because there is only a scheduler), one can (and should) usually live without dynamic memory allocation. But sometimes, it is really needed or it is just more convenient. It is possible to … [Continue reading]

DC motor control with the mosfet switch board

Although, there is no such thing as a general purpose mosfet switch board because of the wide variations in application specific load (resistive, capacitive, inductive or mixed) characteristics, we were able to investigate and demonstrate DC motor … [Continue reading]

Object-orientation in C – Part 4

We continue to build on the example in Part 3, but we go another step further. Even more abstraction and information hiding can be achieved by partially mimicking (part of) the COM manner of programming: strictly talking with interfaces. This style … [Continue reading]

Current limiting with PWM

For particular applications, such as our energy harvester or at least the battery charger part of it, the ability to control the current is an essential property. We must emphasize that the presented method will limit the average current; the … [Continue reading]