Maple, C and Assembly Language ? Performance Comparison
Milorad Pop-To?ić, Igor Skender Department of Computer Engineering School of Electrical Engineering, University of Belgrade, Serbia poptosic@gmail.com, igor.skender@gmail.com
Abstract
We show how to utilize Maple external calling mechanism to speed up function execution by coding them in C and assembly language. Techniques were demonstrated on Jones? algorithm for finding the n-th prime number.
Introduction
In this article, it will be shown how to utilize Maple external calling mechanism in order to solve real problems faster, by calling external functions written in C and assembly language. Maple define_external function was used to call routines written in C and assembly language MASM, from DLL libraries [3,4]. These techniques were demonstrated on the example of Jones? algorithm, an algorithm for finding the n-th prime number [1, 2]. Furthermore, we made measurements and comparison of execution time for different implementations of the algorithm: assembly language, C language, and Maple procedures.
Jones? algorithm
Jones? algorithm for finding the n-th prime number states [1, 2]: Let be the n-th prime number. Formula , which generates the n-th prime number for given n, is given as:
where is a function that returns the remainder of division of number a by number b, where and is a function defined as:
Function returns the array of prime numbers There is a function in Maple, ithprime(n), which returns values of from a database. Our goal is to illustrate what can be achieved by connecting Maple to C and assembly language, on the example of Jones? algorithm for finding the function .
The code for the procedure in Maple for finding function using Jones? algorithm is given below:
The code in C for finding function using Jones? algorithm is given below:
Jones.c
#define M(x,y) ((x)>(y) ? ((x)-(y)):(0)) int i,j,k,n,m,p,f,s; int Jones(int n) { for ( m=n*n, s=i=1; i<=m; i++) { for ( p=0, j=1; j<=i; j++) { for ( f=k=1; k<j; k++) { f=f*k*k; f%=j; } p+=f; } s+=M(1, M(p,n)); } return s; }
In order to call this code from within Maple it should, first, be compiled into a DLL (Dynamic Linking Library). A compiler from Microsoft Visual Studio .NET was chosen at this place. We compile the code by issuing the following command:
> cl.exe -LD -Gy -Gz JonesC.c -link /export:Jones
It is essential to include keyword /export: followed by the name of the function to be exported and used from within Maple. Note that any other C compiler can be used here as long as it produces a DLL with stdcall calling convention, and exports symbol Jones.From this point onwards, compiled DLL library JonesC.dll, is connected to Maple by using define_external function, as follows:
It should be noted that Maple can also call functions from UNIX .so libraries, which have similar function as DLL libraries in Windows.From this point onwards, the call JonesC() from within Maple appears to be exactly the same as a call to a built-in Maple function, although the function Jones from the DLL library gets called.
The procedure in assembly language for finding function using Jones? algorithm is given below [7]:
JonesASM.asm
.586 .model flat, stdcall .code LibMain proc h:DWORD, r:DWORD, u:DWORD mov eax, 1 ret LibMain Endp ; s=ax j=bx k=cx p=si i=di Jones proc n:DWORD LOCAL m:DWORD LOCAL s:DWORD push ebx push ecx push edx mov eax, n mul eax mov m, eax mov eax, 1 mov s, eax mov edi, eax loop1: cmp edi, m jg l0 mov ebx, 1 xor esi, esi loop2: cmp ebx, edi jg l1 mov eax, 1 mov ecx, eax loop3: cmp ecx, ebx jge l2 mul ecx mul ecx div ebx mov eax, edx inc ecx jmp loop3 l2: add esi, eax inc ebx jmp loop2 l1: cmp esi, n jg skip inc s skip: inc edi jmp loop1 l0: pop edx pop ecx pop ebx mov eax, s ret Jones endp End LibMain
Apart form this file, one more is needed. It lists functions, which are to be exported from the DLL, which is, in this case, the function Jones.
JonesASM.def
LIBRARY JonesASM EXPORTS Jones
Compiling and linking the DLL library, using MASM is done by issuing:
> \masm32\bin\ml /c /coff JonesASM.asm > \masm32\bin\Link /SUBSYSTEM:WINDOWS /DLL /DEF:JonesASM.def JonesASM.obj
Generated library JonesASM.dll is connected to Maple, as follows:
The three shown implementations of function Jones are called from within Maple by issuing the following commands, respectively:
Conclusion
Measurements and comparison of execution time for Jones? algorithm were made for all three presented implementations. To accomplish that, we used Maple time() function which returns total processor time used for executing expression. We used this function to calculate execution time for the three solutions, for , by issuing the following commands:
Based on measured values, the chart that shows execution times for three presented implementations was created.
It can be observed from this chart that C and assembly language solutions have considerably better performance, compared to Maple procedures. For procedure in Maple completes in about half an hour, while the same result, by applying C and assembly language solutions, is computed in the matter of seconds. The function that describes the time of execution of Maple procedures rises more sharply, so the differences are even more stressed for larger n. From what is said can be concluded that Maple procedures are rather slow solution for problems which contain large number of iterations, primarily because Maple code is interpreted, and not compiled. In such cases, it is much more efficient to program in C, or even assembly language.
The chart that follows shows the comparison of execution time for procedures written in assembly language and C. We can observe performance advantage of assembly language over C, which becomes more stressed, as n gets larger. For instance, assembly language implementation is about faster for . For that reason, putting in more effort in producing assembly language code is worthwhile, especially for loops repeating billion times or more. For loops repeating couple of million times, there is a minor difference between assembly language and C in terms of execution time, so it is simpler to write such a function in C.
Acknowledgement
This article is based on a semester work in course Practicum of Computer Tools in Mathematics, which is taught in the 5th semester of Computer Engineering program on the Faculty of Electrical Engineering, University of Belgrade. We wish to thank assistant professor Dr Branko Male?ević for acquainting us with this topic.
References
[1] James P. Jones: Formula for the nth prime number, Canadian Mathematical Bulletin 18, (1975), pp. 433--434.
[2] James P. Jones; Daihachiro Sato; Hideo Wada; Douglas Wiens: Diophantine Representation of the Set of Prime Numbers, The American Mathematical Monthly Vol. 83, No. 6 (Jun., 1976), pp. 449-464
[3] Aleksandrs Mihailovs: Writing DLL in Assembly Language for External Calling in Maple - Technical Report, Department of Mathematics, Tennessee Technological University TR No. 2004-5, July 2004, http://www.math.tntech.edu/techreports/TR_2004_5.pdf
[4] Aleksandrs Mihailovs: Writing DLL in Assembly Language for External Calling in Maple, http://www.maplesoft.com/applications/app_center_view.aspx?AID=1295&CID=9&SCID=63
[5] Michael Monagan: Programming in Maple: The Basics, Institut f?r Wissenschaftliches Rechnen ETH-Zentrum, CH-8092 Z?rich, Switzerland
[6] David A. Patterson, John L. Henessy: Computer Organization and Design: The Hardware/Software Interface, Morgan Kaufmann; 3rd edition
[7] Branko Male?ević: Examples for the special course ? Algorithms in C, (according to the MSc course of Department of Algebra and Mathematical Logic, Faculty of Mathematics, Belgrade 1995).
[8] Veljko Milutinović: The Best Method for Presentation of Research Results, Department of Computer Engineering, School of Electrical Engineering, University of Belgrade
Legal Notice: The copyright for this application is owned by the author(s). Neither Maplesoft nor the author are responsible for any errors contained within and are not liable for any damages resulting from the use of this material. This application is intended for non-commercial, non-profit use only. Contact the author for permission if you wish to use this application in for-profit activities.
