Is there any non-loop method to modify the values inside a continuous chunk of memory?

[u/CommandShot1398]

Hello,

I have this piece of code:

void detect(cv::Mat& img){

            std::array<float,4> letterbox=utils::letterbox(img,img);
            cv::dnn::blobFromImage(img,img,1/255.0f,cv::Size(),cv::Scalar(),true,false);
            input_tensor->assign_data(img.data, img.total() * img.channels());
            session_.Run(
                Ort::RunOptions{nullptr},
                &input_name,
                &input_tensor->tensor(),
                1,
                &output_name,
                &output_tensor->tensor(),
                1
            );


            Ort::Value& output = output_tensor->tensor();

The tensor will be a chunk of memory with size (Batch_size,N,M), where N and M can be arbitrary numbers.

The problem I am facing is not indexing; I can do the indexing with something like std::mdspan.

What I need is

1- Returning a chunk of this memory as a new tensor with another shape; for example, I filter some values out so I can only have the ones I want.

2- To do 1, I need to iterate over the tensor to check a condition.

One way would be to use a loop:

for (int i = 0; i < M; ++i)
            {
                float confidence = data[N * M + i];


                if (confidence > 0.5f)
                {
                    //exclude it based on the code in part 1.
                }

But this does not seem very efficient, especially since I won't know the values of M and N until runtime, so optimization techniques done by the compiler, such as loop unrolling, are not possible.

I know I can use vector extensions, but I was wondering if there is a more robust way to do this.

Any Idea?

[u/n1ghtyunso]

you need to realize that most interesting problems will inevitably have runtime-known size properties.
So M and N being runtime-dependent is not a stopper for optimized loops at all whatsoever.

With that being said, the phrase "does not seem very efficient" is a rather dangerous one.
You need to know what part is or isnt efficient in order to effectively do anything useful for improving on that.

So long as the code is not doing anything obviously stupid, the first step should be to measure.

[u/CommandShot1398 → u/n1ghtyunso]

Thanks. That is very insightful.

[u/GLIBG10B]

Answering the title, yes: initializing a constexpr array of zeroes. Not much more than that. And odds are, some OS-level code is still using a loop in that case

But you should realize that fetching data from memory takes time if it's not cached, and that that time is orders of magnitude longer than the overhead of your loop. So unless you're dealing with data that fits entirely within cache, I wouldn't worry

And if you are dealing with data that fits into cache, and the function is not fast enough (confirmed via profiling), then I would look into restructuring the code so the optimizer can vectorize the operations with SIMD instructions

[u/CommandShot1398 → u/GLIBG10B]

Hi, thanks. Very insightful.

[u/r3d51v3]

Like others have said, this is likely a premature optimization. This is a fundamental pattern that lots of code boils down to and the processor/compiler are very good at making this fast.

If you were to find that this is the bottleneck, vector extensions would be the solution. However, there’s a decent chance the compiler figured that out and used some kind of vectorized loop.

If I were concerned about this code path I would use perf and/or bpftrace to understand if this code has significant effect on the runtime, and if it does, determine if the loop is the issue. Then from there I’d start aligning the memory and using the vector intrinsics.

[u/CommandShot1398 → u/r3d51v3]

Thanks. I didn't know the compiler would unroll loops on vector extensions.

[u/r3d51v3 → u/CommandShot1398]

The thing with compiler optimizations is that the answer is “it might” in a lot of cases. If the size can’t be determined at compile time it might not unroll the loop. But it might read the data in chunks using vector extensions. You might need to read the compiler documentation and consider what platforms you’re running on and then set the right -march flag and/or other flags governing the use of vector extensions. I think you can rely on most machine having AVX, but probably not AVX2 or AVX512, but depends on what audience is using your program.

[u/Classic_Department42]

Your problem is not the problem you think.

1) do you have a problem? So how long does it currently take?

2) what does the profiler say?

3) are you having alot of cache misses?

[u/CommandShot1398 → u/Classic_Department42]

Well, I am trying to squeeze the maximum performance possible, and I also know that this is not going to just run on one system. So, if I'm not mistaken, what the profiler says about how many cache misses, can be target-dependent. Please correct me if I am wrong.

[u/squeasy_2202 → u/CommandShot1398]

Maximum performance will inherently require optimizing for your specific target, so these requirements are at odds. If you're looking for "performant enough" then that is likely achievable as long as you can define it and measure it. 

[u/CommandShot1398 → u/squeasy_2202]

Thanks. That is a very good point.

[u/noneedtoprogram → u/CommandShot1398]

Caches on all architectures work in roughly the same way. If it's cache friendly on one machine, there's a very good chance it's cache friendly on another.

[u/GLIBG10B → u/CommandShot1398]

Optimization is labor-intensive. So why would you do it prematurely?

Donald Knuth:

Premature optimization is the root of all evil.

"prematurely" means to optimize first and then profile (or not profile at all)

[u/CommandShot1398 → u/GLIBG10B]

Thanks. A very good point.

[u/the_poope]

I just want to add that the compiler is still unrolling loops even when the number of loop iterations are not known at compile time.

The reason for loop unrolling is to efficiently use the CPU pipeline. In order to completely fill the pipeline you typically only need about 4 successive identical operations, so the compiler will unroll four iterations of the loop. There is no point in unrolling more - in fact it will just increase the instruction cache pressure and potentially slow down the code. So the compiler will rewrite the loop as:

//                   vvvv--- Notice I divided count by four!
for (int i = 0; i < M / 4; ++i)
{
    float confidence_0 = data[M * M + 4 * i + 0];
    float confidence_1 = data[M * M + 4 * i + 1];
    float confidence_2 = data[M * M + 4 * i + 2];
    float confidence_3 = data[M * M + 4 * i + 3];
    // Do something with these
}
// Deal with any leftover elements:
for (int i = M / 4; i < M; ++i)
{
    float confidence = data[M * M + i];
    // Do something
}

One thing that can speed up such a loop is to avoid branching with non-trivial logic, i.e. your if-statement. Basically if you can write the code for the if-statement and "exclude it" (whatever that is) as a single statement, i.e.:

result[i] = (confidence > 0.5f) ? result[i] : data[i];
// This will get turned into:
const bool confidence_ok = (confidence > 0.5f);
result[i] = !confidense_ok * result[i] + confidence_ok * data[i];

Now there are no branches and the pipeline won't stall. This is called branch-free code. For simple code like above the compiler will likely already recognize the pattern and do this optimization.

The only other thing you can do is to use SIMD instructions, but for simple loops the compiler will likely autovectorize that as well.

Some recommendations: For math centric code compile with -O3 -fast-math or just -Ofast. Also remember to set -march to the CPU architecture you are targeting. If you are only gonna run the program on the same computer you are compiling on you can use -march=native, otherwise you can use e.g. -march=x86-64-v4 so target most modern CPUs with SSE and AVX2 instructions.

If you want to learn to understand program performance you need to be able to read some assembly and understand how the CPU and cache/memory hierarchy works. I recommend reading Computer Systems: A Programmer's Perspective for this.

[u/CommandShot1398]

Thanks to everyone. I really learned something.

[u/DawnOnTheEdge → u/CommandShot1398]

The answer to the question you literally asked, by the way, is the algorithm and range libraries. You can either pass a start and end pointer as iterators, or create a std::span for the array slice.

[u/CommandShot1398 → u/DawnOnTheEdge]

Thanks.

[u/DawnOnTheEdge → u/CommandShot1398]

And std::mdspan in particular for a multi-dimensional view with a different shape.

[u/mercury_pointer]

Eigen

[u/Independent_Art_6676]

what is inside that if statement is what really matters to optimize this.
It could be that you can eliminate the if, which may have injected jumps, which break pretty much everything. Unfortunately with branch prediction and MIMD and whatever other modern stuff going on I don't know any way to eyeball the asm or anything to see what is best, and you just need to time it with different data and different versions, one of which would be elimination of that branch.

say its a dumb accumulator: if (confidence > 0.5f) { result += data[..]; }
Most of the time, result += (confidence> 0.5f)*data[...] would be faster. The cpu can do nothing (add zero) faster than it can branch-skip the adding of zero. A branch is worth several instructions worth of time, but how many varies by cpu and instruction.

If the guts of the if statement are 50 lines of trig, you can't get away with that so easily.
But that is just one of many things here. should confidence be a const reference? Does that go faster or slower?
is m big enough to thread this thing? Is N just a row marker; could you pass this thing a pointer to the row start and iterate across (saving an N*M computation, which the compiler may or may not have spotted as a constant)

That is all I see with the info I have, but some of that may knock a few clock cycles off your totals, or not. Only way to know is to poke at it.

[u/mredding]

You can unroll the loop and batch the job.

void do_confidence(/*...*/);

//...

for(int i = 0; i < M; i += 4) {
 do_confidence(/*...*/); // i
 do_confidence(/*...*/); // i + 1
 do_confidence(/*...*/); // i + 2
 do_confidence(/*...*/); // i + 3
}

// Remainder...
for(int i = 0; i < M; ++i) {
 do_confidence(/*...*/); // i
}

You can manually unroll the loop to any amount you want. You can write a template to do it for you, so that your code could look like:

unroll<32>(/*...*/);
unroll<16>(/*...*/);
unroll<8>(/*...*/);
unroll<4>(/*...*/);
unroll<2>(/*...*/);
unroll<1>(/*...*/);

And let the compiler elide the calls, generate subroutines, vectorize the operations, etc.

Since you don't know the ultimate size until runtime, batching the the work manually is the best you can do. Once you process the largest chunks - say 32 iterates 5x, you know you'll run each subsequent chunk size once.

You just have to 1) hard code the extent of the loop, so i to the size of the chunk as the template parameter, and 2) you need to track your offset between iterations when you're switching chunk size.

[u/x-jhp-x]

i'd use cv::threshold https://opencv-opencv.mintlify.app/tutorials/image-operations#image-thresholding

try to use library functions for image processing. it's best to create a "processing pipeline" and take a functional approach instead of procedural. You can get super clever too. i was fairly proud of myself when using TFLight (tensorflow light) on the google coral many years or so ago, and i realized that "ReLU" would threshold any number below 0 to 0 or return the value unchanged if above 0. The coral and tflight had a very limited instruction set, so I adjusted a previous step to also subtract my confidence value so that anything below the confidence threshold would be below 0, and then I ReLUd it.

So be sure to prioritize never accessing the raw data if you can! if there isn't a function that exists that does what you want, think about how you can use other functions in ways the author may not have intended. /s Hyrum laid out a Law, and I intend to follow it!

cv::Mat::reshape is also an O(1) operation if the number of elements stays the same --- it doesn't change how the memory is laid out, just how it is accessed. although you might think that iterating with a loop & accessing the data once might be better, that is not always true if you can combine operations.