ULAB_HAS_FUNCTION_ITERATOR and ULAB_MAX_DIMS: code size and performance

[dhalbert]

My understanding of ulab internals is limited, but I have seen the macros that do nested loops over arrays with multiple dimensions, and then found ULAB_HAS_FUNCTION_ITERATOR, which defines the macros as not statically nested (e.g. BINARY_LOOP).

I thought that setting ULAB_HAS_FUNCTION_ITERATOR to 1 on boards where we are getting close to having space problems might help things, but I was worried about the performance effect. To my surprise, on an Adafruit Metro M4 (SAMD51), setting it caused the code to grow larger substantially:

• ULAB_HAS_FUNCTION_ITERATOR = 0: firmware size 488820 bytes
• ULAB_HAS_FUNCTION_ITERATOR = 1: firmware size 497320 bytes (+ 8500 bytes)

I don't know why this is. It may be a compilation optimization issue, but that's just a guess.

Assuming the size increase could be fixed, do you have an idea of what kind of performance difference I might expect to see? Have you done any benchmarking on this.

Another question I had was whether setting ULAB_HAS_FUNCTION_ITERATOR would allow ULAB_MAX_DIMS to be ignored altogether, because static nested loops would no longer be needed. Or does that not make sense? We have occasionally had users who wanted array support with more dimensions than the default.

Thanks!

[v923z]

My understanding of ulab internals is limited, but I have seen the macros that do nested loops over arrays with multiple dimensions, and then found ULAB_HAS_FUNCTION_ITERATOR, which defines the macros as not statically nested (e.g. BINARY_LOOP).

That's right.

I thought that setting ULAB_HAS_FUNCTION_ITERATOR to 1 on boards where we are getting close to having space problems might help things, but I was worried about the performance effect. To my surprise, on an Adafruit Metro M4 (SAMD51), setting it caused the code to grow larger substantially:

* `ULAB_HAS_FUNCTION_ITERATOR` = 0: firmware size 488820 bytes

* `ULAB_HAS_FUNCTION_ITERATOR` = 1: firmware size 497320 bytes (+ 8500 bytes)

Kwabema's observations from openmv, and mine were similar, at least, for 2D arrays. I noticed gains in flash space only for 3 and 4 dimensions.

The nested loops add something like 12-20 bytes per dimension, so it seems to me that setting up the function call for

micropython-ulab/code/ndarray.c

Line 170 in 38caf84

void ndarray_rewind_array(uint8_t ndim, uint8_t *array, size_t *shape, int32_t *strides, size_t *coords) {

actually adds more. I implemented the function iterator at the very beginning, and since there were no significant benefits, quite a few functions and methods do not even have the option. It would be trivial to add, though.

Assuming the size increase could be fixed, do you have an idea of what kind of performance difference I might expect to see? Have you done any benchmarking on this.

No, benchmarking on hardware is sorely missing. I would really like to have a standard set of test scripts that could be run on various hardware platforms, but my calls for this were not met with interest in the community. The closest that comes to this is in https://github.com/thiagofe/ulab_samples. If you think that this would be a useful exercise, let us discuss it further!

I just don't know how we could entice people to upload their results, or whether there are reasonable hardware emulators, so that we could get the results from virtual environments.

Another question I had was whether setting ULAB_HAS_FUNCTION_ITERATOR would allow ULAB_MAX_DIMS to be ignored altogether, because static nested loops would no longer be needed. Or does that not make sense? We have occasionally had users who wanted array support with more dimensions than the default.

Would you want ulab to support arbitrary dimensions by forgoing the static loops? That could actually be done, though, it would require considerable effort. And it's not only the places, where you iterate, but virtually everywhere. E.g., in

micropython-ulab/code/ndarray.c

Lines 2098 to 2117 in 38caf84

	mp_obj_t ndarray_reshape_core(mp_obj_t oin, mp_obj_t _shape, bool inplace) {
	ndarray_obj_t *source = MP_OBJ_TO_PTR(oin);
	if(!mp_obj_is_type(_shape, &mp_type_tuple) && !mp_obj_is_int(_shape)) {
	mp_raise_TypeError(translate("shape must be integer or tuple of integers"));
	}
	mp_obj_tuple_t *shape;
	if(mp_obj_is_int(_shape)) {
	mp_obj_t *items = m_new(mp_obj_t, 1);
	items[0] = _shape;
	shape = mp_obj_new_tuple(1, items);
	} else {
	shape = MP_OBJ_TO_PTR(_shape);
	}
	if(shape->len > ULAB_MAX_DIMS) {
	mp_raise_ValueError(translate("maximum number of dimensions is " MP_STRINGIFY(ULAB_MAX_DIMS)));
	}

an exception is thrown, whenever the new shape is longer than 4. Or the definition of the ndarray structure contains static arrays

micropython-ulab/code/ndarray.h

Lines 143 to 154 in 38caf84

	typedef struct _ndarray_obj_t {
	mp_obj_base_t base;
	uint8_t dtype;
	uint8_t itemsize;
	uint8_t boolean;
	uint8_t ndim;
	size_t len;
	size_t shape[ULAB_MAX_DIMS];
	int32_t strides[ULAB_MAX_DIMS];
	void *array;
	void *origin;
	} ndarray_obj_t;

which we ought to replace with pointers. That would mean that we've got to work on the the heap. I don't know, whether that has ramifications.

I think this is a very interesting and valuable idea, but given the amount of effort required, I would undertake it only, if there is reasonable interest, and if we can find a way to incrementally implement this. What I mean is that we could begin with a handful of functions (I don't even know, what people use/need), where we explore the implementation, and fix the rest as we go. Would you be OK with that?

And on a related note, if I set up a survey, where people could vote for the most used/popular functions, would you be willing to advertise that at circuitpython? I guess, you don't include everything in your firmware, do you? So you must have a procedure by which you customise ulab.h. I simply don't have the resources to do everything, and I'd like to select based on the needs of the community. There is no point in wasting time with a function that only two people in the whole world use.

[dhalbert]

@v923z Thanks for your detailed reply. I suspected that ULAB_HAS_FUNCTION_ITERATOR might not show a code size improvement for low values of ULAB_MAX_DIMS. When I tested with ULAB_HAS_FUNCTION_ITERATOR = 1 and ULAB_MAX_DIMS=2, the code size increased as above, and when I set the DIMS to 3, it grew even larger and overflowed the board I was build. So I did not try > 3.

We use the supplied ulab.h, as is, except that in circuitpython/py/circuitpy_mpconfig.h we set ULAB_SUPPORTS_COMPLEX = 0.

I do not remember anyone asking for other features to be turned off or on. One person asked for 3D arrays, but it turns out they did not actually need it: they were just confused. So my question was not reflecting a real need, but just what would be possible. I see the issue with the ULAB_MAX_DIMS-sized arrays in various places: I was not aware of that.

We'd be happy to advertise a survey on Discord, the newsletter, etc. To review our current uses of ulab, you could look at https://github.com/adafruit/Adafruit_Learning_System_Guides. spectrogram is popular.

I tried using github search to find Python code that used the exact word "ulab", but did not succeed. Even symbol:ulab did not work. I got a lot of matches with for the equivalent of *ulab*.

[v923z]

@v923z Thanks for your detailed reply. I suspected that ULAB_HAS_FUNCTION_ITERATOR might not show a code size improvement for low values of ULAB_MAX_DIMS. When I tested with ULAB_HAS_FUNCTION_ITERATOR = 1 and ULAB_MAX_DIMS=2, the code size increased as above, and when I set the DIMS to 3, it grew even larger and overflowed the board I was build. So I did not try > 3.

At the time, I looked at the size of the unix executable, but I don't know the validity of conclusions drawn from that. Even stranger is the fact that for two dimensions, if I get rid of the

micropython-ulab/code/ndarray.c

Lines 165 to 168 in d072086

	size_t *ndarray_new_coords(uint8_t ndim) {
	size_t *coords = m_new0(size_t, ndim);
	return coords;
	}

function, and simply use m_new0(size_t, ndim), wherever needed, then the code becomes slightly larger. Similar peculiarities can be observed by changing the number of arguments of specific functions: sometimes more arguments lead to smaller code. Go figure!

We use the supplied ulab.h, as is, except that in circuitpython/py/circuitpy_mpconfig.h we set ULAB_SUPPORTS_COMPLEX = 0.

There might be quite a few functions that are not particularly popular or used, so switching those off might make sense in your case.

I do not remember anyone asking for other features to be turned off or on. One person asked for 3D arrays, but it turns out they did not actually need it: they were just confused. So my question was not reflecting a real need, but just what would be possible. I see the issue with the ULAB_MAX_DIMS-sized arrays in various places: I was not aware of that.

It would not be terribly hard to move to a dynamical number of dimensions, but we don't know the performance hit, and the flash space penalty we would take. As I said, the nested loops as implemented now are rather cheap, both in terms of space, and in execution time. The

micropython-ulab/code/ndarray.c

Line 170 in d072086

void ndarray_rewind_array(uint8_t ndim, uint8_t *array, size_t *shape, int32_t *strides, size_t *coords) {

function simply "unwraps" the nested loops, if the depth of nesting is not known beforehand. I'm also baffled by the fact that it requires so much space, and based on the experience I mentioned above, I don't even know, where I should begin with the optimisation.

We'd be happy to advertise a survey on Discord, the newsletter, etc.

OK, thanks! Then I'll ping you, once I've set up the poll.

To review our current uses of ulab, you could look at https://github.com/adafruit/Adafruit_Learning_System_Guides. spectrogram is popular.

You probably still have an older version of ulab, for the spectrogram is now in utils:

micropython-ulab/code/utils/utils.c

Line 241 in d072086

#if ULAB_UTILS_HAS_SPECTROGRAM

I tried using github search to find Python code that used the exact word "ulab", but did not succeed. Even symbol:ulab did not work. I got a lot of matches with for the equivalent of *ulab*.

Ha! I've also walked into this. Sometimes I'm curious to see what people do with the code, and there is virtually no way of finding that out.