Bit packed array

[Heiner Kücker]

Hallo mal wieder nach längerer Zeit,

ich habe eine kleine Lib veröffentlicht, die Teil eines Projektes ist, das mich schon eine Weile beschäftigt.

http://www.heinerkuecker.de/BitPackedArray.html

Es handelt sich um eine Lib zum speichersparenden Vermerken von ganzzahligen Werten, deren Breite kein ganzzahlig Vielfaches von 8 ist, in einem int-Array bzw. long-Array.

Nur das Speichern ist keine große Sache, es gibt aber noch arraycopy. Dies war etwas aufwändiger. Ich wollte nicht einfach nur Werte lesen und an der neuen Position speichern, sondern möglichst effektiv so viele Bits wie möglich mit einem Zugriff kopieren.

Vor allem die Unit-Tests laufen sehr lange, ich habe da einiges optimiert.

Bisher habe ich noch keinen Fehler gefunden, einige Tests habe ich aber nicht zu Ende laufen lassen, nach einigen Tagen kam mir da ein Win-Update dazwischen.

Eventuell kann jemand meine Lib gebrauchen.

Heiner

[Patrick Roemer]

Post by Heiner Kücker
http://www.heinerkuecker.de/BitPackedArray.html

Da ich zumindest derzeit keinen Bedarf an solcher Funktionalität habe
und die Darreichungsform auch eher unbequem finde, habe ich nicht
reingeschaut. Aber interessieren würde mich schon...

Post by Heiner Kücker
Vor allem die Unit-Tests laufen sehr lange, ich habe da einiges optimiert.
Bisher habe ich noch keinen Fehler gefunden, einige Tests habe ich aber nicht
zu Ende laufen lassen, nach einigen Tagen kam mir da ein Win-Update dazwischen.

...wie man zu Unit Tests kommt, die tagelang laufen?!

Viele Grüße
Patrick

[Stefan Ram]

Post by Patrick Roemer

Post by Heiner Kücker
http://www.heinerkuecker.de/BitPackedArray.html

Da ich zumindest derzeit keinen Bedarf an solcher Funktionalität habe
und die Darreichungsform auch eher unbequem finde, habe ich nicht
reingeschaut. Aber interessieren würde mich schon...

Ich habe nur den Namen der Klasse gelesen und hatte
zirka 30 Minuten Zeit (nicht auf die Uhr gesehen).

Die letzten fünf Zeilen des Programms sind als Kurz-Doc
zum Einstieg wohl am verständlichsten.

Anmerkung: Die Verwendung von »long« für Anzahlen von
Bits und die Verwendung von »int« für Anzahlen von Worten
schafft ein gewisses mehr an statischer Typzusicherheit,
da der Versuch eine Bitanzahl an eine Wortanzahl zuzuweisen
scheitert. In C++ kann man hier aber mit "zero-overhead
abstractions" noch viel weiter gehen und totale Typsicherheit
auf diesem Gebiet erreichen (auch Wortanzahlen können dann
nicht mehr an Bitanzahlen zugewiesen werden, und Literale
können mit eigenen Einheiten versehen werden) ohne daß dies
in C++ irgendwelche Laufzeitkosten verursacht!

final class Bits
{
int[] representation;
int size_in_words = -1;
final long wordsize = java.lang.Integer.SIZE;

public Bits( final long size_in_bits )
{ assert size_in_bits > 0 : "bitsize";
assert ( size_in_bits - 1L )/ wordsize + 1L <=( long )java.lang.Integer.MAX_VALUE : "too long";
this.size_in_words =( int )( ( size_in_bits - 1L )/ wordsize + 1L );
this.representation = new int[ size_in_words ]; }

public int offset_in_words( final long offset_in_bits )
{ assert java.lang.Long.divideUnsigned( offset_in_bits, wordsize )<=( long )java.lang.Integer.MAX_VALUE : "too long";
return ( int )java.lang.Long.divideUnsigned( offset_in_bits, wordsize ); }

public int local_offset( final long offset_in_bits )
{ return( int )java.lang.Long.remainderUnsigned( offset_in_bits, wordsize ); }

public static void set_bit_in_word
( final int word[], final int offset_in_words, final int offset_in_bits )
{ word[ offset_in_words ]|= 1<<offset_in_bits; }

public static void clear_bit_in_word
( final int word[], final int offset_in_words, final int offset_in_bits )
{ word[ offset_in_words ]&= ~(1<<offset_in_bits); }

public static int get_bit_from_word
( final int word[], final int offset_in_words, final int offset_in_bits )
{ return word[ offset_in_words ]&(1<<offset_in_bits); }

public void set_bit( final long offset_in_bits )
{ assert java.lang.Long.divideUnsigned( offset_in_bits, wordsize )<=( long )java.lang.Integer.MAX_VALUE : "too long";
set_bit_in_word( representation, offset_in_words( offset_in_bits ), local_offset( offset_in_bits )); }

public void clear_bit( final long offset_in_bits )
{ assert java.lang.Long.divideUnsigned( offset_in_bits, wordsize )<=( long )java.lang.Integer.MAX_VALUE : "too long";
clear_bit_in_word( representation, offset_in_words( offset_in_bits ), local_offset( offset_in_bits )); }

public int get_bit( final long offset_in_bits )
{ assert java.lang.Long.divideUnsigned( offset_in_bits, wordsize )<=( long )java.lang.Integer.MAX_VALUE : "too long";
return get_bit_from_word( representation, offset_in_words( offset_in_bits ), local_offset( offset_in_bits )); }}



public final class Main
{ public static void main( final java.lang.String[] args )
{

for( int i = 1; i < 1024; ++i )
assert new Bits( i ).size_in_words == (i-1)/32+1 : "size_in_words";

for( int i = 1; i < 1024; ++i )
{ final Bits bits = new Bits( i );
for( int j = 0; j < i; ++j )
{ assert bits.offset_in_words( j )==j/32 : "division";
assert bits.local_offset( j )==j%32 : "remainder"; }}

/* no time to write more "tests"! */
/* a quick usage example: */

final Bits bits = new Bits( 1024 );
bits.set_bit( 412 );
assert( bits.get_bit( 411 )== 0 );
assert( bits.get_bit( 412 )!= 0 );
assert( bits.get_bit( 413 )== 0 ); }}



PS: In Pascal:

packed array [ 0..1024 ] of Boolean

.

[Patrick Roemer]

Post by Stefan Ram

Post by Patrick Roemer

Post by Heiner Kücker
http://www.heinerkuecker.de/BitPackedArray.html

Da ich zumindest derzeit keinen Bedarf an solcher Funktionalität habe
und die Darreichungsform auch eher unbequem finde, habe ich nicht
reingeschaut. Aber interessieren würde mich schon...

...eigentlich was anderes. :)

Post by Stefan Ram
Ich habe nur den Namen der Klasse gelesen und hatte
zirka 30 Minuten Zeit (nicht auf die Uhr gesehen).
Die letzten fünf Zeilen des Programms sind als Kurz-Doc
zum Einstieg wohl am verständlichsten.

Das sieht mir eher nach einer spartanischen Variante von ju.BitSet aus.
Heiners Code dürfte etwas anderes machen.

Viele Grüße
Patrick

[Heiner Kücker]

Post by Patrick Roemer

Post by Heiner Kücker
http://www.heinerkuecker.de/BitPackedArray.html

Da ich zumindest derzeit keinen Bedarf an solcher Funktionalität habe
und die Darreichungsform auch eher unbequem finde, habe ich nicht
reingeschaut. Aber interessieren würde mich schon...
...wie man zu Unit Tests kommt, die tagelang laufen?!

Die Ursache ist die kombinatorische Explosion.

public void testFromArrayCopy_All()
{
for ( int dataElementWidth = 1 ; dataElementWidth < Integer.SIZE ; dataElementWidth++ )
{
for ( int arraySize = 1 ; arraySize <= 37 ; arraySize++ )
{
for ( int srcPos = 0 ; srcPos < arraySize ; srcPos++ )
{
for ( int dstPos = 0 ; dstPos < arraySize ; dstPos++ )
{
for ( int length = 0 ;
length <= arraySize &&
length <= arraySize - srcPos &&
length <= arraySize - dstPos ;
length++ )
{
for ( final int[] thisValues :
new BitPackedIntArrayArraycopyTestValueIterable(
dataElementWidth ,
arraySize ) )
{
for ( final int[] fromValues :
new BitPackedIntArrayArraycopyTestValueIterable(
dataElementWidth ,
arraySize ) )
{

Post by Patrick Roemer
Viele Grüße
Patrick

Danke
Heiner

[Patrick Roemer]

Post by Heiner Kücker

Post by Patrick Roemer
Aber interessieren würde mich schon...
...wie man zu Unit Tests kommt, die tagelang laufen?!

Die Ursache ist die kombinatorische Explosion.
public void testFromArrayCopy_All()
{
for ( int dataElementWidth = 1 ; dataElementWidth < Integer.SIZE ; dataElementWidth++ )
{
for ( int arraySize = 1 ; arraySize <= 37 ; arraySize++ )
{
for ( int srcPos = 0 ; srcPos < arraySize ; srcPos++ )
{
for ( int dstPos = 0 ; dstPos < arraySize ; dstPos++ )
{

[...]

"The number of input and output combinations for trivial programs is
surprisingly large. It is astronomical for typical programs and beyond
comprehension for typical systems. [...] Clearly, we can never test all
inputs, states, or outputs."
Robert V. Binder, Testing Object-Oriented Systems
§3.3: The Limits of Testing

Das ist sehr gründlich gedacht, aber effektiv hast Du damit ja gar keine
Tests, weil niemand sie je (komplett) laufen lassen wird. Unit Tests
sollten eigentlich sogar nach jeder in sich abgeschlossenen
Code-Änderung automatisiert durchlaufen; das kannst Du mit diesem Ansatz
komplett knicken.

Üblicherweise wählt man für Unit Tests Szenarien mit (Kombinationen von)
Extremen oder besonders hervorgehobenen Elementen aus dem erlaubten
Bereich der Eingabewerte (hier etwa: 0, 1, Integer.SIZE,...) und einige
mehr oder minder zufällige Werte, die pars pro toto für die sonstige
Bandbreite stehen. Ergänzen kann man das durch randomisierte Tests a la
QuickCheck[1]. Da gibt es wohl auch diverse Java-Ports; keine Ahnung,
wie es sich damit arbeitet.

Viele Grüße
Patrick

[1] http://www.cse.chalmers.se/~rjmh/QuickCheck/manual.html

[Heiner Kücker]

Post by Patrick Roemer
"The number of input and output combinations for trivial programs is
surprisingly large. It is astronomical for typical programs and beyond
comprehension for typical systems. [...] Clearly, we can never test all
inputs, states, or outputs."
Robert V. Binder, Testing Object-Oriented Systems
§3.3: The Limits of Testing
Das ist sehr gründlich gedacht, aber effektiv hast Du damit ja gar keine
Tests, weil niemand sie je (komplett) laufen lassen wird. Unit Tests
sollten eigentlich sogar nach jeder in sich abgeschlossenen
Code-Änderung automatisiert durchlaufen; das kannst Du mit diesem Ansatz
komplett knicken.
Üblicherweise wählt man für Unit Tests Szenarien mit (Kombinationen von)
Extremen oder besonders hervorgehobenen Elementen aus dem erlaubten
Bereich der Eingabewerte (hier etwa: 0, 1, Integer.SIZE,...) und einige
mehr oder minder zufällige Werte, die pars pro toto für die sonstige
Bandbreite stehen. Ergänzen kann man das durch randomisierte Tests a la
QuickCheck[1]. Da gibt es wohl auch diverse Java-Ports; keine Ahnung,
wie es sich damit arbeitet.

In den Klassen

BitPackedIntArrayArraycopyTestValueIterable

und

BitPackedLongArrayArraycopyTestValueIterable

habe ich statt die Werte mit einem Zähler zu erzeugen
ein Bitmuster erzeugt.

Mit der Verwendung des Bitmusters habe ich erst ab
einer bestimmten Bit-Breite begonnen, bei kleinen
Breiten läuft noch der Zähler.

Teilweise verwende ich auch nur Wert mit allen
Bits 0 oder alternativ allen Bits 1.

Es geht darum, dass die Ränder der Werte eingehalten
werden.

Etwas überrascht hat mich das Verhalten des Verschiebe-Operators

https://stackoverflow.com/questions/1023373/findbugs-warning-integer-shift-by-32-what-does-it-mean

Beim int-Verschiebe-Operator werden nur die niedrigsten 5 Bit des Operanden beachtet, bei Long 6 Bit.


Dieses Verhalten ist aber entsprechend dem Werteüberlauf bei den ganzzahligen Werten, falsches Ergebnis statt Exception.

Post by Patrick Roemer
Viele Grüße
Patrick
[1] http://www.cse.chalmers.se/~rjmh/QuickCheck/manual.html

Bei sowas muss man wahrscheinlich vorher eine Ahnung haben, was schief gehen kann.

Schöne Grüße
Heiner

[Heiner Kücker]

Post by Heiner Kücker

Post by Patrick Roemer
"The number of input and output combinations for trivial programs is
surprisingly large. It is astronomical for typical programs and beyond
comprehension for typical systems. [...] Clearly, we can never test all
inputs, states, or outputs."
Robert V. Binder, Testing Object-Oriented Systems
§3.3: The Limits of Testing
Das ist sehr gründlich gedacht, aber effektiv hast Du damit ja gar keine
Tests, weil niemand sie je (komplett) laufen lassen wird. Unit Tests
sollten eigentlich sogar nach jeder in sich abgeschlossenen
Code-Änderung automatisiert durchlaufen; das kannst Du mit diesem Ansatz
komplett knicken.
Üblicherweise wählt man für Unit Tests Szenarien mit (Kombinationen von)
Extremen oder besonders hervorgehobenen Elementen aus dem erlaubten
Bereich der Eingabewerte (hier etwa: 0, 1, Integer.SIZE,...) und einige
mehr oder minder zufällige Werte, die pars pro toto für die sonstige
Bandbreite stehen. Ergänzen kann man das durch randomisierte Tests a la
QuickCheck[1]. Da gibt es wohl auch diverse Java-Ports; keine Ahnung,
wie es sich damit arbeitet.
Viele Grüße
Patrick
[1] http://www.cse.chalmers.se/~rjmh/QuickCheck/manual.html

Ich habe die Tests für die arraycopy-Methoden des Bit-Packed-Array noch laufen und die dauern schon ziemlich lange.

Wie könnte man die Anzahl der ausgeführten Testfälle verringern, ohne die Korrektheit zu gefährden?

Eine Überlegung ist das Formulieren einer algebraischen Spezifikation.


Diese Zeile bedeutet nichts bzw. ich weiss es nicht:

array[length]

Es gibt eine Variable length, für diese gilt:

int length; length >= 0 && length <= Integer.MAX_INT

Es gibt eine Variable index, für diese gilt:

int index; index >= 0 && index < length

Ein einzelner Wert aus der Anzahl length Werte wird geschrieben als:

array[index]

Eventuell bekommt die erste Zeile dadurch doch irgendwie einen Sinn.

Nun die Methode arraycopy aus java.lang.System:

public static native void arraycopy(
Object src,
int srcPos,
Object dest,
int destPos,
int length);

Zur Vereinfachung sage ich mal:

src == dest == this

Dann ist die Signatur:

public void arraycopy(
int srcPos,
int destPos,
int length);

Es gibt einen Zustand /Inhalt des Arrays vor dem Ausführen der Methode arracopy und einen Zustand /Inhalt des Arrays danach.

Das Array nach dem Ausführen der Methode arraycopy nenne ich:

array'

(Habe ich irgendwo schon mal gesehen)

Die Invariante wäre dann:


if (index >= destPos && index < destPos + Parameter length): array[index - (destPos - srcPos)]
array'[index] =
else: array[index]

'Parameter length' bedeutet Parameter der Methode zur Unterscheidung von der Länge des Arrays.

Man könnte nun naiv über einen Wertebereich

int Array length; length >= 0 && length <= Integer.MAX_INT

array[index] >= Typ.MIN_VALUE && array[index] <= Typ.MAX_VALUE

laufen.

Das ist ganz schön viel.

Leider sind Spezifikation und Implementierung unterschiedliche Dinge.

Anhand der Spezifikation kann man nicht die Grenzfälle und Äquivalenzklassen der Implementierung erkennen.

Die Implementierung könnte einfach eine Tabelle/Map mit Zuordnung der Parameter und des vorherigen Zustandes zum Ergebniszustand sein (wahrscheinlich ist dies nicht die Implementierung, weil der Speicherbedarf ganz schön groß wäre).
Dann müßte man jede Kombination aus Parametern und Vorherzustand testen.

Also benötigt man scheinbar so etwas wie Code-Abdeckung.

Bekanntermaßen reicht Code-Abdeckung nicht aus, man muss auch Zweig-Abdeckung, Pfad-Abdeckung und Daten-Abdeckung beachten.

Hätte man also ein Tool, welches programmatisch die Abdeckung der einzelnen Code-Teile: Statements, Expressions, Bedingungen, Verzweigungen, Wiederholungen, Methoden-Aufrufe je Parametern und Vorherzustand des Arrays aufzeichnet, könnte man in einer Zuordnungs-Tabelle von Parametern und Vorherzuständen zu getesten Code-Teilen, die Parameter und Vorherzustände, die bestimmte Code-Teile redundant testen, finden.

Um darin ein System zu finden, benötigt man Intelligenz, hier droht also der Gödel.

Für einen wiederholten Test könnte man die redundant testenden Parameter und Vorherzustände aussparen.

Aber nach einer Änderung des Codes würde die vorherige Zuordnungstabelle nicht mehr gelten und das ganze müsste wiederholt werden.

Deshalb komme ich zu dem Schluß, dass die Anwendung einer solchen Einsparungsmethode ohne Intelligenz (Gödel) mindestens genauso aufwändig wie der sture Test wäre.

Wenn man aber Intelligenz anwendet, kann man sich irren und dadurch Fehler übersehen.

Eine Alternative wäre noch, dass während des Tests die Code-/Zweig-/Pfad-/Daten-Abdeckung geprüft wird und bei ausreichender Abdeckung abgebrochen wird.
Vor dem Abbrechen wären aber sicher jede Menge redundante Tests ausgeführt worden.

Post by Heiner Kücker
Schöne Grüße
Heiner

[Patrick Roemer]

Post by Heiner Kücker

Post by Patrick Roemer
"The number of input and output combinations for trivial programs is
surprisingly large. It is astronomical for typical programs and beyond
comprehension for typical systems. [...] Clearly, we can never test all
inputs, states, or outputs."
Robert V. Binder, Testing Object-Oriented Systems
§3.3: The Limits of Testing
Das ist sehr gründlich gedacht, aber effektiv hast Du damit ja gar keine
Tests, weil niemand sie je (komplett) laufen lassen wird. Unit Tests
sollten eigentlich sogar nach jeder in sich abgeschlossenen
Code-Änderung automatisiert durchlaufen; das kannst Du mit diesem Ansatz
komplett knicken.
Üblicherweise wählt man für Unit Tests Szenarien mit (Kombinationen von)
Extremen oder besonders hervorgehobenen Elementen aus dem erlaubten
Bereich der Eingabewerte (hier etwa: 0, 1, Integer.SIZE,...) und einige
mehr oder minder zufällige Werte, die pars pro toto für die sonstige
Bandbreite stehen. Ergänzen kann man das durch randomisierte Tests a la
QuickCheck[1]. Da gibt es wohl auch diverse Java-Ports; keine Ahnung,
wie es sich damit arbeitet.
Viele Grüße
Patrick
[1] http://www.cse.chalmers.se/~rjmh/QuickCheck/manual.html

Ich habe die Tests für die arraycopy-Methoden des Bit-Packed-Array noch laufen und
die dauern schon ziemlich lange.

Ach? ;)

Post by Heiner Kücker
Wie könnte man die Anzahl der ausgeführten Testfälle verringern, ohne die Korrektheit
zu gefährden?

Gar nicht. Denn im Prinzip kann im Code jederzeit irgendwas stehen wie

if(dataElementWidth == 637450152 && arraySize == 994637 && ...) {
throw new JustKiddingException();
}

Will meinen, wenn Du nicht alle möglichen Kombinationen von
Eingabewerten prüfst, ist die Korrektheit "gefährdet". Da das nicht
möglich ist, muss man sich mit pragmatischeren Ansätzen bescheiden.

Post by Heiner Kücker
Eine Überlegung ist das Formulieren einer algebraischen Spezifikation.

Das ist genau der Ansatz hinter QuickCheck. Anders als bei klassischen
Unit-Tests, die um konkrete Beispielszenarien herum gebaut sind,
formuliert man "Gesetze", die für alle möglichen Szenarien
(Kombinationen von Eingabewerten,...) gelten müssen. Statt dann aber den
kompletten Wertebereich zu durchlaufen, wie Du es versuchst, begnügt man
sich pro Testlauf mit einer überschaubaren Menge randomisiert erstellter
Szenarien. Damit hat man die Hoffnung, dass Fehler, die eine große
Teilmenge der möglichen Szenarien betreffen, in so gut wie jedem Lauf
auffallen sollten, und Fehler, die nur eine kleine Teilmenge betreffen,
wenigstens eine Chance haben, früher oder später ins Netz zu gehen.

Zusätzlich sollte man natürlich immer noch klassische Tests haben, die
Grenzfälle, typische Szenarien, etc. deterministisch prüfen. Und die
muss man halt mit einer Mischung von strukturierter Analyse, gesundem
Menschenverstand, Erfahrung und Bauchgefühl auswählen, wobei die
Dekompositionshierarchie einen unterstützen oder, wenn schlecht gewählt,
auch sabotieren kann.

Es ist ja kein Zufall, dass der oben zitierte Binder ein Ziegelstein mit
über 1000 Seiten ist - und nur eines von unzähligen Werken über
Testdesign und -strategien...

Post by Heiner Kücker
Leider sind Spezifikation und Implementierung unterschiedliche Dinge.
Anhand der Spezifikation kann man nicht die Grenzfälle und Äquivalenzklassen
der Implementierung erkennen.

Man will die Tests aber nicht von der Implementierung abhängig machen,
weil die eventuell beim Schreiben der Tests noch gar nicht (vollständig)
existiert, und weil sie sich wiederum jederzeit ändern kann.

Post by Heiner Kücker
Statements, Expressions, Bedingungen, Verzweigungen, Wiederholungen, Methoden-Aufrufe
je Parametern und Vorherzustand des Arrays aufzeichnet, könnte man in einer Zuordnungs-
Tabelle von Parametern und Vorherzuständen zu getesten Code-Teilen, die Parameter und
Vorherzustände, die bestimmte Code-Teile redundant testen, finden.
Um darin ein System zu finden, benötigt man Intelligenz, hier droht also der Gödel.

Und das Halteproblem. Und wiederum die kombinatorische Explosion auf
dieser Ebene. Und, und, und...

Nur als Scherz am Rande, weil von der Idee her verwandt: Es gab da mal
ein Tool[1], das Änderungen im Code vorgenommen hat und dann die Tests
dagegen laufen ließ - wenn die noch grün liefen, war die geänderte
Stelle nicht hinreichend abgedeckt. Nette Idee, aber die
Praxistauglichkeit...

Viele Grüße
Patrick

[1] http://jester.sourceforge.net/

[Joerg Meier]

Post by Patrick Roemer
Nur als Scherz am Rande, weil von der Idee her verwandt: Es gab da mal
ein Tool[1], das Änderungen im Code vorgenommen hat und dann die Tests
dagegen laufen ließ - wenn die noch grün liefen, war die geänderte
Stelle nicht hinreichend abgedeckt. Nette Idee, aber die
Praxistauglichkeit...

Das ist gar nicht so laecherlich; mutation testing gibt es immer noch und
es ist mittlerweile weit genug entwickelt, um normalen unit tests um
einigest voraus zu sein.

http://pitest.org/

Liebe Gruesse,
Joerg

[Heiner Kücker]

Post by Joerg Meier

Post by Patrick Roemer
Nur als Scherz am Rande, weil von der Idee her verwandt: Es gab da mal
ein Tool[1], das Änderungen im Code vorgenommen hat und dann die Tests
dagegen laufen ließ - wenn die noch grün liefen, war die geänderte
Stelle nicht hinreichend abgedeckt. Nette Idee, aber die
Praxistauglichkeit...

Das ist gar nicht so laecherlich; mutation testing gibt es immer noch und
es ist mittlerweile weit genug entwickelt, um normalen unit tests um
einigest voraus zu sein.
http://pitest.org/

Ja

http://jug-karlsruhe.de/content/mutation-testing/

Post by Joerg Meier
Liebe Gruesse,
Joerg

Schöne Grüße
Heiner

[Patrick Roemer]

Post by Joerg Meier

Post by Patrick Roemer
Nur als Scherz am Rande, weil von der Idee her verwandt: Es gab da mal
ein Tool[1], das Änderungen im Code vorgenommen hat und dann die Tests
dagegen laufen ließ - wenn die noch grün liefen, war die geänderte
Stelle nicht hinreichend abgedeckt. Nette Idee, aber die
Praxistauglichkeit...

Das ist gar nicht so laecherlich; mutation testing gibt es immer noch und
es ist mittlerweile weit genug entwickelt, um normalen unit tests um
einigest voraus zu sein.
http://pitest.org/

Das klingt etwas schräg - Mutation Testing operiert doch gerade auf
"normalen Unit-Tests" und fügt denen sozusagen noch eine Metatestebene
hinzu. Ich nehme mal an, gemeint ist, dass solchermassen "gehärtete"
Unit-Tests ihren Kollegen voraus sind.

Gibt es denn da Erfahrungswerte mit Projekten oberhalb von
Additionsserver, Fibonacci und Palindromen? Was konkretes habe ich auf
Anhieb nicht gefunden.

Ich würde erwarten, dass die Laufzeiten immer noch jenseits von gut und
böse sind. Klingt z.B. hier auch so: "Even though mutation testing
reveals defects in code, it should be used wisely, because it is an
extremely costly and time-consuming process."[1] Wie auch anders - die
Laufzeit muss ja mindestens (normale Laufzeit der Tests) x (Anzahl der
Mutationen) sein...

Weiter wäre ich skeptisch, was "false positives" angeht, also dass,
ähnlich wie bei klassischer Coverage, Code angemeckert wird, der gar
nicht getestet werden soll, wie etwa #toString(). Und mich würde
interessieren, wie mit durch Mutationen entstandenen Endlosschleifen,
etc. verfahren wird.

Ich wollte den Ansatz mal spaßeshalber mit einem Scala-Framework[2]
gegen eines meiner Projekte ausprobieren, bin aber sofort in einen
Bug(?)[3] mit Concurrency-Konstrukten gelaufen. :/ (Was natürlich
überhaupt nichts über PIT aussagt.)

Viele Grüße
Patrick

[1] https://www.baeldung.com/java-mutation-testing-with-pitest
[2] https://github.com/sugakandrey/scalamu
[3] https://github.com/sugakandrey/scalamu/issues/5

[Heiner Kücker]

Post by Patrick Roemer

Post by Heiner Kücker
Ich habe die Tests für die arraycopy-Methoden des Bit-Packed-Array noch laufen und
die dauern schon ziemlich lange.

Ach? ;)

Post by Heiner Kücker
Wie könnte man die Anzahl der ausgeführten Testfälle verringern, ohne die Korrektheit
zu gefährden?

Gar nicht. Denn im Prinzip kann im Code jederzeit irgendwas stehen wie
if(dataElementWidth == 637450152 && arraySize == 994637 && ...) {
throw new JustKiddingException();
}
Will meinen, wenn Du nicht alle möglichen Kombinationen von
Eingabewerten prüfst, ist die Korrektheit "gefährdet". Da das nicht
möglich ist, muss man sich mit pragmatischeren Ansätzen bescheiden.

Post by Heiner Kücker
Eine Überlegung ist das Formulieren einer algebraischen Spezifikation.

Das ist genau der Ansatz hinter QuickCheck. Anders als bei klassischen
Unit-Tests, die um konkrete Beispielszenarien herum gebaut sind,
formuliert man "Gesetze", die für alle möglichen Szenarien
(Kombinationen von Eingabewerten,...) gelten müssen. Statt dann aber den
kompletten Wertebereich zu durchlaufen, wie Du es versuchst, begnügt man
sich pro Testlauf mit einer überschaubaren Menge randomisiert erstellter
Szenarien. Damit hat man die Hoffnung, dass Fehler, die eine große
Teilmenge der möglichen Szenarien betreffen, in so gut wie jedem Lauf
auffallen sollten, und Fehler, die nur eine kleine Teilmenge betreffen,
wenigstens eine Chance haben, früher oder später ins Netz zu gehen.
Zusätzlich sollte man natürlich immer noch klassische Tests haben, die
Grenzfälle, typische Szenarien, etc. deterministisch prüfen. Und die
muss man halt mit einer Mischung von strukturierter Analyse, gesundem
Menschenverstand, Erfahrung und Bauchgefühl auswählen, wobei die
Dekompositionshierarchie einen unterstützen oder, wenn schlecht gewählt,
auch sabotieren kann.
Es ist ja kein Zufall, dass der oben zitierte Binder ein Ziegelstein mit
über 1000 Seiten ist - und nur eines von unzähligen Werken über
Testdesign und -strategien...

Echt schwierig.

Post by Patrick Roemer

Post by Heiner Kücker
Um darin ein System zu finden, benötigt man Intelligenz, hier droht also der Gödel.

Und das Halteproblem. Und wiederum die kombinatorische Explosion auf
dieser Ebene. Und, und, und...

Das Halteproblem ist eine andere Formulierung des Gödelschen Unvollsändigkeitssatzes.

Post by Patrick Roemer
Viele Grüße
Patrick

Danke
Heiner