Inspired by Alex' and Nidud's friendly exchange of views, I wrote a testbed that downloads bible.txt from the Canterbury Large Corpus, multiplies it 50x and sorts the resulting file:
; if the file is not in the current folder, get it online
void FileRead$("http://www.data-compression.info/Corpora/LargeCanterburyCorpus.zip")
Intel(R) Core(TM) i5-2450M CPU @ 2.50GHz (MMX, SSE, SSE2, SSE3, SSSE3, SSE4.1, SSE4.2, AVX)
Masm32 assort:
1519100 lines sorted in 6.4 seconds
1519100 lines sorted in 6.4 seconds
1519100 lines sorted in 6.4 seconds
1519100 lines sorted in 6.4 seconds
1519100 lines sorted in 6.3 seconds
t0=[(According as it is written, God hath given them the spirit ...]
tn=[Ziph, and Telem, and Bealoth, ...]
MasmBasic QSort:
1519150 lines sorted in 1.3 seconds
1519150 lines sorted in 1.3 seconds
1519150 lines sorted in 1.3 seconds
1519150 lines sorted in 1.3 seconds
1519150 lines sorted in 1.3 seconds
t0=[(According as it is written, God hath given them the spirit ...]
tn=[Ziph, and Telem, and Bealoth, ...]
CRT QSort:
1519150 lines sorted in 1.7 seconds
1519150 lines sorted in 1.7 seconds
1519150 lines sorted in 1.7 seconds
1519150 lines sorted in 1.7 seconds
1519150 lines sorted in 1.7 seconds
t0=[(According as it is written, God hath given them the spirit ...]
tn=[Ziph, and Telem, and Bealoth, ...]
Source & exe attached. Timings welcome, even more welcome theories why the algos are equally fast for smaller files (crt1.exe) but diverge so much for the large ones. Note that MasmBasic QSort is a quick sort but not a quicksort - it's actually a (stable) merge sort.
One more observation: For a perfectly random array, timings for MB and CRT are closer.
Recall esi, t$() ; load a text array from file (http://www.webalice.it/jj2006/MasmBasicQuickReference.htm#Mb1172)
Scramble t$()
NanoTimer()
Intel(R) Core(TM) i5-2450M CPU @ 2.50GHz
MasmBasic QSort:
1519150 lines sorted in 1.64 seconds
1519150 lines sorted in 1.64 seconds
1519150 lines sorted in 1.64 seconds
CRT QSort:
1519150 lines sorted in 1.76 seconds
1519150 lines sorted in 1.75 seconds
1519150 lines sorted in 1.77 seconds
EDIT: attachment removed, see reply #6
Intel(R) Core(TM) i7-4790 CPU @ 3.60GHz (MMX, SSE, SSE2, SSE3, SSSE3, SSE4.1, SSE4.2, AVX)
BibleSortCrt1
Masm32 assort: 1519100 lines sorted in 4.3 seconds
MasmBasic QSort: 1519150 lines sorted in 0.85 seconds
CRT QSort: 1519150 lines sorted in 1.1 seconds
BibleSortCrt50
Masm32 assort: 11473858 lines sorted in 53. seconds
MasmBasic QSort: Fatal error: HeapAlloc
Thanks, sinsi. 11473858 lines looks very odd, 7.55 times the expected value. What are your sizes of bible.txt and Bible50.txt?
Btw it seems that HeapAlloc likes failing for allocations above about one GB - stuff for another thread.
202,369,600 bible.txt
10,118,480,000 Bible50.txt
Second try...
Intel(R) Core(TM) i7-4790 CPU @ 3.60GHz (MMX, SSE, SSE2, SSE3, SSSE3, SSE4.1, SSE4.2, AVX)
BibleSortCrt1
Masm32 assort: 30382 lines sorted in 0.0067 seconds
MasmBasic QSort: 30383 lines sorted in 0.0068 seconds
CRT QSort: 30383 lines sorted in 0.011 seconds
BibleSortCrt50
Masm32 assort: 1519100 lines sorted in 4.3 seconds
MasmBasic QSort: 1519150 lines sorted in 0.84 seconds
CRT QSort: 1519150 lines sorted in 1.0 seconds
4,047,392 bible.txt
202,369,600 Bible50.txt
deleted
Thanks, sinsi & nidud. There seems to be a problem with my logic :bgrin:
What kind of crash did you get, nidud? HeapAlloc? I've searched around a bit, and it seems more people have problems to allocate big chunks, see http://stackoverflow.com/questions/10365653/why-does-dynamic-memory-allocation-fail-after-600mb for an example.
EDIT: Version 2 attached - source & single exe, the logic is now OK.
i told ya god was gonna get ya :biggrin:
...and his wrath was great
and he did smote them
and their bodies were strewn along the side of Heap Mountain
Quote from: dedndave on March 27, 2015, 01:38:29 AM
i told ya god was gonna get ya :biggrin:
You are confused, Dave - it's just the heap manager :P
OK, here is one for the poor owners of a P4 :biggrin:
If I start with the crt version, MB chokes here, too. Perhaps it's simply heap fragmentation, but the phenomenon starts intriguing me. Having 4GB memory (of which 2 or 3 should be available in Win32) and getting problems at 200 MB is strange.
Interesting read: Overcoming Windows Memory Allocation Limitations (http://www.exelisvis.com/Support/HelpArticlesDetail/TabId/219/ArtMID/900/ArticleID/3346/3346.aspx)
Jochen, specify /LARGEADDRESSAWARE switch to the linker's command line when linking, this for some extent may "solve" the memory allocation problem, especially on 64 bit Windows versions (you'll be probably able to allocate in one chunk ~1 GB on 32 bit OS and ~2 GB on 64 bit OS with this switch specified). I did not tested the prog yet.
Jochen, when you do a Recall every time - does it with each call free the previously allocated buffer? That may be the reason if the code does not free the buffer previously allocated, so after some runs the memory gets full (leaks of losted previous arrays of data).
prescott w/htt
Intel(R) Pentium(R) 4 CPU 3.00GHz (MMX, SSE, SSE2, SSE3)
Masm32 assort for Bible.txt:
30382 lines sorted in 0.0251 seconds
30382 lines sorted in 0.0257 seconds
30382 lines sorted in 0.0228 seconds
30382 lines sorted in 0.0233 seconds
30382 lines sorted in 0.0234 seconds
t0=[(According as it is written, God hath given them the spirit ...]
t30381=[Ziph, and Telem, and Bealoth, ...]
MasmBasic QSort for Bible.txt:
30383 lines sorted in 0.0273 seconds
30383 lines sorted in 0.0271 seconds
30383 lines sorted in 0.0273 seconds
30383 lines sorted in 0.0273 seconds
30383 lines sorted in 0.0281 seconds
t0=[(According as it is written, God hath given them the spirit ...]
t30381=[Ziph, and Telem, and Bealoth, ...]
CRT QSort for Bible.txt:
30383 lines sorted in 0.0338 seconds
30383 lines sorted in 0.0339 seconds
30383 lines sorted in 0.0408 seconds
30383 lines sorted in 0.0353 seconds
30383 lines sorted in 0.0348 seconds
t0=[(According as it is written, God hath given them the spirit ...]
t30382=[Ziph, and Telem, and Bealoth, ...]
Masm32 assort for Bible20.txt:
607640 lines sorted in 4.30 seconds
607640 lines sorted in 4.30 seconds
607640 lines sorted in 4.28 seconds
607640 lines sorted in 4.30 seconds
607640 lines sorted in 4.30 seconds
t0=[(According as it is written, God hath given them the spirit ...]
t607639=[Ziph, and Telem, and Bealoth, ...]
MasmBasic QSort for Bible20.txt:
607660 lines sorted in 1.22 seconds
607660 lines sorted in 1.21 seconds
607660 lines sorted in 1.22 seconds
607660 lines sorted in 1.21 seconds
607660 lines sorted in 1.21 seconds
t0=[(According as it is written, God hath given them the spirit ...]
t607639=[Ziph, and Telem, and Bealoth, ...]
CRT QSort for Bible20.txt:
607660 lines sorted in 1.33 seconds
607660 lines sorted in 1.33 seconds
607660 lines sorted in 1.33 seconds
607660 lines sorted in 1.34 seconds
607660 lines sorted in 1.35 seconds
t0=[(According as it is written, God hath given them the spirit ...]
t607659=[Ziph, and Telem, and Bealoth, ...]
QuoteIf I start with the crt version, MB chokes here, too.
if you want to see something weird
put the processor identification at the end instead of the beginning
compare times between the 2 programs :redface:
Quote from: Antariy on March 27, 2015, 05:16:34 AM
Jochen, when you do a Recall every time - does it with each call free the previously allocated buffer? That may be the reason if the code does not free the buffer previously allocated, so after some runs the memory gets full (leaks of losted previous arrays of data).
It does free the buffer. There is no leak.
Quote from: dedndave on March 27, 2015, 05:26:05 AMif you want to see something weird
put the processor identification at the end instead of the beginning
compare times between the 2 programs :redface:
Can't see any difference here with 50x version. Timings and strings identical. This is weird indeed.
What I found in the meantime is that I have a flaw in the design of Recall: It allocates too generously memory for the string pointers, assuming that the worst case is a file with CrLfs only. This buffer gets shrunk (reallocated) at the end, but on entry it can be a problem. In fact, VMMap (https://technet.microsoft.com/en-us/sysinternals/dd535533.aspx)says that up to 1.05 GB are committed, which is far too much for a 200MB file. I will have to change that.
Anyway, the last version posted works fine on my Win7-64 system, and the timings are interesting, but obviously I have to do some homework :icon_cool:
Thanxalot to both of you :icon14:
Quote from: jj2007 on March 27, 2015, 06:27:50 AM
Quote from: Antariy on March 27, 2015, 05:16:34 AM
Jochen, when you do a Recall every time - does it with each call free the previously allocated buffer? That may be the reason if the code does not free the buffer previously allocated, so after some runs the memory gets full (leaks of losted previous arrays of data).
It does free the buffer. There is no leak.
What I found in the meantime is that I have a flaw in the design of Recall: It allocates too generously memory for the string pointers, assuming that the worst case is a file with CrLfs only. This buffer gets shrunk (reallocated) at the end, but on entry it can be a problem. In fact, VMMap (https://technet.microsoft.com/en-us/sysinternals/dd535533.aspx)says that up to 1.05 GB are committed, which is far too much for a 200MB file. I will have to change that.
Anyway, the last version posted works fine on my Win7-64 system, and the timings are interesting, but obviously I have to do some homework :icon_cool:
Thanxalot to both of you :icon14:
:t Did you try to use LARGEADDRESSAWARE switch? Remember than on x64 system 32 bit program has much more memory than on 32 bit system, so what is working on x64 may be out of memory on 32 bit OS.
As for the explanation why it performs better than MASM32 lib algo - well, for that we should know how your algo is implemented :biggrin: But actually I have not experiencies with sorting algos at all, I even didn't look to the MASM32's algo :biggrin: So without info about implementation from your side it's hard to think why it's so.
Large files test was useful and in this extent - improve design of the algo which was not related to the speed but to data handling :t
Quote from: Antariy on March 27, 2015, 06:40:39 AM:t Did you try to use LARGEADDRESSAWARE switch?
Thanks, but this would just hide the problem. Of course, if I had a concrete application that needs more memory, I could use that, but it's not a solution. I must work on the design of the algo. Again, for files under 200 MB there is no problem, it works fine.
Quote from: jj2007 on March 27, 2015, 06:44:50 AM
Quote from: Antariy on March 27, 2015, 06:40:39 AM:t Did you try to use LARGEADDRESSAWARE switch?
Thanks, but this would just hide the problem. Of course, if I had a concrete application that needs more memory, I could use that, but it's not a solution. I must work on the design of the algo. Again, for files under 200 MB there is no problem, it works fine.
Well, I did not say it's solution, just mentioned that if it may be useful for you. You currently read entire file into memory before you starting the scan of it and separating the lines to pointers? Do you do inplace separation, inserting zero in the CR/LF place?
Quote from: Antariy on March 27, 2015, 06:48:15 AMDo you do inplace separation, inserting zero in the CR/LF place?
Yes, exactly. Masm32 ltok and Hutch' new tokeniser use the same technique afaik. It's extremely efficient for read-only arrays (frequent case). It is a bit less efficient when you start heap-allocating new strings, but even in the most extreme case, only the memory of the original file size hangs around. No harm done if it doesn't reach the gigabyte range.
The alternative would be to copy each string to a heap-allocated new string, and delete the original array afterwards. That is awfully slow, and given that each heapstring neads a header and has trailing unused bytes, it is hardly more memory-efficient.
New version with strongly improved memory management. Now six Million 'bible' lines can be sorted without problems. There is a version with 10 Mio lines, but it choked sometimes - see bx$ in the source.
Getting text files
Reading Bible200.txt
Reading 6076600 lines took 0.658 seconds
Reading 6076600 lines took 0.640 seconds
***
CRT QSort for Bible200.txt:
6076600 lines sorted in 7.45 seconds
6076600 lines sorted in 7.44 seconds
6076600 lines sorted in 7.44 seconds
Writing 6076600 lines took 5.52 seconds
t0=[(According as it is written, God hath
t6076599=[Ziph, and Telem, and Bealoth, .
MasmBasic QSort for Bible200.txt:
6076600 lines sorted in 6.21 seconds
6076600 lines sorted in 6.37 seconds
6076600 lines sorted in 6.34 seconds
Writing 6076600 lines took 5.34 seconds
t0=[(According as it is written, God hath
t6076399=[Ziph, and Telem, and Bealoth, .
Intel(R) Core(TM) i5-2450M CPU @ 2.50GHz
:redface:
I move that old computers be banned ... anyone second the motion?
Perhaps we could pass the hat to retire these aging warhorses, save a lot of trouble chasing down anachronistic bugs
Get dedndave a nice new Windows 8.1 machine, maybe even Windows 10 :biggrin:
[edit] just kidding of course - actually, as we all know, "Older is Better"
i like my P4 prescott :biggrin:
XP media center edition
4 GB ram (3 usable, i guess)
had it 10 years - it's been a good machine
although, i may pick up a used win7-64 laptop for business use
win8, win10 - no thank you
Crash again, with the i7-4790 and Win8.1Pro
Windows 7 Ultimate 64-bit
Getting text files
Downloading Canterbury Corpus
4047392 21.03.1997 15:31:58 bible.txt
Unzipping to C:\Users\tester\Desktop\Sort6MioLines\Bible.txt
4638690 26.02.1997 11:12:00 E.coli
2473400 18.03.1997 15:13:34 world192.txt
Building 50*Bible.txt as Bible50.txt
Building 200*Bible.txt as Bible200.txt
Reading Bible200.txt
Reading 6076600 lines took 0.963 seconds
Reading 6076600 lines took 1.28 seconds
Reading 6076600 lines took 1.11 seconds
***
CRT QSort for Bible200.txt:
6076600 lines sorted in 9.80 seconds
6076600 lines sorted in 9.81 seconds
6076600 lines sorted in 9.72 seconds
Writing 6076600 lines took 2.79 seconds
t0=[(According as it is written, God hath given them the spirit ...]
t6076599=[Ziph, and Telem, and Bealoth, ...]
MasmBasic QSort for Bible200.txt:
6076600 lines sorted in 9.07 seconds
6076600 lines sorted in 9.00 seconds
6076600 lines sorted in 8.93 seconds
Writing 6076600 lines took 1.85 seconds
t0=[(According as it is written, God hath given them the spirit ...]
t6076399=[Ziph, and Telem, and Bealoth, ...]
Last error: The operation completed successfully.
AMD A10-7850K APU with Radeon(TM) R7 Graphics (MMX, SSE, SSE2, SSE3, SSSE3, SSE4.1, SSE4.2, AVX)
--- hit any key ---
Windows 10 Preview 64-bit
Getting text files
Downloading Canterbury Corpus
4047392 21.03.1997 15:31:58 bible.txt
Unzipping to C:\Users\user\Desktop\Sort6MioLines\Bible.txt
4638690 26.02.1997 11:12:00 E.coli
2473400 18.03.1997 15:13:34 world192.txt
Building 50*Bible.txt as Bible50.txt
Building 200*Bible.txt as Bible200.txt
Reading Bible200.txt
Reading 6076600 lines took 1.37 seconds
Reading 6076600 lines took 1.30 seconds
Reading 6076600 lines took 1.30 seconds
***
CRT QSort for Bible200.txt:
6076600 lines sorted in 10.2 seconds
6076600 lines sorted in 10.2 seconds
6076600 lines sorted in 9.87 seconds
Writing 6076600 lines took 23.3 seconds
t0=[(According as it is written, God hath given them the spirit ...]
t6076599=[Ziph, and Telem, and Bealoth, ...]
MasmBasic QSort for Bible200.txt:
6076600 lines sorted in 9.12 seconds
6076600 lines sorted in 9.03 seconds
6076600 lines sorted in 8.77 seconds
Writing 6076600 lines took 9.23 seconds
t0=[(According as it is written, God hath given them the spirit ...]
t6076399=[Ziph, and Telem, and Bealoth, ...]
Last error: The operation completed successfully.
Intel(R) Core(TM)2 Quad CPU Q9450 @ 2.66GHz (MMX, SSE, SSE2, SSE3, SSSE3, SSE4.1)
--- hit any key ---
Windows 8.1 Professional 64-bit
Getting text files
Downloading Canterbury Corpus
4047392 21.03.1997 15:31:58 bible.txt
Unzipping to C:\Users\sinsi\Desktop\Sort6MioLines\Bible.txt
4638690 26.02.1997 11:12:00 E.coli
2473400 18.03.1997 15:13:34 world192.txt
Building 50*Bible.txt as Bible50.txt
Building 200*Bible.txt as Bible200.txt
Reading Bible200.txt
Reading 6076600 lines took 0.572 seconds
Reading 6076600 lines took 0.545 seconds
Reading 6076600 lines took 0.653 seconds
*
Fatal error: HeapAlloc
Thanxalot, Sinsi & Dave - especially for the Windows 10 preview test :bgrin:
Re HeapAlloc error: it's 1.6GB in the peak, quite a lot. But it works much better than the previous version, which chokes earlier.
deleted
Thanks. Here is WinXP, Celeron M (failing with HeapAlloc):
Getting text files
Downloading Canterbury Corpus
4047392 21.03.1997 15:31:58 bible.txt
Unzipping to C:\DOCUME~1\USER\DOCUME~1\DOWNLO~1\Bible.txt
4638690 26.02.1997 11:12:00 E.coli
2473400 18.03.1997 15:13:34 world192.txt
Building 50*Bible.txt as Bible50.txt
Building 200*Bible.txt as Bible200.txt
Reading Bible200.txt
Reading 6076600 lines took 37.9 seconds
Reading 6076600 lines took 32.8 seconds
Reading 6076600 lines took 32.5 seconds