1
$\begingroup$

I have large arrays of data organized so that it can be processed efficiently using array processing libraries. However, there are times when I only need to process slices of the arrays where a slice might be an arbitrary, non-contiguous subset defined by a select set of index values.

For example

result = someArrayProcess(objects)
result = result(chosenSet)

might be replaced by

result = someArrayProcess(objects(chosenSet),t)

Is there a way I can get some confidence whether the second example is more or less efficient without actually running tests? What would I be looking for in the array packages that might be available to ascertain whether they handle this sort of slicing efficiently (without running baseline tests)? Up to this point, I have used array slicing as a convenient way to develop readable and manageable code, but now I want to take it to production, where efficiency will be an issue.

As I write this, I'm threading my way through some of the similar questions. I see that striding is a way to efficiently access non-contiguous array elements. I assume that some array packages would leverage methods like this and some wouldn't. What packages maximize the use of methods like this?

This would probably be coded in C++. I am interested in how array packages in this and other languages (including Python) treat slicing with arbitrary subsets.

Motivation

I'm looking into making some architectural revisions that leverage array processing (and eventually moving it into GPU processing). The objective is to provide architectural simplification (for easier design management) using array expressions rather than element-level processing.

Since this would be a radical transition from the current approach, I will have to address concerns about efficiency trade-offs. The current solutions sacrifice exactness in performance to obtain efficiency, while being overwhelmingly difficult to manage due to their convoluted elements. They are now outdated, considering the advances that have been made in processing hardware since they were originally developed.

I prefer design simplification and performance accuracy over efficiency, but real-time requirements require that I consider efficiency, too.

$\endgroup$
2
$\begingroup$

First of all, it will be hard to proceed with certainty without "actually running baseline tests". Because your dilemma can be summarized, as follows:

readability and convenience vs. performance and efficiency

While readability, convenience, and maintainability of the code are very important, the heavy computations still have to be done efficiently and use as much of the computational power as possible. Arrays are very special in that regard because they are stored contiguously in memory (column- or row-wise); thus, if one accesses them in the order they are stored, it minimizes the amount of cache misses, improving the usage of the CPU. Moreover, the vectorization instructions can be applied easier (depends on the compiler and its settings).

Now, with the introduction of slicing the array, excessive using strides, one will definitely sacrifice some efficiency. How much? Depends on the heaviness of the array computations, surrounding logic, basic quality of the other code, compiler, CPU, RAM etc. So, actual benchmarking is important to make a decision on how to organize the data-flow.

The picture below (IT Hare) has much more information, but you might look into the difference between the time required for L1-, L2-, L3-, RAM-read. By introducing non-contiguous access to your array, you will increase the amount of time your code will have to do L2-read instead of L1 and L3 instead of L2. Or if your arrays are very large and access is completely random, most reads will be performed from RAM every time, which is horrendous.

enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.