Question about processing efficiency and optimization.

The linked list example is likely the slowest. But it all depends on so many things. A profiler can be useful.

Have you profiled your code? You may find a sequential loop from 0 to collumns*rows*3 fastest as you're going to have lots of cache hits that way... Completely depends on your app...

What is your target compiler? Target hardware? How often is this code called? Have you already confirmed that this code is a performance issue via profiling, or are you prematurely optimizing? What is the in-memory format of data being operated upon? SoA or AoS? Are you doing multithreading? Targeting a NUMA system? Is raw throughput priority, or do you need to handle things like battery lifespan and power consumption?

Correct me if I'm wrong but, what comes to mind, to me at least, is a rather generic example such like applying 3000*3 being faster than applying 3000*3, it's something generic that doesn't really rely on programming languages, compilers or O.S.

I made some research about code profilers and, going a little off topic, aren't they the same as debuggers?

I'll try to me as specific as possible to add to my previous question.

*I use the GNU compiler G++ on Eclipse Helios which is, obviously, for CPP.
*The program would run on a linux (Ubuntu), desktop pc.
*The code is actually part of a package to write Jpeg files, which uses many of these for loops and linked lists, I want to learn as much as I can to optimize the time it takes to get quantized DCT coefficients from RGB data, as of now, it takes 6 seconds to generate these coefficients for a 1024X1024 image, which comprises of a unsigned char of size (1024*1024*3).
*As my code is entirely cross-platform and packaged on different independent classes, I guess its developed under SOA from what I researched.
*The code runs on a single thread, thats the main reason why its so slow I think but, I believe I can make all this operation a lot faster by optimizing my code. Im also very interested in parallel programing but want to stick with what I know for now.
*I don`t know if my program targets NUMA system. Is this compiler relative?
*I want to make the code run as fast as it can, therefore disregarding power consumption, which should not be much of a problem since the code should run a multi-core processor.

Sorry about any mistakes and, hope to be clear enough.
Off course, thank you for the replies.

*The code is actually part of a package to write Jpeg files, which uses many of these for loops and linked lists, I want to learn as much as I can to optimize the time it takes to get quantized DCT coefficients from RGB data, as of now, it takes 6 seconds to generate these coefficients for a 1024X1024 image, which comprises of a unsigned char of size (1024*1024*3).

Since this is a fairly common problem, why not use an existing library?

JPEG algorithms have been optimized into oblivion, from integer-based to SSE and GPUs, take your pick.

Since JPEG is used in everything, from cameras, phones, video players and cameras (MPEG), browsers, OSes, literally everything, it's quite hard to find a set of algorithms which have been optimized more.

[quote name='TMarques' timestamp='1314046479' post='4852501']
*The code is actually part of a package to write Jpeg files, which uses many of these for loops and linked lists, I want to learn as much as I can to optimize the time it takes to get quantized DCT coefficients from RGB data, as of now, it takes 6 seconds to generate these coefficients for a 1024X1024 image, which comprises of a unsigned char of size (1024*1024*3).

Since this is a fairly common problem, why not use an existing library?

JPEG algorithms have been optimized into oblivion, from integer-based to SSE and GPUs, take your pick.

Since JPEG is used in everything, from cameras, phones, video players and cameras (MPEG), browsers, OSes, literally everything, it's quite hard to find a set of algorithms which have been optimized more.
[/quote]

I appreciate your suggestion Antheus and I have considered it before, however, the knowledge I gathered while learning everything is of much value and improved my software engineering skills greatly along the way, thats whats important to me. As for the optimization techniques, it applies for a wide variety of problems on the programming scope and I believe every programmer should understand how to make his or hers code as optimized as possible.

Best regards!

Correct me if I'm wrong but, what comes to mind, to me at least, is a rather generic example such like applying 3000*3 being faster than applying 3000*3, it's something generic that doesn't really rely on programming languages, compilers or O.S.

You are completely wrong.

Tail recursion will always be faster in Lisp than in Visual Basic. This is a simple case where a programming language choice can affect implementation realities in a big way.

Even within the ecosystem of a single language, some compilers are good at certain things, while others are not. I would write very different C for Clang on a SSE3 multicore CPU than I would for a microcontroller or even for a game console like the PS3.

Operating systems are also a case where some strong points show up (and some weak points) when it comes to performance. There are well known issues with Linux and memory allocation behavior, for instance (c.f. the OOM Killer). Certain versions of Windows have had terribly bad multiprocessor implementation problems. Some versions of Windows will only work well when avoiding swapping virtual memory to disk; others cope fine; others (mainly server versions) can be tuned either way. Some niche OSes exist entirely for very specific reasons (such as VxWorks) and will perform well only when used according to those specifications. Mobile phone/tablet OSes are another great example of requiring specific workarounds or approaches to get good results.

And that's just software, which is arguably the easiest thing to deal with. Once you start working with the diversity of hardware systems available, you're in for a wild ride.

The difference between a 256KB and a 512KB L2 cache on an otherwise identical CPU die can dictate entirely different programming style. The difference between an integrated memory controller and an outrider-style northbridge can make a radical change in memory access speeds, especially in NUMA environments. Throw in more nontrivial things like FSB speeds, southbridge bus speeds, storage device latency, network speeds... the actual performance of a program depends on all of these factors, and often in very significant ways.

A computer is a system of highly interdependent elements. Treating programming like an abstract art wherein only mathematical elegance is relevant to performance is begging for bad results.

A major problem here is that academia continues to teach extremely outdated nonsense when it comes to optimization. They often harp on things like algorithmic complexity and big-O characteristics, while completely ignoring (or ignorant of) the fact that these things are misleading at best on cache-heavy hardware architectures. They also assume optimal data throughput on a standard Von Neumann machine architecture, which is bogus and naive, because (1) modern computers are not Von Neumann machines and (2) even if they were, data source throughput is never optimal in practice.

I made some research about code profilers and, going a little off topic, aren't they the same as debuggers?[/quote]

Um, not hardly. Whoever told you that should never be trusted for information again.

I'll try to me as specific as possible to add to my previous question.

*I use the GNU compiler G++ on Eclipse Helios which is, obviously, for CPP.
*The program would run on a linux (Ubuntu), desktop pc.
*The code is actually part of a package to write Jpeg files, which uses many of these for loops and linked lists, I want to learn as much as I can to optimize the time it takes to get quantized DCT coefficients from RGB data, as of now, it takes 6 seconds to generate these coefficients for a 1024X1024 image, which comprises of a unsigned char of size (1024*1024*3).
*As my code is entirely cross-platform and packaged on different independent classes, I guess its developed under SOA from what I researched.
*The code runs on a single thread, thats the main reason why its so slow I think but, I believe I can make all this operation a lot faster by optimizing my code. Im also very interested in parallel programing but want to stick with what I know for now.
*I don`t know if my program targets NUMA system. Is this compiler relative?
*I want to make the code run as fast as it can, therefore disregarding power consumption, which should not be much of a problem since the code should run a multi-core processor.

Sorry about any mistakes and, hope to be clear enough.
Off course, thank you for the replies.
[/quote]

What version of G++? What libraries are you using, and what versions of those? What specific distro and version of Linux are you targeting? What specs of "desktop PC"? (I can run Linux on a 386 for goodness sake... be specific!)

If you aren't using SIMD instruction sets or GPGPU techniques, you're wasting your time and will always be at least an order of magnitude slower than comparable JPEG libraries. Use them instead - either use them outright, or read their code for understanding. Trying to independently recreate decades of research into image compression will end only in pain and frustration.

I don't think you know what SoA and AoS stand for (Structure of Arrays and Array of Structures, respectively). These are data organization principles and have nothing to do with being "cross platform" or how your classes are organized.

Also, you contradict yourself. Are you targeting a Linux distro, or are you writing something that needs to work on multiple platforms? If the latter, which platforms? Be specific.

Multithreading does not magically make code faster. Single threading does not magically make code slower. In point of fact it is extremely hard to write multithreaded code which is generally faster than single-threaded equivalents. Do not make the mistake of confusing multithreaded concurrency with parallel processing; they are very different techniques with very different applications. It is almost always possible to gain speed at nearly linear rates by running the same program in parallel, either across CPU cores or across physical machines; it is almost never possible to do this with multithreading on a single CPU core.

NUMA is a hardware term and has nothing to do with compilers. Look it up.

If you want to use multicore processors to their fullest, you need to either run multiple copies of your program (ideally one per core) - i.e. process level parallelism - or you need multithreading. You will never use a multicore CPU to its potential writing single threads of execution. By the same token, if you need raw throughput, you absolutely must be writing everything in terms of SIMD instructions from day one, or you are fighting a losing battle. Even better, use GPGPU techniques.


Again, I strongly suggest that you look at optimized JPEG libraries instead of trying to recreate all this stuff in vacuum. You will save yourself a lot of headaches.

I suspect your biggest performance gain will come from getting your code running on multiple threads. Assuming you're processing lots of files I'd go with creating one or two more threads than you have available CPU cores. The extra threads are there to keep the CPU busy even when some threads are blocked doing file I/O. I'd also recommend acquiring a mutex round all file access - that way multiple threads won't hit the hard drive at the same time causing unnecessary seeks.

Each thread would pull a task from a thread safe queue, process it, and repeat till the queue is empty. You'd need a main thread that simply filled up the queue, started the threads, and waited for them all to complete.

I made some research about code profilers and, going a little off topic, aren't they the same as debuggers?[/quote]

Any decent profiler will give you a breakdown of the percentage of execution time spent in each function. That is they tell you where to target your optimizations. They don't do the same thing as a debugger at all.

When you're using a profiler make sure it's done on optimized code (i.e. compiled with -O3), or you won't get useful results.

ApochPiQ

I will get to GPGPU as soon as I have the code as optimized as possible, 6 seconds to construct a data is unacceptable even for an outdated computing system.
Overall goal is to have a good grasp of optimization techniques including parallel programming and, learning Jpeg compression is a good way to get things started so I hope you understand why I can't take your suggestion.

Also, SOA stands for Service Oriented Architecture as well, first result on google, you should have just said Structure of Arrays and Array of Structures in the first place.

I suspect your biggest performance gain will come from getting your code running on multiple threads. Assuming you're processing lots of files I'd go with creating one or two more threads than you have available CPU cores. The extra threads are there to keep the CPU busy even when some threads are blocked doing file I/O. I'd also recommend acquiring a mutex round all file access - that way multiple threads won't hit the hard drive at the same time causing unnecessary seeks.

Each thread would pull a task from a thread safe queue, process it, and repeat till the queue is empty. You'd need a main thread that simply filled up the queue, started the threads, and waited for them all to complete.

I made some research about code profilers and, going a little off topic, aren't they the same as debuggers?

Any decent profiler will give you a breakdown of the percentage of execution time spent in each function. That is they tell you where to target your optimizations. They don't do the same thing as a debugger at all.

When you're using a profiler make sure it's done on optimized code (i.e. compiled with -O3), or you won't get useful results.
[/quote]

Adam,

I don't have a problem writing files and retrieving input from the program, everything is done efficiently and seamlessly, the problem is with matrix and vector operation, right now I have lots of redundant "for loops" that I need to eliminate to improve performance.

There are four steps taken, converting RGB to YCbCr, applying DCT, quantizing and performing run length encoding, I have done all these steps in separate loops mainly because I was just concerned on having the entire algorithm working. Now that It does, I have to rewrite my code to make it more efficient. The proper way of doing it is separating all RGB data into 8x8 blocks and calculating each step on these block all at once, that improves greatly the time taken to perform calculation and, I believe the final step for optimization is parallel calculation of all 8x8 blocks.

I've learned an Eclipse Profiler plugin, any recommendations?

Thanks in advance.

Didnt read much of previous posts, but doesnt Visual Studio always break(expands) for loops always it can?


simple(stupid) examples:
for( it 0 to 10 )
array(it) = it;

expands to

array(0) = 0
array(1) = 1
array(2) = 2
...

or

for( it 0 to 100 )
array(it) = it;

expands to

for( it 0 to 100, it += 10)
array(it) = 0
array(it+1) = 1
array(it+2) = 2
...

Dont remember where I got that from..

I will get to GPGPU as soon as I have the code as optimized as possible, 6 seconds to construct a data is unacceptable even for an outdated computing system.
Overall goal is to have a good grasp of optimization techniques including parallel programming and, learning Jpeg compression is a good way to get things started so I hope you understand why I can't take your suggestion.

My suggestion was to look at other people's code for guidance. Why can't you do that?

Also, SOA stands for Service Oriented Architecture as well, first result on google, you should have just said Structure of Arrays and Array of Structures in the first place.[/quote]

My search for "soa aos" turned up a first page full of results, each of which describes in detail what the acronyms mean. Don't whine to me because I didn't do your research for you. If you want to be teaching yourself advanced programming techniques, I suggest you develop a bit more work ethic when it comes to looking up things you don't know.

I don't have a problem writing files and retrieving input from the program, everything is done efficiently and seamlessly, the problem is with matrix and vector operation, right now I have lots of redundant "for loops" that I need to eliminate to improve performance.[/quote]

Does your profiler agree with this assumption? Because there's a perfectly good chance you're wrong about what is slowing down your code.

I've learned an Eclipse Profiler plugin, any recommendations?[/quote]


Learn at least four different profilers. Every one has strengths and weaknesses and slightly different techniques for measuring code performance. Ideally, learn at least one instrumenting profiler and at least two sampling profilers.

Didnt read much of previous posts, but doesnt Visual Studio always break(expands) for loops always it can?

Loop unrolling is indeed a very common C/C++ optimization technique. However, manual partial unrolls can often work better than expecting the compiler to be smart enough to do a perfect partial (or even complete) unroll by itself. At the end of the day, compiler optimization heuristics will often miss more sophisticated code manipulations because it simply isn't possible (even in theory) to know all the different ways to rearrange a piece of code that might be faster.

Does your profiler agree with this assumption? Because there's a perfectly good chance you're wrong about what is slowing down your code.

Profiler is mostly redundant here. Really, there is nothing to examine. Not with JPEG.

The perfect algorithms have been implemented 10-15 years ago. Not just good enough, but essentially perfect in every possible aspect.