Concatenating Approach: Improving the Performance of Data Structure Implementation
Subject Areas :
1 - ZAnjan University
2 - Malek Ashtar University of Technology
Keywords: Programming Language, , Data Structure Handling, , High-Level Abstraction, , Concatenating, ,
Abstract :
Data structures are important parts of the programs. Most programs use a variety of data structures and quality of data structures excessively affects the quality of the applications. In current programming languages, they are defined by storing a reference to the data element in the data structure node. Some shortcomings of the current approach are limits in the performance of a data structure and poor mechanisms to handle key and hash attributes. These issues can be observed in the Java programming language which that dictates the programmer to use references to data element from the node. Clearly it is not an implementation mistake. It is a consequence of the Java paradigm which is common in almost all object-oriented programming languages. This paper introduces a new mechanism called access method, to implement a data structure efficiently which is based on the concatenating approach to data structure handling. In the concatenating approach, one memory block stores both the data element and the data structure node. According to the obtained results, the number of lines in the access method is reduced and reusability is increased. It builds data structure efficiently. Also it provides suitable mechanisms to handle key and hash attributes. Performance, simplicity, reusability and flexibility are the major features of the proposed approach.
[1] J. H. Drew, D. L. Evans, A. G. Glen, and L. M. Leemis, “Data Structures and Simple Algorithms,” in Computational Probability, Springer, 2017, pp. 89–109.
[2] I. Haller, A. Slowinska, and H. Bos, “Scalable data structure detection and classification for C/C++ binaries,” Empir. Softw. Eng., vol. 21, no. 3, pp. 778–810, 2016.
[3] M. Basios, L. Li, F. Wu, L. Kanthan, and E. T. Barr, “Optimising Darwinian Data Structures on Google Guava,” in International Symposium on Search Based Software Engineering, 2017, pp. 161–167.
[4] M. Basios, L. Li, F. Wu, L. Kanthan, D. Lawrence, and E. Barr, “Darwinian Data Structure Selection,” arXiv Prepr. arXiv1706.03232, 2017.
[5] T. H. CORMEN, C. E. LEISERSON, R. L. RIVEST, and C. STEIN, Introduction to Algorithms 3rd Edition. MIT press, 2009.
[6] C. Van Reeuwijk and H. J. Sips, “Adding tuples to Java: A study in lightweight data structures,” in Proceedings of the Concurrency Computation Practice and Experience, 2005, vol. 17, no. 5–6 SPEC. ISS., pp. 423–438.
[7] M. Sakkinen, “Disciplined Inheritance,” in ECOOP 1989: European Conference on Object-Oriented Programming, 1989, pp. 39–57.
[8] Y. Zhang, M. C. Loring, G. Salvaneschi, B. Liskov, and A. C. Myers, “Lightweight, flexible object-oriented generics,” in ACM SIGPLAN Notices, 2015, vol. 50, no. 6, pp. 436–445.
[9] S. Lindell, “A normal form for first-order logic over doubly-linked data structures,” Int. J. Found. Comput. Sci., vol. 19, no. 1, pp. 205–217, 2008.
[10] C. Loncaric, E. Torlak, and M. D. Ernst, “Fast synthesis of fast collections,” ACM SIGPLAN Not., vol. 51, no. 6, pp. 355–368, 2016.
[11] Y. Smaragdakis and D. S. Batory, “DiSTiL: A transformation library for data structures,” in Proceedings of USENIX Conference on Domain-Specific Languages, 1997, no. October, p. 257270.
[12] Java.net, “JMH Test,” 2017. [Online]. Available: http://openjdk.java.net/projects/code-tools/jmh/.
[13] N. Khammassi and J.-C. Le Lann, “A high-level programming model to ease pipeline parallelism expression on shared memory multicore architectures,” Simul. Ser., vol. 46, no. 5, pp. 63–70, 2014.
[14] Y. Smaragdakis, “Technical Perspective High-Level Data Structures,” Commun. ACM, vol. 55, no. 12, p. 2380656, 2012.
[15] S. J. Rosenschein and S. M. Katz, “Selection of representations for data structures,” in Proceedings of the 1977 symposium on Artificial intelligence and programming languages., 1977, pp. 147–154.
[16] S. Katz and R. Zimmerman, “An advisory system for developing data representations,” in Proceedings of the 7th international joint conference on Artificial intelligence, 1981, pp. 1030–1036.
[17] E. Schonberg, J. T. Schwartz, and M. Sharir., “An automatic technique for selection of data representations in setl programs,” ACM Trans. Program. Lang. Syst., vol. 3, no. 2, pp. 126–143, 1981.
[18] E. Schonberg, J. T. Schwartz, and M. Sharir., “Automatic data structure selection in setl.,” in Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, 1979, pp. 197–210.
[19] J. R. Low, “Automatic data structure selection: an example and overview,” Commun. ACM, vol. 21, no. 5, pp. 376–385, 1978.
