Dynaplex: inferring asymptotic runtime complexity of recursive programs.
Saved in:
| Title: | Dynaplex: inferring asymptotic runtime complexity of recursive programs. |
|---|---|
| Authors: | Ishimwe, Didier1, Nguyen, ThanhVu2, Nguyen, KimHao1 |
| Source: | ICSE: International Conference on Software Engineering. 2022, p61-64. 4p. |
| Subjects: | Recursive programming, Computer software, Logarithms, Polynomials, Mathematical symmetry |
| Abstract: | Automated runtime complexity analysis can help developers detect egregious performance issues. Existing runtime complexity analysis are often done for imperative programs using static analyses. In this demo paper, we demonstrate the implementation and usage of Dynaplex, a dynamic analysis tool that computes the asymptotic runtime complexity of recursive programs. Dynaplex infers recurrence relations from execution traces and solve them for a closed-form complexity bound. Experimental results show that Dynaplex can infer a wide range of complexity bounds (eg: logarithmic, polynomial, exponential, non-polynomial) with great precision (eg: O(nlog23) for karatsuba). A video demonstration of Dynaplex usage is available at https://youtu.be/t7dhwZ7fbVs [ABSTRACT FROM AUTHOR] |
| Copyright of ICSE: International Conference on Software Engineering is the property of Association for Computing Machinery and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
|
Full text is not displayed to guests.
Login for full access.
|
|
| FullText | Links: – Type: pdflink Text: Availability: 1 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 185195916 AccessLevel: 6 PubType: Conference PubTypeId: conference PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: Dynaplex: inferring asymptotic runtime complexity of recursive programs. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Ishimwe%2C+Didier%22">Ishimwe, Didier</searchLink><relatesTo>1</relatesTo><br /><searchLink fieldCode="AR" term="%22Nguyen%2C+ThanhVu%22">Nguyen, ThanhVu</searchLink><relatesTo>2</relatesTo><br /><searchLink fieldCode="AR" term="%22Nguyen%2C+KimHao%22">Nguyen, KimHao</searchLink><relatesTo>1</relatesTo> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22ICSE%3A+International+Conference+on+Software+Engineering%22">ICSE: International Conference on Software Engineering</searchLink>. 2022, p61-64. 4p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Recursive+programming%22">Recursive programming</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+software%22">Computer software</searchLink><br /><searchLink fieldCode="DE" term="%22Logarithms%22">Logarithms</searchLink><br /><searchLink fieldCode="DE" term="%22Polynomials%22">Polynomials</searchLink><br /><searchLink fieldCode="DE" term="%22Mathematical+symmetry%22">Mathematical symmetry</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: Automated runtime complexity analysis can help developers detect egregious performance issues. Existing runtime complexity analysis are often done for imperative programs using static analyses. In this demo paper, we demonstrate the implementation and usage of Dynaplex, a dynamic analysis tool that computes the asymptotic runtime complexity of recursive programs. Dynaplex infers recurrence relations from execution traces and solve them for a closed-form complexity bound. Experimental results show that Dynaplex can infer a wide range of complexity bounds (eg: logarithmic, polynomial, exponential, non-polynomial) with great precision (eg: O(nlog23) for karatsuba). A video demonstration of Dynaplex usage is available at https://youtu.be/t7dhwZ7fbVs [ABSTRACT FROM AUTHOR] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>Copyright of ICSE: International Conference on Software Engineering is the property of Association for Computing Machinery and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=185195916 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1145/3510454.3516853 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 4 StartPage: 61 Subjects: – SubjectFull: Recursive programming Type: general – SubjectFull: Computer software Type: general – SubjectFull: Logarithms Type: general – SubjectFull: Polynomials Type: general – SubjectFull: Mathematical symmetry Type: general Titles: – TitleFull: Dynaplex: inferring asymptotic runtime complexity of recursive programs. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Ishimwe, Didier – PersonEntity: Name: NameFull: Nguyen, ThanhVu – PersonEntity: Name: NameFull: Nguyen, KimHao IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 05 Text: 2022 Type: published Y: 2022 Titles: – TitleFull: ICSE: International Conference on Software Engineering Type: main |
| ResultId | 1 |
