Revolutionising the processof software development
Justyna Petke
Centre for Research in Evolution, Search and Testing
University College London

CREST

Genetic Improvementof Software
Justyna Petke
Centre for Research in Evolution, Search and Testing
University College London

CREST

Thank you

Mark HarmanCREST

Yue Jia

Alexandru Marginean

What does the word “Computer” mean?
Oxford Dictionary“a person who makes calculations,especially with a calculating machine.”

Wikipedia“The term "computer", in use from the mid 17th
century, meant "one who computes": a person
performing mathematical calculations.”
CREST

Genetic Improvement

Justyna PetkeWhat does the word “Computer” mean?
Oxford Dictionary“a person who makes calculations,especially with a calculating machine.”

Wikipedia“The term "computer", in use from the mid 17thcentury, meant "one who computes": a person
performing mathematical calculations.”
CREST

Genetic Improvement

Justyna PetkeWho are the programmers

CREST

Genetic Improvement

Justyna PetkeWho are the programmers

CREST

Genetic Improvement

Justyna PetkeWho are the programmers

CREST

Genetic Improvement

Justyna PetkeWho are the programmers

it’s always been people
CREST

Genetic Improvement

Justyna PetkeWho are the programers

it’s always been people
CREST

Genetic Improvement

Justyna PetkeWho are the programers

lots of people
CREST

Genetic Improvement

Justyna PetkeWhy people?

human computers seem quaint today
will human programmers seem quaint tomorrow ?

CREST

Genetic Improvement

Justyna Petkeprogramming is changing

CREST

Genetic Improvement

Justyna PetkeFunctional
Requirements

Non-FunctionalRequirements

Requirements

CREST

Genetic Improvement

Justyna PetkeFunctionalRequirements

Non-FunctionalRequirements
Execution TimeMemory

functionality ofthe Program

Bandwidth
EnergySize

CREST

Genetic Improvement

Justyna Petke

Software Design Process

CREST

Genetic Improvement

Justyna Petke

Software Design Process

CREST

Genetic Improvement

Justyna Petke

Software Design Process

CREST

Genetic Improvement

Justyna Petke

Software Design Process

CREST

Genetic Improvement

Justyna Petke

Software Design Process

CREST

Genetic Improvement

Justyna Petke

Multiplicity
Multiple
DevicesMultiple
Platforms
Conflicting
Objectives

CREST

Genetic Improvement

Justyna PetkeWhich requirements must be human coded ?
Functional
Requirements

Non-Functional
Requirements

humans have todefine these
CREST

Genetic Improvement

Justyna PetkeWhich requirements are essential to human ?
FunctionalRequirements

humans have todefine these
CREST

Genetic Improvement

Non-Functional
Requirements

we can optimise
theseJustyna Petke

Can it work ?

CREST

Genetic Improvement

Justyna Petke

Software Uniqueness

500,000,000 LoC
one has to write approximately 6 statements
before one is writing unique code

CREST

Genetic Improvement

Justyna Petke

Software UniquenessM. Gabel and Z. Su.
A study of the uniqueness of source code. (FSE 2010)

500,000,000 LoC
one has to write approximately“The space6 ofstatements
candidate
before one is writing unique code

programs is far smaller
than we might suppose.

CREST

Genetic Improvement”

Justyna Petke

Software Robustness

after one line changes up to 89% of programs
that compile run without error

CREST

Genetic Improvement

Justyna Petke

Software Robustness

W. B .Langdon and J. Petke
Software is Not Fragile. (CS-DC 2015)“

after one line changes Software
up to 89% engineeringof programs
that compile run without error

artefacts are more robust
than is often assumed.

”

CREST

Genetic Improvement

Justyna PetkeNon-Functional
Requirements

How can we optimise
these ?
CREST

Genetic Improvement

Justyna PetkeGenetic Improvement

http://www.cs.ucl.ac.uk/staff/ucacbbl/gismo/
CREST

Genetic Improvement

Justyna PetkeWhich requirements are essential to human ?
Functional
Requirements

humans have todefine these
CREST

Genetic Improvement

Non-Functional
Requirements

we can optimise
these
Justyna PetkeGenetic Improvement
Framework
SoftwareSensitivity
Analysis

SearchTest
data

PrograImproved
ms
SoftwareFitness

Non-functional
property Test

CREST

Genetic Improvement

Justyna PetkeEfficiency Improvement
Bowtie2

Sensitivity
Analysis

GP
Test
data

Non-functional
property Test

PrograPrograPrograBowtiemsmsms
ImprovFitness

70 times faster30+ interventions
7 after clean up
slight semantic improvement

W. B. Langdon and M. Harman
Optimising Existing Software with Genetic Programming.
Transactions on Evolutionary Computation (TEC) 2015

CREST

Genetic Improvement

Justyna PetkeMutation

Source file

Line (type)

Orig. code

New codereplaced

bt2_io.cpp

622 (for2)

i < offsLenSampled

i < this->_nPat

replaced

sa_rescomb.cpp

50 (for2)

i < satup_->offs.size()0sa_rescomb.cpp
69 (for2)< satup_->offs.size()
Runtimereduction from12 jdays
to 4 hoursdisabled

CREST

replacedaligner_swsse_ee_u8
.cpp

707

vh =_mm_max_epu8(vh,vf);deletedaligner_swsse_ee_u8
.cpp

766

pvFStore += 4;

replacedaligner_swsse_ee_u8
.cpp

772

_mm_store_si128(pvHStore, vh);deletedaligner_swsse_ee_u8
.cpp

778

ve =_mm_max_epu8(ve,vh);

Genetic Improvement

vmax = vlo;

vh =_mm_max_epu8(vh,vf);

Justyna PetkeEfficiency Improvement
CUDA

Sensitivity
AnalysisGP
Testdata

PrograPrograPrograCUDAmsmsms
Improv

Fitness

Non-functional
property Test
W.B. Langdon , B.Y.H. Lam , J. Petke & M. Harman
Improving CUDA DNA Analysis Software with Genetic Programming
Genetic and Evolutionary Computation Conference (GECCO) 2015

CREST

Genetic Improvement

Justyna PetkeEfficiency Improvement
Challenge: Use genetic improvement to improve program
efficiency of a state-of-the-art bioinformatics program for DNA
sequence mapping called BarraCUDA, consisting of 8,000+ linesof code.
Results: The improved version of BarraCUDA is up to 3x
faster than the original on large real-world datasets. The newversion has been adopted into development and has been
downloaded over 1,000 times so far. Ported by IBM to one of
their super computers and adopted by Lab7.
W.B. Langdon , B.Y.H. Lam , J. Petke & M. Harman
Improving CUDA DNA Analysis Software with Genetic Programming
Genetic and Evolutionary Computation Conference (GECCO) 2015

CREST

Genetic Improvement

Justyna PetkeGenetic Improvement
Framework
SoftwareSensitivity
Analysis

SearchTest
data

PrograImprovedms
SoftwareFitness

Non-functional
property Test

CREST

Genetic Improvement

Justyna Petke

Software Specialisationwith Transplants
Sensitivity
Analysis

SearchTestdataProgra
msFitness

Non-functional
property Test

CREST

Genetic Improvement

Justyna Petke

CREST

Genetic Improvement

Justyna Petke

Question

Can we improve the efficiency of an already highly-optimised piece ofsoftware using genetic programming?

Genetic Improvement

Justyna Petke

Motivation for choosing a SAT solver
Bounded Model Checking
Planning
Software Verification
Automatic Test Pattern Generation
Combinational Equivalence Checking
Combinatorial Interaction Testing
and many other applications..

Genetic Improvement

Justyna Petke

Motivation for choosing a SAT solver

MiniSAT-hack track in SAT solver competitions- good source for software transplants

Genetic Improvement

Justyna Petke

Contributions

Introduction of multi-donor software transplantation
Use of genetic improvement as means to specialise software

Genetic Improvement

Justyna Petke

Contributions

Introduction of multi-donor software transplantation
Use of genetic improvement as means to specialise software

Genetic Improvement

Justyna Petkev1

Software Specialisation
with Transplants

MiniSat
v2

MiniSatSensitivity
Analysis

GP
Test
data

v3

MiniSat

PrograPrograPrograMiniSatmsmsms
Improv

Fitness

Non-functional
property Test
Justyna Petke, Mark Harman, William B. Langdon and Westley Weimer
Using Genetic Improvement & Code Transplants to Specialise a C++
program to a Problem Class
European Conference on Genetic Programming (EuroGP) 2014
CREST

Genetic Improvement

Justyna Petke

Program Representation

Changes at the level of lines of source code
Each individual is composed of a list of changes
Specialised grammar used to preserve syntax

Genetic Improvement

Justyna PetkeExample
IaQHp2`nRj8=,,4] B7] IA6naQHp2`nRj8= ]`2im`M 7Hb2c$M]

IA6naQHp2`nRj8= ,,4]U5QFV]IaQHp2`nRj3=,,4]] InaQHp2`nRj3= ]&GQ;n+QmMie9YYcf Rj3 f'$M]

InaQHp2`nRj3=,,4]bQ`iUTbVc]

IaQHp2`nRjN=,,4]GBi Tc BMi B- Dc$M]

IaQHp2`nR9y=,,4]7Q`U] I7Q`RnaQHp2`nR9y= ]c] I7Q`knaQHp2`nR9y= ]c] I7Q`jnaQHp2`nR9y= ]V &$M]

I7Q`RnaQHp2`nR9y=,,4]B 4 D 4 - T 4 HBinlM/27]

I7Q`knaQHp2`nR9y=,,4]B I TbXbBx2UV]

I7Q`jnaQHp2`nR9y=,,4]BYY]

Genetic Improvement

Justyna PetkeCode Transplants
GP has access to both:• the host program to be evolved• the donor program(s)code bank contains all lines of source code GP has access toGenetic Improvement

Justyna Petke

Question

How much runtime improvement can we achieve?

Genetic Improvement

Justyna Petkev1

Software Specialisation
with Transplants

MiniSat
v2

MiniSatSensitivity
Analysis

GP
Test
data

v3

MiniSatNon-functional
property Test

PrograPrograPrograMiniSatmsms
ms
Improv

Fitness

Multi-donor transplant
Specialised for a particularapplication domain
17% faster

Justyna Petke, Mark Harman, William B. Langdon and Westley Weimer
Using Genetic Improvement & Code Transplants to Specialise a C++
program to a Problem Class
European Conference on Genetic Programming (EuroGP) 2014
CREST

Genetic Improvement

Justyna Petke

Real-world cross-systemtransplantation
Sensitivity
Analysis

SearchTest
data

Programs

Fitness

Non-functional
property Test

CREST

Genetic Improvement

Justyna PetkeDonorfeatureReal-world cross-systemtransplantation
Sensitivity
Analysis

Search
Test
data

Host

Non-functional
property Test

FitnessHost’
featureAutotransplanted newfunctionality and passed
all tests for 12 out of 15systems & transplanted
a video encoding into
the VLC media player

Earl T. Barr, Mark Harman,Yue Jia, Alexandru Marginean, and Justyna Petke
Automated Software Transplantation
International Symposium on Software Testing and Analysis (ISSTA) 2015

CREST

Genetic Improvement

Justyna PetkeAutomated Software Transplantation
E.T. Barr, M. Harman,Y. Jia, A. Marginean & J. Petke
ACM Distinguished Paper Award at ISSTA 2015
Gold ‘Humie’ Award Winner at GECCO 2016
over 2,000 shares ofarticle incoverage inCREST

Genetic Improvement

Justyna PetkeWhy Autotransplantation?
~100 players

Check opensource repositories
Why nothandle
H.264?

Video Player

Start fromscratch

CREST

Genetic Improvement

Justyna PetkeAutomated Software
Transplantation
Donor
ENTRY

Manual Work:
Organ Entry

V
Organ
Organ Test
Suite

Organ’s Test Suite
Host
Implantation Point

CREST

Genetic Improvement

Justyna PetkeμTrans
Host
Implantation
Point

Donor

Stage 1:
Static Analysis

Stage 2:
GeneticProgramming

Stage 3:
Organ
Implantation

Organ Test
Suite

Host
Beneficiary

OrganEntry

CREST

Genetic Improvement

Justyna Petket* Complete

**t
enact

C *
AEell Docu EveWme* Easy toed
RntaluISSTA ** use * Consis A

rtifSubjects

at e dden12
Subjects

Idct
MytarCflow
Webserver
is a promising
techre tests. TheTuxCrypttechences using public
Pidginnder-test (SUT).
Itt technique to Cflow
genality and flexibility,
SoX
rected random test-Type

Size
KLOC

Donor
Donor
Donor
Donor
Donor
Host
Host
Host
Case Study
Donor
Host

ck-directed random
hods [5, 25]. Others
x264
to prove their theVLC
re is an interestingy analyzing the dyg feedback-directedck-directed
CREST random
Genetic Improvement
dustries and under-

2.3
0.4251.7
2.7363254363422

Minimal size: 0.4k
Max size: 422k
Average Donor:16k
Average Host: 213k

Justyna PetkeExperimental Methodology
and Setup
HostImplantation
Point

64 bit Ubuntu 14.10
16 GB RAM
8 threads
CREST

Genetic Improvement

Donor
Organ Test
SuiteOE

Host
Beneficiary

μSCALPEL
Implantation
Point

Organ

Justyna Petkeactt* Complete

**ten

C *
AEell Docu EveWme

* Easy toed
RntaluISSTA *
* use * Consis Artif

Empirical Studyat e diden12] is a promising techare tests. The techuences using public
under-test (SUT). It
nt technique to genality and flexibility,
irected random testack-directed random
hods [5, 25]. Others
to prove their theere is an interestingby analyzing the dyng feedback-directedack-directed randomndustries and under-in 12 out of 15 experiments
we successfully autotransplanted
new functionality

s of feedback-directed
died. To the best of
posed extensions to27], but they failed
ted random testing.
ance had never been
te characteristics ofng a model SUT andthe obtained knowlts generation, amplierated tests.
this paper.

ss stop increasing atdom seeds?

ssen the dependency
CREST
overall performance

Genetic Improvement

Justyna Petket* Complete**tenact

C *AEell Docu EveW

Case Studyme* Easy toed
RntaluISSTA *
* use * Consis A

rtifat e dden12

Transplant Time & Test Suites
Time (hours) Regression Regression++ Acceptance
H.264

within 26 hours performed a task
26
100%
100%
that took developers
an avg of 20 days of elapsed time

is a promising techre tests. The techences using publicnder-test (SUT). Itt technique to genality and flexibility,rected random testck-directed random
hods [5, 25]. Others
to prove their there is an interestingy analyzing the dyg feedback-directedck-directed
CREST random
Genetic Improvement
dustries and under-100%

VLC

H264

Justyna Petke* http://crest.cs.ucl.ac.uk/autotransplantation/MuScalpel.html
CREST

Genetic Improvement

Justyna Petke

Memory vs speed trade offs
Sensitivity
Analysis

SearchTest
data

ProgramsFitness

Non-functional
property Test

CREST

Genetic Improvement

Justyna Petke

Memory vs speed trade offs
Systemmalloc

SystemSensitivity
Analysis

GPTestdata

Non-functional
property Test

Fitness

optimisedmallocImprove execution timeby 12% or achieve a 21%
memory consumption
reduction

Fan Wu, Westley Weimer, Mark Harman,Yue Jia and Jens Krinke
Deep Parameter Optimisation
Genetic and Evolutionary Computation Conference (GECCO) 2015

CREST

Genetic Improvement

Justyna Petke

Reducing Energy Consumption
Sensitivity
Analysis

SearchTest
dataProgramsFitness

Non-functional
property Test

CREST

Genetic Improvement

Justyna Petke

Reducing Energy Consumption
Improved MiniSat
application 1v1MiniSatv2

MiniSatSensitivity
Analysis

GPTestdatav3

MiniSatNon-functional
property Test

Fitness

Improved MiniSat
application 2
Improved MiniSat
application 3

Energy consumption canbe reduced by up to 25%

Bobby R. Bruce Justyna Petke Mark Harman
Reducing Energy Consumption Using Genetic Improvement
Conference on Genetic and Evolutionary Computation (GECCO 2015)

CREST

Genetic Improvement

Justyna PetkeGrow and Graftnew functionality?

Sensitivity
Analysis

SearchTest
dataProgra
msFitness

Non-functional
property Test

CREST

Genetic Improvement

Justyna PetkeGrow and Graftnewfunctionality
GraftGrow
Human
Knowledge

GPTestdataFeature

Sensitivity
AnalysisNon-functional
property Test

GPTestdataFitness

Host System
FeatureFitness

Non-functional
property TestMark Harman,Yue Jia and Bill Langdon,
Babel Pidgin: SBSE can grow and graft entirely new functionality into a real world system
Symposium on Search-Based Software Engineering (SSBSE) 2014 (Challenge track)

CREST

Genetic Improvement

Justyna PetkeGenetic Improvement Applications
Improving software efficiency
Improving energy consumption
Porting old code to new hardware
Grafting new functionality into an existing system
Specialising software for a particular problem class
OtherCREST

Genetic Improvement

Justyna PetkeGenetic Improvement Visibility
First International Workshop on
Genetic Improvement
at GECCO 2015, Madrid, Spain
www.geneticimprovementofsoftware.com

Special Session on GI http://www.wcci2016.org/

Second International Workshop on Genetic Improvement
at GECCO 2016, Denver, Colorado
Special Issue
on GI

CREST

Genetic Improvement

Justyna PetkeGenetic Improvement of Software
geneticimprovementofsoftware.com

Functional Properties

New Feature

Non-functional Properties
Execution Time
MemoryFunctionality
Improvement

EnergyError

CREST

Genetic Improvement

Justyna PetkeGenetic Improvement of Softwaregeneticimprovementofsoftware.com

Functional Properties
New Feature
Functionality
Improvement

Error

Bug Repair

Non-functional Properties
Execution Time
MemoryBandwidthEnergy
Size

CREST

Genetic Improvement

Justyna PetkePictures used with thanks from these sources

Stonehenge: By Yuanyuan Zhang [All right reserved] via Flickr
BBC_Micro: [Public domain], via Wikimedia Commons
IMac: By Matthieu Riegler, Wikimedia Commons [CC-BY-3.0 (http://creativecommons.org/licenses/by/3.0)], via Wikimedia Commons
Ada Lovelace: By Alfred Edward Chalon [Public domain], via Wikimedia Commons
Programmer: undesarchiv, B 145 Bild-F031434-0006 / Gathmann, Jens / CC-BY-SA [CC-BY-SA-3.0de (http://creativecommons.org/licenses/by-sa/3.0/de/deed.en)], via Wikimedia Commons

CREST

Genetic Improvement

Justyna Petke