research-article

Evolving sqrt into 1/x via software data maintenance

Authors:

Oliver KraussAuthors Info & Claims

GECCO '20: Proceedings of the 2020 Genetic and Evolutionary Computation Conference Companion

Pages 1928 - 1936

https://doi.org/10.1145/3377929.3398110

Published: 08 July 2020 Publication History

Abstract

While most software automation research concentrates on programs' code, we have started investigating if Genetic Improvement (GI) of data can assist developers by automating aspects of the maintenance of parameters embedded in source code. We extend recent GI work on optimising compile time constants to give new functionality and describe the transformation of a GNU C library square root function into the double precision reciprocal function, drcp. Multiplying by 1/x (drcp) allows division free division without requiring the hardware to support division. The evolution (6 seconds) and indeed the GI dp division (7.14 ± 0.012 nS) are both surprisingly fast.

References

[1]

2009. ARM1176JZF-S Technical Reference Manual (revision: r0p7 ed.). http://infocenter.arm.com/help/topic/com.arm.doc.ddi0301h/DDI0301H_arm1176jzfs_r0p7_trm.pdf

[2]

John Ahlgren et al. 2020. WES: Agent-based User Interaction Simulation on Real Infrastructure. In GI @ ICSE 2020, Shin Yoo et al. (Eds.). https://research.fb.com/wp-content/uploads/2020/04/WES-Agent-based-User-Interaction-Simulation-on-Real-Infrastructure.pdf Invited Keynote.

Digital Library

[3]

Nadia Alshahwan. 2019. Industrial experience of Genetic Improvement in Facebook. In GI-2019, ICSE workshops proceedings, Justyna Petke et al. (Eds.). IEEE, Montreal, 1. Invited Keynote.

Digital Library

[4]

Nadia Alshahwan et al. 2018. Deploying Search Based Software Engineering with Sapienz at Facebook. In SSBSE 2018 (LNCS), Thelma Elita Colanzi and Phil McMinn (Eds.), Vol. 11036. Springer, Montpellier, France, 3--45.

[5]

Gabin An et al. 2019. PyGGI 2.0: Language Independent Genetic Improvement Framework. In Proceedings of the 27th Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering ESEC/FSE 2019), Sven Apel and Alessandra Russo (Eds.). ACM, Tallinn, Estonia, 1100--1104.

Digital Library

[6]

Kevin Ashton. 2009. That 'Internet of Things' Thing. RFID journal (June 22 2009). http://www.itrco.jp/libraries/RFIDjournal-That%20Internet%20of%20Things%20Thing.pdf

[7]

Earl T. Barr et al. 2015. Automated Software Transplantation. In International Symposium on Software Testing and Analysis, ISSTA 2015, Tao Xie and Michal Young (Eds.). ACM, Baltimore, Maryland, USA, 257--269. ACM SIGSOFT Distinguished Paper Award.

Digital Library

[8]

Earl T. Barr et al. 2015. The Oracle Problem in Software Testing: A Survey. IEEE Transactions on Software Engineering 41, 5 (May 2015), 507--525. http://dx.doi.org/109/TSE.2014.2372785

Digital Library

[9]

Alexander E. I. Brownlee et al. 2019. Gin: genetic improvement research made easy. In GECCO '19, Manuel Lopez-Ibanez et al. (Eds.). ACM, Prague, Czech Republic, 985--993.

Digital Library

[10]

Bobby R. Bruce. 2015. Energy Optimisation via Genetic Improvement A SBSE technique for a new era in Software Development. In Genetic Improvement 2015 Workshop, William B. Langdon et al. (Eds.). ACM, Madrid, 819--820.

Digital Library

[11]

Bobby R. Bruce et al. 2016. Deep Parameter Optimisation for Face Detection Using the Viola-Jones Algorithm in OpenCV. In Proceedings of the 8th International Symposium on Search Based Software Engineering, SSBSE 2016 (LNCS), Federica Sarro and Kalyanmoy Deb (Eds.), Vol. 9962. Springer, Raleigh, North Carolina, USA, 238--243.

[12]

Nathan Burles et al. 2015. Object-Oriented Genetic Improvement for Improved Energy Consumption in Google Guava. In SSBSE (LNCS), Yvan Labiche and Marcio Barros (Eds.), Vol. 9275. Springer, Bergamo, Italy, 255--261.

[13]

Keith C. Clarke. 2003. Geocomputation's future at the extremes: high performance computing and nanoclients. Parallel Comput. 29, 10 (2003), 1281--1295.

Digital Library

[14]

James S. Collofello and Jeffrey J. Buck. 1987. Software Quality Assurance for Maintenance. IEEE Software 4, 5 (Sep 1987), 46--51.

Digital Library

[15]

Fabricio Gomes de Freitas and Jerffeson Teixeira de Souza. 2011. Ten Years of Search Based Software Engineering: A Bibliometric Analysis. In Third International Symposium on Search based Software Engineering (SSBSE 2011) (LNCS), Myra B. Cohen and Mel O Cinneide (Eds.), Vol. 6956. Springer, Szeged, Hungary, 18--32.

[16]

Sayed Mehdi Hejazi Dehaghani and Nafiseh Hajrahimi. 2013. Which Factors Affect Software Projects Maintenance Cost More? Acta Informatica Medica 21, 1 (Mar 2013), 63--66.

[17]

E. W. Dijkstra. 1969. "Testing shows the presence, not the absence of bugs." in Software Engineering Techniques: Report of a conference sponsored by the NATO Science Committee (Robert M. McClure, 2001 ed.). NATO, Scientific Affairs Division, Brussels, Rome, Italy, Chapter 3.1, 16. http://homepages.cs.ncl.ac.uk/brian.randell/NATO/nato1969.PDF

[18]

Anna I. Esparcia-Alcazar et al. 2018. Using genetic programming to evolve action selection rules in traversal-based automated software testing: results obtained with the TESTAR tool. Memetic Computing 10, 3 (Sept. 2018), 257--265.

[19]

Gordon Fraser and Andrea Arcuri. 2011. EvoSuite: automatic test suite generation for object-oriented software. In 8^th European Software Engineering Conference and the ACM SIGSOFT Symposium on the Foundations of Software Engineering (ESEC/FSE '11). ACM, Szeged, Hungary, 416--419.

Digital Library

[20]

Nikolaus Hansen and Andreas Ostermeier. 2001. Completely Derandomized Self-Adaptation in Evolution Strategies. Evolutionary Computation 9, 2 (Summer 2001), 159--195.

Digital Library

[21]

Scott Hanson et al. 2009. A Low-Voltage Processor for Sensing Applications With Picowatt Standby Mode. IEEE Journal of Solid-State Circuits 44, 4 (April 2009), 1145--1155.

[22]

Saemundur O. Haraldsson et al. 2017. Fixing Bugs in Your Sleep: How Genetic Improvement Became an Overnight Success. In GI-2017, Justyna Petke et al. (Eds.). ACM, Berlin, 1513--1520. Best paper.

Digital Library

[23]

Mark Harman et al. 2012. The GISMOE challenge: Constructing the Pareto Program Surface Using Genetic Programming to Find Better Programs. In The 27th IEEE/ACM International Conference on Automated Software Engineering (ASE 12). ACM, Essen, Germany, 1--14.

Digital Library

[24]

Mark Harman et al. 2014. Babel Pidgin: SBSE Can Grow and Graft Entirely New Functionality into a Real World System. In Proceedings of the 6th International Symposium, on Search-Based Software Engineering, SSBSE 2014 (LNCS), Claire Le Goues and Shin Yoo (Eds.), Vol. 8636. Springer, Fortaleza, Brazil, 247--252. Winner SSBSE 2014 Challange Track.

[25]

Mark Harman and Bryan F. Jones. 2001. Search Based Software Engineering. Information and Software Technology 43, 14 (Dec. 2001), 833--839.

[26]

Gunel Jahangirova et al. 2016. Test Oracle Assessment and Improvement. In Proceedings of the 25th International Symposium on Software Testing and Analysis (ISSTA'16). ACM, Saarbruecken, Germany, 247--258.

Digital Library

[27]

Yue Jia et al. 2015. Grow and Serve: Growing Django Citation Services Using SBSE. In SSBSE 2015 Challenge Track (LNCS), Shin Yoo and Leandro Minku (Eds.), Vol. 9275. Springer, Bergamo, Italy, 269--275.

[28]

John R. Koza. 1992. Genetic Programming: On the Programming of Computers by Natural Selection. MIT press.

Digital Library

[29]

John R. Koza et al. 2003. What's AI Done for Me Lately? Genetic Programming's Human-Competitive Results. IEEE Intelligent Systems 18, 3 (May/June 2003), 25--31.

Digital Library

[30]

Oliver Krauss and W. B. Langdon. 2020. Automatically Evolving Lookup Tables for Function Approximation. In EuroGP 2020: Proceedings of the 23rd European Conference on Genetic Programming (LNCS), Ting Hu et al. (Eds.), Vol. 12101. Springer Verlag, Seville, Spain, 84--100.

[31]

W. B. Langdon. 2015. Genetic Improvement of Software for Multiple Objectives. In SSBSE (LNCS), Yvan Labiche and Marcio Barros (Eds.), Vol. 9275. Springer, Bergamo, Italy, 12--28. Invited keynote.

[32]

W. B. Langdon. 2018. Genetic Improvement GISMOE Blue Software Tool Demo. Technical Report RN/18/06. University College, London, London, UK. http://www.cs.ucl.ac.uk/fileadmin/user_upload/blue.pdf

[33]

W. B. Langdon. 2019. Genetic Improvement of Data gives double precision invsqrt. In 7th edition of GI @ GECCO 2019, Brad Alexander et al. (Eds.). ACM, Prague, Czech Republic, 1709--1714.

Digital Library

[34]

William B. Langdon et al. 2017. Inferring Automatic Test Oracles. In Search-Based Software Testing, Juan P. Galeotti and Justyna Petke (Eds.). Buenos Aires, Argentina, 5--6.

[35]

William B. Langdon et al. 2018. Evolving better RNAfold structure prediction. In EuroGP 2018: Proceedings of the 21st European Conference on Genetic Programming (LNCS), Mauro Castelli et al. (Eds.), Vol. 10781. Springer Verlag, Parma, Italy, 220--236.

[36]

W. B. Langdon et al. 2020. Bit-Rot: Computer Software Degrades over Time. IEEE Software Blog. (11 March 2020). http://blog.ieeesoftware.org/2020/03

[37]

W. B. Langdon and M. Harman. 2010. Evolving a CUDA Kernel from an nVidia Template. In 2010 IEEE World Congress on Computational Intelligence, Pilar Sobrevilla (Ed.). IEEE, Barcelona, 2376--2383.

[38]

William B. Langdon and Mark Harman. 2015. Grow and Graft a better CUDA pknotsRG for RNA pseudoknot free energy calculation. In Genetic Improvement 2015 Workshop, William B. Langdon et al. (Eds.). ACM, Madrid, 805--810.

Digital Library

[39]

William B. Langdon and Mark Harman. 2015. Optimising Existing Software with Genetic Programming. IEEE Transactions on Evolutionary Computation 19, 1 (Feb. 2015), 118--135.

Digital Library

[40]

W. B. Langdon and Brian Yee Hong Lam. 2017. Genetically Improved BarraCUDA. BioData Mining 20, 28 (2 Aug. 2017).

[41]

William B. Langdon and Ronny Lorenz. 2017. Improving SSE Parallel Code with Grow and Graft Genetic Programming. In GI-2017, Justyna Petke et al. (Eds.). ACM, Berlin, 1537--1538.

Digital Library

[42]

William B. Langdon and Justyna Petke. 2015. Software is Not Fragile. In Complex Systems Digital Campus E-conference, CS-DC'15 (Proceedings in Complexity), Pierre Parrend et al. (Eds.). Springer, 203--211. Invited talk.

[43]

William B. Langdon and Justyna Petke. 2018. Evolving Better Software Parameters. In SSBSE 2018 Hot off the Press Track (LNCS), Thelma Elita Colanzi and Phil McMinn (Eds.), Vol. 11036. Springer, Montpellier, France, 363--369.

[44]

W. B. Langdon and Justyna Petke. 2019. Genetic Improvement of Data gives Binary Logarithm from sqrt. In GECCO '19 Companion, Richard Allmendinger et al. (Eds.). ACM, Prague, Czech Republic, 413--414.

Digital Library

[45]

William LaPlante and Robert Wisnieff. 2018. Final Report of the Defense Science Board Task Force on the Design and Acquisition of Software for Defense Systems. Technical Report. DoD, USA. https://dsb.cto.mil/reports/2010s/DSB_SWA_Report_FINALdelivered2-21-2018.pdf

[46]

Claire Le Goues et al. 2010. The case for software evolution. In Proceedings of the FSE/SDP workshop on Future of software engineering research, FoSER'10, Gruia-Catalin Roman and Kevin J. Sullivan (Eds.). ACM, Santa Fe, New Mexico, USA, 205--210.

Digital Library

[47]

Claire Le Goues et al. 2019. Automated Program Repair. Commun. ACM 62, 12 (Dec. 2019), 56--65.

Digital Library

[48]

Ronny Lorenz, Stephan H. Bernhart, Christian Höner zu Siederdissen, Hakim Tafer, Christoph Flamm, Peter F. Stadler, and Ivo L. Hofacker. 2011. ViennaRNA Package 2.0. Algorithms for Molecular Biology 6, 1 (2011).

[49]

Alexandru Marginean et al. 2015. Automated Transplantation of Call Graph and Layout Features into Kate. In SSBSE (LNCS), Yvan Labiche and Marcio Barros (Eds.), Vol. 9275. Springer, Bergamo, Italy, 262--268.

[50]

Alexandru Marginean et al. 2019. SapFix: Automated End-to-End Repair at Scale. In 41st International Conference on Software Engineering, Joanne M. Atlee and Tevfik Bultan (Eds.). ACM, Montreal, 269--278.

Digital Library

[51]

P. W. Markstein. 1990. Computation of elementary functions on the IBM RISC System/6000 processor. IBM Journal of Research and Development 34, 1 (Jan 1990), 111--119.

Digital Library

[52]

Roger J. Martin and Wilma M. Osborne. 1983. Guidance on software maintenance. NBS Special Publication 500-106. National Bureau of Standards, Department of Commerce, Washington DC, USA. http://nvlpubs.nist.gov/nistpubs/Legacy/SP/nbsspecialpublication500-106.pdf

[53]

Michael Mohan and Des Greer. 2018. A survey of search-based refactoring for software maintenance. Journal of Software Engineering Research and Development 6, 3 (7 February 2018).

[54]

Gordon E. Moore. 1965. Cramming more components onto integrated circuits. Electronics 38, 8 (April 19 1965), 114--117.

[55]

Vojtech Mrazek et al. 2015. Evolutionary Approximation of Software for Embedded Systems: Median Function. In Genetic Improvement 2015 Workshop, William B. Langdon et al. (Eds.). ACM, Madrid, 795--801.

Digital Library

[56]

Paulo Augusto Nardi and Eduardo F. Damasceno. 2015. A Survey on Test Oracles. Journal on Advances in Theoretical and Applied Informatics 1, 2 (2015), 50--59.

[57]

Justice Opara-Martins et al. 2016. Critical analysis of vendor lock-in and its impact on cloud computing migration: a business perspective. Journal of Cloud Computing 5, 4 (2016).

Digital Library

[58]

Michael Orlov and Moshe Sipper. 2011. Flight of the FINCH through the Java Wilderness. IEEE Transactions on Evolutionary Computation 15, 2 (April 2011), 166--182.

Digital Library

[59]

Justyna Petke. 2015. Constraints: The Future of Combinatorial Interaction Testing. In 2015 IEEE/ACM 8th International Workshop on Search-Based Software Testing. Florence, 17--18. http://dx.doi.org/

Digital Library

[60]

Justyna Petke et al. 2014. Using Genetic Improvement and Code Transplants to Specialise a C++ Program to a Problem Class. In 17th European Conference on Genetic Programming (LNCS), Miguel Nicolau et al. (Eds.), Vol. 8599. Springer, Granada, Spain, 137--149.

Digital Library

[61]

Justyna Petke et al. 2018. Genetic Improvement of Software: a Comprehensive Survey. IEEE Transactions on Evolutionary Computation 22, 3 (June 2018), 415--432. http://dx.doi.org/

[62]

Justyna Petke et al. 2018. Specialising Software for Different Downstream Applications Using Genetic Improvement and Code Transplantation. IEEE Transactions on Software Engineering 44, 6 (June 2018), 574--594.

[63]

Mauro Pezze and Cheng Zhang. 2015. Automated Test Oracles: A Survey. In Advances in Computers. Vol. 95. Elsevier, 1--48.

[64]

Adam Porter and Janos Sztipanovits (Eds.). 2001. Workshop on New Visions for Software Design and Productivity: Research and Applications. Number 000-041. USA Govt.'s NCO NITRD, Nashville. https://www.cs.umd.edu/~aporter/Docs/sdp_wrkshp_final.pdf

[65]

Eric Schulte et al. 2010. Automated Program Repair through the Evolution of Assembly Code. In Proceedings of the IEEE/ACM International Conference on Automated Software Engineering. ACM, Antwerp, 313--316.

Digital Library

[66]

Eric Schulte et al. 2014. Post-compiler Software Optimization for Reducing Energy. In Proceedings of the 19th International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS'14. ACM, Salt Lake City, Utah, USA, 639--652.

Digital Library

[67]

Eric Schulte et al. 2015. Repairing COTS Router Firmware without Access to Source Code or Test Suites: A Case Study in Evolutionary Software Repair. In Genetic Improvement 2015 Workshop, William B. Langdon et al. (Eds.). ACM, Madrid, 847--854. Best Paper.

Digital Library

[68]

Jeongju Sohn et al. 2016. Amortised Deep Parameter Optimisation of GPGPU Work Group Size for OpenCV. In Proceedings of the 8th International Symposium on Search Based Software Engineering, SSBSE 2016 (LNCS), Federica Sarro and Kalyanmoy Deb (Eds.), Vol. 9962. Springer, Raleigh, North Carolina, USA, 211--217.

[69]

Zdenek Vasicek and Vojtech Mrazek. 2017. Trading between quality and nonfunctional properties of median filter in embedded systems. Genetic Programming and Evolvable Machines 18, 1 (March 2017), 45--82.

Digital Library

[70]

David R. White. 2017. GI in No Time. In GI-2017, Justyna Petke et al. (Eds.). ACM, Berlin, 1549--1550. http://dx.doi.org/

Digital Library

[71]

David R. White et al. 2011. Evolutionary Improvement of Programs. IEEE Transactions on Evolutionary Computation 15, 4 (Aug. 2011), 515--538.

Digital Library

[72]

David R. White et al. 2017. Deep Parameter Tuning of Concurrent Divide and Conquer Algorithms in Akka. In 20th European Conference on the Applications of Evolutionary Computation (Lecture Notes in Computer Science), Giovanni Squillero and Kevin Sim (Eds.), Vol. 10200. Springer, Amsterdam, 35--48.

[73]

Fan Wu et al. 2015. Deep Parameter Optimisation. In GECCO '15, Sara Silva et al. (Eds.). ACM, Madrid, 1375--1382.

Digital Library

[74]

Tianyi Zhang and Miryung Kim. 2017. Automated Transplantation and Differential Testing for Clones. In Proceedings of the 39th International Conference on Software Engineering. IEEE Press, Buenos Aires, Argentina, 665--676.

Digital Library

Cited By

Sobania DBriesch MRöchner PRothlauf F(2023)MTGP: Combining Metamorphic Testing and Genetic ProgrammingGenetic Programming10.1007/978-3-031-29573-7_21(324-338)Online publication date: 29-Mar-2023
https://doi.org/10.1007/978-3-031-29573-7_21
Langdon WKrauss O(2021)Genetic Improvement of Data for Maths FunctionsACM Transactions on Evolutionary Learning and Optimization10.1145/34610161:2(1-30)Online publication date: 29-Jul-2021
https://dl.acm.org/doi/10.1145/3461016

Index Terms

Evolving sqrt into 1/x via software data maintenance
1. Software and its engineering
  1. Software creation and management
    1. Search-based software engineering

Recommendations

Genetic Improvement of Data for Maths Functions

We use continuous optimisation and manual code changes to evolve up to 1024 Newton-Raphson numerical values embedded in an open source GNU C library glibc square root sqrt to implement a double precision cube root routine cbrt, binary logarithm log2 and ...
Genetic improvement of data gives binary logarithm from sqrt
GECCO '19: Proceedings of the Genetic and Evolutionary Computation Conference Companion

Automated search in the form of the Covariance Matrix Adaptation Evolution Strategy (CMA-ES), plus manual code changes, transforms 512 Newton-Raphson floating point start numbers from an open source GNU C library, glibc, table driven square root ...
Energy Optimisation via Genetic Improvement: A SBSE technique for a new era in Software Development
GECCO Companion '15: Proceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation

The discipline of Software Engineering has arisen during a time in which developers rarely concerned themselves with the energy efficiency of their software. Due to the growth in both mobile devices and large server clusters this period is undoubtedly ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '20: Proceedings of the 2020 Genetic and Evolutionary Computation Conference Companion

July 2020

1982 pages

ISBN:9781450371278

DOI:10.1145/3377929

General Chair:
Carlos Artemio Coello Coello
CINVESTAV-IPN

Copyright © 2020 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 July 2020

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO '20

Sponsor:

SIGEVO

GECCO '20: Genetic and Evolutionary Computation Conference

July 8 - 12, 2020

Cancún, Mexico

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
56
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Sobania DBriesch MRöchner PRothlauf F(2023)MTGP: Combining Metamorphic Testing and Genetic ProgrammingGenetic Programming10.1007/978-3-031-29573-7_21(324-338)Online publication date: 29-Mar-2023
https://doi.org/10.1007/978-3-031-29573-7_21
Langdon WKrauss O(2021)Genetic Improvement of Data for Maths FunctionsACM Transactions on Evolutionary Learning and Optimization10.1145/34610161:2(1-30)Online publication date: 29-Jul-2021
https://dl.acm.org/doi/10.1145/3461016

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents