A skeleton code for Text Scroller via Drag-and-Drop

[Sanmayce]

Enter Gesch encoding...

It's time to break away, no more limitations on browsing Italian/French/German/Spanish/Bulgarian/Russian ... without using any UNICODE!

In next days will write the search panel in which all those symbols (from my Gesch codepage), for now I wrote only the converter from UTF-8 to Gesch, attached at the end.

Here it is the "legacy" codepage, which in my opinion was made by a total schmuck:

 

Here is the newwave in codepage encodings :P

 

As always, I checked all the converted symbols against the https://utf8-chartable.de, and there were no mismatches:

 

 

One quick example is how Don Quixote is readable in Gesch encoding:

 

Simply, when I need to browse some UTF-8 file, I won't be bothered whether there are Russian or/and French or/and German texts within, just will run UTF8toGesch.exe converter and Drag-n-Drop the .Gesch file.
In next releases will add the ability to search for those symbols.

Halving the file size comes as a "side effect", as a bonus. For example I have one Russian corpus 15,000+ ebooks in UTF-8 strong and 11GB in size. Guess what, instead of fulltext searching 11GB in UTF-8 the traverse distance becomes ~6GB.

[Sanmayce]

The need for more ergonomic (that is, easily accessible) shortcuts (strictly keyboardish) got me thinking...

Holy hell, why no one introduced the analogues/counterparts of "double-clicks" - the first that comes to mind: the "double-hits".
Both, being just taps.
Currently, in Masakari there are:
- shortcuts, purely keyboardish;
- shortcuts, mix of keys and mouse buttons;
- shortcuts, purely mouseish, just mouse stuff - buttons and wheel.

From revision 8.1+ onward, following double-hits were implemented:
Double LShift; Double LCtrl; Double LAlt; Double RAlt.
The thing is that "legacy" shortcuts as Ctrl+F3 (even the F3) force the user to "locate" their position and to overreach - meaning hovering pass the SPACEBAR area - which is most easy to hit since the wrists/palms have support, and are simply closer.
To me, the traditional key sequences are to be replaced/enriched with more convenient, more close to the first row of the keyboard, ones.
Currently, my main keyboard is a nasty one (laptopish, with low profile, non-tactile, half-sized F-keys, and tightly packed), when e.g. a LCtrl+F3 search is needed, spotting this halved F3 is a drag, therefore the double-hit of e.g. LCtrl saves the situation - just double-tap it - the timings between the two pressings are handled by the same logic as the mouse double/triple/quadruple-clicks.
The following stand-alone etude is the same as the previously shared mouse_mumbo-jumbo.bas, except:

Code: QB64: [Select]

1. buttondown1 = _MOUSEBUTTON(1)

should be replaced with

Code: QB64: [Select]

1. KeyTap_buttondown1 = _KEYDOWN(LSHIFTkey&)

The attached package contains the most refined revision so far, with all accompanying  tools, 32bit and 64bit executables for Windows, and 64bit ELF for Linux.
There is one file, called Word-list_584879_words_Russian_Spell-Check.txt.Gesch.oneline.198, it serves as a scroll line-by-line testfile benchmark, on my laptop running both Windows 10 and Fedora 33, it gave 45 Lines-Per-Second scroll speed:

 

And the PDF booklet with the QB64 sourcecode at:
www.sanmayce.com/Masakari.zip

 

[Sanmayce]

My word is for QB64 toolbox/application enrichment.

Didn't want to initiate a thread about hashing, especially for having the so needed fastest 128bit hash function.
As the need for speed is constantly on my mind, recently I wrote Gumbotron:
https://github.com/google/highwayhash/issues/102#

 

The idea is to solve problematic search/index scenarios with reliable/optimized tools/etudes and feeding the QB64 application with resultant data.
Too often 1,000,000,000 records e.g. 64,128 or 256 bytes long are to be searched, how to deal with it?!
The discussions in other sub-forums focus on languages and their advance features, but the problem stays as long as one sees within the box and forgets to look outwith, that is, beyond the languages limitations.
Gumbotron is such a case, it makes the hashing in inside-out not in outside-in manner, meaning all the permutations of the key for hashing are dealt with outside the hasher itself, the "traditional" hashers make all kind of rotations/multiplications/shifts within the body serving as a LINEAR MIXER, but the really smart coders already did such a LINEAR MIXER hardwarely embedding all the stages of AES into a single instruction with latency 3 clocks and throughput 1 clock!
So, the moral is to exploit all the available resources (either languages, CPU extensions, algorithms), not to burden oneself with giving tasks as forcing a dog to pull a plug, yes the ox is better, but dog has other functionality - it is a matter of proper assignment.

Hm, don't feel I am getting my point across, back in the day Assembler/Assembly was popularized by the "bad guy" Phil Katz, the documentary says a lot. The favorite part of mine is where the screen says "... the damage was done" referring to speeding up the ARC 10x, rewriting C parts into Assembly. Very funny and sad at the same time, the bad guy gives PKARC/PKZIP and teaches in a practical way how things are to be done, and the community slams him as being the devil. If the devil offers superspeeds, let us reject them since they are ... born in sin, hee-hee.

Also, reading, in the forum, the discussion about highlighting/popularizing the usefulness of QB64, didn't want to write obvious things, yet to me the most obvious way is by ... example.
Yes, sharing etudes/tools written well with real practical value would showcase the power of one approach/language/method in a macho (Clint Eastwood's last film taught me this word) way.
Imagine, a well-written tool, it would serve as an ad for the language used, quite naturally. Having such a good forum prompts for sharing code that catches the attention of users and makes them enthusiasts, daring to try themselves, but they have to have a starting point/code/tool to play with.
Will share this thread/tool on the biggest English language forum:
https://forum.thefreedictionary.com/postst31183p4_MASAKARI--The-people-s-choice--General-Purpose-Grade--English-wordlist.aspx

And just wanted to announce the incoming new Masakari revision allowing dictionaries lookups in a better way than most software out there, including the original Oxford, Webster, Wiktionary...
My vision is to present all the .DSL files into an unified/standardized manner, simplistic and ergonomic, having in mind cross-searches as well.
The draft looks like this (yes, targeting the old and super durable laptops, as Thinkpad, having low resolutions as 1366x768):

 

Writing such a practical tool (allowing quick lookups into 16+1+1+1 major dictionaries) could serve as a starting point for contemplating new ideas of refining and boosting the search capabilities even more...

I intend gradually to add all these:

Code: QB64: [Select]

1. 02/28/2021  08:34 PM        42,257,313 Dictionary_Specification_Language_(ABBYY_Software_House)_American_Heritage_Dictionary_4_(En-En)_UTF-8.dsl
2. 02/28/2021  08:36 PM       299,225,953 Dictionary_Specification_Language_(ABBYY_Software_House)_Britannica_Encyclopedia_2010_1.563_miled_(En-En)_ANSI.dsl
3. 02/28/2021  08:58 PM        75,122,799 Dictionary_Specification_Language_(ABBYY_Software_House)_Cambridge_Advanced_Learner's_Dictionary_4th_Ed_(En-En).dsl
4. 02/28/2021  09:00 PM        23,413,283 Dictionary_Specification_Language_(ABBYY_Software_House)_Collins_COBUILD_Advanced_Learner's_English_Dictionary_(5th_ed)_(En-En).dsl
5. 02/28/2021  09:05 PM        37,870,978 Dictionary_Specification_Language_(ABBYY_Software_House)_Longman_Activator_2nd_Ed_(En-En).dsl
6. 02/28/2021  09:10 PM        52,743,002 Dictionary_Specification_Language_(ABBYY_Software_House)_Longman_Dictionary_of_Contemporary_English_5th_Ed_(En-En).dsl
7. 02/28/2021  09:19 PM        83,412,925 Dictionary_Specification_Language_(ABBYY_Software_House)_Macmillan_English_Dictionary_(En-En)_UTF-8.dsl
8. 02/28/2021  09:19 PM        29,772,872 Dictionary_Specification_Language_(ABBYY_Software_House)_Macmillan_English_Thesaurus_(En-En)_UTF-8.dsl
9. 02/28/2021  09:15 PM       101,528,058 Dictionary_Specification_Language_(ABBYY_Software_House)_Merriam-Webster's_Collegiate_Dictionary_11th_Edition_(En-En).dsl
10. 02/28/2021  09:29 PM        57,854,694 Dictionary_Specification_Language_(ABBYY_Software_House)_Oxford_Advanced_Learner's_Dictionary_8th_Edition_(En-En).dsl
11. 02/28/2021  09:32 PM        44,362,425 Dictionary_Specification_Language_(ABBYY_Software_House)_Oxford_American_Dictionary_2nd_Edition.dsl
12. 02/28/2021  09:33 PM        11,747,238 Dictionary_Specification_Language_(ABBYY_Software_House)_Oxford_American_Thesaurus_(En-En).dsl
13. 02/28/2021  09:38 PM       559,408,265 Dictionary_Specification_Language_(ABBYY_Software_House)_Oxford_English_Dictionary_2nd_Edition_Version_4_(En-En)_ANSI.dsl
14. 02/28/2021  09:33 PM        53,483,030 Dictionary_Specification_Language_(ABBYY_Software_House)_Random_House_Webster's_Unabridged_Dictionary_(En-En)_UTF-8.dsl
15. 02/28/2021  09:53 PM        12,202,934 Dictionary_Specification_Language_(ABBYY_Software_House)_The_Collins_Cobuild_School_Dictionary_of_American_English_(En-En).dsl
16. 02/28/2021  08:26 PM       137,754,899 Dictionary_Specification_Language_(ABBYY_Software_House)_Webster's_Unabridged_3_(En-En)_UTF-8.dsl
17.  
18. 03/28/2019  02:31 PM         5,340,386 dict2txt_Online_Etymology_Dictionary1.1.txt
19.  
20. 10/08/2021  08:42 AM     7,015,793,795 enwiktionary-20210920-pages-articles.xml
21.  
22. 07/10/2021  09:57 PM     1,917,822,288 Machine-Learning_Urban_Dictionary_Definitions_Corpus_(1999_-_May-2016).words.json
23.  

For a long time, the need for English language speedy lookups into constellation of dictionaries (on a netbook) drives me toward writing a tool sidekicking macholy, once and for all.

[Sanmayce]

Thanks @The Librarian for sharing this:
https://www.qb64.org/forum/index.php?topic=1598.0

This function is a must-have, for example it can be used for controlling _LIMIT in a "stepping" fashion, as the CPUs are downclocked.

Consider a main loop with _LIMIT 500 and the user is using the application touch-and-go-ly, it is a good idea to reduce the 500 by 10% each minute (down to 90%) of inactiveness i.e. not doing keyboard input.

Here is a bit modified variant, after 13 minutes it enters maximum ... minimum:

 

Already incorporated this etude in Masakari r.8.1++, also finished the Schizandrafield rev.D lookup functionality:

 

Simple functionalities such as automatic highlighting of identical entries (above and below) to the current/inverse line are nice since the eyes stop constantly seeking whether neighbors are identical.

Also, finally, did what every GUI tool has to offer - the Color Scheme defined in a file (allowing the user to play with it), in this case the file is called Masakari.RGB - it is 48 bytes long, all the 16 colors given from 0 to 15 in three bytes sequence, RGB:

 

Sometimes, when working outdoors (on a shiny day), more brightness is needed, laptops lack such a regulator so just pressing 'I' will increase all channels by 1 point:

 

The feeling, of seeing the actual window colorized, is different from seeing some small box, moreover the combinations of foreground and background are tricky to please the user, therefore one can play with channels and intensity and once seeing a pleasing combination then can save the RGB values on paper and remap whichever color in the Masakari.RGB is wanted to be replaced.

[Sanmayce]

What is the quicksort routine that QB64 community uses?!

Back in the day, I wrote an XMS QuickSort, now dusted off and shared here.
From time to time, I visit the very informative site 'rosettacode' where multi languages etudes are given side by side, it is a shame QB64 is not presented there as it should, especially unacceptable is the situation with the QS64, standing for QuickSort 64bit, not having its QB64  presence.
Today, I have added my Quicksort variant, thus putting QB64 in this must-be "Quick" category:

https://rosettacode.org/wiki/Sorting_algorithms/Quicksort#QB64

Soon will include this very subroutine into Masakari sorting the QWORD  long indexes to lines...

Also, did make a benchmark (source code and binary attached) with QB64 executable which can be used as a general speed benchmark, stressing caches and somewhat uncached (or rather not well cached) RAM accesses (despite QS being with good locality) - very interesting it would be when AMD 3D cache comes along, and mostly with M1 Apple's unified memory (with RAM latency ~35ns being the half of PCs, AFAIK).
Whoever owns M1 Max, please compile it and share with us how well Apple performs.

On my Kaby Lake laptop (i5-7200U 3.1GHz max turbo, 36GB DDR4 2133MHz) it took 11 minutes to sort 1.7 billion QWORDS (i.e. 8 bytes elements). They are in range 0..9, which makes sorting harder due to the many repetitions.

Here we go:

 

The panel at the end checks for sanity:

 

Actually, the digits come from the 22,338,618 bytes long file containing the dump of 2^74207281-1, which was the biggest known prime number in 2016.

Here is the dumper of my testdataset, thanks to Fabrice Bellard:

Code: C++: [Select]

1. // https://bellard.org/mersenne.html
2. // A small C program to print the biggest prime number
3. // Here it is (448 bytes):
4. /*
5. int m=1811939329,N=1,t[1<<26]={2},a,*p,i,e=73421233,s,c,U=1;g(d,h){for(i=s;i<1<<
6. 25;i*=2)d=d*1LL*d%m;for(p=t;p<t+N;p+=s)for(i=s,c=1;i;i--)a=p[s]*(h?c:1LL)%m,p[s]
7. =(m*1U+*p-a)*(h?1LL:c)%m,*p=(a*1U+*p)%m,p++,c=c*1LL*d%m;}main(){while(e/=2){N*=2
8. ;U=U*1LL*(m+1)/2%m;for(s=N;s/=2;)g(136,0);for(p=t;p<t+N;p++)*p=*p*1LL**p%m*U%m;
9. for(s=1;s<N;s*=2)g(839354248,1);for(a=0,p=t;p<t+N;)a+=*p<<(e&1),*p++=a%10,a/=10;
10. }while(!*--p);for(t[0]--;p>=t;)putchar(48+*p--);}
11. */
12. // This program computes 2^74207281-1, which was the biggest known prime number in 2016 (about 23 million digits !). For more information about how it was // found and who found it, look at the GIMPS Project .
13. //
14. // I compiled it successfully with gcc with Linux. In order to compile it, your C compiler must support the 64 bit long long type.
15. //
16. // In order to have a small and yet asymptotically efficient code, I decided to do the computation of 2N-1 directly in base 10. The power involves repeated // squarings and multiplications by two. The squarings are implemented by doing fast convolutions using a Number Theoretic Transform.
17. //
18. // A previous version of this program to compute 2^6972593-1 won the International Obfuscated C Code Contest of Year 2000.
19. //
20. // Thanks to Marco Cecchi who suggested some syntactic changes to save a few characters.
21. //
22. // This program is Freeware.
23. //
24. // Fabrice Bellard - http://bellard.org/
25. // last update: Sep 26, 2016
26.  

[jack]

From time to time, I visit the very informative site 'rosettacode' where multi languages etudes are given side by side, it is a shame QB64 is not presented there as it should, especially unacceptable is the situation with the QS64, standing for QuickSort 64bit, not having its QB64  presence.

yes I agree, here's one for the graphics experts https://rosettacode.org/wiki/Honeycombs

[bplus]

What is the quicksort routine that QB64 community uses?!

I've been using a recursive QuickSort, eg for Single Type:

Code: QB64: [Select]

1. Sub QuickSort (start As Long, finish As Long, array() As Single)
2.     Dim Hi As Long, Lo As Long, Middle As Single
3.     Hi = finish: Lo = start
4.     Middle = array((Lo + Hi) / 2) 'find middle of array
5.     Do
6.         Do While array(Lo) < Middle: Lo = Lo + 1: Loop
7.         Do While array(Hi) > Middle: Hi = Hi - 1: Loop
8.         If Lo <= Hi Then
9.             Swap array(Lo), array(Hi)
10.             Lo = Lo + 1: Hi = Hi - 1
11.         End If
12.     Loop Until Lo > Hi
13.     If Hi > start Then Call QuickSort(start, Hi, array())
14.     If Lo < finish Then Call QuickSort(Lo, finish, array())
15. End Sub

[bplus]

yes I agree, here's one for the graphics experts https://rosettacode.org/wiki/Honeycombs

I did that one a couple years ago in JB.

[Sanmayce]

@jack
Glad that you also see the miss, will try to share rev.3 which will feature an unseen partitioning, hopefully helping in scenarios with duplicative keys almost dominating the array...

@bplus
Thanks, that's what I need, variants of QB64 community helping in refining the current fastest ones.
Since my focus is on 64bit file/string manipulations (as in the example with Wikipedia XML ~74GB having 1+billion lines), all LONG variables are obsolete i.e. 2 billion (signed, you know) are limiting dealing with big data. So, I have included your tiny (modified to be 64bit) variant as performer #3, thus we can see how my (rev.1) published on ROSETTACODE fares against yours, also as performer #2, I have put rev.2 boosting speed by just finishing with Insertionsort (nothing new), my dummy logic was to choose 7999 elements long chunks unsorted, because 7999*8<64KB, hoping the L1 data cache can house it. I have an idea to write entirely new partitioning in rev.3, we will see in practice its behavior.

Run/Performer #3 proves slower than the ROSETTACODE QB64 etude:

Code: QB64: [Select]

1. _Define A-Z As _INTEGER64
2. Sub QuickSort (start As _Integer64, finish As _Integer64, array() As _Integer64)
3.     Lo = start: Hi = finish
4.     Middle = array((Lo + Hi) \ 2)
5.     Do
6.         Do While array(Lo) < Middle: Lo = Lo + 1: Loop
7.         Do While array(Hi) > Middle: Hi = Hi - 1: Loop
8.         If Lo <= Hi Then
9.             Swap array(Lo), array(Hi)
10.             Lo = Lo + 1: Hi = Hi - 1
11.         End If
12.     Loop Until Lo > Hi
13.     If Hi > start Then Call QuickSort(start, Hi, array())
14.     If Lo < finish Then Call QuickSort(Lo, finish, array())
15. End Sub
16.  

It would be nice fellow members to share their ideas and benchmarks, so we can pair the QuickBasic64 with QuickSort64.

Here comes the 32bit code generated by QB64 v.2.01, Core 2 Duo 2.9GHz, DDR2 266MHz:

 

Here comes the 64bit code generated by QB64 v.2.01, i5-7200U 3.1GHz, DDR4 1066MHz:

 

Wanna see modern machines running this benchmark in order to get the picture more clearly...

[Sanmayce]

Glad to share my latest refinement, source code and the two binaries (for Linux and Windows) are in the attached package.
Here comes the new Quicksort rev.3 with the new 'Magnetica' partitioning, compared side-by-side with the mainstream recursive Quicksort with 'Classica' partitioning.
Generally, we have three major scenarios:
- FEW distinct keys;
- MANY distinct keys;
- ALL distinct keys.

In first two cases, the new implementation is faster or equal to the "Standard" one:

Under Windows:

 

Under Linux:

 

Sadly, in the third case, it is somewhat slower.
Anyway, benchmarking will show the practical value of 'Magnetica', personally, I started to use it already.

[Sanmayce]

Having been "side-tracked" by tuning my old function for two weeks, resulted in writing, by chance, the FASTEST Quicksort, known to me.

 

Enjoy!

[Sanmayce]

One can learn, in a lazy manner, a lot just by seeing the sort being ... animated.

Couldn't resist not to make a video showing the beautiful Magnetica train - the actual visualized sort process.

The sorting pauses for 3 seconds each time when the orange train collides with the Jndx - the right "sentinel" colored in red.

I chose for the testfile an old interview in English, ~27KB long, the window/matrix for sorting is 300 columns x 80 lines <27KB.
This type of sorts are quite useful in compression/indexing since each position demands statistics for order 1..8 bytes long Building-Blocks, inhere we sort order 1 i.e. letters.

For more fun, added Quicksort 'Classica' recursive dealing with the same array, the interesting thing here is one to compare Classica's Swaps and Comparisons versus Magnetica's ones:

Magnetica: 66,008 and 115,721
Classica: 132,663 and 355,221

Total Smackdown.

[Sanmayce]

The attached C function is the fastest quicksort I could write, so far.

Thanks to PCBoy Studios, here comes a short animated demo of Quicksort 'Magnetica' (initial release):

Now, the new function is more robust against quadratic behavior, since it was strengthened with median of 5 pivot - branchlessly on top of that!

And for all fellow members who need maximum speed in their sorting, here comes the usage of the "header" written in C, ready to go in QB64:

Code: QB64: [Select]

1. Declare CustomType Library "qsm"
2.     Sub Quicksort_QB64_v5 (ByVal QWORDS As _Offset, Byval Left As _Integer64, Byval Right As _Integer64)
3. End Declare
4.  
5. Quicksort_QB64_v5 _Offset(QWORDS~&&(LBound(QWORDS~&&))), 0, UBound(QWORDS~&&) - LBound(QWORDS~&&)
6.  

Enfun!

Oh, and  @bplus your recursive quicksort crashes (with mere 100,000 elements) without even giving an error on exit, it occurs with 'Organ Pipe' data. Your test program modified is given below in order to reproduce the crash. My advice, start using the attached QB64 "intrinsic", updated on 2021-Nov-28:

 

Code: QB64: [Select]

1. Declare CustomType Library
2.     Sub memcpy (ByVal dest As _Offset, Byval source As _Offset, Byval bytes As Long)
3. End Declare
4. _ControlChr Off
5.  
6. _Title "Recursive Vrs NonRecursive test with Quicksort" 'b+ 2021-11-01, Sanmayce added some stuff 2021-Nov-26
7. _Define A-Z As _UNSIGNED _INTEGER64
8. ReDim Shared As _Unsigned _Integer64 ArrayHigh
9. ArrayHigh = 2 * 50000
10. 'ArrayHigh = 2 * 5000000
11. ReDim Shared As _Unsigned _Integer64 n(1 To ArrayHigh), m(1 To ArrayHigh), z(1 To ArrayHigh) 'z(0 To ArrayHigh - 1)
12.  
13. Declare CustomType Library "qsm" ' Notice that 'CustomType' makes things work, using 'STATIC' gives errors during compilation
14.     Sub Quicksort_QB64_v5 (ByVal QWORDS As _Offset, Byval Left As _Integer64, Byval Right As _Integer64)
15. End Declare
16.  
17. 'For i = 1 To ArrayHigh
18. '    n(i) = i '13 'i
19. 'Next
20. 'For i = ArrayHigh To 2 Step -1 ' Fisher Yates Shuffle
21. '    Swap n(i), n(Int(Rnd * i) + 1)
22. '    m(i) = n(i) ' copy m off n
23. '    z(i) = n(i) ' copy m off n
24. 'Next
25.  
26. ' Generate 'OrganPipe' data:
27. For i = 1 To ArrayHigh
28.     If i <= ArrayHigh \ 2 Then
29.         n(i) = i
30.         m(i) = n(i) ' copy m off n
31.         z(i) = n(i) 'z(i - 1) = n(i) ' copy m off n
32.     Else 'ArrayHigh \ 2 + 1 .. ArrayHigh
33.         n(i) = ArrayHigh - i + 1
34.         m(i) = n(i) ' copy m off n
35.         z(i) = n(i) 'z(i - 1) = n(i) ' copy m off n
36.     End If
37. Next
38. 'Print z(1), z(2)
39. 'Print z(ArrayHigh - 1), z(ArrayHigh)
40.  
41.  
42. a$ = "1234567890"
43. b$ = "ABCDEFGHIJ"
44.  
45. memcpy _Offset(a$) + 1, _Offset(z(1)), 8
46. Print a$
47. memcpy _Offset(a$) + 1, _Offset(z(ArrayHigh)), 8
48. Print a$
49.  
50. Print "Test arrays ready. Testing Recursive QuickSort first."
51. 'n(1) = ArrayHigh
52. 'm(1) = n(1)
53. 'z(1) = n(1)
54.  
55. 'crashes with OrganPipe
56. GoTo 1
57. T# = Timer(.001)
58. QuickSort 1, ArrayHigh
59. QuickSortT# = Timer(.001) - T#
60. For i = 1 To ArrayHigh - 1
61.     If n(i) > n(i + 1) Then Print "NOT OK!": End
62. Next
63. Print "QuickSort checked, QuickSort time was"; QuickSortT#
64. 1
65.  
66. T# = Timer(.001)
67. Quicksort_QB64
68. QuicksortQB64T# = Timer(.001) - T#
69. For i = 1 To ArrayHigh - 1
70.     If m(i) > m(i + 1) Then Print "NOT OK!": End
71. Next
72. Print "Quicksort_QB64 checked, Quicksort_QB64 time was"; QuicksortQB64T#
73.  
74.  
75. 'T# = Timer(.001)
76. 'Quicksort_QB64_v2
77. 'QuicksortQB64T# = Timer(.001) - T#
78. 'For i = 1 To ArrayHigh - 1
79. '    If z(i) > z(i + 1) Then Print "NOT OK!": End
80. 'Next
81. 'Print "Quicksort_QB64_v2 checked, Quicksort_QB64_v2 time was"; QuicksortQB64T#
82.  
83. Print LBound(z), UBound(z), ArrayHigh
84. 'Print _Offset(z(0))
85. Print _Offset(z(1)), _Offset(z(LBound(z)))
86. 'Print _Offset(z(2))
87.  
88. T# = Timer(.001)
89. Quicksort_QB64_v5 _Offset(z(LBound(z))), 0, UBound(z) - LBound(z) ' with 'STATIC' library: error: invalid conversion from 'unsigned int' to 'void*' [-fpermissive] Quicksort_QB64_v4(((uptrszint)((&(((uint64*)(__ARRAY_UINTEGER64_QWORDS[0]))
90. QuicksortQB64Tv5# = Timer(.001) - T#
91.  
92. Print z(1), z(2), z(3), z(4), z(5)
93. Print z(ArrayHigh - 1), z(ArrayHigh)
94.  
95. For i = 1 To ArrayHigh - 1
96.     'If z(i - 1) > z(i - 1 + 1) Then Print "NOT OK!": End
97.     If z(i) > z(i + 1) Then Print "NOT OK!": End
98. Next
99. Print "Quicksort_QB64_v5 checked, Quicksort_QB64_v5 time was"; QuicksortQB64Tv5#
100.  
101. Print: Print "Verdict: On 'OrganPipe' data, QuicksortQB64v5 (in C) is "; Int(QuicksortQB64T# / QuicksortQB64Tv5#); "times faster than QuicksortQB64 (in QB64)."
102.  
103. ' recursive
104. Sub QuickSort (start As _Unsigned _Integer64, finish As _Unsigned _Integer64)
105.     Lo = start: Hi = finish
106.     Middle = n((Lo + Hi) \ 2)
107.     Do
108.         Do While n(Lo) < Middle: Lo = Lo + 1: Loop
109.         Do While n(Hi) > Middle: Hi = Hi - 1: Loop
110.         If Lo <= Hi Then
111.             Swap n(Lo), n(Hi)
112.             Lo = Lo + 1: Hi = Hi - 1
113.         End If
114.     Loop Until Lo > Hi
115.     If Hi > start Then QuickSort start, Hi
116.     If Lo < finish Then QuickSort Lo, finish
117. End Sub
118.  
119. ' non recursive
120. ' ref:  https://rosettacode.org/wiki/Sorting_algorithms/Quicksort#QB64
121. Sub Quicksort_QB64
122.     Left = LBound(m)
123.     Right = UBound(m)
124.     LeftMargin = Left
125.     ReDim Stack&&(Left To Right)
126.     StackPtr = 0
127.     StackPtr = StackPtr + 1
128.     Stack&&(StackPtr + LeftMargin) = Left
129.     StackPtr = StackPtr + 1
130.     Stack&&(StackPtr + LeftMargin) = Right
131.     Do 'Until StackPtr = 0
132.         Right = Stack&&(StackPtr + LeftMargin)
133.         StackPtr = StackPtr - 1
134.         Left = Stack&&(StackPtr + LeftMargin)
135.         StackPtr = StackPtr - 1
136.         Do 'Until Left >= Right
137.             Pivot~&& = m((Left + Right) \ 2)
138.             Indx = Left
139.             Jndx = Right
140.             Do
141.                 Do While (m(Indx) < Pivot~&&)
142.                     Indx = Indx + 1
143.                 Loop
144.                 Do While (m(Jndx) > Pivot~&&)
145.                     Jndx = Jndx - 1
146.                 Loop
147.                 If Indx <= Jndx Then
148.                     If Indx < Jndx Then Swap m(Indx), m(Jndx)
149.                     Indx = Indx + 1
150.                     Jndx = Jndx - 1
151.                 End If
152.             Loop While Indx <= Jndx
153.             If Indx < Right Then
154.                 StackPtr = StackPtr + 1
155.                 Stack&&(StackPtr + LeftMargin) = Indx
156.                 StackPtr = StackPtr + 1
157.                 Stack&&(StackPtr + LeftMargin) = Right
158.             End If
159.             Right = Jndx
160.         Loop Until Left >= Right
161.     Loop Until StackPtr = 0
162. End Sub
163.  
164.  
165. Sub Quicksort_QB64_v2
166.  
167.     InsertionsortTHRESHOLD = 0 '19
168.     Left = LBound(z)
169.     Right = UBound(z)
170.     ReDim Stack&&(Left To Right)
171.     StackPtr = 0
172.     StackPtr = StackPtr + 1
173.     Stack&&(StackPtr + LeftMargin) = Left
174.     StackPtr = StackPtr + 1
175.     Stack&&(StackPtr + LeftMargin) = Right
176.     Do 'Until StackPtr = 0
177.         Right = Stack&&(StackPtr)
178.         Left = Stack&&(StackPtr - 1)
179.         StackPtr = StackPtr - 2
180.         Do 'Until Left >= Right
181.  
182.             ''Classica' partitioning [
183.             'Pivot~&& = z((Left + Right) \ 2)
184.             'Indx = Left
185.             'Jndx = Right
186.             'Do
187.             '    Do While (z(Indx) < Pivot~&&)
188.             '        Indx = Indx + 1
189.             '    Loop
190.             '    Do While (z(Jndx) > Pivot~&&)
191.             '        Jndx = Jndx - 1
192.             '    Loop
193.             '    If Indx <= Jndx Then
194.             '        If Indx < Jndx Then Swap z(Indx), z(Jndx)
195.             '        Indx = Indx + 1
196.             '        Jndx = Jndx - 1
197.             '    End If
198.             'Loop While Indx <= Jndx
199.             ''Classica' partitioning ]
200.  
201.             ' 'Magnetica' partitioning [
202.             Jndx = Right
203.             PL = Left
204.             PR = Left
205.             Swap z((Left + Right) \ 2), z(PR) 'Swap z(Left + (Right - Left) \ 4), z(PR)
206.             Pivot~&& = z(PR)
207.             Do While PR < Jndx
208.                 If Pivot~&& > z(PR + 1) Then
209.                     Swap z(PL), z(PR + 1)
210.                     PL = PL + 1
211.                     PR = PR + 1
212.                 ElseIf Pivot~&& = z(PR + 1) Then
213.                     PR = PR + 1
214.                 Else ' < i.e. Pivot~&& < z(PR + 1)
215.                     Do While Pivot~&& < z(Jndx)
216.                         Jndx = Jndx - 1
217.                     Loop
218.                     If PR + 1 < Jndx Then Swap z(PR + 1), z(Jndx)
219.                     Jndx = Jndx - 1
220.                 End If
221.             Loop
222.             Jndx = PL - 1
223.             Indx = PR + 1
224.             ' 'Magnetica' partitioning ]
225.  
226.             If Indx + InsertionsortTHRESHOLD < Right Then 'if the remaining chunk is bigger than 'InsertionsortTHRESHOLD' push it to stack, otherwise leave all such chunks unsorted
227.                 StackPtr = StackPtr + 2
228.                 Stack&&(StackPtr - 1) = Indx
229.                 Stack&&(StackPtr) = Right
230.             End If
231.             Right = Jndx
232.         Loop Until Left >= Right
233.     Loop Until StackPtr = 0
234.     'Left = LBound(z)
235.     'Right = UBound(z)
236.     'For i = Left + 1 To Right ' i.e. 1 to size-1 omitting the first (which is 0)
237.     '    j = i
238.     '    Do While j >= 1 'Nah, start using a sentinel
239.     '        If z(j - 1) > z(j) Then Swap z(j - 1), z(j) Else Exit Do
240.     '        j = j - 1
241.     '    Loop
242.     'Next i
243. End Sub
244.  

[bplus]

Oh, and  @bplus your recursive quicksort crashes (with mere 100,000 elements) without even giving an error on exit,

Did 100,000,000 items for me without mods:
 

[Sanmayce]

Did 100,000,000 items for me without mods:

You didn't notice what the QB64 snippet holds, in above post. It is your test, but modified to sort 'Organ Pipe' instead of 'Random' dataset. It crashes with 100,000 using QB64 32bit. It is interesting to see how much QB64 64bit can handle before crashing. Beside this, qsm.h is from 11x to 2x faster, that's why I recommend it. In the screenshot below, Run #1 is your QB64 code, whereas Run #2 is qsm.h:

 

Code: QB64: [Select]

1. Laptop Intel i5-7200U 3.1GHz max turbo, 36GB DDR4 2133MHz:
2. +--------------------+---------------------------+---------------------------+---------------------------+
3. | Performer/Keys     | FEW distinct              | MANY distinct             | ~ALL distinct             |
4. +--------------------+-------------+-------------+-------------+-------------+-------------+-------------+
5. |  Operating System, | Windows 10, | Fedora 33,  | Windows 10, | Fedora 33,  | Windows 10, | Fedora 33,  |
6. |      Compiler, -O3 | Intel v15.0 | GCC 10.2.1  | Intel v15.0 | GCC 10.2.1  | Intel v15.0 | GCC 10.2.1  |
7. +--------------------+-------------+-------------+-------------+-------------+-------------+-------------+
8. | qsort              |  58 seconds | 360 seconds | 343 seconds | 535 seconds | 444 seconds | 519 seconds |
9. | Magnetica r.2      |  35 seconds |  35 seconds | 214 seconds | 222 seconds | 271 seconds | 286 seconds |
10. | Bentley-McIlroy    |  39 seconds |  41 seconds | 203 seconds | 230 seconds | 275 seconds | 313 seconds |
11. +--------------------+-------------+-------------+-------------+-------------+-------------+-------------+
12. Legend (The time is exactly the Sort process time):
13. FEW = 2,233,861,800 keys, of them distinct = 10;
14. MANY = 2,482,300,900 keys, of them distinct = 2,847,531;
15. ~ALL = 2,009,333,753 keys, of them distinct = 1,912,608,132
16.  

Quick highlights:
- GLIBC's qsort is just trash;
- Intel's qsort is trashy;
- Bentley-McIlroy is good, however the disassembly (-O3) shows many weird vector instructions used, not good for a scalar code;
- Magnetica r.2 is nice, the disassembly (-O3) gladdens the eyes.

Finally, wanted all fellow members, interested in writing their own "intrinsics" (in its original sense - "essential"), to have one booklet showing how much C code can reinforce the QB64 muscle flexing:

 

With this my Quicksort detour is completed.