Filter: 2013

Ein recht interessanter, nicht direkt offensichtlicher Fehler, kam mir vor einiger Zeit unter die Finger. Hierzu ein Stück Code:

class CMyVariant
{
public:
    CMyVariant();
    virtual ~CMyVariant();
 
    // Getter & Setter
 
protected:
    union
    {
        int64_t nTime;
        float fValue;
    };
};
 
int main()
{
    CMyVariant v1;
    ...
    // Variant v1 setzt nTime
    ... 
    CMyVariant v2 = v1;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

Auswirkungen

Die Klasse soll einen Variant-Datentypen darstellen, der zum Transport von Werten über Netzwerke und innerhalb von Anwendung benutzt werden kann. Der Wert nTime hält eine Zeit in Millisekunden, dieser sollte die aktuelle Uhrzeit tragen, war jedoch ca. alle 24 Tage um 70 Minuten versetzt. Wie dass?

Analyse

Da es eine Regelmäßigkeit gibt, die scheinbar mit der Zeit zusammenhängt, lassen sich die Werte gut zurückrechnen (in Millisekunden):

• 70 Minuten = 4200000 Millisekunden = 0x00401640
• 24 Tage = 2073600000 Millisekunden…

Ein Filter für bestimmte Datenmuster ist immer dann brauchbar, wenn Datensätze eingegrenzt bzw. ausgeschlossen werden sollen. Es wird hier anhand eines Filters zur Eingrenzung von Zeichenkettensuchoperationen, mit einem Beispiel, beschrieben. Natürlich lässt sich dieses Verfahren auf beliebige Daten anwenden und ist eine effektive Hilfe die nötigen Suchoperationen stark zu verringern und somit die Laufzeit des Codes zu verbessern.

Beispiel (Quellcode): patternfilter.cpp
Download (Quellcode): patternfilter.zip

Beschreibung

Mit Hilfe einer Funktion zur Mustererzeugung, wird jedes Element des Objektes in einem Datenfeld (entspricht einem Alphabet) mit seinem Wert als vorhanden markiert. Besteht ein Element aus mehreren Teilen, kann auch der Hashwert verwendet werden. Dies ist für das zu durchsuchende Muster sowie für das gesuchte Muster gleich. Sind die gleichen Markierungen, für beide Muster, im Datenfeld vorhanden, sind gleiche Elemente in den Objekten.

Da aber die Position der Elemente nicht, ggf. Hashw…

Vor kurzem lief mir ein interessanter Bug über den Weg, dazu erst kurzer Beispielcode:

uint64_t nTimeout;
 
void Func1()
{
    uint64_t nTickCount = GetTickCount();
    myLock.lock();
    ...
    nTimeout = nTickCount;
    ...
    myLock.unlock();
}
 
void Func2()
{
    uint64_t nTickCount = GetTickCount();
    myLock.lock();
    ...
    if((nTickCount-nTimeout)/1000>30) // Beispiel 30s 
        // Timeout
    ...
    myLock.unlock();
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

Auswirkungen

Func1 und Func2 werden von unterschiedlichen Threads aufgerufen. Func1 setzt ab und zu, aber rechtzeitig innerhalb der 30s den Timeout zurück. Trotzdem wirft Func2 ab und zu einen Timeout.

Analyse

Der Code hat mindestens zwei Probleme:

Das erste Problem ist, dass der TickCounter jeweils vor der Sperre gelesen wird. So kann es passieren, das innerhalb der Sperre in Func2 nTickCount kleiner als nTimeout ist. Dies ist dann der Fall, wenn nach dem Lesen des TickCounters in Func2 der Thread angehalten wird…

Die binäre Suche hilft sehr schnell zu entscheiden, ob ein Element in einem sortierten Datenfeld vorhanden ist. Dabei werden maximal nur log2(n) Vergleiche benötigt, die Position zu finden, an der dieses Element sein sollte sofern vorhanden.

Beispiel (Quellcode): binarysearch.cpp
Download (Quellcode): binarysearch.zip

Beschreibung

Die binäre Suche schaut in der Mitte des Datenfeldes, ob der gesuchte Wert größer oder kleiner des Feldschlüsselwertes ist. Ist er kleiner, wird der untere Teil des Datenfeldes weiter benutzt, im anderen Fall der obere. Bei nächsten Durchlauf, wird mit dem entsprechenden Teilfeld weitergearbeitet. Die Suche ist beendet, wenn nur noch ein Element vorhanden ist und dieses dem gesuchten Wert entspricht.

Aufgrund dieser Vorgehensweise, ist es unbedingt notwendig, dass dieses Datenfeld sortiert ist. Nur in diesem Fall kann davon ausgegangen werden, dass nach dem Wertevergleich, das entsprechende Teilfeld den Suchwert nicht enthalten kann.

Beispieldarstellung

In diesem Bild wird di…

Mergesort gehört auf Grund der vorhersagbaren, stabilen Laufzeit, der möglichen stabilen Sortierung und der möglichen Parallelisierung zu den beliebten Sortierverfahren. Die Anzahl der nötigen Schiebeoperationen liegt bei n*log2(n), die Anzahl der maximal benötigten Vergleiche kann durch die Summe der log(n) Durchläufe von den Zweiterpotenzen des Durchlaufs minus Eins errechnet werden.

Beispiel (Quellcode): mergesort.cpp
Download (Quellcode): mergesort.zip

Aufteilung des Feldes

Bei der rekursiven Variante ist es möglich, das Eingangsfeld immer zu halbieren (linke und rechte Hälfte), bis nur zwei oder weniger Elemente zu Verfügung stehen. Die maximale Rekursionsebene liegt bei log2 der Elementgesamtanzahl. Bei Beispielhaften 65536 Elementen also nur 16 Ebenen.

Bei der nicht rekursiven/iterativen Variante, wird direkt mit der kleinstmöglichen Teilfeldgröße (zwei Elemente) begonnen und die Teilfeldgröße in jedem Durchgang erhöht/verdoppelt. Ebenso wie bei der rekursiven Variante beträgt die Anzahl der Durc…