|
|
This looks like homework. You need to be able to learn the topics that will let you do this assignment yourself.
|
|
|
|
|
I expect so. It's not particularly complicated.
"WPF has many lovers. It's a veritable porn star!" - Josh Smith As Braveheart once said, "You can take our freedom but you'll never take our Hobnobs!" - Martin Hughes.
My blog | My articles | MoXAML PowerToys | Onyx
|
|
|
|
|
letaya wrote: can i get a program code
certainly you can
Yusuf
Oh didn't you notice, analogous to square roots, they recently introduced rectangular, circular, and diamond roots to determine the size of the corresponding shapes when given the area. Luc Pattyn[^]
|
|
|
|
|
letaya wrote: can i get a program code
You may also try to code yourself it... 
If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler.
-- Alfonso the Wise, 13th Century King of Castile.
This is going on my arrogant assumptions. You may have a superb reason why I'm completely wrong.
-- Iain Clarke
[My articles]
|
|
|
|
|
New Symbian executable uses Deflate algoritm for compression.
Where can i get help/algo/source related to this algorithm?
Thanks in advance.
|
|
|
|
|
Google 
Regards
David R
|
|
|
|
|
K. Sushilkumar wrote: Where can i get help/algo/source related to this algorithm?
Oh, many places. Books, School/College/Uni, TWWWW (The Whole World Wide Web)
Yusuf
Oh didn't you notice, analogous to square roots, they recently introduced rectangular, circular, and diamond roots to determine the size of the corresponding shapes when given the area. Luc Pattyn[^]
|
|
|
|
|
Hi all,
probably not the right forum to post such a question.
But I could not find any more appropriate.
It is a general question about new processors.
Do they still support SSE instructions ? I suppose so.
Is it relevant to write new programs that exploit both data parallelism (i.e. SSE) and multi-threading (multi-processors) ?
Does anyone know the strategy of parallel compilers like Intel C++ compiler or Visual C++ : do they compile seamlessly into SSEx instructions ?
Thanks in advance,
Jean-Marie Epitalon
|
|
|
|
|
Processors must be backward-compatible, so each processor supports the extensions of the previous ones.
Here are some SSE-related links I've found (the Intel link describes their C/C++ compiler):
http://www.tommesani.com/Docs.html
http://www.codeproject.com/KB/recipes/BubbleSortWithSSE2.aspx
http://softwarecommunity.intel.com/isn/downloads/softwareproducts/pdfs/347602.pdf
http://www.hayestechnologies.com/en/techsimd.htm#SSE2
|
|
|
|
|
Thanks Alan for your answer.
I did also some research on the internet in the mean time.
I can answer to my own question :
yes, Intel C++ compiler supports SSE instructions. It parallelizes and compiles directly some code into SSE instructions in a process called autovectorization.
For those that might be interested, follow the link "Product in depth" in the page :
[^]
Microsoft Visual Studio 2008 does not provide that.
Jean-Marie
|
|
|
|
|
epitalon wrote: Microsoft Visual Studio 2008 does not provide that.
Rather than ask the compiler to guess what type of calculation you're performing and hope it is able to optimize it for you, programmers should just stop being lazy and do it properly: align your variables/structures to 16-byte boundaries, parallelize your algorithm (fine-tune it) by hand, and then use compiler intrinsics (supported by MS, Intel and GNU compilers). Better yet, use something like SSEPlus so that your app chooses the most appropriate instruction set to use for the CPU its running on. That way you can be sure you're getting the best performance for speed-sensitive calculations.
link[^]
|
|
|
|
|
Thanks Mike for your answer.
I understand that I don't need the compiler to decide when to parallelize for me. But I don't know the syntax I should use to program parallel code and compile it into SSE instructions.
By the way, I have Visual Studio 2005. Is the feature you are talking about availlable in VS2005 or should I upgrade to VS2008 ?
What are the "compiler intrinsics" you are talking about ?
Regards,
Jean-Marie
|
|
|
|
|
epitalon wrote: What are the "compiler intrinsics" you are talking about ?
That wasn't me, that was a quote from the discussion I provided the link to. You should follow the links that people provide in replies.
Here is another[^]
|
|
|
|
|
can you explain to me how to calculate the offset in row-major and column-major order when there are 3 or 4 dimensions involved?
|
|
|
|
|
Hi,
I can't explain it any better than this[^].
Luc Pattyn [Forum Guidelines] [My Articles]
- before you ask a question here, search CodeProject, then Google
- the quality and detail of your question reflects on the effectiveness of the help you are likely to get
- use the code block button (PRE tags) to preserve formatting when showing multi-line code snippets
|
|
|
|
|
the formula given on that page doesn't work right.. Especially if each item takes up more than one byte or if there are more than two dimensions... My book does it a totally different way, I just wish there was some kind of chart that I could check to make sure my program was calculating the row major / column major order correctly because right now i think i have it working but i'm not sure if my logic is correct, i need something to check it with!
|
|
|
|
|
OK, for an array with dimensions (d0, d1, ... d8, d9) the offset of element (e0, e1, ... e8, e9) is either
e9 + d9*( e8 + d8*( .... + d2*( e1 + d1 * e0)...)) which does not use d0
or
e0 + d0*( e1 + d1*( .... + d7*( e8 + d8 * e9)...)) which does not use d9
depending on the scheme you want to use
AFAIK that corresponds to the formulae in Wikipedia.
Warning for VB users: the dimensions indicate the number of elements in a rank, not the maximum index
Luc Pattyn [Forum Guidelines] [My Articles]
- before you ask a question here, search CodeProject, then Google
- the quality and detail of your question reflects on the effectiveness of the help you are likely to get
- use the code block button (PRE tags) to preserve formatting when showing multi-line code snippets
|
|
|
|
|
I have a MASM routine that generates assembly code to implement a Quicksort. All is working, including support for embedded keys in records, support for signed/unsigned, big-endian/little endian, keys of BYTES/WORDS/DWORDS/FLOATS/DOUBLES/EXTENDED_FLOATING, null terminated strings for BYTES or WORDS (element count=0), multiple elements for any data type (counts from 1-2048), multiple data types for a secondary key including its use as a tie-breaker for equal primary keys to make the QuickSort Stable. I will add support for MMX and XMM keys, but the current quest is to add the capability to declare Ascending or Descending in any mixture for either the primary key or for the secondary key (one can be ascending, the other descending, or both the same - either ascending or descending). I could just invert the conditional transfers and keep the comparison order the same, or invert the comparison order and keep the conditional transfers the same, or finally, just swap the indexes at entry and restore them at exit (XCHG) and keep all of the rest of the extensive code the same.
Note, the source code is extensive, but the macro invocation conditionally assembles only what is required and there is not a lot of checking what should be done next. Inserting the XCHG's for each comparison would add code (small) and execution cycles (small), but the compare logic is the highest use code of the whole sort. Conditionally assembling a version for ascending order and a different version for descending order is basically a copy and paste with an exchange of either the indices (and has no extra code or cycles), or a change of the conditional transfers. It seems that maintaining the two copies in parallel might be dangerous - fixes to one set of code would have to always be applied to the other set, and we all know how often that strategy fails - duplicate versions aren't!
So the question is, should I swap the indices and which way should I do this - swap the indices or swap the comparison order, or should I create two versions, one for ascending and the other for descending?
Please feel free to jump in with both feet and kick up a little dust, but this is a Quicksort so I don't want to hear about C++ or C# and overloaded operators with all of the bloat that goes along with HLL.
Hmm, I just thought of a way to allow both the primary key and the secondary key to have null terminated strings. The lowest offset of ether key has to end at the higher offset, and the highest offset has to end at the end of the record. More goodie to add, but carefully since the secondary key logic was a copy of the primary key logic, with different parameters, and I already stripped out the support for a null terminated string (more than one line). Remember that bit about duplicate versions that aren't? Oh, well!
Dave.
|
|
|
|
|
Hi,
Wow. Quite a question.
not sure why you are doing all this in assembly, but whatever the language, this would be my approach:
for each comparison, calculate a difference, which is negative if object1<object2, zero if equal, and positive-non-zero when object1>object2
then multiply that difference by a factor which is +1 for ascending and -1 for descending. The result indicates precede (negative), don't know (zero), or follow (positive-non-zero).
When you have multiple sort criteria, handle the primary one first, if that results in "don't know", continue with the next criterion.
[EDITED because of HTML eater]
Luc Pattyn [Forum Guidelines] [My Articles]
- before you ask a question here, search CodeProject, then Google
- the quality and detail of your question reflects on the effectiveness of the help you are likely to get
- use the code block button (PRE tags) to preserve formatting when showing multi-line code snippets
modified on Tuesday, April 7, 2009 9:14 PM
|
|
|
|
|
Luc,
Thank you for the reply.
And I was worried about adding two XCHGs, and you want me to put in a MUL? OMG!
Actually, you can get the same effect for descending by just changing the ordering of the compare arguments, i.e. compare object2 to object1. This is exactly what C++ does for an IF, it keeps your comparison code (i.e. >=, generates a jae or jge depending on sign) but reverses the compared values and skips around the body of the IF if it is not >=. This, however, leaves the code much different than the code for an ascending sort, somewhat harder to maintain and enhance. That was why I was thinking about XCHG'ing the indices and keeping the same code for both sort types.
Another difficulty with that approach is that floating compares do not affect the usual flags, only the flags in the FPU. You have to extract the FPU flags and make special compares to effect a ja or a jb, and the tests are of a TEST nature with a je or jne, not a ja or jb. I have all of this working, and I am now testing the tie-breaker/secondary_key code.
Dave Augustine.
|
|
|
|
|
if you don't want to multiply by +1/-1 you can conditionally negate the difference, that's bound to be cheaper than two conditional XCHG. However a single MUL is probably the fastest on any Pentium or better thanks to having separate integer units and needing no unpredictable change of program flow.
An alternative is self-modifying code where you execute either a NOP or a NEG on diff. 
Luc Pattyn [Forum Guidelines] [My Articles]
- before you ask a question here, search CodeProject, then Google
- the quality and detail of your question reflects on the effectiveness of the help you are likely to get
- use the code block button (PRE tags) to preserve formatting when showing multi-line code snippets
|
|
|
|
|
Luc,
Thank you again. When I get done, I will post (if not too big) or send you some zips of an ascending and a descending DWORD sort and the same for float - just the actual quick sort code.
Dave.
|
|
|
|
|
I have completed development on my Quicksort. The following is the timing for the sort using just an array of DWORDS. The rest of the tests work as planed, ascending/descending, signed/unsigned, big-endian/little-endian, two different sort keys allowed, BYTES/WORDS/DWORDS/Floats/Doubles/extended_floating, BYTE or WORD null terminated strings, up to 2048 elements per key, fully automated test and tracing environment to verify results.
Do you have a feel for what a good timing benchmark might be for this size of a sort?
The following timings are only for the actual sorting, not the setup. The data
is prepared, start time taken, sorted, end time taken, time difference is
accumulated, loop back 1023 more times.
The random data originally was created by randomly selecting a number from the
set, saving the number, shrinking the set, and recalculating a new random number
on a decremented range. This was taking too long to shrink up a 1024*1024 DWORD
buffer for each extraction. The method was changed to just create a random
number in the range of 0 to ((1024*1024)-1), save the random number, decrement
the range, and calculate another random number for the decremented range. Since
there are potentially many duplicates, and probably not all numbers are present,
the checking was changed from comparing the sorted array against a known
ascending or descending array, to individually comparing each DWORD pair
(comparing element n to element n+1) and verifying that it is not above (if an
ascending sort) or not below (if a descending sort).
Note: The sort completed with only a 4096 byte stack, sorting 1024*1024 DWORDS.
Building Ascending data.
Building Descending data.
1024*1024 Ascending DWORDS sorted 1024 times Ascending, time in msec: 37144, good compare. 36.27 msec/iteration.
1024*1024 Ascending DWORDS sorted 1024 times Descending, time in msec: 46130, good compare. 45.05 msec/iteration.
1024*1024 Descending DWORDS sorted 1024 times Ascending, time in msec: 47689, good compare. 45.57 msec/iteration.
1024*1024 Descending DWORDS sorted 1024 times Descending, time in msec: 53870, good compare. 52.61 msec/iteration.
Building Random data.
1024*1024 Random DWORDS sorted 1024 times Ascending, time in msec: 158389, good compare. 154.67 msec/iteration.
1024*1024 Random DWORDS sorted 1024 times Descending, time in msec: 141898, good compare. 138.57 msec/iteration.
I do have code samples (.LST output) if you are interested.
Dave.
|
|
|
|
|
I don't fully understand your test cases, however here are two questions you can ask yourself:
1. why is there a big difference between "Ascending DWORDS sorted 1024 times Ascending" and "Descending DWORDS sorted 1024 times Descending"?
2. how does the timing compare with a regular quicksort as is offered in some libraries?
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
