Arrays flags or new Array class

[dvd101x]

While doing benchmarks I noted that creating a matrix is expensive due to validation of rectangularity.

In some cases an array has already a known size or is know to be rectangular and maybe could be checked for size and validated for rectangularity multiple times before being converted to a Matrix.

Some ways to prevent this are:

• Add flags to the array for size and rectangularity to avoid multiple checks. (With caution due to the possibility of mutation)
• Add a skip validation flag for the matrix creation. (There is a hack sprinkled in the codebase to avoid validation)
• Make a new class that tracks the size, if it's validated, if it is rectangular, jagged or heterogeneous and gets a free pass when converted to a matrix and is rectangular and throws an error if it is heterogeneous or jagged without even starting a validation for rectangularity again.

I see the cool proposal for a notation for arrays at #3568 and even though I was waiting to express this thought until I have a better grasp on operations on jagged arrays and implementing a flat matrix (from stdlib or otherwise) maybe it's better to express this idea early.

[gwhitney]

Your news doesn't surprise me. Seems as though matrices end up being converted back and forth to arrays in multiple places in the code, and I guess every round trip revalidates. Maybe a DimensionedArray derived class of the built-in Array would help and be safest? Just speculating.

[dvd101x]

Thanks, just a clarification, the main offender is deep cloning the array, then validating and lastly checking the size. I will include a quick demonstration.

[gwhitney]

Right ok so the most important thing is to avoid unnecessary round-trips (in either direction) between Matrix and Array, of which there are many in the code. Your Algo15 definitely helps with that.

[josdejong]

Thanks for bringing this up David. Makes sense that that validation takes time. Similar to passing datatype in case it contains homogeneous data, we can probably add a new argument to pass a flag denoting that it is known to be rectangular and does not need size validation.

Another idea could be to leave the validation of individual cells in the Matrix to not be an array out, I think that is the most expensive part.

[gwhitney]

I think we are mostly agreeing, all I am saying is try to find a packaging for the return value in which any tags/derived info will not need to be deleted.

[dvd101x]

Yes I think we are in agreement. I was enumerating alternatives, not specifically to address your comments or my preferences. Sorry for the confusion.

[josdejong]

We indeed do need these tags like isRectangular, isHomogeneous, etc. I think attaching this meta information to Arrays will be problematic though (and if we do, probably better to only add one very unique key like array.__mathjs__ = { isRectangular: true, isHomogeneous: true, ...}. I think the main problem is that after you've attached the meta data, a user may alter the contents of the array, and then the meta data is invalid.

So instead, I think it is better to have a wrapper class around Array that keeps track of this meta information and updates it when changes are made via the methods of the class. This is exactly the idea of the DenseMatrix class 😉. I think we can extend this class with more meta data.

Making this class a derived class of Array may partially work: you can overwrite all methods to trigger updating the meta data when needed. But I think you can't get triggers when a nested array is updated by the user. Unless maybe when using a Proxy on top of Array or so?

[gwhitney]

Hmm, I think you are right: taggedArray[2] = 0.7 has to have special behavior (if the type of the array was bigint, now it's "mixed" or something like that). And it's not clear to me that there's any way to implement that behavior with just a wrapper class. So it seems like it would need to be a Proxy-ed array that intercepts all property accesses and does the correct thing. And now there will be the question of whether the performance penalty of this Proxy undercuts the performance advantage we were trying to achieve (and even whether it's worth the effort to implement the whole Proxy to do the benchmarking).

I can think of one potential intermediate solution that potentially has lower performance penalty: pass back a frozen tagged Array. Then you have to call our clone method, which removes the tags, to get a modifiable copy. In other words, you just forget everything you know about an Array when you "release" it to be modified, so that it will be entirely re-checked from scratch if it then comes back into mathjs. Then in the docs we could have a "Why are the Arrays I get from mathjs not modfiable?" section, where we explain the performance hit that comes from re-tagging Arrays. We could in addition provide methods or functions to update entries maintaining the correctness of the tags, so that you can also avoid the re-check by using only the mathjs-provided ways of changing an Array.

[dvd101x]

Something actionable is think about the possibility on extending DenseMatrix to include non rectangular arrays and a fast creation (skipping sizing and validation). Then use it for functions that internal expect arrays with multiple steps and at the end return an array without tags.

It all depends on what is the boundary of DenseMatirx. In numpy for example matrices (considered for deprecation) are only 2D and arrays (numpy arrays) are rectangular arrays of N dims.