API docs state that Arrays are fixed size, but they aren't

Yes, that makes good sense. It would be nice to have some knowledge of the internals since it would help with understanding the implications of various design decisions in terms of memory usage and performance.

> One would hope that CIQ uses something like a linked-list to make the operations efficient.

I don’t think it does. You can tell by creating a handful of Number arrays of different sizes (e.g. 1 element, 10 elements, 100 elements), running the app in the sim, and using the memory viewer.

You will find that there’s a certain amount of overhead for the array object itself (15 bytes). Each element takes exactly 5 bytes (1 bytes for type and 4 bytes for value).

Besides, implementing an array via linked-list would only be more time efficient for the use cases of adding and removing elements.

For other use cases, the performance would be a lot worse:

e.g. Read all items from 1000-element array:

(implemented as an actual array): this is basically a single memcpy of 5000 bytes

(implemented as a linked list): (follow pointer, copy 5 bytes) x 1000

e.g. Read item from arbitrary array index:

(implemented as an actual array): O(1) lookup

(implemented as a linked list): O(n) lookup (unless you also have a hash table to map array indices to individual items)

Clearly a linked-list would be a lot worse than an array in terms of space (memory) efficiency.

“from the existed underlying array.” => “from the existing underlying array”

> From my understanding it is by creating a new array of a different size then copying the items inside the array. Which makes them expensive operations.

This was my initial take.

However, regardless of how it’s actually implemented, the *API documentation* says that items can be added and removed to existing Arrays:

add(): Add an Object to the end of an Array.

remove(): Remove an Object from an Array.

If it’s the case that some (or all of these) operations are actually creating a new array with the previous contents copied over, it would be nice if this was documented, otherwise this does create an understandable confusion given that the summary says Array objects are fixed size.

I assume that regardless of the actual implementation, the array object itself is mutated by these methods, meaning that after calling add() or remove() on an instance of an Array, a new instance is not created but the same instance is updated, so that all references to the original instance will see the changes. Perhaps this is why the documentation simply says “Add an Object to the end of an array”, rather than “Copy the contents of the current array to a new array, with the new Object added at the end” — the latter text would give the false impression that a new instance is created, when it’s actually the existing instance that is updated. [Ofc, in order for the hypothetical “create new instance implementation” to work in practice, methods like add() would have to return an Array, but obviously they don’t]

If I’m understanding the situation properly, there are actually *two* concepts at play when we’re talking about the “array”.

- The Array object [instance of the Toybox.Lang.Array class]. This object presumably contains a pointer to the actual array on the heap (for lack of a better term, I’ll call this the ‘underlying array’.) When methods like Array.add() are called, a new underlying array is created, and existed items are copied from the old underlying array, which is then discarded.

- The underlying array on the heap: *It’s the underlying array which is fixed size, not the Array object.*

So it does seem that the literal text “*Array objects* are fixed size…” is wrong. Without any assumption or knowledge about the underlying implementation, it’s clear that an instance of the Array class is *not* fixed size. Array.size() can change after the Array is created.

Here’s the existing summary:

”Array objects are fixed size, numerically indexed, single dimensional, and take any Objects [including Arrays] as members. Array keys must be Numbers, but Array values may be any type of Object.”

Perhaps this could be rewritten as something like:

”Array objects are variable size, numerically indexed, single dimensional, and take any Objects [including Arrays] as members. Array keys must be Numbers, but Array values may be any type of Object.

The Array class is implemented with a fixed-size underlying array, which means that methods such as add() and addAll() are expensive: when elements are added, a new underlying array is created and existing elements are copied over from the existed underlying array. ”

Ops, I didn't quite understand your comment. Yes indeed it would be expensive if CIQ does it by creating new arrays each time. One would hope that CIQ uses something like a linked-list to make the operations efficient.