Number lists in Dart: in-depth explanation

Hello everybody,

I’m Ilia, and I’m a software developer.

I created ml_algo and ml_linalg libraries in Dart programming language several years ago. I’d like to share my experience with the number lists in the Dart programming language, which I gained during the development of the mentioned libraries.

The Numeric computation article from the Dart dev team helped me in the development — I take a lot of information on the number lists from there.

First, let’s take a look at the types of lists in the standard Dart libraries:

Regular list, which is represented by List class
Typed lists (dart:typed_data library): — Lists of integers: Int8List, Int16List, Int32List, Int64List — Lists of doubles: Float32List, Float64List
SIMD lists (dart:typed_data library): — Lists of integers: Int32x4List — Lists of doubles: Float32x4List, Float64x2List

`List` class

The very basic list, nothing special at all. We can store data of any type in such lists:

It’s better to call such a list an object list. Why object? It’s because everything in Dart is an instance of the Object class. Even numbers: when we use a number in our code, Dart creates an object for the number.

Because of that, the list of objects can be represented as a sequence of CPU pointers to the corresponding objects:

It’s quite logical that the size of an element, in this case, is equal to the size of the CPU pointer. If the target architecture requires 32 bits to encode the address of an object in the memory, the list’s element size is 32 bits as well.

Let’s compare object lists of double and integer values:

Let’s apply a simple mathematical operation to every element of the lists and measure the performance:

The benchmark results for the integer list:

The benchmark results for the list of double values:

Mathematically, the values of the lists are the same, but benchmark results are different.

What is the reason for that?

Dart treats integer and double numbers in the object list differently.

It appeared that Dart doesn’t create objects for integers if they are less than the CPU pointer size, but it does create objects for all the double values.

As we saw, avoiding creating the object for small integers saves a lot of time: the list of small integers is an unbeatable winner.

Let’s now define integer and double lists with bigger values:

The element size for the list of integer values no longer fits in pointer size, a value 1e19 is bigger than a memory address on the target machine.

Now the performance measurement results are almost the same for both lists:

Key takeaways for the Object List:

Dart doesn’t create objects for small integers (less than the CPU pointer size)
Dart creates objects for all integers which are greater than the CPU pointer size and for all values of all other types

The main disadvantages of the Object List are:

we need extra memory since we need to allocate an object for each element
every time we need to manipulate a value, we should find the corresponding object in the memory by the CPU pointer and “unbox” the object; it’s time-consuming

Fortunately, there is another kind of list in Dart which doesn’t have such disadvantages.

Typed lists

Another kind of Dart list is a *typed list. *These lists differ from the previous ones: typed lists can store only numeric data unlike them. Dart doesn’t create objects for elements of the list. Instead, it stores numbers directly in the field:

Remember, Dart doesn’t create objects for integers in the case of Object Lists. Let’s compare the performance of the regular list and the typed integer list:

Let’s apply the same operation to measure the performance of the lists:

It’s strange, but the object list beats the typed integer list. Why did this happen? It appeared that Dart uses a technique called “tagging” and “untagging”.

To not allocate memory for objects to store small integers (they don’t need an object, they are smaller than the CPU pointer), Dart marks them by doubling their value. By doing so, Dart ensures that the low bit of the integer number is always zero:

So, if the low bit is zero, Dart understands that it’s a small integer number.

Other values (medium to big integers, double values, etc.) always have 1 at their low bit since they are objects and are represented in the memory by CPU pointers. CPU pointer ends with 0, so Dart just adds 1: therefore, we always have 1 at the low bit for objects:

Dart shifts the value to get the original value (since the value is doubled) to perform operations with small integers. This operation is called “untagging”:

Object lists don’t need tagging and untagging, unlike typed ones, which is why sometimes Object lists with small integers can be faster than the typed ones. It’s said in the Numeric computation article from the Dart dev team:

If list is an object list, no smi* tagging or untagging occurs. Note that some integer operations—for example, addition—can work on tagged smi values while others—for example, multiplication—must first untag the smi values. If list is a typed list, the loaded value must be tagged and then, before the result is stored, it must be untagged. Furthermore, the index (i) into a typed list is untagged and then tagged.

*smi — small integer

Things are easier with float-typed lists. They are always faster than the object lists of double values:

Benchmark results:

Dart doesn’t have special techniques for doubles like tagging and untagging, it always creates objects for the values and stores only CPU pointers for them in the field. The only exception is typed lists — Dart stores double values right in the field without creating objects for them, which is why typed lists in the case of double values are faster than the object lists.

Key takeaways for the Typed List:

Sometimes integer object lists can be faster than typed ones because typed lists utilize “tagging” and “untagging” techniques
Float-typed lists are always faster than object lists with double values
Typed lists are always winners in terms of memory usage: they don’t allocate objects, and the programmer can leverage the list element size by utilizing specific list types like Int8List, Float32List etc.

SIMD lists

SIMD (single instruction, multiple data) is a completely different type of typed list, it deserves a separate article — stay tuned to get notified on new posts in my medium blog.

That’s pretty much it!

I hope you enjoyed the journey with Dart numeric lists.

Stay safe and do a benchmarking!

You can find the source code of all the benchmarks in this repo.

All the measurements were made on Mackbook Pro 2019 (2.6 GHz 6-Core Intel Core i7)