|
|
Dear all,
I don't know if this the best place for posting my message, but I'll try...
I am trying to figure out which the best approach for the implementation of a class of a (VERY LARGE, LARGE = 1e6 - 1e7) arrays of 2-by-2 matrices. My contraints are the following:
- I have to perform a number of mathematical operations on this matrices, like C = A * B * D avoiding the creation of temporaries (due to size of these objects). Overoloading operators is not a problem, but I DO need a good starting point
- the execution speed of this operations must be as high as possible, since I have to perform a large number of operations.
I've been googling for the last 3-4 days and I've found a number of different approaches for the soultion of this problem (downloadable libraires, expression templates, block-copy techinques), but I haven't found a well performing solution for my problem yet.
Can anybody help me, please?
|
|
|
|
|
As I understand your problem I would suggest reference counting smart pointers.
Have a look here[^].
"It's supposed to be hard, otherwise anybody could do it!" - selfquote
"High speed never compensates for wrong direction!" - unknown
|
|
|
|
|
misterMF wrote: I have to perform a number of mathematical operations on this matrices, like C = A * B * D avoiding the creation of temporaries
Specialised functions are probably the easiest way to control exactly what happens, e.g.
void Mult3(Matrix const & A, Matrix const & B, Matrix const & D, Matrix& C)
{
}
Expression templates are the way I'd think if I were doing something more involved - I believe Blitz++[^] is meant to be quite good - certainly, this section[^] promises what you're needing - whether it can deliver is another matter...
|
|
|
|
|
Hi,
having an array with millions of matrices, your app's performance probably will be memory-bandwidth limited, i.e. the amount of data you will want to read from/write to memory (or CPU cache) will be the limiting factor.
So the organization of the work will be of utmost importance; try to work locally, i.e. do all that needs to be done on a subset (say a few 100KB) of the data, then move on to the next subset.
If you want more suggestions or help, you should tell us more about the application, and the data types involved.
|
|
|
|
|
One thing that will kill performance in this quantity is allocating and deleting objects. This is where you want to use some form of fixed memory allocation--that is preallocating blocks of objects.
Anyone who thinks he has a better idea of what's good for people than people do is a swine.
- P.J. O'Rourke
|
|
|
|
|
Thank you very much for your precious suggestions . I'll start with the implementation to see where the bottlenecks are.
I'll start declaring my class more or less like this:
template< typename T >
class TTransferMatrix < std::valarray<t>> : public TTransferMatrix_base < std::valarray<t>>
{
private:
const size_t N_ELEMENTS;
size_t arraySize;
std::valarray< T > m00;
std::valarray< T > m01;
std::valarray< T > m10;
std::valarray< T > m11;
public:
}
</t></t>
In the template, <t> can be any basic type. In my application, I'll need to work complex numbers.
Do you think that STD::VALARRAY is a good choice as the basic container?
I know that the STD::VALARRAY class is not really optimized for numerics (as they would like us to believe...), but I performed some tests long time ago and I noticed that filling/reading a STD::VALARRAY was faster than using STD::VECTOR.
|
|
|
|
|
I have an application which is experiencing heap corruption being reported by NTDLL. It only occurs when I have a heavy calculation running simultaneously in 2 threads, which are working on different data.
The symptoms are that the area being used for strings gets corrupted. All objects only make use of the STL and/or new/delete.
Known facts:
1. There are no memory leaks (that we know of)
2. All pointers get set to NULL once freed
3. There are no shared variables between the threads (in my code anyway).
4. It does not occur in the debug build
5. Turning off all compiler optimisations does not help
I have tried setting breakpoints on memory writes to catch where these overwrites are happening and it always seems to be in the STL for either std::string or std::vector destructors.
I have updated my STL headers as per the list of bugs in the STL at Dinkumware's website (the provider of the STL for MS VC6), but this doesn't fix any bugs in the libraries provided by MS which come pre-compiled.
Any ideas on what may be the issue or things I can try and isolate the problem with? Its been 3 days of hard slog so far with very little to show for it. 
[Edit]
We tracked down this article which seems to be directly relevant for the cause of our problem:
http://support.microsoft.com/kb/813810[^]
Although we havn't managed to test it yet were hopeful and it may be of use to others.
[/Edit]
If you vote me down, my score will only get lower
modified on Tuesday, January 20, 2009 6:02 AM
|
|
|
|
|
Is there any synchronization done between the 2 threads or any threads for that matter? You say that the 2 threads are working on different sets of data but can it be that they are reporting progress or results using some shared part of the code?
> The problem with computers is that they do what you tell them to do and not what you want them to do. <
|
|
|
|
|
Neither thread synchronises at all.
One is the UI thread for when the user starts a manual calculation. The other is a worker thread that when it needs to interface with the UI uses PostMessage.
The UI thread during calculation also does periodic calls to Get/Pump message etc so these do get processed. Any work done in the UI uses CString etc plus new/delete on obejcts as required.
If you vote me down, my score will only get lower
|
|
|
|
|
Ummm, good question Roger. Maybe I should vote it as such.... 
Roger Allen wrote: I have an application which is experiencing heap corruption being reported by NTDLL.
In what way is this "reported" by NTDLL?
Two things comes to mind that I would checkout based on your statement that it doesn't happen when debug built:- Is a release built library used with a debug built application (or the other way around) where memory allocations are done in one and deallocations in the other?
- Is something alocated with e.g.
new and then deleted with free() (or the other way around)?
One other thing is that the debug built version is very forgiving and I assume you've read this article[^].
It could also be an uninitialized variable that gets initialized when debug built.
"It's supposed to be hard, otherwise anybody could do it!" - selfquote
"High speed never compensates for wrong direction!" - unknown
|
|
|
|
|
Roger Stoltz wrote: In what way is this "reported" by NTDLL?
The message reported is usually
Heap corruption detected at
Sometimes also see text saying that a block at has been modified after being freed at +offset
Roger Stoltz wrote: Is a release built library used with a debug built application (or the other way around) where memory allocations are done in one and deallocations in the other?
The entire application is built using release versions and libraries of everything. I have used dependency walker to check all the included DLLs/dependencies and these are all release versions of the CRT etc
Roger Stoltz wrote: Is something alocated with e.g. new and then deleted with free() (or the other way around)?
All code uses new/delete or delete [] as appropriate.
Roger Stoltz wrote: One other thing is that the debug built version is very forgiving and I assume you've read this article[^].
It could also be an uninitialized variable that gets initialized when debug built.
I'll take a look at the article, thanks for the link 
If you vote me down, my score will only get lower
|
|
|
|
|
Roger Allen wrote: Sometimes also see text saying that a block at
has been modified after being freed at
+offset
To my knowledge the only way a software keeps track of this and report it with the words you've quoted above, is if it uses the MFC framework built with new defined to DEBUG_NEW.
It could be that DEBUG_NEW is used instead of the ordinary new operator.
It would use the allocator from the release built CRT, but with extra info and boundary checks when released. You'll get more info on this from the link I provided in my previous post.
"It's supposed to be hard, otherwise anybody could do it!" - selfquote
"High speed never compensates for wrong direction!" - unknown
|
|
|
|
|
Roger Stoltz wrote: To my knowledge the only way a software keeps track of this and report it with the words you've quoted above, is if it uses the MFC framework built with new defined to DEBUG_NEW.
It could be that DEBUG_NEW is used instead of the ordinary new operator.
mmm thats an interesting point. I will check the whole app for that one.
I went through PJ's article on the release build. Its something I have read before but its been a while. A few updates etc in it but nothing jumped out from it as a possible cause of the issues were seeing.
If you vote me down, my score will only get lower
|
|
|
|
|
Roger Allen wrote: I will check the whole app for that one.
Well, how did it go? Found anything suspicious?
A missing #ifdef _DEBUG perhaps?
Roger Allen wrote: I went through PJ's article on the release build.
Ummm, "PJ"? What article is that? Or you mean "Professor Joe"? 
Nevertheless, one thing to look for when the debug version does what it's supposed to and the release version does not, is uninitialized variables. A lot of them get initialized in the debug version behind curtains.
"It's supposed to be hard, otherwise anybody could do it!" - selfquote
"High speed never compensates for wrong direction!" - unknown
|
|
|
|
|
Roger Stoltz wrote: Ummm, "PJ"? What article is that? Or you mean "Professor Joe"?
For some reason I had it my head it was by PJ Naighter, its Actually by Joesph Newcomer 
Roger Stoltz wrote: Nevertheless, one thing to look for when the debug version does what it's supposed to and the release version does not, is uninitialized variables. A lot of them get initialized in the debug version behind curtains.
Its something were checking also. Its slowely being escalated to the whole team looking for it.
If you vote me down, my score will only get lower
|
|
|
|
|
It would be nice to know if, or rather when, you find something.
I'm curious and it would be a good experience for myself as well; another pitfall to avoid and possibly how to do it.
Good luck in your hunt for that illusive bug.
"It's supposed to be hard, otherwise anybody could do it!" - selfquote
"High speed never compensates for wrong direction!" - unknown
|
|
|
|
|
Roger Stoltz wrote: It would be nice to know if, or rather when, you find something.
I'm curious and it would be a good experience for myself as well; another pitfall to avoid and possibly how to do it.
Good luck in your hunt for that illusive bug.
Should we ever track it down I will post a message in this thread.
We have exhausted most conventional methods of tracking it atm. Were building a test suite now which will setup the same conditions which will allow us to remove/add sections as we go to see where the unwanted interaction is occuring.
If you vote me down, my score will only get lower
|
|
|
|
|
We think we may have now tracked the problem down.
Seems its not our bug
http://support.microsoft.com/kb/813810[^]
Apparently the VC6 implementation of std::string is not that multiprocessor/thread safe 
[edit]
And yes, following one of the suggestions in the article fixed our problem. Now we need to decide which way we want to do the fix in the final product.
[/edit]
If you vote me down, my score will only get lower
|
|
|
|
|
Roger Allen wrote: And yes, following one of the suggestions in the article fixed our problem.
Nice. Congratulations to you and your team.
Well done Roger!
"It's supposed to be hard, otherwise anybody could do it!" - selfquote
"High speed never compensates for wrong direction!" - unknown
|
|
|
|
|
Roger Stoltz wrote: Ummm, "PJ"? What article is that? Or you mean "Professor Joe"?
PJ Naughter[^]... He used to be a very active member of Codeproject.com many years ago. After he created his own website[^] he stopped updating his articles and rarely visits anymore. There are some excellent libraires available on his website. Microsoft awarded him with MVP status in 2007[^] due to his contributions.
Best Wishes,
-David Delaune
|
|
|
|
|
Well, I found PJ's site about a decade ago when I had a job I resigned from in 2000.
But I couldn't remember whether he had written something about the differences between the debug and release versions. That combined with the fact that I linked to Joe's site made me unsure about what the other Roger meant.
"It's supposed to be hard, otherwise anybody could do it!" - selfquote
"High speed never compensates for wrong direction!" - unknown
|
|
|
|
|
- Are you using a multi-threaded C run-time (I'm sure you are, but am asking for completeness )
- Are the STL objects being allocated in the same module (EXE/DLL) as they're destructed in? If not, you need to ensure you build all your different modules with a DLL version of the C run-time.
#2 has caused the same symptoms for me in the past as you're experiencing.
|
|
|
|
|
Stuart Dootson wrote: Are you using a multi-threaded C run-time (I'm sure you are, but am asking for completeness )
Yes, they all use the Multithreaded DLL for CRT etc. Double and triple checked.
Stuart Dootson wrote: Are the STL objects being allocated in the same module (EXE/DLL) as they're destructed in? If not, you need to ensure you build all your different modules with a DLL version of the C run-time.
I beleive they are all allocated/destructed in the same module, but they do all use the same Multithreaded DLL
At the moment were suspecting a hidden shared variable somewhere and combing the entire application for any file scope variables that should have been declared const which arn't.
1 suspect vector of objects has been found but that was before lunch and hasn't been fully investigated yet.
If you vote me down, my score will only get lower
|
|
|
|
|
My gut instinct is buffer overruns. Get an eval copy of BoundsChecker and run your stuff through it.
(And if doing a lot of new/delete, consider going to fixed, preallocated buffers.)
Anyone who thinks he has a better idea of what's good for people than people do is a swine.
- P.J. O'Rourke
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
