Re: Code optimization - C# Discussion Boards

tvbarnard20-Oct-09 1:33

20-Oct-09 1:33

Thought you'd like to know I sat up the whole of last night testing combinations of for-loops/pointers/foreach statements and these were my findings:

Hands down the fastest combination was

int boundC = classifiers.count;
int boundI = images.count;

for(int c = 0; c < boundC; c++)
{
   for(int i = 0; i < boundI; i++)
   {
      //use unsafe code to declare pointers to
      //image's data and classifier's data

      //do computations
   }
}

I then tried your idea to combine all images into one array, and use a seperate array to hold each respective image's data.

That reduced the time by about a factor 2! And the best thing with this method was that as I added more images, it reduced the time by an even larger factor (compared to using the List<images>)

I then tried using a parallel loop (threads) and discovered that the only way to protect the data is to use "lock (allClassifiers) { }". Unfortunately, using lock give the same processing power as without using parallel/threads. My assumption is that locking the data prevents simultaneous access, nullifying the use of threads.

tvb

Luc Pattyn20-Oct-09 1:40

20-Oct-09 1:40

yep. No big surprise, except locking the classifiers makes no sense to me, as it kills all parallelism and I don't see the need. IMO you either did something wrong, or forgot to tell me something...

did you compact the data with shorts?

Smile | :)

Luc Pattyn

I only read code that is properly indented, and rendered in a non-proportional font; hint: use PRE tags in forum messages

Local announcement (Antwerp region): Lange Wapper? 59.24% waren verstandig genoeg om NEEN te stemmen; bye bye viaduct.

tvbarnard20-Oct-09 6:50

20-Oct-09 6:50

Yes, I used ushorts for all the data. I can't say exactly what the effects were for the classifiers, but making the image data ushorts definitely helped.

Do you maybe know how I could use parallism without locking the data? Locking it seems the only way to keep it safe, and like you say, nullifies the point of using parallism...

tvb

Luc Pattyn20-Oct-09 6:53

20-Oct-09 6:53

tvbarnard wrote:
how I could use parallism

I already told you I would use N threads (N=#cores), and give them 1/Nth of the classifiers each. I have no experience with Parallel.For

Smile | :)

Luc Pattyn

I only read code that is properly indented, and rendered in a non-proportional font; hint: use PRE tags in forum messages

Local announcement (Antwerp region): Lange Wapper? 59.24% waren verstandig genoeg om NEEN te stemmen; bye bye viaduct.

tvbarnard20-Oct-09 6:55

20-Oct-09 6:55

Yeah, was actually asking if you could elaborate on that, but now that you say it like that I understand Big Grin | :-D

tvb

Luc Pattyn18-Oct-09 11:24

18-Oct-09 11:24

tvbarnard wrote:
the system uses at least 200,000 classifiers

what is a classifier? what thing in your source code equals 200,000?

can you please explain, maybe give some numeric examples, I want to see to what extent "locality of data" applies.

and how long does it take to do all you want done for just one image?

Smile | :)

Luc Pattyn

I only read code that is properly indented, and rendered in a non-proportional font; hint: use PRE tags in forum messages

Local announcement (Antwerp region): Lange Wapper? 59.24% waren verstandig genoeg om NEEN te stemmen; bye bye viaduct.

tvbarnard18-Oct-09 22:37

18-Oct-09 22:37

Sorry for the confusion.

In context of my system, a classifier would describe the way an image is evaluated and "classified" to contain a certain object in the image.

In my case, a classifier is a set of points in the image that respectively either get added or subtracted and thus return a real value. Using a threshold one can then decide accroding to the real value, whether the image represents that object or not.

For example, say you have a classifier:

int[] classifier = new int[] { 5, 6, 22}

then the image would be evaluated by adding all pixel values at coordinates {5, 6, 22} (assuming the image has been reshaped as a vector, and not a matrix).

Hope this is clear enough!

The point of the whole excercise, is to evaluate a set of classifiers on all images (each) and determine which is the best classifier. So what makes the excercise so computationally intensive, is that there exist at least 200,000 classifiers.

To answer your question on how long it takes to do an image, I haven't time it since it doesn't take very long. But the problem becomes exponentially more difficult if you increase your amount of images to let say 3000. I would estimate 3000 images, with 200,000 classifiers takes about 4min. 4 min doesn't sound long, but this must be done 500 times Smile | :)

500x4min = 33hrs!

The reason why I need to optimize this, is because firstly, it's not suppose to take so long (many papers report much faster times), and I also don't personally have the time to wait 30+hrs.

tvb

Luc Pattyn19-Oct-09 4:27

19-Oct-09 4:27

Sorry, I still:
- don't understand how your textual explanation fits your code;
- what "f" represents in your code;
- which array/list/whatever holds a classifier;
- and now also where that "500" is coming from.

And I fail to understand it at the higher level, i.e. what is really happening.

But I gave you another reply about cache efficiency and parallelism errors. Maybe that helps you.
If you need more advice, make sure to show sufficient code and provide explanations that refer to actual variables; in my experience, if you fail to explain it properly, chances are huge that you will fail to make it run efficiently too.

Smile | :)

Luc Pattyn

I only read code that is properly indented, and rendered in a non-proportional font; hint: use PRE tags in forum messages

Local announcement (Antwerp region): Lange Wapper? 59.24% waren verstandig genoeg om NEEN te stemmen; bye bye viaduct.

tvbarnard19-Oct-09 4:42

19-Oct-09 4:42

Very sorry, the problem is that the theory behind the code is very complex, so I try not to refer to the theory too much.

To answer:
1. A classifier is exactly the same as a feature, hence I use the terms interchangeably (sorry bout that)
2. The 500 refers to the amount of iterations the entire process must be carried out (where the entire process refers to the evaluation of all classifiers/features on all images)

Thanks for your willingness to help (I know it's a bit confusing)

If you give me a few minutes I'll come up with a more generic/descriptive code example for you.

tvb

tvbarnard18-Oct-09 3:31

18-Oct-09 3:31

Sorry, to answer your questions:

I load the images at the start of the program using pointers to traverse the image and store each pixel into the array (one by one). After that, I never reference the files themself again, so how I load the data shouldn't make any difference.

tvb

Not Active18-Oct-09 3:30

Not Active

18-Oct-09 3:30

tvbarnard wrote:
2. Parrallel processing the images (but I ended up with errors).

What were the errors? How did you code it? Did you use the Parallel Framework[^]

only two letters away from being an asset

tvbarnard18-Oct-09 3:36

18-Oct-09 3:36

I am not sure which parallel libraries you are refering to, but to be specific, I used the following line of code:

Parallel.For(0, bound, delegate(int i)
{

);

I didn't get errors in compiling, just got errors in my results.

I know my results were wrong, because the results I got were immediately different.

Any other parallel approaches you would suggest?

I also tried using normal referencing instead of pointers but I still got incorrect results.

tvb

Not Active18-Oct-09 3:53

Not Active

18-Oct-09 3:53

Only one Parallel Framework I'm aware of.

only two letters away from being an asset

Alan Balkany19-Oct-09 5:12

Alan Balkany

19-Oct-09 5:12

A couple of suggestions...

It takes a lot longer to process doubles than ints. Can you use ints for pixels?

A good algorithm for discovering classifiers is the ID3 algorithm (http://en.wikipedia.org/wiki/ID3_algorithm[^]). It analyzes your training set and automatically produces a decision tree that will classify a new case. Each branch of the decision tree will compare a feature (in this case a pixel) of the new case with a threshold.

tvbarnard19-Oct-09 5:31