GitHub - gyrdym/ml_linalg: SIMD-based linear algebra and statistics for data science with dart

SIMD-based linear algebra and statistics for data science with Dart

TABLE OF CONTENTS

What is linear algebra
What is SIMD
Vectors
Matrices
- Matrix operations
vector_math and ml_linalg differences
Contacts

Linear algebra

In a few words, linear algebra is a branch of mathematics that works with vectors and matrices. Vectors and matrices are practical tools in real-life applications, such as machine learning algorithms. These significant mathematical entities are implemented in plenty of programming languages.

As Dart offers developers good instrumentation, e.g. highly optimized virtual machine, specific data types and rich out-of-the-box library, Dart-based implementation of vectors and matrices has to be quite performant.

Among numerous standard Dart tools, there are SIMD data types, and support of SIMD computational architecture served as inspiration for creating this library.

What is SIMD?

SIMD stands for Single instruction, multiple data - it's a computer architecture that allows to perform uniform mathematical operations in parallel on a list-like data structure. For instance, one has two arrays:

final a = [10, 20, 30, 40];
final b = [50, 60, 70, 80];

and one needs to add these arrays element-wise. Using the regular architecture this operation could be done in the following manner:

final c = List(4);

c[0] = a[0] + b[0]; // operation 1
c[1] = a[1] + b[1]; // operation 2
c[2] = a[2] + b[2]; // operation 3
c[3] = a[3] + b[3]; // operation 4

As you may have noticed, we need to do 4 operations one by one in a row using regular computational approach. But with help of SIMD architecture we may do one arithmetic operation on several operands in parallel, thus element-wise sum of two arrays can be done for just one step:

Vectors

A couple of words about the underlying architecture

The library contains two high performant vector classes based on Float32x4 and Float64x2 data types - Float32x4Vector and Float64x2Vector (the second one is generated from the source code of the first vector's implementation)

Most of element-wise operations in the first one are performed in four "threads" and in the second one - in two "threads".

Implementation of both classes is hidden from the library's users. You can create a Float32x4Vector or a Float64x2Vector instance via Vector factory (see examples below).

One can create Float32x4-based vectors the following way:

import 'package:ml_linalg/linalg.dart';

void main() {
  final vector = Vector.fromList([1.0, 2.0, 3.0, 4.0, 5.0], dtype: DType.float32);
}

or simply

import 'package:ml_linalg/linalg.dart';

void main() {
  final vector = Vector.fromList([1.0, 2.0, 3.0, 4.0, 5.0]);
}

since dtype is set to DType.float32 by default.

One can create Float64x2-based vectors the following way:

import 'package:ml_linalg/linalg.dart';

void main() {
  final vector = Vector.fromList([1.0, 2.0, 3.0, 4.0, 5.0], dtype: DType.float64);
}

Float32x4-based vectors are much faster than Float64x2-based ones, but Float64x2-based vectors are more precise since they use 64 bits to represent numbers in the memory versus 32 bits for Float32x4-based vectors.

Nevertheless, Float32x4 representation uses by default since usually 32 bits is enough for number precision, and along with that, this representation is more performant.

The vectors are immutable: once created, the vector cannot be changed. All the vector operations lead to creation of a new vector instance (of course, if the operation is supposed to return a Vector).

Both classes implement Iterable<double> interface, so it's possible to use them as regular iterable collections.

It's possible to use vector instances as keys for HashMap and similar data structures and to look up a value by the vector-key, since the hash code for equal vectors is the same:

import 'package:ml_linalg/vector.dart';

final map = HashMap<Vector, bool>();

map[Vector.fromList([1, 2, 3, 4, 5])] = true;

print(map[Vector.fromList([1, 2, 3, 4, 5])]); // true
print(Vector.fromList([1, 2, 3, 4, 5]).hashCode == Vector.fromList([1, 2, 3, 4, 5]).hashCode); // true

Vector benchmarks

To see the performance benefits provided by the library's vector classes, one may visit benchmark directory: one may find there a baseline benchmark - element-wise summation of two regular List instances and a benchmark of a similar operation, but performed on two Float32x4Vector instances on the same amount of elements and compare the timings:

Baseline benchmark (executed on Macbook Air mid 2017), 2 regular lists each with 10,000,000 elements:

Actual benchmark (executed on Macbook Air mid 2017), 2 vectors each with 10,000,000 elements:

It took 15 seconds to create a new regular list by summing the elements of two lists, and 0.7 second to sum two vectors - the difference is significant.