[REBOL] Re: Implicit Copying: WAS => Re: Re: How to remove the last item of a se
From: g::santilli::tiscalinet::it at: 6-May-2002 21:01
Hi Jason,
On Monday, May 06, 2002, 2:56:53 PM, you wrote:
JC> What does 0(1) mean?
In few words, that the algorithm requires constant time (not
dependent on the size of the input). It's the common notation to
express the upper bound to the complexity of an algorithm.
JC> ..Does that mean every time you add/append to it?
Not every time. Only if you go beyond the allocated space.
I.e. when you write:
str: make string! 1024
you get an empty string, but REBOL actually allocates the space
needed for 1024 characters. So you can append to it without REBOL
needing to reallocate the string, until to get to more than 1024
characters. (REBOL will not respect the number you give precisely.
It only guarantees that it is allocating AT LEAST that amount of
space.)
JC> In general when I do
>>> test: ""
JC> == ""
>>> append test {hello }
JC> == "hello "
>>> append test {hello }
JC> == "hello hello "
>>> append test {hello }
JC> == "hello hello hello "
JC> ..is REBOl copying 'test' internally each time?
To answer your question, one should know how much space did REBOL
allocate when you wrote:
test: ""
(You can look at system/stats or use some of the tools on the REB
to discover it.) Also, it might depend on the OS too, since a
smart OS might just increase the allocated space without having to
move any data if there is space available after the end of the
allocated chunk of memory.
JC> Once 'htmlpage' is over 1024, does REBOL also starts copying it in the
JC> background for each addition?
I think it increases it by a factor of 2 each time, up until a
limit (whose value I don't recall), after which it increases
linearly.
JC> We need to build large image hyperlink matrices in HTML and want REBOL to return
JC> the result string as fast as possible.
If you know in advance how much space you'll need, you can
preallocate it. If you don't, you can only make guesses, or use a
trick such as:
my-func: func [a b c /local result] [
result: clear ""
; code that appends to result
copy result
]
so that after calling my-func some times, result (which is not
created each time, but reused) will get to the needed size, and
the copying happens only once when returning the value (copying
that can be avoided in some cases). Of course noone stops the GC
from freeing the used space every time you clear it, but I don't
think it is really doing it, in the current version at least.
Regards,
Gabriele.
--
Gabriele Santilli <[g--santilli--tiscalinet--it]> -- REBOL Programmer
Amigan -- AGI L'Aquila -- REB: http://web.tiscali.it/rebol/index.r
