possible bug? Radically different time profile for list access in script objects or by explicit reference.
possible bug? Radically different time profile for list access in script objects or by explicit reference.
- Subject: possible bug? Radically different time profile for list access in script objects or by explicit reference.
- From: email@hidden (Michael Sullivan)
- Date: Fri, 8 Mar 2002 11:17:00 -0500
- Organization: Society for the Incurably Pompous
I wanted to post a copy of this over here because I'm not sure if any of
the apple folks read the macscrpt list.
In a discussion of sorts, and just how much faster Serge's qsort is than
a number of other folk's attempts at an n log n sort -- it came up that
applescript has a radically different time profile for accessing lists
through a reference (or encoded in a script object). The standard
handling is *far* slower on long lists.
Here is Serge Belleudy-d'Espinose's sample for seeing the behavior in
question:
------ test script
set vList to {}
set vRange to 1000
repeat with i from 1 to vRange
set end of vList to i
end repeat
set tStart to the ticks
-- slow
repeat with vItem in vList
set vItem to contents of vItem
-- do stuff with vItem
end repeat
set tMiddle to the ticks
-- fast
script vObject
property xList : missing value
end script
tell vObject
set its xList to vList
repeat with vItem in its vList
set vItem to contents of vItem
-- do stuff with vItem
end repeat
end tell
set tStop to the ticks
{tMiddle - tStart, tStop - tMiddle}
------ end test script
Note by trying different size lists that the behavior of the first
traversal is O(n^2), while the second one is O(n).
Here is a post I just wrote on the other list which has some speculation
on what might be going on:
Michael Sullivan writes:
>
Paul skinner writes:
>
> Looping through a 50000 item list takes 42 minutes.
>
> Looping through a reference to a 50000 item list takes 7 seconds.
>
> Looping through a reference to "MY" 50000 item list takes 8 seconds.
>
> Looping through a script object's 50000 item list takes 2 seconds.
>
> Looping through "MY" 50000 item list takes 2 seconds.
>
>
>
> To get larger differences without resorting to the ticks...
>
>
> Looping through a 200000 item list takes a really long time!
>
> (Somewhere in the neighbor hood of 2.85 hours. I hope you didn't
>
> think I'd really try to find out.)
>
>
Be glad you didn't, because it actually would have taken more like 10
>
hours. For some reason looping through lists without using some sort of
>
reference (or putting them in a script object) has O(n^2) behavior. Try
>
testing it with 500 items, then 1000 items. The reference forms will
>
take twice as long with 1000 items, but the standard form will take *4*
>
times as long. This is why for long lists, the time taken is
>
outrageous.
>
>
It's interesting -- we have a bunch of sorts written for applescript
>
that all fall victim to this bug. Instead of being O(nlogn) or O(n^2),
>
they end up being O(n^2logn) or O(n^3).
>
>
I call it a bug, because there's no good reason I can see that not using a
>
reference should cause this kind of difference. A small constant
>
factor, sure, but not O(n) v O(1) on returning an item.
>
>
Essentially, it's as if the whole list is being traversed every time you
>
get a single item in the one case, versus just going to the right spot
>
to grab the item in all the others. As if you had to search for each
>
item in the list, rather than accessing it by position.
>
>
> Looping through a reference to a 200000 item list takes 26 seconds.
>
> Looping through a reference to "MY" 200000 item list takes 27 seconds.
>
> Looping through a script object's 200000 item list takes 7 seconds.
>
> Looping through "MY" 200000 item list takes 7 seconds.
>
>
>
> If I can get a speed up of about 1466% by using the term 'my' when
>
> looping through lists does that mean that AppleScript's normal list
>
> access methods are broken?
>
>
Yes. Well, not really broken, exactly, as that would imply
>
non-correctness, but it certainly looks like a bug, or a design flaw
>
since O(1) item access is clearly expected on lists (and you get it
>
when using a reference).
>
>
I'd like to see a comment from Chris N. on this one.
>
>
My guess is that a temporary copy of the list is being made every time
>
an item is accessed, even if the list will not be changed. Explicitly
>
specifying a reference (which probably happens internally if using a
>
script object), tells the interpreter that the existing list can be
>
used.
>
>
My guess is that there's a missing "const &" (or whatever the equivalent
>
construct is in the language actually used -- 'const &' is C++) in some
>
important function prototypes in the list code.
>
>
The difference in speed between a script object or "my list" and the
>
explicit references is probably the difference between having the
>
reference resolved as an interpreted applescript step, and having it
>
done in the underlying compiled functions.
>
>
>
Michael
Should this be submitted as a bug report?
--
Michael Sullivan
Business Card Express of CT Thermographers to the Trade
Cheshire, CT email@hidden
_______________________________________________
applescript-users mailing list | email@hidden
Help/Unsubscribe/Archives:
http://www.lists.apple.com/mailman/listinfo/applescript-users
Do not post admin requests to the list. They will be ignored.