The compiler won't cache the result of size() if it's possible for it to change in the loop. If an optimization isn't applicable to a piece of code, I can't imagine any sane optimizing compiler attempting to apply it anyway.
The compiler won't cache the result of size() if it's possible for it to change in the loop. If an optimization isn't applicable to a piece of code, I can't imagine any sane optimizing compiler attempting to apply it anyway.
Cogman
Lifer
- Sep 19, 2000
- 10,280
- 131
- 106
Who said anything about thread safety? You said the increment operator compiled down to more then one operation in c++, I said it didn't. incl is an x86 command, all x86 processors have it.
The only way I could see the inc operator being more then one operation is if it is replacing a register before it is incrementing. Then I could see it being five ops, IE
Pushl %eax
movl (%edx + 4), %eax
incl %eax
movl %eax, (%edx + 4)
popl %eax
However, if thats the case, then just about any operation will potentially take up to 5 operations.
Cogman
Lifer
- Sep 19, 2000
- 10,280
- 131
- 106
Not true, I just did a compiled test. While there isn't a function call (it is inlined on an -O2 optimization with gcc) the size is being checked every time, even though it doesn't change.
However, I do stand corrected about the rawbob thing, I could have sworn I saw a speed boost by doing it, but it had no effect. Live and learn
You are both correct. Processors always follow the fetch, operate, store model of computation. The true number of operations would depend on how well the compiler optimizes register access. In a worst case the ++ operator could take multiple operations to execute. Doing an increment in a single operation is not guaranteed.
That said, I think there is a general misunderstanding about the difference between atomic and non-atomic operations and how that relates to thread safety. In a multi-threaded environment you can't guarantee that your fetch-operate-store model will not be interrupted by another process. Say this happens:
Thread 1: Copy A to B
Thread 1: Decr B
Thread 2: Copy A to B
Thread 2: Incr B
Thread 2: Save C to A
Thread 1: Save B to A
Thread 2 will have no idea what value is stored and weird things will happen. This wouldn't happen if the operation was atomic. Atomic operations are guaranteed to be uninterrupted by the processor. So when he brought up the issue of thread safety it was implicit that the problem was with the operation taking multiple instructions.
This is an interesting thread. Its been ages since I studied computer architecture.
1. Increment is not an atomic operation unless specified (ie. with the lock prefix on Intel archs). The Bakery Algorithm is a classic example of how to work-around that without using atomic operations.
2. C is call-by-value therefore it doesn't matter if the for-loop increments the value of 'i' because the integer value was already copied in the call to createthread().
2. C is call-by-value therefore it doesn't matter if the for-loop increments the value of 'i' because the integer value was already copied in the call to createthread().
- Mar 31, 2003
- 11,679
- 0
- 81
Real quick - I don't want to get too far away from SIMD/SMT discussion; however, Cogman, your second operation confuses me a little bit.
Is calling the cos() method and the other vector methods more costly than allocating space (and then deallocating space) on the run-time stack for all of those double values?
Also - others suggested something other than a vector<vector<double>> type. Does someone have any other suggestions? There are a ton of these arrays (Both local and global via public class) which all need to be saved to a memory address that is passed into this subroutine (multiple returned values).
I originally tried using a vector theVecArray[3] - an array of vectors, but it was too hard to pass or manage between functions.
Furthermore, since I am dealing with 2D vectors, I need to instantiate the rows of the vectors in advance. It seemed to me as I was doing this that I was doing it in, quite possibly, the least efficient way possible (This is 1 example):
I'm learning a TON in this thread - thank you for any advice or pointers you can give.
Thanks,
-Kevin
Is calling the cos() method and the other vector methods more costly than allocating space (and then deallocating space) on the run-time stack for all of those double values?
Also - others suggested something other than a vector<vector<double>> type. Does someone have any other suggestions? There are a ton of these arrays (Both local and global via public class) which all need to be saved to a memory address that is passed into this subroutine (multiple returned values).
I originally tried using a vector theVecArray[3] - an array of vectors, but it was too hard to pass or manage between functions.
Furthermore, since I am dealing with 2D vectors, I need to instantiate the rows of the vectors in advance. It seemed to me as I was doing this that I was doing it in, quite possibly, the least efficient way possible (This is 1 example):
I'm learning a TON in this thread - thank you for any advice or pointers you can give.
Thanks,
-Kevin
degibson
Golden Member
- Mar 21, 2008
- 1,389
- 0
- 0
This thread has grown enormously in size, so I can't do my usual due diligence this morning and read everything. Sorry. However:
1) x++ is not safe to use on a shared variable without synchronization.
2) The bakery algorithm will not succeed on modern hardware with shared memory. It will succeed among timeshared processes, but it fails under weaker consistency models without fences.
3) OP: If you're going to restructure your code for threading, get rid of calls to push_back as those create loop-carry dependencies. Instead, resize() the vector before you start operating on it instead of adding things to it on the fly.
4) OP: vector<vector>> is fine once they are loaded. As you already know, they can be a pain to load in the first place.
5) OP: Listen to cogman's post about GetTickCount(). Do not ignore the need to profile where the time goes in your application.
1) x++ is not safe to use on a shared variable without synchronization.
2) The bakery algorithm will not succeed on modern hardware with shared memory. It will succeed among timeshared processes, but it fails under weaker consistency models without fences.
3) OP: If you're going to restructure your code for threading, get rid of calls to push_back as those create loop-carry dependencies. Instead, resize() the vector before you start operating on it instead of adding things to it on the fly.
4) OP: vector<vector>> is fine once they are loaded. As you already know, they can be a pain to load in the first place.
5) OP: Listen to cogman's post about GetTickCount(). Do not ignore the need to profile where the time goes in your application.
- Mar 31, 2003
- 11,679
- 0
- 81
Right now, on a 3x500,000 vector<vector<double>> (I filled it from [trigfunction](0:499,999) ) I used the QueryPerformanceCounter() to determine the run time of my simple CrossProduct function.
I call this function 5 times in my test and I got back:
37.35ms
37.61ms
37.13ms
37.35ms
36.98ms
I am trying to figure out how I can manage to write this function using compiler intrinsics or inline assembly.
-Kevin
- Dec 11, 1999
- 16,328
- 4,003
- 75
Looking through what I used last time I used compiler intrinsics, it looks like the PDFs on this page were my main guide, followed by Intel's manuals.
Stack allocation is a simple matter of adding to a stack pointer register, SPX, if I recall. The data might even get stored in registers, if there are enough. (8 registers, 6 values, not including temp calculation values - the compiler probably can't do it but you might be able to by hand.) Alternatively, you could try something like this, though I don't use C++ much, so I have no idea if my syntax is correct:
Stack allocation is a simple matter of adding to a stack pointer register, SPX, if I recall. The data might even get stored in registers, if there are enough. (8 registers, 6 values, not including temp calculation values - the compiler probably can't do it but you might be able to by hand.) Alternatively, you could try something like this, though I don't use C++ much, so I have no idea if my syntax is correct:
Edit: Oh, so that's what's with the space before the i.
Cogman
Lifer
- Sep 19, 2000
- 10,280
- 131
- 106
Ok, so with the code you provided, on my Q6600 and default settings I was able to run it in 300ms on average, after making the following changes, I dropped it down to an average of about 120 ms. You'll probably have to change some things around, however, this is my final optimized code. (for the cross product).
The biggest speed impact came from using resize instead of push_back every time. that cut about 100ms off of the time. the double vector trick cut off about 40ms, and replacing the return with a pass by reference output variable cut off the remaining 40ms. You could probably shave a few more instructions off if you make the assumption that the first dimension of the vector will always be 3.
I'll see if I can't get a working threaded example for you next
The data set was just rand() cast into a double 200000 times for the all 3 of the dimensions. Timing was done outside of the function.
The biggest speed impact came from using resize instead of push_back every time. that cut about 100ms off of the time. the double vector trick cut off about 40ms, and replacing the return with a pass by reference output variable cut off the remaining 40ms. You could probably shave a few more instructions off if you make the assumption that the first dimension of the vector will always be 3.
I'll see if I can't get a working threaded example for you next
The data set was just rand() cast into a double 200000 times for the all 3 of the dimensions. Timing was done outside of the function.
- Mar 31, 2003
- 11,679
- 0
- 81
Well I found that doing a resize() was more expensive than using a for loop. I don't quite understand why though - in my mind it should be shorter. I just eliminated the push_back though which saved 10ms off the aforementioned times.
I also found that if you do a .reserve() it shaves off a small amount of time as well.
Ken - that website is amazing. I am reading through every bit of that code that I can get my hands on. If I can get my cross product function running with Compiler Intrinsics, the Project Manager has given me approval to present my findings and my division may, perhaps, switch to my code (I'm only an intern too )
I can't thank all of you enough for this thread - I can't begin to describe how much I have learned thus far. Not to mention the number of resources that I am not reading through.
-Kevin
I also found that if you do a .reserve() it shaves off a small amount of time as well.
Ken - that website is amazing. I am reading through every bit of that code that I can get my hands on. If I can get my cross product function running with Compiler Intrinsics, the Project Manager has given me approval to present my findings and my division may, perhaps, switch to my code (I'm only an intern too
)I can't thank all of you enough for this thread - I can't begin to describe how much I have learned thus far. Not to mention the number of resources that I am not reading through.
-Kevin
Cogman
Lifer
- Sep 19, 2000
- 10,280
- 131
- 106
Ok, be forwarned that a ton of code is following.. Also note that the gains I noticed where minimal at best. This is your warning.
I managed to thread the cross product, however, there where no noticed speed increases at 200,000 units. So I tested it with 200,000,000 units. The difference was still minimal (1200 ms vs 1300 ms). Either way, this is what I came up with (I haven't check the results, but I believe they should be correct)
Again, gains where minimal. I suspect that thread creation is eating up a fair amount of the actual gains. A thread pool might help to mitigate that loss.
I didn't employ any sort of mutex/semaphore as none of the threads should be modifying the same data at the same time. (if they do, that data is invalid)
BTW, are you using compiler optimizations? If not, turn them on. That might cause you to see some nifty speed boosts.
I managed to thread the cross product, however, there where no noticed speed increases at 200,000 units. So I tested it with 200,000,000 units. The difference was still minimal (1200 ms vs 1300 ms). Either way, this is what I came up with (I haven't check the results, but I believe they should be correct)
Again, gains where minimal. I suspect that thread creation is eating up a fair amount of the actual gains. A thread pool might help to mitigate that loss.
I didn't employ any sort of mutex/semaphore as none of the threads should be modifying the same data at the same time. (if they do, that data is invalid
)BTW, are you using compiler optimizations? If not, turn them on. That might cause you to see some nifty speed boosts.
- Mar 31, 2003
- 11,679
- 0
- 81
Optimizations are indeed turned on. They make a rather large difference actually - and this is the MS VC++ Compiler. I would imagine the Intel or GNU compiler would work even better.
I am really struggling at writing code that would create the cross product in SIMD though. I could have sworn that there was a SIMD instruction explicity for the cross product; however, I can't find it.
-Kevin
I am really struggling at writing code that would create the cross product in SIMD though. I could have sworn that there was a SIMD instruction explicity for the cross product; however, I can't find it.
-Kevin
degibson
Golden Member
- Mar 21, 2008
- 1,389
- 0
- 0
Well, there is the problem that your data type is double. SIMD works a lot better when your native data type is small (e.g., char, short, or even float). Many datapaths are only 64 or 128-bit in the first place, and on a 128-bit datapath you will not get more than 2x the FP computational throughput, ignoring all the other overheads. Depending on your platform, you might even be limited more by memory bandwidth.
If this is really critical code, you might try a modern GPU. They recently introduced support for double data types (though not all are IEEE compliant double types). However, if the whole computation is just a cross-product, its probably not worth the effort of streaming the data out over PCIe and then back again.
- Mar 31, 2003
- 11,679
- 0
- 81
Well this is one of many critical operations. From what I can understand, the code this concerns uses a lot of trig operations over vectors, lots of vector computation.
We use doubles simply because 6 decimal places of precision is not enough. The numbers are certainly small enough to be floats, but we need somewhere in the neighborhood of 10 decimals of precision.
If there is someway we can get this precision with SP Floating Points, I am more than willing to research it.
-Kevin
Cogman
Lifer
- Sep 19, 2000
- 10,280
- 131
- 106
Well, if you interested, I've made an intrinsic SSE3 version of the cross product. However, the results are horrible (they did verify that thread creation was the major slowdown though
)For a single threaded app, the code doubled the time it takes to do a cross multiply. the multithreaded version absorbed the difference with no problem.
Just to show how I did it (may not be the best way.) here is the code I used.
Maybe you could use arrays and allocate with new/delete instead of using vectors. It might lower overhead.
- Dec 11, 1999
- 16,328
- 4,003
- 75
I've been working on my own SSE2 (don't think it needs SSE3!) version of the cross multiply code. One thing I've found is that a Core 2 is limited by the number of memory reads it can do: one per cycle, with latency 2. Assuming vectors work like arrays, reading vector1[0][ i] requires 3 reads, or 6 cycles; but it can be interleaved with another read so two of those "only" take 7 cycles. That means the double assignments inside these loops take at least 21 cycles.
Again, I'm not sure about vectors; but if the outer vectors contained arrays of doubles, and you did:
double *vector10 = vector1[0];
double *vector20 = vector2[0];
double *vector11 = vector1[1];
double *vector21 = vector2[1];
double *vector12 = vector1[2];
double *vector22 = vector2[2];
before the loop, that would save two cycles on each load, making it take just 15 cycles. Doing the same for out[][] might help, too.
Cogman, could you please post your testing code, so I can compare what I'm working on with your results?
Again, I'm not sure about vectors; but if the outer vectors contained arrays of doubles, and you did:
double *vector10 = vector1[0];
double *vector20 = vector2[0];
double *vector11 = vector1[1];
double *vector21 = vector2[1];
double *vector12 = vector1[2];
double *vector22 = vector2[2];
before the loop, that would save two cycles on each load, making it take just 15 cycles. Doing the same for out[][] might help, too.
Cogman, could you please post your testing code, so I can compare what I'm working on with your results?
- Mar 31, 2003
- 11,679
- 0
- 81
Well, I am trying to implement the cross product by swapping vectors, but with a double it messes things up a bit.
Is there any way to extract more decimals of precision out of a single precision floating point? If I could use an SP float, I could extract, theoretically, 4x the throughput. I could also store all 3 variables into the register instead of using 2 registers to store the first 3.
This is what I am working with right now:
V1 <3xn>:
x1 x4
x2 x5
x3 x6
V2 <3xn>:
y1 y4
y2 y5
y3 y6
If I do a read into a standard _m128 data type from vector<vector<double>> array, I should grab x1, x2 and y1, y2. In order to do the cross product using swaps I have to waste 1/2 of an _m128 read in.
_m128 = *vector1
_m128 = *vector2
_m128 = ++*vector1
_m128 = ++*vector2
That would mean x3 and y3 are read in 2x (or if I increment them 2x - more would be read in).
From what I have been reading - using the swap calls and then multiplying _m128's values in their entirety at once is the most efficient way.
If someone knows anyway to grab more decimals of precision using a float instead of "wasting" a double, I am all ears.
-Kevin
Is there any way to extract more decimals of precision out of a single precision floating point? If I could use an SP float, I could extract, theoretically, 4x the throughput. I could also store all 3 variables into the register instead of using 2 registers to store the first 3.
This is what I am working with right now:
V1 <3xn>:
x1 x4
x2 x5
x3 x6
V2 <3xn>:
y1 y4
y2 y5
y3 y6
If I do a read into a standard _m128 data type from vector<vector<double>> array, I should grab x1, x2 and y1, y2. In order to do the cross product using swaps I have to waste 1/2 of an _m128 read in.
_m128 = *vector1
_m128 = *vector2
_m128 = ++*vector1
_m128 = ++*vector2
That would mean x3 and y3 are read in 2x (or if I increment them 2x - more would be read in).
From what I have been reading - using the swap calls and then multiplying _m128's values in their entirety at once is the most efficient way.
If someone knows anyway to grab more decimals of precision using a float instead of "wasting" a double, I am all ears.
-Kevin
- Mar 31, 2003
- 11,679
- 0
- 81
Well I just had an idea which may end up taking more time overall:
When I read the values into the _m128 data type if I do:
_m128 = (float)(*vector1 * 10000)
I would achieve 10 decimals of precision and still be well within the bounds of a 32bit SP float value.
Then before I pass the value back to the caller, I simply cast it as a double and then divide by 10000.
That would allow me to fit 4 values in each SSE2 register and thereby move through the vector much faster in my mind. I'm not sure how much (or if my cast will work) overhead in involved in my multiply and cast though.
-Kevin
When I read the values into the _m128 data type if I do:
_m128 = (float)(*vector1 * 10000)
I would achieve 10 decimals of precision and still be well within the bounds of a 32bit SP float value.
Then before I pass the value back to the caller, I simply cast it as a double and then divide by 10000.
That would allow me to fit 4 values in each SSE2 register and thereby move through the vector much faster in my mind. I'm not sure how much (or if my cast will work) overhead in involved in my multiply and cast though.
-Kevin
The precision of a float is fixed. You will not gain more precision by multiplying it by 10,000; all that will do is move some of the lost precision to the left of the decimal point.
I have great difficulty believing that this function is the performance bottleneck of your application. Have you done any profiling yet, or are you just assuming that this needs to be aggressively optimized?
Even an SSE2 implementation isn't that much faster:
It takes about 60-70% of the time of the original code, but it requires the vector to be 16-byte aligned (although that's the default for MSVC++'s "new") and its size to be a multiple of two. Meanwhile, the majority of the time in the function is eaten by the resize of the vectors, since vector default initializes every element. You would see much greater performance gains by simply using a container that allows for uninitialized values; one possibility may be to write an allocator that does nothing in its "construct" function.
But again, I imagine that there are other areas in the program that can be more easily optimized for much greater gains. For example, copying one of these humongous vector<vector<>>'s would be horribly slow, so ensure that you never return one by value or assign to a new variable.
With 2,000,000 elements, this cross-product loop (excluding the vector resize) takes only ~65 ms (~41 with SSE2); unless you're calling it hundreds or thousands of times, that's pretty insignificant.
I have great difficulty believing that this function is the performance bottleneck of your application. Have you done any profiling yet, or are you just assuming that this needs to be aggressively optimized?
Even an SSE2 implementation isn't that much faster:
It takes about 60-70% of the time of the original code, but it requires the vector to be 16-byte aligned (although that's the default for MSVC++'s "new") and its size to be a multiple of two. Meanwhile, the majority of the time in the function is eaten by the resize of the vectors, since vector default initializes every element. You would see much greater performance gains by simply using a container that allows for uninitialized values; one possibility may be to write an allocator that does nothing in its "construct" function.
But again, I imagine that there are other areas in the program that can be more easily optimized for much greater gains. For example, copying one of these humongous vector<vector<>>'s would be horribly slow, so ensure that you never return one by value or assign to a new variable.
With 2,000,000 elements, this cross-product loop (excluding the vector resize) takes only ~65 ms (~41 with SSE2); unless you're calling it hundreds or thousands of times, that's pretty insignificant.
- Dec 11, 1999
- 16,328
- 4,003
- 75
Well, I figured out why none of my ideas were working. I'm using gcc 4.3.3, and gcc is too smart for me! Once I compiled with gcc -S to look at the assembly source, I found that it (1) pre-calculates things like out[1], so out[1][ i] is only two operations, and (2) it found the possibility for SIMD all by itself and inserted it automatically!
I'm going to try OpenMP next...
Edit: OpenMP is just slightly faster, but uses much more CPU. To enable it, #include <omp.h>, link with its library, and make the central loop look like the following:
I'm going to try OpenMP next...
Edit: OpenMP is just slightly faster, but uses much more CPU. To enable it, #include <omp.h>, link with its library, and make the central loop look like the following:
- Mar 31, 2003
- 11,679
- 0
- 81
So if I had 1.23456789, obviously in a float only 1.234567 would be accurate. So even if I multiplied by 100 resulting in a double with 123.456789 and then casted it to a float, it would still not be accurate?
Well in the program/project I am working on, it more than likely isn't the problem. Cross product; however, is one of the bottlenecks for the code that my boss and others use elsewhere. I haven't actually seen the code as it is in the TS:SCI area (thus someone would have to bring it out to me).
As for the profiler, I actually haven't run the code through a profiler yet for the simple fact that, in VS2008, the profiler is only available in 2 version. My company owns VS2008 Professional which does not include it.
Well the code, running on multiple computers normally takes a weekend to run through the datasets that they task it with. So saving 60-70% on one part of the program that is called extensively should be at least somewhat beneficial.
As for writing our own allocater - honestly that is above me. If you point me to some code guides that explain the concert I would happily read over it, learn it, and try my hand at it.
Well, in my code, I am in control of the array in question; however, in others code, it is not in my control and used a little too extensively to just up and switch unless I can prove huge gains.
Array sizes, from what I am told, are in the 3x(x)00,000's. There are, again from what I understand, many of these per data set, so there should be a least a decent gain.
--------------------
Having said that, the only other information I know at this point is that trig functions are called for each element in the array currently. I assume if I were to read in the values into the _m128 data type, call the crossproduct and loop that way, I would save time?
--------------------
gcc compiler is so great
. I think they switched to the Intel compiler briefly and, while it was faster, it also broke some things. So, until someone rewrites that program, we are stuck with the MS (<-bleh) compiler.Yea, I was looking at that as well. I'll have to investigate the results when paired with the SSE code.
Thanks for all the help guys. As I said, I have learned a TON from this thread and am still eagerly burning through all documentation on both concepts that I can
-Kevin
Floats aren't like that, they are like scientific notation. So hypothetically if 1.23456789 is rounded to 1.234567, then in float it would be 1.234567 x 10^0. If you multiply by 10,000, you get 1.234567 x 10^5, so no, you don't get anything with that, you don't get a fixed number of digits to the right of the decimal point, that's why it's called a floating point. I'm just using base 10 for the idea here, the base is actually 2 so the representation is different.
TRENDING THREADS
-
Discussion Zen 5 Speculation (EPYC Turin and Strix Point/Granite Ridge - Ryzen 9000)- Started by DisEnchantment
- Replies: 20K
-
Discussion Intel current and future Lakes & Rapids thread- Started by TheF34RChannel
- Replies: 23K
-
Discussion Intel Meteor, Arrow, Lunar & Panther Lakes Discussion Threads
- Started by Tigerick
- Replies: 12K
-
Discussion Speculation: Zen 4 (EPYC 4 "Genoa", Ryzen 7000, etc.)- Started by Vattila
- Replies: 13K
-
Facebook
Twitter