NO

Author Topic: frequency of ints in huge array  (Read 8383 times)

Offline jj2007

  • Member
  • *
  • Posts: 441
Re: frequency of ints in huge array
« Reply #30 on: July 05, 2014, 07:41:09 PM »
I got only an empty dialog with 'last chance ...'

Sorry... the setup is a bit mean in that it requires that Masm32 is installed - the reason being that an assembler library can do harm in the wrong hands. That's why there is this little obstacle.

Anyway, I'll see if I can provide you a *.lib file with the integer sort.

Offline JohnF

  • Member
  • *
  • Posts: 1114
    • http://www.johnfindlay.plus.com/
Re: frequency of ints in huge array
« Reply #31 on: July 05, 2014, 07:49:53 PM »
Here is Pelle's OPenMP quick_sort (SORT_METHOD  3, fastest) now working with unsigned int.

Here it completes a 20000000 sort in 1.35 secs.

For anyone but Czerny, that is.

John
« Last Edit: July 05, 2014, 07:52:27 PM by JohnF »

Offline jj2007

  • Member
  • *
  • Posts: 441
Re: frequency of ints in huge array
« Reply #32 on: July 05, 2014, 08:53:33 PM »
That is pretty fast! I managed to add the sort to a little library (attached), here is a test:

#include <stdio.h>
#include <windows.h>      // MessageBox
#pragma warn(disable:2216)         // retval never used
#pragma warn(disable:2118)          // para not referenced
#pragma comment(lib, "\\Masm32\\MasmBasic\\Res\\xTimer.lib")      // adjust to your path

extern void      __cdecl xTimerStart(void);            // uses QPC and returns
extern int      __stdcall xTimerEnd(void);            // microseconds

extern int __stdcall MbArrSort(int*pStart, int elements, int pKey, int mode);        // MasmBasic ArraySort

int main(int argc, char* argv[]) {

  int i, MyArr[6]={123, 789, 456, 111, 333, 222};

  xTimerStart();
  // mode=size (4, 8 ) or (32 and real) or (64 and ascending)
  MbArrSort(&MyArr[0], 6, 0, 4+64);      // size 4, integer, ascending
  printf("Sorting took %i microseconds\n", xTimerEnd());


  for ( i=0; i<6; i++ ) printf("%i\t%i\n", i, MyArr[ i ] )

  return MessageBox(0, "Sorted?", "Confirm:", MB_YESNO | MB_ICONINFORMATION);
}

What is rather odd is that the linker can't find MbArrSort unless xTimerStart is also being used. I often call assembler routines from C, it always works, and sort and timer are not connected in any way, so for the time being it's a mystery...

MbArrSort handles also QWORD, float and double arrays, see the mode comment.
« Last Edit: July 05, 2014, 08:58:19 PM by jj2007 »

Offline JohnF

  • Member
  • *
  • Posts: 1114
    • http://www.johnfindlay.plus.com/
Re: frequency of ints in huge array
« Reply #33 on: July 06, 2014, 07:50:26 AM »
POLINK: fatal error: File not found: '\masm32\lib\masm32.lib'.

masm32.lib   
gdi32.lib   
user32.lib   
Comctl32.lib   
Comdlg32.lib   
shell32.lib   
oleaut32.lib   
ole32.lib   
msvcrt.lib   
masmbasic.lib   

You asked if I were disgusted by asm, well I'm getting close!

John
« Last Edit: July 06, 2014, 08:19:51 AM by JohnF »

Offline jj2007

  • Member
  • *
  • Posts: 441
Re: frequency of ints in huge array
« Reply #34 on: July 06, 2014, 12:40:14 PM »
POLINK: fatal error: File not found: '\masm32\lib\masm32.lib'.

John,

It seems there are some dependencies that require a Masm32 installation - sorry for that.

In any case, Pelle's quicksort is probably fast enough. My sort is a radix sort, it is faster than the Masm32 library quicksort if the integer range is not fully used, but somewhat (10%?) slower if the full 32-bit are present in the array.

Offline JohnF

  • Member
  • *
  • Posts: 1114
    • http://www.johnfindlay.plus.com/
Re: frequency of ints in huge array
« Reply #35 on: July 06, 2014, 01:33:22 PM »
Yes Pelle's qsort is good enough. I've tried other implementations of qsort and Pelle's wins every time. In fact the C run time lib has many fast routines in it.

John

czerny

  • Guest
Re: frequency of ints in huge array
« Reply #36 on: July 06, 2014, 01:52:59 PM »
Yes Pelle's qsort is good enough. I've tried other implementations of qsort and Pelle's wins every time. In fact the C run time lib has many fast routines in it.
Must be an asm-implementation. But I do not understand the speed factor 4 or 5 comparing MySort and qsort. What could be optimized?

My pivot element is the very first element in an intervall. This should be no big problem if the data is sort of random. One could choose the median as a better choice, but to find the median costs time.

What else could be optimized?

Offline JohnF

  • Member
  • *
  • Posts: 1114
    • http://www.johnfindlay.plus.com/
Re: frequency of ints in huge array
« Reply #37 on: July 06, 2014, 02:01:32 PM »
Yes Pelle's qsort is good enough. I've tried other implementations of qsort and Pelle's wins every time. In fact the C run time lib has many fast routines in it.
Must be an asm-implementation. But I do not understand the speed factor 4 or 5 comparing MySort and qsort. What could be optimized?

My pivot element is the very first element in an intervall. This should be no big problem if the data is sort of random. One could choose the median as a better choice, but to find the median costs time.

What else could be optimized?

You could try a different sort method, maybe it would better qsort on this occasion.

However, if I were you I'd pick the fastest option available which is probably Pelle's qsort - unless you can find a fast asm routine that is.

I've tried to better Pelle's CRT routines with asm but have always been beaten by the CRT lib.
 
EDIT: attached is M.S. qsort.c. I've not tried it.

John

« Last Edit: July 06, 2014, 02:19:27 PM by JohnF »

Offline jj2007

  • Member
  • *
  • Posts: 441
Re: frequency of ints in huge array
« Reply #38 on: July 06, 2014, 03:07:04 PM »
I've tried to better Pelle's CRT routines with asm but have always been beaten by the CRT lib.

The CRT routines are in general fast, and some cannot be improved with asm. However, many can be beaten easily with a factor 2-3. One reason is that most of them are still pre-SSE2 for backward compatibility.

czerny

  • Guest
Re: frequency of ints in huge array
« Reply #39 on: July 06, 2014, 03:17:25 PM »
However, if I were you I'd pick the fastest option available which is probably Pelle's qsort - unless you can find a fast asm routine that is.
For my actual needs I will use qsort. That's ok.

But there is still a lack of understanding which bothers me. I do not expect to beat an asm-routine with c. I would expect a factor of, say 2. An factor 5 says to me: there must be some algorithmic improvements!

czerny

  • Guest
Re: frequency of ints in huge array
« Reply #40 on: July 06, 2014, 03:21:41 PM »
... still pre-SSE2 for backward compatibility.
fortunately!

Offline frankie

  • Global Moderator
  • Member
  • *****
  • Posts: 1571
Re: frequency of ints in huge array
« Reply #41 on: July 06, 2014, 08:38:19 PM »
I tryied another system to reduce the time without ordering the array.
It uses hashing.
You can play with hash table dimensions to reduce/extend the time or the memory used (they have opposite behaviour).
The time overheading is due, as clear to anybody, to the huge number of loops to check the array. The indexing technique used with hashing avoid loops and hash handling is widly repayed by faster access.
The project posted show how it works, but it is not optimized yet. You can get much better results with a faster hashing library that reduce memory access, and using rehashing to remove looping in bucket extension.
I hope this is useful or at least shows the right way...

Offline jj2007

  • Member
  • *
  • Posts: 441
Re: frequency of ints in huge array
« Reply #42 on: July 06, 2014, 10:01:14 PM »
... still pre-SSE2 for backward compatibility.
fortunately!

Hmmm....: Pelles C Release Candidate 5 (for 32-bit Windows Vista/7/8)

That's a much tougher obstacle IMHO ;-)

czerny

  • Guest
Re: frequency of ints in huge array
« Reply #43 on: July 06, 2014, 10:13:31 PM »

Offline jj2007

  • Member
  • *
  • Posts: 441
Re: frequency of ints in huge array
« Reply #44 on: July 06, 2014, 11:03:59 PM »
No, the restriction to Vista and upwards:
- about 25% of all PCs run with XP
- about 2% run with CPUs that don't have SSE2...