Benchmarking "sort" in JS, ASObC, AS etc

chrillek · July 7, 2023, 1:22pm

Inspired (or triggered?) by a recent post here I decided to run my own benchmarks on a more relevant task, namely sorting an array of (random) numbers.

The AppleScript code

use framework "Foundation"
use scripting additions
global arrayLength
global l

set arguments to (current application's NSProcessInfo's processInfo's arguments) as list

if count of arguments is 5 then
  set arrayLength to (item 5 of arguments) as number
else
  set arrayLength to 10000
end if

on setup()
	set l to {}
	repeat with i from 1 to arrayLength
		set end of my l to random number arrayLength
	end repeat
end setup


on qsort(theList, l, r)
	script o
		property cutoff : 10
		property p : theList
		
		on qsrt(l, r)
			set i to l
			set j to r
			set v to my p's item ((l + r) div 2)
			
			repeat while (j > i)
				set u to my p's item i
				repeat while (u < v)
					set i to i + 1
					set u to my p's item i
				end repeat
				
				set w to my p's item j
				repeat while (w > v)
					set j to j - 1
					set w to my p's item j
				end repeat
				
				if (i > j) then
				else
					set my p's item i to w
					set my p's item j to u
					set i to i + 1
					set j to j - 1
				end if
			end repeat
			
			if (j - l < cutoff) then
			else
				qsrt(l, j)
			end if
			
			if (r - i < cutoff) then
			else
				qsrt(i, r)
			end if
		end qsrt
		
		on isrt(l, r)
			set x to l
			set z to l + cutoff - 1
			if (z > r) then set z to r
			
			set v to my p's item x
			repeat with y from (x + 1) to z
				if (my p's item y < v) then
					set x to y
					set v to my p's item y
				end if
			end repeat
			
			tell my p's item l
				set my p's item l to v
				set my p's item x to it
			end tell
			
			set u to my p's item (l + 1)
			repeat with i from (l + 2) to r
				set v to my p's item i
				if (v < u) then
					set my p's item i to u
					repeat with j from (i - 2) to l by -1
						if (v < my p's item j) then
							set my p's item (j + 1) to my p's item j
						else
							set my p's item (j + 1) to v
							exit repeat
						end if
					end repeat
				else
					set u to v
				end if
			end repeat
		end isrt
	end script
	
	set listLen to (count theList)
	if (listLen > 1) then -- otherwise the handler will error
		-- Translate negative indices
		if (l < 0) then set l to listLen + l + 1
		if (r < 0) then set r to listLen + r + 1
		
		if (r = l) then
			-- No point in sorting just one item
		else
			-- Transpose transposed indices
			if (l > r) then
				set temp to l
				set l to r
				set r to temp
			end if
			
			if (r - l < o's cutoff) then
				-- Skip the Quicksort if cutoff or less items
			else
				o's qsrt(l, r)
			end if
			o's isrt(l, r)
		end if
	end if
	
	return -- nothing
end qsort

setup()
log arrayLength as string & " runs"
set startTime to current application's NSDate's now
qsort(l, 1, -1)
set thetime to ((startTime's timeIntervalSinceNow()) * -1000) as integer
log "pure AS: " & thetime & "ms"

setup()

set my text item delimiters to character id 0
set startTime to current application's NSDate's now
set c to run script "`" & l & ".split('\\x00').sort((a,b) => a-b))`" in "JavaScript"
set thetime to ((startTime's timeIntervalSinceNow()) * -1000) as integer
log "run script: " & thetime & "ms"

setup()

set NSl to current application's NSArray's arrayWithArray:l
set startTime to current application's NSDate's now
set c to NSl's sortedArrayUsingSelector:"compare:"
set thetime to ((startTime's timeIntervalSinceNow()) * -1000) as integer
log "NSArray: " & thetime & "ms"

setup()

set sortArray to "const l = '" & l & "';l.split('\\x00').sort((a,b) => a-b)"
set theJSContext to current application's JSContext's new()
set startTime to current application's NSDate's now
--set c to ((theJSContext's evaluateScript:sortArray)'s toObject() as list)
set c to ((theJSContext's evaluateScript:sortArray)'s toArray() as list)
set thetime to ((startTime's timeIntervalSinceNow()) * -1000) as integer
log "JSCore: " & thetime & "ms"

setup()

set sortArray to "const l = '" & l & "';l.split('\\x00').sort((a,b) => a-b)"
set theJSContext to current application's JSContext's new()
set startTime to current application's NSDate's now
--set c to ((theJSContext's evaluateScript:sortArray)'s toObject() as list)
set c to theJSContext's evaluateScript:sortArray
set thetime to ((startTime's timeIntervalSinceNow()) * -1000) as integer
log "JSCore, no cast: " & thetime & "ms"

The JavaScript code

(() => {
const  args = $.NSProcessInfo.processInfo.arguments;
const arrayLength = args.count == 5 ? +args.js[4].js : 10000;
const l = [];
for (i = 0 ; i < arrayLength; i++) {
  l[i] = Math.floor(Math.random() * 10000);
}
const startTime = Date.now();
l.sort((a,b) => a-b);
console.log(`${arrayLength} numbers sorted in ${Date.now() - startTime} ms`);
})()

Remarks

If the scripts are saved each to a separate file, they can be run by osascript -l <language> <scriptFile> <count>. <language> is “AppleScript” or “JavaScript”, <count> is the number of elements in the array/list to sort
The scripts output the timing results to standard error using log (AppleScript) and conole.log (JavaScript)
The array is set up anew before each different method to sort it for the AppleScript stuff
The qsort algorithm in the “pure AS” implementation is stolen from a post by @Nigel_Garvey here, from about 2012.

For the timing, I ran every script 10 times with the same array size like so repeat 10 { osascript -l AppleScript sort_bench.applescript 20000 } 2>&1 | sort in macOS’ zsh shell. This proved to give more stable results (aka a smaller standard deviation) than running them in Script Editor. In the latter, the results for the same method varied widely.

The results

1000 elements
pure AS: 296ms	    / 0.3
run script: 100ms	/ 0.1
NSArray: 0ms        / 0
JSCore: 3.2ms	    / 0.003
JSCore, no cast: 2ms / 0.002 
JS: 1.4ms           / 0.001

5000 elements:
pure AS: 394ms / 0.08
run script: 210ms / 0.04
NSArray: 2ms / 0.0004
JSCore: 16ms / 0.0032
JSCore, no cast: 10ms / 0.002
JS: 7ms / 0.0014

10000 elements:
pure AS: 569ms / 0.057
run script: 346ms / 0.035
NSArray: 4ms / 0.0004
JSCore: 35ms / 0.0035
JSCore, no cast: 21ms / 0.0021
JS: 12ms /0.0012

15000 elements:
pure AS: 660ms / 0.044
run script: 433ms / 0.029
NSArray: 7ms / 0.0005
JSCore: 49ms / 0.0033
JSCore, no cast: 31ms / 0.0021
JS: 19ms / 0.0013

20000 elements:
pure AS: 724ms / 0.036
run script: 587ms / 0.030
NSArray: 9ms / 0.0006
JSCore: 69ms / 0.0035
JSCore, no cast: 45ms / 0.003
JS: 27ms / 0.0018

It is quite obvious from the numbers that sorting an array in ObjC using NSArray is the fastest method, followed by the pure JavaScript sort() method.

NoteThat is, as @Nigel_Garvey points out below, partially due to the fact that the conversion from an AS list to a NSArray is not measured – this takes sometimes longer than the sort itself.

ObjC is about five times as fast as JS here. Next comes running the JavaScript in JSCore, which needs considerably time to coerce the result back to a list (compare the results for JSCore and JSCore, no cast). As was to be expected, pure AppleScript was the slowest method. Not so expected (after the results mentioned in the other thread) is that run script is faster than the pure AS variant.

I didn’t bother with running JS in Safari – too far-fetched for my taste.

Nigel_Garvey · July 7, 2023, 1:59pm

Hi @chrillek. That should be
set startTime to current application's NSDate's new()
in every case.

Ideally, each method should be tested on identical copies of the same list, since the actual time a sort takes depends on how many of what are being sorted from what initial state of disorder — as well as the type of sort and how competently it’s implemented, of course. Also, everything needed to convert the list to the other language’s equivalent and get a list result back at the end should be included in all the timings. (They’re not in the NSArray test, for example.) But your results are probably broadly correct.

chrillek · July 7, 2023, 2:15pm

Why? NSDates now returns a new NSDate object initialized to the current date and time, according to the documentation. And I don’t find a new() method in the NSDate documentation – but that might be just me.

Either that or averaging the results over a number of runs… It’s all in the law of big numbers

True. I created the two JSCore tests (with and without conversion to AS) because I noticed that there the conversion back to AS takes a lot of time.

For the record: With 10000 elements, the NSarray approach takes about 14ms with the conversion from AS to ObjC which is more than the pure JS solution. So, that is costly, since the conversion takes more time than the sort itself.

Nigel_Garvey · July 7, 2023, 2:37pm

NSDate's now errored when I ran the script and I assumed it was a bad edit. But I see now that now was introduced in macOS 10.15. My system’s macOS 10.14 (Mojave). According to Shane’s book, parameterless ASObjC methods should be followed by parentheses, not just left bare.

new() is a convenience method that’s existed for some time. In the case of NSDate, it produces an NSDate object initialised to the instant of its creation, much as you say now() does.

robertfern · July 7, 2023, 3:48pm

Do you have a link to the script? Would like to see if the old routine has been optimized.

chrillek · July 7, 2023, 4:03pm

I took it from this thread

and didn’t really bother to figure out if it was the latest or best – I just wanted a reasonably good Quicksort implementation in AppleScript. There might be better ones out there.

CJK · July 7, 2023, 8:18pm

It’s not actually doing any sorting, so that might be why:

chrillek:

                               ⤹                                 ↰
set c to run script "`" & l & ".split('\\x00').sort((a,b) => a-b))`" in "JavaScript"
                               🠵                                  🠵

The placement of the quotes means that the entire expression is simply a string. What this reveals, though, is that the mere task of assembling and returning a string using run script takes about as long as a standard script sorting 20000 items. I shouldn’t think the actual creation of a JS string will be the culprit, so it’s a combination of

Calling out to run script ₊ instantiation of a JavaScriptOSA shell

and/or

list → string conversion/concatenation

I imagine the latter presents the more significant burden.

Nigel_Garvey · July 7, 2023, 10:51pm

The “qsort” posted above is a Quicksort that’s been optimised to handle just the initial heavy lifting and to leave the fine detail to an insertion sort. In this version, the Quicksort simply leaves partitions of less than ten items and a single insertion sort sweeps the entire list after the Quicksort finishes. An alternative would be to switch to the insertion sort for just the short partitions while the QuickSort’s still in progress. The algorithmologist (?) Robert Sedgewick reckoned the latter was more efficient, but it doesn’t seem to make much difference in AppleScript. There are other ways to optimise Quicksort too, such as median-of-three pivot selection and tail call elimination. But it’s a lot of code to include them all.

When I was experimenting with the various sort algorithms years ago, I found that Quicksort’s speed came from the relatively few moves it needs to get items into the right parts of a list. However (in my implementations, at least!) it performs a lot more comparisons during a sort than does merge sort, so the latter’s faster at sorting items which take a long time to compare. My guess is that the language-provided sorts in chrillek’s tests are merge sorts, these being about the same speed as Quicksort in general use and stable into the bargain. But it’s just a guess.

chrillek · July 8, 2023, 9:51am

After the kind remarks of @Nigel_Garvey and @cjk, I fixed the code in the AppleScript script (the one that runs sort natively, using ASObjC, JavaScriptCore and run script ... in "JavaScript"). Please find the fixed version below. It now times the necessary casting operations, too, and all sorts are now real sorts, not only string operations

AppleScript code to benchmark "sort"

use framework "Foundation"
use scripting additions
global arrayLength
global l

set arguments to (current application's NSProcessInfo's processInfo's arguments) as list

if count of arguments is 5 then
  set arrayLength to (item 5 of arguments) as number
else
  set arrayLength to 10000
end if

on setup()
	set l to {}
	repeat with i from 1 to arrayLength
		set end of my l to random number arrayLength
	end repeat
end setup


on qsort(theList, l, r)
	script o
		property cutoff : 10
		property p : theList
		
		on qsrt(l, r)
			set i to l
			set j to r
			set v to my p's item ((l + r) div 2)
			
			repeat while (j > i)
				set u to my p's item i
				repeat while (u < v)
					set i to i + 1
					set u to my p's item i
				end repeat
				
				set w to my p's item j
				repeat while (w > v)
					set j to j - 1
					set w to my p's item j
				end repeat
				
				if (i > j) then
				else
					set my p's item i to w
					set my p's item j to u
					set i to i + 1
					set j to j - 1
				end if
			end repeat
			
			if (j - l < cutoff) then
			else
				qsrt(l, j)
			end if
			
			if (r - i < cutoff) then
			else
				qsrt(i, r)
			end if
		end qsrt
		
		on isrt(l, r)
			set x to l
			set z to l + cutoff - 1
			if (z > r) then set z to r
			
			set v to my p's item x
			repeat with y from (x + 1) to z
				if (my p's item y < v) then
					set x to y
					set v to my p's item y
				end if
			end repeat
			
			tell my p's item l
				set my p's item l to v
				set my p's item x to it
			end tell
			
			set u to my p's item (l + 1)
			repeat with i from (l + 2) to r
				set v to my p's item i
				if (v < u) then
					set my p's item i to u
					repeat with j from (i - 2) to l by -1
						if (v < my p's item j) then
							set my p's item (j + 1) to my p's item j
						else
							set my p's item (j + 1) to v
							exit repeat
						end if
					end repeat
				else
					set u to v
				end if
			end repeat
		end isrt
	end script
	
	set listLen to (count theList)
	if (listLen > 1) then -- otherwise the handler will error
		-- Translate negative indices
		if (l < 0) then set l to listLen + l + 1
		if (r < 0) then set r to listLen + r + 1
		
		if (r = l) then
			-- No point in sorting just one item
		else
			-- Transpose transposed indices
			if (l > r) then
				set temp to l
				set l to r
				set r to temp
			end if
			
			if (r - l < o's cutoff) then
				-- Skip the Quicksort if cutoff or less items
			else
				o's qsrt(l, r)
			end if
			o's isrt(l, r)
		end if
	end if
	
	return -- nothing
end qsort

setup()
-- pure AppleScript implementation
log "runs: " & arrayLength as string
set startTime to current application's NSDate's now
qsort(l, 1, -1)
set thetime to ((startTime's timeIntervalSinceNow()) * -1000) as integer
log "pure AS: " & thetime & "ms"

setup()
-- run script ... in "JavaScript"
set my text item delimiters to character id 0
set startTime to current application's NSDate's now
set scriptCode to "const l = '" & l & "';l.split('\\x00').sort((a,b) => a-b)"
set c to run script scriptCode in "JavaScript"
set thetime to ((startTime's timeIntervalSinceNow()) * -1000) as integer
log "run script: " & thetime & "ms"

setup()
-- ASObjC with NSArray
set startTime to current application's NSDate's now
set NSlist to current application's NSArray's arrayWithArray:l
set c to NSlists's sortedArrayUsingSelector:"compare:"
set thetime to ((startTime's timeIntervalSinceNow()) * -1000) as integer
log "NSArray: " & thetime & "ms"

setup()
-- JavaScriptCore
set theJSContext to current application's JSContext's new()
set startTime to current application's NSDate's now
set sortArray to "const l = '" & l & "';l.split('\\x00').sort((a,b) => a-b)"
set c to ((theJSContext's evaluateScript:sortArray)'s toArray() as list)
set thetime to ((startTime's timeIntervalSinceNow()) * -1000) as integer
log "JSCore: " & thetime & "ms"

setup()
-- JavaScriptCore without casting back to AS list
set theJSContext to current application's JSContext's new()
set startTime to current application's NSDate's now
set sortArray to "const l = '" & l & "';l.split('\\x00').sort((a,b) => a-b)"
set c to theJSContext's evaluateScript:sortArray
set thetime to ((startTime's timeIntervalSinceNow()) * -1000) as integer
log "JSCore, no cast: " & thetime & "ms"

Results

As can be seen, pure JavaScript performs slightly better than NSArray. The distance gets bigger with larger arrays. That may be because the ASObjC implementation using NSArray has to convert from an AppleScript list to an NSArray.

All other implementations (or utilization) of sort perform far worse, with pureAS the worst. JSCore is the best of the slow ones.

Interestingly, the time to sort 1000 elements remains mostly constant for most of the cases. Only pureAS performs noticeably slower for smaller arrays and is up-to par with run script at about 30000 elements.

These results are more congruent with intuition: JavaScript and the Foundation framework probably use similar, highly optimized sort algorithms. The ASObjC variant must still be slower than the pure JS one since it has to convert data from AppleScript to ObjC.

There’s only a single sort in the tests, namely the one of Apple’s JavaScript engine. How that is implemented … no idea. The ECMAscript standard keeps mum about that, it only requires a certain behavior. It may well be that they use different algorithms depending on array size.

And since it’s always the same function doing the actual work, one can see clearly the overhead introduced by the various methods to employ this function. To put it bluntly: If someone needs raw speed with sort, they should use NSArray or code in JavaScript directly. Anything else will slow things down to a crawl.

Nigel_Garvey · July 8, 2023, 11:03am

The NSArray method takes half as long again if you cast the sorted array back to list, but it’s still the fastest overall.

Just for something to do on a Saturday, here’s a minor reworking of your test script. The only significant differences are that all the sorts do the same sort and the overall running time is thus much shorter, especially with longer lists.

use framework "Foundation"
use scripting additions

on qsort(theList, l, r)
	script o
		property cutoff : 10
		property p : theList
		
		on qsrt(l, r)
			set i to l
			set j to r
			set v to my p's item ((l + r) div 2)
			
			repeat while (j > i)
				set u to my p's item i
				repeat while (u < v)
					set i to i + 1
					set u to my p's item i
				end repeat
				
				set w to my p's item j
				repeat while (w > v)
					set j to j - 1
					set w to my p's item j
				end repeat
				
				if (i > j) then
				else
					set my p's item i to w
					set my p's item j to u
					set i to i + 1
					set j to j - 1
				end if
			end repeat
			
			if (j - l < cutoff) then
			else
				qsrt(l, j)
			end if
			
			if (r - i < cutoff) then
			else
				qsrt(i, r)
			end if
		end qsrt
		
		on isrt(l, r)
			set x to l
			set z to l + cutoff - 1
			if (z > r) then set z to r
			
			set v to my p's item x
			repeat with y from (x + 1) to z
				if (my p's item y < v) then
					set x to y
					set v to my p's item y
				end if
			end repeat
			
			tell my p's item l
				set my p's item l to v
				set my p's item x to it
			end tell
			
			set u to my p's item (l + 1)
			repeat with i from (l + 2) to r
				set v to my p's item i
				if (v < u) then
					set my p's item i to u
					repeat with j from (i - 2) to l by -1
						if (v < my p's item j) then
							set my p's item (j + 1) to my p's item j
						else
							set my p's item (j + 1) to v
							exit repeat
						end if
					end repeat
				else
					set u to v
				end if
			end repeat
		end isrt
	end script
	
	set listLen to (count theList)
	if (listLen > 1) then -- otherwise the handler will error
		-- Translate negative indices
		if (l < 0) then set l to listLen + l + 1
		if (r < 0) then set r to listLen + r + 1
		
		if (r = l) then
			-- No point in sorting just one item
		else
			-- Transpose transposed indices
			if (l > r) then
				set temp to l
				set l to r
				set r to temp
			end if
			
			if (r - l < o's cutoff) then
				-- Skip the Quicksort if cutoff or less items
			else
				o's qsrt(l, r)
			end if
			o's isrt(l, r)
		end if
	end if
	
	return -- nothing
end qsort

on test(arguments)
	if ((count arguments) is 5) then
		set arrayLength to (item 5 of arguments) as number
	else
		set arrayLength to 10000
	end if
	
	-- Create a list to sort.
	script o
		property l : {}
	end script
	repeat arrayLength times
		set end of o's l to (random number arrayLength)
	end repeat
	log "List length: " & arrayLength
	
	-- Copy the list for the in-line AS sort, but this won't be necessary for the other sorts.
	copy o's l to theList
	-- pure AppleScript implementation
	set startTime to current application's NSDate's new()
	qsort(theList, 1, -1)
	set thetime to ((startTime's timeIntervalSinceNow()) * -1000) as integer
	log "AK/NG 'qsort': " & thetime & "ms"
	
	-- run script ... in "JavaScript"
	set startTime to current application's NSDate's new()
	set scriptCode to "const l = '" & join(o's l, character id 0) & "';l.split('\\x00').sort((a,b) => a-b)"
	set c to run script scriptCode in "JavaScript"
	set thetime to ((startTime's timeIntervalSinceNow()) * -1000) as integer
	log "run script: " & thetime & "ms"
	
	-- ASObjC with NSArray
	set startTime to current application's NSDate's new()
	set NSlist to current application's NSArray's arrayWithArray:(o's l)
	set c to (NSlist's sortedArrayUsingSelector:"compare:") as list
	set thetime to ((startTime's timeIntervalSinceNow()) * -1000) as integer
	log "NSArray: " & thetime & "ms"
	
	-- JavaScriptCore
	set startTime to current application's NSDate's new()
	set theJSContext to current application's JSContext's new()
	set sortArray to "const l = '" & join(o's l, character id 0) & "';l.split('\\x00').sort((a,b) => a-b)"
	set c to ((theJSContext's evaluateScript:sortArray)'s toArray() as list)
	set thetime to ((startTime's timeIntervalSinceNow()) * -1000) as integer
	log "JSCore: " & thetime & "ms"
	
	-- JavaScriptCore without casting back to AS list
	set startTime to current application's NSDate's new()
	set theJSContext to current application's JSContext's new()
	set sortArray to "const l = '" & join(o's l, character id 0) & "';l.split('\\x00').sort((a,b) => a-b)"
	set c to theJSContext's evaluateScript:sortArray
	set thetime to ((startTime's timeIntervalSinceNow()) * -1000) as integer
	log "JSCore, no cast: " & thetime & "ms"
end test

on join(lst, delim)
	set astid to AppleScript's text item delimiters
	set AppleScript's text item delimiters to delim
	set txt to lst as text
	set AppleScript's text item delimiters to astid
	return txt
end join

on run
	test((current application's NSProcessInfo's processInfo()'s arguments()) as list)
end run

chrillek · July 8, 2023, 4:20pm

Sure? That seems a bit contra-intuitive. And here, it takes about half as long if I don’t cast back to a list:

List length: 100000
NSArray: 229ms
NSArray, no cast: 141ms

and for a larger array:

List length: 500000
NSArray: 1280ms
NSArray, no cast: 773ms

And just for completeness’ sake, I added another method to the JS version:

startTime = Date.now();
const sortedList = $(l).sortedArrayUsingSelector("compare:").js.map(s => s.js);
console.log(`JS -> NSArray: ${Date.now() - startTime}ms`);

which gives

pureJS: 13ms
JS -> NSArray: 389ms

So, abysmal would be the correct description here. Most of the time will be consumed by the casting operations from JS to NSArray and back from NSArray to JS. After that, all the elements have to be converted to JS numbers, too.

Conclusion: Do as much as you can in JavaScript, if you’re coding in it anyway. Excursions in ObjC land are expensive time-wise.

Nigel_Garvey · July 8, 2023, 4:38pm

Half as long again — ie. one and a half times as long.

chrillek · July 8, 2023, 4:42pm

Ah. The vagaries of a foreign language … I’d never encountered that term before, so it send me barking up the wrong tree. My apologies.

Nigel_Garvey · July 8, 2023, 5:02pm

No problem. I didn’t realise you weren’t a native English speaker. Your English is very good!

peavine · July 9, 2023, 1:18pm

FWIW, I edited Nigel’s script to include a few additional ASObjC scenarios. Also, for no particular reason, I eliminated script objects from the code. The results on my 2023 Mac mini with arrayLength set to 10000 were:

(JSCore from a list to a JSValue: 108ms)
(JSCore from a list to a list: 113ms)
(Run Script JavaScript from a list to a List: 149ms)
(ASObjC from an array to an array: 5ms)
(ASObjC from a list to an array: 8ms)
(ASObjC from a list to a list: 11ms)

I tested Nigel’s script on my computer and, not surprisingly, the results (where available) were essentially identical to those above.

My results with arrayLength set to 50000 were:

(JSCore from a list to a JSValue: 545ms)
(JSCore from a list to a list: 571ms)
(Run Script JavaScript from a list to a List: 635ms)
(ASObjC from an array to an array: 29ms)
(ASObjC from a list to an array: 47ms)
(ASObjC from a list to a list: 61ms)

chrillek · July 10, 2023, 9:46am

Right, I’m not coded by ChatGPT. Nor do I use it to write code.

So, 10000 items get sorted in 19.7ms – that’s a bit slower than the ASObjC variant using NSArray. I wonder how that might be the explained.

chrillek · July 10, 2023, 10:05am

So, on your machine ASObjC runs sort faster than Swift, and by one order of magnitude? Curious. Did you run the swift code as script, or did you compile it?

chrillek · July 10, 2023, 10:40am

Thanks for the link to Jukka’s post on stack overflow. That looks really not very good for Swift, though the post is three years old – your test seems to show the same abysmal sort behavior.

@Fredrik71 When I compile the code without any flag, it runs in about 4400 ms on my machine. When I compile it with -O (which seems reasonable), it runs in about 100 ms. Might be worth trying.

robertfern · July 23, 2023, 5:40pm

Here is the QuickSort routine I use. pure AppleScript and compact.

on quickSort(blist) -- Non-Recursive FASTEST
	local px, lo, hi, L, H, sw -- px means 'Pivot Index'
	script Q
		property stack : {}
		property alist : blist
	end script
	--=Q
	set end of Q's stack to {1, count Q's alist}
	repeat until (count Q's stack) = 0
		set lo to item 1 of item 1 of Q's stack
		set hi to item 2 of item 1 of Q's stack
		set px to item ((hi + lo) div 2) of Q's alist -- start partitionHoare
		set L to lo
		set H to hi
		repeat
			repeat while item L of Q's alist < px
				set L to L + 1
			end repeat
			repeat while item H of Q's alist > px
				set H to H - 1
			end repeat
			if L ≥ H then exit repeat
			set sw to item L of Q's alist
			set item L of Q's alist to item H of Q's alist
			set item H of Q's alist to sw
			set L to L + 1
			set H to H - 1
		end repeat
		set px to H -- end of partitionHoare
		set Q's stack to rest of Q's stack
		if px + 1 < hi then
			set beginning of Q's stack to {px + 1, hi}
		end if
		if lo < px then
			set beginning of Q's stack to {lo, px}
		end if
	end repeat
end quickSort

Shane_Stanley · July 24, 2023, 2:35am

In the case of Objective-C, arrays are usually stored in subclasses of NSArray, depending on their contents. The subclasses then have their own implementations for the sort methods, customised to suit the particular subclass. The result is that when you sort a large array in ASObjC, the sorting probably uses a different routine than when you sort a small array – the optimisation is done for you.