As many other modern programming languages, Pharo spreads its applications into computationally demanding fields such as machine learning, big data, cryptocurrency, etc. This raises a need for fast numerical computation libraries. In this work, we propose to speed up the low-level computations by calling the routines from highly optimized external libraries, e.g., LAPACK or BLAS through the foreign function interface (FFI). As a proof of concept, we build a prototype implementation of linear regression based on the DGELSD routine of LAPACK. Using three benchmark datasets of diferent sizes, we compare the execution time of our algorithm agains pure Pharo implementation and scikit-learn - a popular Python library for machine learning. We show that LAPACK&Pharo is up to 2103 times faster than pure Pharo. We also show that scikit-learn is 8-5 times faster than our prototype, depending on the size of the data. Finally, we demonstrate that pure Pharo is up to 15 times faster than the equivalent implementation in pure Python. Those findings can lay the foundation for the future work in building fast numerical libraries for Pharo and further using them in higher-level libraries such as pharo-ai.
Pharo (https://pharo.org/) is an open-source dynamically-typed reflective, object-oriented
programming language inspired by Smalltalk [
In this paper, we propose to speed up the numerical computations in Pharo by calling lowlewel routines from the highly optimized external libraries such as LAPACK or BLAS. As a proof of concept, we propose a prototype implementation of the linear regression algorithm in Pharo based on the DGELSD routine of LAPACK.5 We benchmark our algorithm against both an alternative implementation in pure Pharo and scikit-learn — a widely used Python library for machine learning.
The Pharo & LAPACK implementation is 1820 times faster than pure Pharo on a small-size dataset (200K rows) and 2103 times faster on a medium-size dataset (1M rows). This serves as a proof of concept that the speed of numerical algorithms, and more specifically machine learning in Pharo can be significantly improved by calling highly optimized external libraries through FFI. We also show that scikit-learn is still 8-5 times faster than our prototype implementation in Pharo (depending on the size of data), which might be caused by data preprocessing and other optimizations. We propose to further explore this diference in future work. Finally, we show that pure Pharo implementation of linear regression is about 5-15 times faster than the equivalent implementation in pure Python. This can be explained by the just-in-time compilation performed by Pharo virtual machine.
The rest of this paper is structured in the following way. In Section 2, we discuss the possibility of implementing a machine learning library in Pharo and the challenges associated with it. In Section 4, we briefly explain the foreign function interface (FFI) and how it can be used to call C and Fortran routines from Pharo. In Section 3, we explain diferent implementations of the linear regression algorithm that we have selected for benchmarking.
Modern machine learning is resource demanding. It requires fast algorithms capable of processing large volumes of data. Many algorithms in machine learning are based on matrix algebra and numerical optimization. This raises the need for fast libraries that implement the basic algebraic operations such as matrix-vector multiplication and also highly optimized algebraic algorithms as singular value decomposition, Cholesky decomposition, eigenvector and eigenvalues calculation, etc. for diferent types of matrices, i.e., symmetric, orthogonal, hermitian, etc.
In Pharo, there is PolyMath — a library for numerical computations and scientific computing. With its 60 packages and 903 green tests6 PolyMath provides a wide range of algorithms that cover various aspects of mathematics: diferential equations, complex numbers, fuzzy algorithms, etc. It also provides matrix algebra, statistical distributions, and numerical optimization methods that can be particularly useful for machine learning. That being said, some algorithms that are 5All the code, the datasets, and the instructions on how to reproduce our experiment are available at https: //anonymous.4open.science/r/lapack-experiment-55FB. 6Measured at https://github.com/PolyMathOrg/PolyMath on June 1, 2022. Python
LAPACK
SciPy scikit-learn Pharo
LAPACK
PolyMath pharo-ai implemented in PolyMath are very slow, compared to the similar numerical libraries in other languages. For example, as we will see in Section 6, the linear regression implementation that is based on the singular value decomposition (SVD) provided by PolyMath takes almost 5 hours to converge on a dataset with 5,000 rows and 5 columns.
There is also an ongoing efort in Pharo community to implement the tools for data science, machine learning, artificial intelligence, data mining, etc. 7 One such library is pharo-ai — a collection of diferent machine learning algorithms implemented in Pharo: linear and logistic regression, support vector machines, K-means, naive bayes, etc. It is inspired by scikit-learn, a similar machine learning library in Python. scikit-learn is a popular library that has many industrial applications. Many of its algorithms are very fast because internally scikit-learn depends on a mathematical library scipy, which in turn depends on LAPACK — an eficient low-level library implemented in Fortran that provides fast algorithms for linear algebra.
We propose to improve the speed of PolyMath and pharo-ai by calling LAPACK routines through foreign function interface — a technique for calling external functions which is already implemented by Pharo (see Section 4). In Figure 1, we show how LAPACK is used by scikitlearn in Python and propose a way how it could be used by pharo-ai library. In this scheme, PolyMath implements various high-level mathematical algorithms by delegating low-level algebraic operations to LAPACK. Then pharo-ai simply depends on PolyMath to implement fast machine learning algorithms.
As a proof of concept, in this paper we present a prototype implementation of linear regression
in Pharo based on LAPACK. We benchmark the training time of our model and show that it is
almost 500 times faster than the pure Pharo implementation.
7For the non-extensive list of diferent machine learning libraries and tools in Pharo, see https://github.com/
pharo-ai/awesome-pharo-ml.
3. Linear regression and How it is Implemented
Linear Regression is a machine learning algorithms that models a relationship between the
input matrix and the output vector [
⎛ 11 . . . 1 ⎞ ⎛ 1 ⎞ ⎛ 0⎞ = ⎜⎝ ... . . . ... ⎟⎠ ; = ⎜⎝ ... ⎟⎠ ; = ⎜⎝ ... ⎟⎠ 1 . . .
The task of linear regression is to find a set of parameters = ( 0, . . . , ) such that the predictions ˆ = ℎ () are as close as possible to the real output values . The function ℎ (also known as hypothesis function) is defined as: ℎ () = 0 + 11 + · · · +
This is an optimization problem: we need to minimize the objective function that is often defined as mean squared error: ( ) =
1 ∑︁( − ℎ (:))2 =1
We have selected linear regression for benchmarking because: (1) it is one of the most well known and commonly used machine learning algorithms; (2) it can be solved by finding a minimum norm solution to the linear least squares problem — an algorithm of linear algebra that is implemented in LAPACK.
Gradient Descent Solution Gradient descent is the iterative numerical optimization technique that is used by many machine learning algorithms, including linear regression.
It is based on the fact that derivative of the function in a given point is positive if the function is increasing and negative if it is decreasing. This means that by subtracting the value of derivative ( ), scaled by a parameter (called the learning rate), from the current value of parameter , we decrease the cost ( ): () = () − ( ) Least Squares Solution Alternatively, the problem of linear regression can be expressed in terms of linear least squares. In this case, = is viewed as a system of linear equation where is the unknown. Unless all points of the dataset lie on a straight line, this system has no solutions. However, it is possible to find the closest approximation to the solution by solving the system = ˆ where ˆ is the orthogonal projection of onto the columnspace of (thus the distance between true output and predicted output ˆ is the smallest). This is the same as ifnding the optimal parameters ˆ by minimizing the norm:
ˆ = argmin ⃒⃒ ⃒⃒ − ⃒⃒ ⃒⃒ 2 In this work, we compare the following implementations of linear regression: 1. Iterative gradient descent implementation in pure Pharo and pure Python. 2. Least squares implementation in Pharo (our prototype) and Python (scikit-learn) that are both based on a routine from LAPACK library.
As many modern programming languages, Pharo supports the Foreign Function Interface (FFI) —
the mechanism that allows the call of routines from another programming language [
The method fiCall:library: is understood by every object in Pharo. It accepts two arguments which specify the shared library and the signature of a method that should be called. The value returned by this method will be the same as the return value of the external function that is being called.
Calling LAPACK routine The Linear Algebra PACKage (LAPACK) is a Fortran library that provides routines for solving systems of simultaneous linear equations, least-squares solutions of linear systems of equations, eigenvalue problems, and singular value problems, matrix factorizations, etc. In this work, we use one specific routine of LAPACK that computes the minimum-norm solution to a real linear least squares problem — DGELSD.8 It accepts as input matrix and vector and finds the solution vector ˆ which minimizes the norm || − ||2 (see Section 3).
Research Questions In our study, we answer the following research questions:
• RQ.1 - Measuring LAPACK speedup. How much time improvement can we achieve by
calling LAPACK from Pharo?
• RQ.2 - Comparing to scikit-learn. How does Pharo & LAPACK implementation compare to
the one provided by scikit-learn?
• RQ.3 - Comparing pure Pharo with Python. How does pure Pharo implementation of linear
regression compare to equivalent pure Python implementation?
8https://www.netlib.org/lapack/explore-html/d7/d3b/group__double_g_esolve_
ga94bd4a63a6dacf523e25f617719f752.html
Datasets for benchmarking We generated three datasets of diferent sizes using the make_regression()
method of scikit-learn with a random linear regression model with a fixed seed. The sizes of
those datasets can be seen in Table 1. The number of columns was fixed at 20 and the number
of rows was gradually increased. We did this because the height (number of rows) and width
(number of columns) of a dataset have diferent efect on the training time [
The first 19 columns represent the input matrix . They contain floating point numbers that are normally distributed around 0 with standard deviation 1. The last column of each dataset represents the output vector generated by applying a non-biased linear regression model with gaussian noise. Measuring the execution time In this study, we only measure that time that it takes to train the linear regression model as it is generally the most consuming part of the machine learning workflow. In Pharo, we measure time using the timeToRun method: time := [ "... some code..." ] timeToRun.
In Python, we use the time library: import t i m e s t a r t _ t i m e = t i m e . t i m e ( ) # . . . some c o d e . . . t i m e = t i m e . t i m e ( ) − s t a r t . t i m e ( )
In this section, we answer the research questions and discuss the results of our experiments. The benchmarks were run in a MacBook Pro 2015 with a Intel i7 processor of 4 cores and 2.2G Hz and 16 GB of RAM memory. The operating system is Monterrey v12.4. To run the benchmarks, we closed all the applications that could be closed. In addition, we disconnected the Internet and did not use the computer while experiment was in progress. The computer was plugged into the charger for the duration of the experiment.
To answer the first research question, we measured the execution time of two implementations of linear regression on the three datasets that were discussed in Section 5. The first implementation was implemented in pure Pharo (no external libraries) and based on gradient descent. The second implementation was based on least squares, implemented by calling the DGELSD LAPACK routine from Pharo. As can be seen in Table 2, the LAPACK implementation was 1820 times faster on small dataset and 2103 times faster on medium dataset. We could not measure the execution time of pure Pharo implementation on large dataset because it was too long and we had to stop it after 5 hours. The LAPACK implementation took about 15 seconds to converge on the same dataset. Summary: Calling LAPACK routines from Pharo can provide a significant speedup. The linear regression implemented with Pharo&LAPACK is 462 times faster than the pure Pharo implementation when measured on small dataset and 284 times faster on medium dataset.
We compared the execution time of LAPACK-based implementation of linear regression in Pharo to the one provided by LinearRegression class in scikit-learn, which is also based on the DGELSD routine of LAPACK. As can be seen in Table 3, scikit-learn is 8 times faster than our implementation on small dataset, 8 times faster on medium dataset, and 5 times faster on large dataset. Considering that scikit-learn is well designed library with many industrial users and our implementation is a prototype, we hypothesize that this diference is due to various optimizations that are performed in scikit-learn. For example, it uses a highly optimized data structure NumPy9. A further study is needed to explain this phenomenon. Summary: scikit-learn implementation is 8 times faster than our prototype implementation in Pharo. It is 5 times faster on a large dataset. RQ.3 - Comparing pure Pharo with pure Python We also compare pure Pharo and pure Python implementations of linear regression based on gradient descent. As can be seen in Table 4, Pharo is 5 times faster than Python on small dataset and 15 times faster on medium dataset. We could not measure the execution time on large dataset, because in both cases it was too long and we had to stop the experiment. Summary: The implementation of gradient descent-based linear regression in pure Pharo (no external libraries) is about 5-15 times faster than the equivalent implementation in pure Python, depending on the size of the dataset.
We consider the four types of validity threats that were presented by Wohlin et al., [
External Validity • In this work, we demonstrated how the training time of linear regression can be reduced using LAPACK. The same technique can be used for many other machine learning algorithms: logistic regression, neural networks, etc. Nonetheless, there are also algorithms that can not benefit from it because, unlike linear regression, they do not require heavy matrix-vector calculations. Some examples include k-means or k-nearest neighbours. Those algorithms can still be boosted with optimized C code called through FFI, but this requires a separate study.
Over the years, Pharo has been successfully applied in various domains of scientific
computing and numerical optimization. Many of those applications use the algorithms provided by
PolyMath [
In this work, we benchmark our prototype implementation of linear regression against
scikitlearn — a Python machine learning library that is widely used in both research and industry [
To the best of our knowledge, this is the first attempt to implement a fast numerical library in Pharo by calling an external library such as LAPACK. It is also the first study that benchmarks the machine learning algorithms in Pharo.
In this work we presented a proof of concept that demonstrates how numerical computations in Pharo can be boosted by calling the routines highly optimized external libraries through FFI. We built a prototype implementation of linear regression algorithm in Pharo based on the DGELSD routine from LAPACK. We measured the execution time on three benchmark datasets and compared it to the time that is needed to train the analogous models in scikit-learn and in pure Pharo. We show that LAPACK-based implementation is up to 2103 times faster than pure Pharo but still 8-5 times slower than scikit-learn implementation, which also uses LAPACK underneeth. We also show that pure Pharo implementation is up to 15 times faster than the equivalent model implemented in pure Python. This interesting finding can be explained by just-in-time compilation that is performed by Pharo virtual machine. 10. Acknowledgements We are grateful to Vincent Aranega and Guillermo Polito for their valuable advice and explanations of just-in-time compilation in Pharo. Oleksandr Zaitsev also thanks Arolla10 software company for financing his work during this study.