Re: Maximum list size [was Re: Sifting a list sans loop]
Re: Maximum list size [was Re: Sifting a list sans loop]
- Subject: Re: Maximum list size [was Re: Sifting a list sans loop]
- From: email@hidden (Michael Sullivan)
- Date: Tue, 29 Jan 2002 18:48:10 -0500
- Organization: Society for the Incurably Pompous
Mark Myers writes:
>
> So what is the limit for the number of items when returning a list, and
>
> what syntax might invoke it?
>
I was wondering the same thing myself. When I generated all the prime
>
numbers up to 50000 I created a list with 41537 members. I had put
>
error handling in the script to capture the point at which the list
>
"broke" and it never did.
Returning a list is not what breaks -- creating a new list is what
breaks at over 4060 + <mumble> items. If you are returning an existing
list that happens to have over 4100 items in it, it's no problem.
*Creating* a list within one command is the problem.
Since the error is stack overflow, I'm guessing the the algorithm used
in the various functions which generate a list is a recursive one which
is compiled to something using a stack, and the stack space allowed for
AS is 4096 word (each list item requires a level of recursion, and each
level of recursion requires a word on the stack to hold the instruction
pointer for popping back out to the calling function). There are
probably some other things that end up on the stack for various reasons
which is why the error happens sometimes at 4074, and sometimes at 4071,
etc.
My guess is that if you find the error consistently happens at 4071 with
one method, and 4074 with another, that the first method is doing
something different which takes an extra 3 words of stack space.
Chris Nebel or Jon Pugh probably know definitely whether I am very close
here or barking up the wrong tree. The fact that neither has said
anything like this yet makes me think they figure we're all a right
bunch of accuracy geeks without enough work to do for worrying about
it... :)
>
Then I set up a script that would build a
>
list with 1000000 members and it worked fine up to the point where I got
>
bored and stopped it, around a quarter of a million members. I found
>
that the process, even using a reference to the list and using "set end
>
to..." became very slow after 200000 members. It appeared to slow down
>
steadily the more members there were in the list.
>
Is there a limit to list size, other than available memory? Why does
>
adding items to the end of a list get slow when the list is large?
In a singly linked list, adding items to the end of the list is O(n).
In AppleScript, the constant factor for anything done with a compiled
bit of code from a single AS instruction is low enough that until the
list grows fairly large, the differences are overwhelmed by the high
constant time involved in interpreting the apple event request and
returning and calling appropriate machine code.
I suspect that, in fact, lists are doubly linked but "end" for some
reason does not use the tail info, while "item -1" does (or there may be
some very tricky structure going on that I'm not guessing at that gives
a similar result). "Item -1" appears to take longer for small to medium
size lists (probably a more involved interpretation than for "end"), but
on large lists remains constant, while end gets longer, until, as you
notice here, it can be quite slow on very large lists. See Kai
Edwards's post about test times for various ways to test whether a file
spec string represents a folder. My supposition and your result is
consistent with the data there.
Michael
--
Michael Sullivan
Business Card Express of CT Thermographers to the Trade
Cheshire, CT email@hidden