DIM and room
Andrew W
capacity, the array does not occupy the full extent of its memory and
so HIMEM-top of variables is not the same as it would be were the array
full.
However, can I be sure that if at the start of the program when I
READ/INPUT# a certain amount of data into the array that the displayed
memory available (HIMEM-top of variables) won't be used up by the rest
of the program, thus preventing full expansion of the array later in
the program's use?
regards,
A.Weston
--
Staffordshire, Great Britain.
druck
> If I've reserved an array using DIM and proceed to use it below
> capacity, the array does not occupy the full extent of its memory and
> so HIMEM-top of variables is not the same as it would be were the array
> full.
If its an array of strings, as the array itself just contains pointers to the
string data, which is allocated on the heap.
> However, can I be sure that if at the start of the program when I
> READ/INPUT# a certain amount of data into the array that the displayed
> memory available (HIMEM-top of variables) won't be used up by the rest
> of the program, thus preventing full expansion of the array later in
> the program's use?
If you completely run out of memory in the application space you wont be able
populate the rest of the string array. But as long as there is enough memory
you wont be prevented from completing the population after other memory
claims.
---druck
--
The ARM Club Free Software - http://www.armclub.org.uk/free/
The 32bit Conversions Page - http://www.quantumsoft.co.uk/druck/
Steve Drain
> Andrew W wrote:
> > If I've reserved an array using DIM and proceed to use it below
> > capacity, the array does not occupy the full extent of its memory and
> > so HIMEM-top of variables is not the same as it would be were the array
> > full.
> If its an array of strings, as the array itself just contains pointers to the
> string data, which is allocated on the heap.
Just to elaborate a little.
Numeric arrays are dimensioned as full arrays but with a zero value for
each element - integer elements are 4 bytes and float elements are 5
bytes (or 8 bytes for BASIC64). So once dimensioned there is no change
in the memory requirement.
String arrays are dimensioned as a full set of 'string infomation
blocks' (SIB) each of 5 bytes (a pointer and string length byte) which
are initially null. From then on the string values themselves are
allocated in just the same way as single string variables and come from
the heap. However, there is a cunning system, the string allocation
table, that reuses string blocks that are no longer allocated, so it can
be quite difficult to predict exactly how much memory will be required
by a program at runtime.
> > However, can I be sure that if at the start of the program when I
> > READ/INPUT# a certain amount of data into the array that the displayed
> > memory available (HIMEM-top of variables) won't be used up by the rest
> > of the program, thus preventing full expansion of the array later in
> > the program's use?
If they are numeric arrays you have no further problem. If they are
string arrays you may come up against a memory limit at runtime and the
usual recommendation is to increase the WimpSlot in stages until there
are no runtime limits.
BTW HIMEM-TOP is not really a reliable indication of available memory
because you have to take into account the Stack which may also hold
local arrays etc. You might get more feel for how all this fits together
from my comprehensive StrongHelp BASIC manual at:
http://www.users.zetnet.co.uk/kappa/basic.htm
--
; ,', * Basalt * - gives RO 3.10+ versions of BASIC V new and alternative
;,' keywords, dynamic memory for arrays and blocks, new variable types.
;', Legal, fast and simple to use. Freeware - version 0.98ß - 19 Aug 03
,; ',, Steve Drain, Kappa : http://www.users.zetnet.co.uk/kappa/basalt.htm
Andrew W
<URL:mailto:steve...@kappa.zetnet.co.uk> wrote:
> druck wrote:
<snip>
> > > However, can I be sure that if at the start of the program when I
> > > READ/INPUT# a certain amount of data into the array that the displayed
> > > memory available (HIMEM-top of variables) won't be used up by the rest
> > > of the program, thus preventing full expansion of the array later in
> > > the program's use?
>
> If they are numeric arrays you have no further problem. If they are
> string arrays you may come up against a memory limit at runtime and the
> usual recommendation is to increase the WimpSlot in stages until there
> are no runtime limits.
>
> BTW HIMEM-TOP is not really a reliable indication of available memory
> because you have to take into account the Stack which may also hold
> local arrays etc.
I'm using DIM A% -1
P.HIMEM-A%
I'm assuming the stack is in the variable workspace?
> You might get more feel for how all this fits together
> from my comprehensive StrongHelp BASIC manual at:
>
> http://www.users.zetnet.co.uk/kappa/basic.htm
>
I'll have a look at this thanks.
Andrew W
<URL:mailto:ne...@druck.freeuk.com> wrote:
> > If I've reserved an array using DIM and proceed to use it below
> > capacity, the array does not occupy the full extent of its memory and
> > so HIMEM-top of variables is not the same as it would be were the array
> > full.
>
> If its an array of strings, as the array itself just contains pointers to the
> string data, which is allocated on the heap.
>
> > However, can I be sure that if at the start of the program when I
> > READ/INPUT# a certain amount of data into the array that the displayed
> > memory available (HIMEM-top of variables) won't be used up by the rest
> > of the program, thus preventing full expansion of the array later in
> > the program's use?
>
> If you completely run out of memory in the application space you wont be able
> populate the rest of the string array. But as long as there is enough memory
> you wont be prevented from completing the population after other memory
> claims.
>
So for example if I want an array of 5 strings, potentially 255 bytes
in length, DIM text$(4), then if memory was going to become limited I'd
need to make sure that at no time HIMEM-top of variables left less than
255*5 bytes available?
i.e. I'd have to assume that the arrays were always at maximum usage?
Sophie Wilson
Or you'ld have to know how much memory is in the deallocated strings - see
PList procedures in the assistant library below.
--Sophie
10REM > Assistant - Sophie's aid to AB debugging. PROCAssHelp
20PROCASSHELP:END
30DEF PROCASSHELP
40DEF PROCasshelp
50DEF PROCAssHelp
60PRINT"Assistant procedure library:"
70PRINT"FNScalarProduct(A(),B()) scalar product of real vectors"
80PRINT"PROCDumpProg display hex of program"
90PRINT"PROCPurgeProg purge trailing spaces from program"
100PRINT"PROCShowIntArray(A%()) display integer array"
110PRINT"PROCShowRealArray(A()) display real array"
120PRINT"PROCShowStringArray(A$()) display string array"
130PRINT"PROCPList compute space in string store"
140PRINT"PROCPListA display string store lists"
150PRINT"PROCPListI display space in each string store
list"
160ENDPROC
170DEF PROCDUMPPROG
180DEF PROCdumpprog
190DEF PROCDumpProg
200LOCAL Z%,@%:@%=4:PRINT"Program is:-"
210FOR Z%=PAGE TO TOP-1:PRINT~?Z%;:NEXT:PRINT';TOP-PAGE" bytes long"
220ENDPROC
230DEF PROCPURGEPROG
240DEF PROCpurgeprog
250DEF PROCPurgeProg
260Z%=PAGE:A%=Z%:REPEAT
270S%=Z%:L%=S%?1*256+S%?2
280B%=S%?3:REM length of original line
290Z%+=B%
300REM trailing spaces
310WHILE S%?(B%-1)=32:B%-=1:ENDWHILE
320REM new end of line mark
330S%?B%=13
340FOR Q%=0 TOB%:A%?Q%=S%?Q%:NEXT
350A%?3=B%
360A%+=B%
370UNTIL Z%?1=&FF
380A%?1=&FF
390PRINT Z%-A%" bytes saved"
400END
410ENDPROC
420DEF PROCSHOWINTARRAY(A%())
430DEF PROCshowintarray(A%())
440DEF PROCShowIntArray(A%())
450CASE DIM(A%()) OF
460WHEN 1
470LOCAL Z%,@%:@%=&A0A:FOR Z%=0 TO DIM(A%(),1):PRINT A%(Z%);:NEXT:PRINT
480WHEN 2
490LOCAL X%,Y%,@%:@%=&A0A
500FOR X%=0 TO DIM(A%(),1):FOR Y%=0 TO DIM(A%(),2)
510PRINT A%(X%,Y%);:NEXT:PRINT
520NEXT
530OTHERWISE
540ERROR 142,"Can't show big arrays yet"
550ENDCASE
560ENDPROC
570DEF PROCSHOWREALARRAY(A())
580DEF PROCshowrealarray(A())
590DEF PROCShowRealArray(A())
600CASE DIM(A()) OF
610WHEN 1
620LOCAL Z%,@%:@%=&80A:FOR Z%=0 TO DIM(A(),1):PRINT A(Z%);:NEXT:PRINT
630WHEN 2
640LOCAL X%,Y%,@%:@%=&80A
650FOR X%=0 TO DIM(A(),1):FOR Y%=0 TO DIM(A(),2)
660PRINT A(X%,Y%);:NEXT:PRINT
670NEXT
680OTHERWISE
690ERROR 142,"Can't show big arrays yet"
700ENDCASE
710ENDPROC
720DEF PROCSHOWSTRINGARRAY(A$())
730DEF PROCshowstringarray(A$())
740DEF PROCShowStringArray(A$())
750CASE DIM(A$()) OF
760WHEN 1
770LOCAL Z%,@%:@%=&904:FOR Z%=0 TO DIM(A$(),1):PRINT Z%" <"A
$(Z%)">":NEXT:PRINT
780WHEN 2
790LOCAL X%,Y%,@%:@%=&904
800FOR X%=0 TO DIM(A$(),1):FOR Y%=0 TO DIM(A$(),2)
810PRINT A$(X%,Y%);:NEXT:PRINT
820NEXT
830OTHERWISE
840ERROR 142,"Can't show big arrays yet"
850ENDCASE
860ENDPROC
870DEF FNSCALARPRODUCT(A(),B())
880DEF FNScalarProduct(A(),B())
890IF DIM(A())<>1 OR DIM(B())<>1 ERROR 42,"Scalar product needs vectors"
900IF DIM(A(),1)<>DIM(B(),1) ERROR 42,"Scalar product vectors should be
same size"
910LOCAL C()
920DIM C(DIM(A(),1)):C()=A()*B()
930=SUM C()
940DEF PROCPLIST
950DEF PROCPList
960P%=END:[OPT0:STR R8,P%:MOV PC,R14:]:CALL END
970B%=0:C%=0:D%=!END-&700+256+512+256:FOR E%=4 TO256 STEP 4
980A%=D%-4+E%:WHILE!A%:C%+=1:B%+=E%:A%=!A%:ENDWHILE
990NEXT
1000PRINT"There are ";B%" bytes in the list, ";C%" entries"
1010ENDPROC
1020DEF PROCPLISTA
1030DEF PROCPListA
1040P%=END:[OPT0:STR R8,P%:MOV PC,R14:]:CALL END
1050B%=0:C%=0:D%=!END-&700+256+512+256:LOCAL@%:@%=10:FOR E%=4 TO256 STEP 4
1060A%=D%-4+E%:IF!A% THEN
1070PRINT"Size ";E%" bytes:"
1080WHILE!A%:PRINT~A%;:C%+=1:B%+=E%:A%=!A%:ENDWHILE:PRINT
1090ENDIF
1100NEXT
1110PRINT"There are ";B%" bytes in the list, ";C%" entries"
1120ENDPROC
1130DEF PROCPLISTI
1140DEF PROCPListI
1150P%=END:[OPT0:STR R8,P%:MOV PC,R14:]:CALL END
1160B%=0:C%=0:D%=!END-&700+256+512+256:LOCAL@%:@%=10:FOR E%=4 TO256 STEP 4
1170A%=D%-4+E%:IF!A% THEN
1180F%=0:WHILE!A%:C%+=1:B%+=E%:F%+=1:A%=!A%:ENDWHILE
1190PRINT"Size"E%" bytes: "F%" entries (";F%*E%" bytes)"
1200ENDIF
1210NEXT
1220PRINT"There are ";B%" bytes in the list, ";C%" entries"
1230ENDPROC
ne...@rtrussell.co.uk
: I'm assuming the stack is in the variable workspace?
No, the stack grows down from HIMEM. If you're using a version
of BASIC which supports DIM LOCAL you can discover the current
bottom of the stack with DIM S% LOCAL -1. So in this case the
amount of free space would be found as follows:
DIM S% LOCAL -1 : REM Bottom of stack
DIM H% -1 : REM Top of heap
free_space% = S% - H%
Richard
http://www.rtrussell.co.uk/
To reply by email change 'news' to my forename.
druck
[Useful stuff snipped]
Great to know you are still tuning in!
Steve Drain
> Andrew W wrote:
> > So for example if I want an array of 5 strings, potentially 255 bytes
> > in length, DIM text$(4), then if memory was going to become limited
> > I'd need to make sure that at no time HIMEM-top of variables left less
> > than 255*5 bytes available?
> > i.e. I'd have to assume that the arrays were always at maximum usage?
> Or you'ld have to know how much memory is in the deallocated strings - see
> PList procedures in the assistant library below.
>
> --Sophie
I think I am right to observe that although it tells you more about
memory used it still cannot tell you how future use of strings may
increase the requirement, because it depends on whether there are
matches to the lengths of deallocated blocks.
I can remember how you showed that with lots of random string
allocations memory usage would eventually stabilise, but the final
figure is not entirely predictable and it will not be much help in this
case. ;-)
I am still unhappy with the use of HIMEM-FSA [3] as an indicator of
available memory. Basalt has a function that returns the current Free
Space, but even that cannot predict how the Stack will change.
Because Basalt has a dynamic heap above HIMEM it also has a method of
allocating string blocks [1] from that and this reduces the uncertainty
of memory usage highlighted here. It is not as fast on assignment, but
is suitable for longish, seldom changed strings and it has the advantage
that unallocated blocks may be CLEARed. [2]
[1] LET a$=STRING$(128,"a") allocates a block from the dynamic heap if a
128 byte string block is not available - note that LET cannot here be
used in programs for normal assignments.
[2] CLEAR$ 128 removes all string blocks more than 127 bytes long from
the string allocation table if they have been claimed from the dynamic
heap.
[3] FSA = free space address (I think) and is what Andrew is meaning
by 'top of variables' - this is for general information, not for
Sophie, of course ;-)
ne...@rtrussell.co.uk
: Or you'ld have to know how much memory is in the deallocated strings - see
: PList procedures in the assistant library below.
As Sophie's monitoring the group perhaps I can ask a relevant
question. Delving through the records of changes to BASIC V
I see that at one time a string was allowed to expand into
contiguous free-space (i.e. if a string stored at the very top
of the heap exceeded its allocated size, it could be lengthened
without reallocation). This facility was removed because it
could result in excessive memory consumption in specific, if
uncommon, circumstances.
When changing BBC BASIC for Windows to support 65535-character
strings I encountered exactly this phenomenon, and similarly
concluded that expanding a string into contiguous free-space
must not be allowed. However further investigation proved this
not to be strictly true. If a block of the correct size is
available in the the deallocated string space then, indeed, it
must be used in preference to expanding, however *if no block
of that size* exists in the deallocated string space then it
is OK to expand into contiguous free space rather than allocate
a new block.
This meant I only had to reverse the order of two tests. If a
block of the correct length is available use it, otherwise if
the string is at the top of the heap then expand it in place.
Comparing 'BBC BASIC for Windows' with 'Brandy' (both of which
support 65535-character strings) BBC BASIC invariably uses less
memory for strings, sometimes significantly less.
The question for Sophie is did she try this in BASIC V ? It
might have resulted in a worthwhile reduction in string memory
usage.
Richard.
Steve Drain
> Sophie Wilson wrote:
> > Or you'ld have to know how much memory is in the deallocated strings - see
> > PList procedures in the assistant library below.
> strings I encountered exactly this phenomenon, and similarly
> concluded that expanding a string into contiguous free-space
> must not be allowed. However further investigation proved this
> not to be strictly true. If a block of the correct size is
> available in the the deallocated string space then, indeed, it
> must be used in preference to expanding, however *if no block
> of that size* exists in the deallocated string space then it
> is OK to expand into contiguous free space rather than allocate
> a new block.
>
> This meant I only had to reverse the order of two tests. If a
> block of the correct length is available use it, otherwise if
> the string is at the top of the heap then expand it in place.
>
> Comparing 'BBC BASIC for Windows' with 'Brandy' (both of which
> support 65535-character strings) BBC BASIC invariably uses less
> memory for strings, sometimes significantly less.
>
> The question for Sophie is did she try this in BASIC V ? It
> might have resulted in a worthwhile reduction in string memory
> usage.
In the absence of an immediate reply I'll butt in. ;-)
I think this does happen in BASIC V, but I would describe it
differently. If a string block that is being deallocated is at the top
of the heap then FSA is *reduced* (AFAIK the only time it is) and the
block is not added to the string allocation table (SAT).
This leads to the equivalent of what you describe above. If a string
variable with its block at the top of the heap is extended then the
block is abandoned and only if a free block of the new size is not
available from the SAT is a new extended block claimed, expanding the
heap over the space originally occupied by the abandoned string block.
Does that make sense? ;-)
Andrew W
<URL:mailto:sophie...@bigfoot.com> wrote:
> >>
> > So for example if I want an array of 5 strings, potentially 255 bytes
> > in length, DIM text$(4), then if memory was going to become limited
> > I'd need to make sure that at no time HIMEM-top of variables left less
> > than 255*5 bytes available?
> > i.e. I'd have to assume that the arrays were always at maximum usage?
>
> Or you'ld have to know how much memory is in the deallocated strings - see
> PList procedures in the assistant library below.
>
<snip listing>
Thanks very much.
Andrew W
<URL:mailto:steve...@kappa.zetnet.co.uk> wrote:
>
>
> I think I am right to observe that although it tells you more about
> memory used it still cannot tell you how future use of strings may
> increase the requirement, because it depends on whether there are
> matches to the lengths of deallocated blocks.
>
> I can remember how you showed that with lots of random string
> allocations memory usage would eventually stabilise, but the final
> figure is not entirely predictable and it will not be much help in this
> case. ;-)
>
varies between 20-30 bytes) then I'm assuming that doesn't deallocate
very much although I'd have to read into how the allocation system
works to check that.
Andrew W
<URL:mailto:ne...@rtrussell.co.uk> wrote:
> No, the stack grows down from HIMEM. If you're using a version
> of BASIC which supports DIM LOCAL you can discover the current
> bottom of the stack with DIM S% LOCAL -1. So in this case the
> amount of free space would be found as follows:
>
> DIM S% LOCAL -1 : REM Bottom of stack
> DIM H% -1 : REM Top of heap
> free_space% = S% - H%
>
What about earlier BASIC, no easy way?
The stack size depends upon how many loops and procedures are in use
at any one time doesn't it? If I'm only using, say, 2 at a time then
the stack won't be very big at all will it?
Richard Russell
> This leads to the equivalent of what you describe above. If a string
> variable with its block at the top of the heap is extended then the
> block is abandoned and only if a free block of the new size is not
> available from the SAT is a new extended block claimed, expanding the
> heap over the space originally occupied by the abandoned string block.
> Does that make sense? ;-)
I guess it's pretty easy to do the test. What value does this
program print when run on BASIC V:
CLEAR
A$ = ""
DIM M% -1
FOR N% = 0 TO 255
A$ = STRING$(N%,"*")
NEXT
DIM P% -1
PRINT P%-M%
On BBC BASIC for Windows V3.11 it prints 255 and on Brandy V1.16
it prints 4736 !
Martin Dann
ne...@rtrussell.co.uk (Richard Russell) wrote:
> I guess it's pretty easy to do the test. What value does this
> program print when run on BASIC V:
>
> CLEAR
> A$ = ""
> DIM M% -1
> FOR N% = 0 TO 255
> A$ = STRING$(N%,"*")
> NEXT
> DIM P% -1
> PRINT P%-M%
>
> On BBC BASIC for Windows V3.11 it prints 255 and on Brandy V1.16
> it prints 4736 !
*basic
ARM BBC BASIC V version 1.16 (C) Acorn 1989
Starting with 8384764 bytes free
>AUTO
10CLEAR
20A$=""
30DIM M% -1
40FOR N%=0 TO 255
50A$=STRING$(N%,"*")
60NEXT
70DIM P% -1
80PRINT P%-M%
90
Escape
>RUN
256
>
It is 256 not 255 as string storage blocks are always complete words (4bytes).
--
Typed by monkey #27662472869676 on typewriter #7552416572242
When emailing me, please include the word Banana in the subject line.
Steve Drain
> rtrussell wrote:
> > No, the stack grows down from HIMEM. If you're using a version
> > of BASIC which supports DIM LOCAL you can discover the current
> > bottom of the stack with DIM S% LOCAL -1. So in this case the
> > amount of free space would be found as follows:
> >
> > DIM S% LOCAL -1 : REM Bottom of stack
> > DIM H% -1 : REM Top of heap
> > free_space% = S% - H%
> >
> What about earlier BASIC, no easy way?
There is a tiny bit of code in my StrongHelp manual to return the stack
pointer - search for STACKP. There is also no need to do the DIM H% -1
trick from earlier versions of BASIC because FSA is returned by the
function END.
> The stack size depends upon how many loops and procedures are in use
> at any one time doesn't it? If I'm only using, say, 2 at a time then
> the stack won't be very big at all will it?
Apart from the depth of loops/procedures there are the preserved global
values of local variables. It does not take many longish strings to
extend the stack quite a way, and then if you have local arrays they are
created on the stack, too. ;-)
Steve Drain
> Steve Drain wrote:
> > I can remember how you showed that with lots of random string
> > allocations memory usage would eventually stabilise, but the final
> > figure is not entirely predictable and it will not be much help in this
> > case. ;-)
> Also if the elements of the array vary little (I think one dimension
> varies between 20-30 bytes) then I'm assuming that doesn't deallocate
> very much although I'd have to read into how the allocation system
> works to check that.
String blocks have a granularity of 4 bytes. If your string lengths
vary more then new blocks will be claimed, but of course de-allocated
ones may be re-used, too.
Just to scare you, from that figure of varying from 20-30 bytes I
can conceive a worst case requiring more than 4 times your initial size
of of array. ;-)
druck
> I guess it's pretty easy to do the test. What value does this
> program print when run on BASIC V:
>
> CLEAR
> A$ = ""
> DIM M% -1
> FOR N% = 0 TO 255
> A$ = STRING$(N%,"*")
> NEXT
> DIM P% -1
> PRINT P%-M%
>
> On BBC BASIC for Windows V3.11 it prints 255 and on Brandy V1.16
> it prints 4736 !
256 on BASIC V 1.35 from RISC OS 5.06
Steve Drain
> Steve Drain wrote:
> > This leads to the equivalent of what you describe above. If a string
> > variable with its block at the top of the heap is extended then the
> > block is abandoned and only if a free block of the new size is not
> > available from the SAT is a new extended block claimed, expanding the
> > heap over the space originally occupied by the abandoned string block.
> > Does that make sense? ;-)
> I guess it's pretty easy to do the test. What value does this
> program print when run on BASIC V:
>
> CLEAR
> A$ = ""
> DIM M% -1
> FOR N% = 0 TO 255
> A$ = STRING$(N%,"*")
> NEXT
> DIM P% -1
> PRINT P%-M%
>
> On BBC BASIC for Windows V3.11 it prints 255 and on Brandy V1.16
> it prints 4736 !
It is 256, as I would expect.
BTW I mentioned in another reply that the function END returns the
value of FSA, so a slight modification and addition:
CLEAR
A$ = ""
M% = END
FOR N% = 0 TO 255
A$ = STRING$(N%,"*")
NEXT
A$ = ""
PRINT END - M%
Prints 0!
Sophie Wilson
> Sophie Wilson <sophie...@bigfoot.com> wrote:
>
>: Or you'ld have to know how much memory is in the deallocated strings
>: - see PList procedures in the assistant library below.
>
> As Sophie's monitoring the group perhaps I can ask a relevant
> question.
I'm not sure that my random visits can be dignified with the word
"monitoring" - one certainly shouldn't hold one's breath waiting for me
to reply!
> Delving through the records of changes to BASIC V I see that at one
> time a string was allowed to expand into contiguous free-space (i.e.
> if a string stored at the very top of the heap exceeded its allocated
> size, it could be lengthened without reallocation). This facility was
> removed because it could result in excessive memory consumption in
> specific, if uncommon, circumstances.
Yes. See the end for the full story.
> When changing BBC BASIC for Windows to support 65535-character strings
> I encountered exactly this phenomenon, and similarly concluded that
> expanding a string into contiguous free-space must not be allowed.
> However further investigation proved this not to be strictly true. If
> a block of the correct size is available in the the deallocated string
> space then, indeed, it must be used in preference to expanding,
> however *if no block of that size* exists in the deallocated string
> space then it is OK to expand into contiguous free space rather than
> allocate a new block.
No, its still not OK.
> This meant I only had to reverse the order of two tests. If a block
> of the correct length is available use it, otherwise if the string is
> at the top of the heap then expand it in place.
>
> Comparing 'BBC BASIC for Windows' with 'Brandy' (both of which support
> 65535-character strings) BBC BASIC invariably uses less memory for
> strings, sometimes significantly less.
>
> The question for Sophie is did she try this in BASIC V ? It might
> have resulted in a worthwhile reduction in string memory usage.
Tried all sorts of things: as you'll see below, I could reduce the
string memory usage, but only with dramatic increases in runtime. The
attached is an internal Acorn document - "William" is William Stoye,
then in charge of RISC OS 3.
--Sophie
. > Storage 26th February 1988
The storage allocator in BASIC V
--------------------------------
Recently I've had a complaint about the storage allocator in BASIC V, so
this is a note describing what it does (and why) and what alternatives exist.
It may be that the complainant didn't understand what was happening and no
problem exists!
Minerva (who use BASIC as the front end to their data base programs) sent
the following program to demonstrate "a bug":
armageddon = FALSE
long$ = "Hello - I am quite a long string definition in this context"
short$ = "Hello - I'm short"
REPEAT
T$ = short$
short$ = long$
short$ = T$
T$ = long$
PRINTHIMEM-END " Bytes free"
UNTIL armageddon:REM not very long in this case
The program cyclically allocates short and long strings, in a sequence which
ultimately causes the interpreter to run out of contiguous free memory.
Simpler sequences (such as omitting T$=long$) are successfully dealt with.
The missing space is still available to the BASIC interpreter for storing
strings in - its just that no appropriate strings are being allocated.
What BASIC does:
----------------
When a string is stored, the currently allocated storage space is
immediately used if the number of words is compatible (all allocation is
dealt with in words - strings of length 1, 2, 3 and 4 are the same for
allocation purposes); otherwise the space is deallocated: it is stored on
the appropriate member of an array of free lists, each list having one size
in words (i.e. there are 64 seperate lists, one for each of 4, 8, 12 .. 256
byte sizes). This makes allocation of the new space for a string very quick:
check the free list corresponding to the desired length, if there is an
entry, take it; otherwise use new space (which will raise the value of END).
In addition the interpreter checks to see if the space is contiguous with
the value of END; which allows the deallocation and reallocation to be
skipped in favour of readjusting the current size (and the value of END
might actually decrease!). This trick catches a lot of simple pathological
cases (such as extending a string one character at a time) and is
responsible for the Minerva program "working" with T$=long$ deleted.
What is needed to stop Minerva's test program:
----------------------------------------------
Minerva's program continually deallocates 20 byte blocks and reallocates new
60 byte blocks, with the changes in T$ from long$ to short$ being handled by
the contiguous with END mechanism. The minimal change to the program is to
either delete T$=long$ or ADD another string rubbish$="jim" after this line
to make the contiguous check return false. Removing the contiguity check
from the interpreter would similarly make the program stop "eating" space.
(Of course, removing the contiguity check would make examples like
FORZ=1TO255:A$+="H":NEXT pathological - it would use 8320 bytes instead of
294).
Why does the contiguity check harm this program?
------------------------------------------------
The check means that a string can shrink from 60 bytes to 20 bytes without
deallocating the 60 byte block it was using. A new 60 byte block is
allocated next time around, deallocating the 20 byte block.
With no contiguity check all deallocated strings end up in the string free
list, rather than being placed into the main contiguous store sometimes.
They thus get used "equally". So once the free list has got to a steady
state size, all allocation/deallocation will be done from it.
Unfortuneately, a steady state size for the free list is large - between
200K and 800K depending on the probability of reallocating into a string
rather than creating a new one and on the range of sizes of strings being
allocated.
The SThrash program
-------------------
As a test for the string allocator, I wrote a program which allocates lots
of strings of random sizes over other strings: this program was used to tune
BASIC's algorithms.
REM > SThrash
PROCA:END
DEF PROCA
LOCAL A$()
DIM A$(1000)
X=RND(-12345)
DIM B$(255):FORZ%=0TO255:B$(Z%)=STRING$(Z%,"#"):NEXT
T%=TIME
FORZ%=1TO10000
A$(RND(1000))=B$(RND AND 255)
NEXT
PRINTTIME-T%
A$()=""
ENDPROC
It allocates 10,000 strings with reallocation occuring 10 times in the life
of each string. The performance of the interpreter was measured in terms of
time taken, number of bytes on free list, number of entries in free list -
lower being better.
bytes entries time
No contiguity check 201284 1554 276
Contiguity check 201696 1557 274
(note that the times have been recomputed for BASIC V 1.03).
Increasing the 10,000 to 100,000 shows that steady state is near:
bytes entries time
No contiguity check 242104 1853 2747
Contiguity check 244276 1870 2739
The contiguity check (in spite of taking time itself) reduces the execution
time since it is cheaper to deal with free space than the free lists.
Because of the good behaviour of the contiguity check in terms of simple
extension, I chose to use it since its general behaviour was only
fractionally worse than the unbiased program. And it was quicker! In
situations where there are fewer reallocations (make A$() larger) the
contiguity check worked better than the unbiased algorithm: using A$(10000)
and 10,000 strings produced:
bytes entries time
No contiguity check 837664 6455 276
Contiguity check 837572 6453 275
(Note the larger number of bytes in the freelist since there are more
strings being used)
Doing Better
------------
What else can be done? Another way of looking at the Minerva program is that
the storage being deallocated should be made contiguous; this is called
coalescing and is expensive in general: the returned block should be checked
against every deallocated block in the free lists to find out if it is
contiguous with any of them. Pairs and triples should be merged together.
Doing this would produce a free list biased towards large entries so one
also has to fragment blocks in the free list on allocation - if there is no
entry the right size, pick a larger one and split it up (coalescing the tail
section if possible!) (finally using free space if there is no large entry
at all).
As I say the general case is very expensive: but something simpler can be
done that catches some behaviour: COAL (coalesce on deallocation) by
checking the head of each free list entry only - this reduces COAL costs to
64 contiguity checks (and only check for pair coalscence - ignore triples).
Only checking entries which will produce a total block <=256 bytes halves
(in general) the amount of work. FOAL (fragment on allocation) can be done
by looking at the free list entries, splitting a larger one and not
coalescing the fragment. Similarly only trying to fragment entries of
certain sizes larger than the desired block reduces the amount of work.
COAL and FOAL are conditional switches inside BASIC: here are the SThrash
performances, in all cases no contiguity check is being made:
bytes entries time
No contiguity check 201284 1554 276
COAL 206740 1458 329
FOAL 200128 1589 267
COAL+FOAL 194724 1404 321
As can be seen, COAL makes fewer entries but they're bigger on average so
more space got used. FOAL breaks things down: more entries but less space on
average (and FOAL is quite quick in the steady state). COAL+FOAL wins out!
(the quicker time for COAL+FOAL is because the COAL phase makes FOAL more
likely to succeed). FOAL by itself would not fix the Minerva program, COAL
would - but only because the coalesced fragments make a block of exactly the
right size. A simpler strategy to COAL (coalesce only with the head of the
free list) would have fixed the Minerva program if long$ had been 40 bytes!
So why don't we just put COAL+FOAL in all the time?
---------------------------------------------------
Although the times above don't look radically different, there are some
nasty cases for COAL and FOAL to deal with. Case one: new allocations - FOAL
will check all the free list entries before allocating some new memory. Case
two: new deallocations - COAL will check all the free list entries, trying
to coalesce with nothing.
DIMA$(10000):A$()="A" provokes case one behaviour.
A$()="" subsequently provokes case two behaviour.
These are the times in centiseconds:
Case 1 Case 2
No contiguity check 15 9
COAL 15 75
FOAL 131 10
COAL+FOAL 123 75
Provoking both case one and case two behaviour simultaneously is possible:
DIM A$(10000):A$()="A":T%=TIME:A$()="FREDA":P.TIME-T%
COAL+FOAL takes 195 centiseconds - while the normal interpreter takes only
18 to 19 centiseconds. Over a factor of 10 slower! (And considering that a
large number of things like address changes and string copy are the same for
all interpreters, the actual situation in the string allocator must be
horrible). In the SThrash program case one and two behaviour occurs only
near the beginning - when the steady state is reached COAL still costs
something, but FOAL is sharply mitigated.
Recommendations
---------------
Too much in this area depends on public image. Does one want to be slow but
sure? Fast and inaccurate? A good compromise? React to criticism? Be good
for small programs?
We could:
(a) Remove the contiguity check
+ fixes the Minerva test program cheaply and quickly
+ performs fractionately better in the steady state (sometimes)
+ reaches steady state quicker
- not a true fix
- small string allocation gets worse
(b) Use COAL+FOAL
+ fixes the Minerva test program
+ fixes a lot of other things
+ performs a lot better in the steady state
- still some pathological cases possible
- time consuming
- small string allocation gets worse
- introduces bugs?
(c) Bluff it out
+ no change to interpreter in this area - must be correct!
+ quickest
- Minerva and others may be unhappy
Please discuss and advise.
-------------------------------------------------------------------------
Postscript:
Noone except William replied to this message. And he recommended option (c).
I chose to implement option (a) in BASIC 1.03. Ah well.
Later:
The Minerva behaviour can also be fixed by not using COAL or FOAL at all,
but recoding the contiguity check such that the contiguity check does not
extend the allocation, but can reduce it. This is only slightly slower than
BASIC 1.02. This behaviour is in BASIC 1.04 on. The performance of SThrash
is better than all previous algorithms except FOAL derived ones (201056
bytes in the list, 1552 entries).
Andrew W
<URL:mailto:steve...@kappa.zetnet.co.uk> wrote:
> Andrew Wwrote:
> > rtrussell wrote:
> > > No, the stack grows down from HIMEM. If you're using a version
> > > of BASIC which supports DIM LOCAL you can discover the current
> > > bottom of the stack with DIM S% LOCAL -1. So in this case the
> > > amount of free space would be found as follows:
> > >
> > > DIM S% LOCAL -1 : REM Bottom of stack
> > > DIM H% -1 : REM Top of heap
> > > free_space% = S% - H%
> > >
> > What about earlier BASIC, no easy way?
>
> There is a tiny bit of code in my StrongHelp manual to return the stack
> pointer - search for STACKP.
Why do you add 36 to R13?
> There is also no need to do the DIM H% -1
> trick from earlier versions of BASIC because FSA is returned by the
> function END.
>
What lies between TOP and END then?
> > The stack size depends upon how many loops and procedures are in use
> > at any one time doesn't it? If I'm only using, say, 2 at a time then
> > the stack won't be very big at all will it?
>
> Apart from the depth of loops/procedures there are the preserved global
> values of local variables. It does not take many longish strings to
> extend the stack quite a way, and then if you have local arrays they are
> created on the stack, too. ;-)
>
The joy of plenty of RAM ;-)
A.Weston
--
Staffordshire, Great Britain.
> Get off my bridge.
Martin Dann
Andrew W <nospam@invalid> wrote:
> In article <ant11201...@kappa.zetnet.co.uk>, Steve Drain
> <URL:mailto:steve...@kappa.zetnet.co.uk> wrote:
> > There is a tiny bit of code in my StrongHelp manual to return the stack
> > pointer - search for STACKP.
>
> Why do you add 36 to R13?
Most RISC OS stacks are descending. i.e. as you put stuff onto the stack
then the stack pointer is reduced.
Adding a number to the stack pointer effectively reduces the size of the
stack. Adding 36 reduces the stack by 9 words. I would guess that this
is the amount of data put onto the stack by calling the routine, so
that the value returned is the correct value, not the value during
the routine.
Martin.
Steve Drain
> Steve Drain wrote:
> > pointer - search for STACKP.
> Why do you add 36 to R13?
Making the USR call itself uses the stack!
> > There is also no need to do the DIM H% -1
> > trick from earlier versions of BASIC because FSA is returned by the
> > function END.
> What lies between TOP and END then?
Note that =END is just the function that returns FSA; it would be
confusing to think of it otherwise because the pseudo-variable END= is
used to change the WimpSlot and HIMEM.
The Heap lies between LOMEM and FSA - see the Memory Map - but LOMEM
will be set to the word after TOP unless it is specifically changed.
Andrew W
<URL:mailto:steve...@kappa.zetnet.co.uk> wrote:
> > > There is a tiny bit of code in my StrongHelp manual to return the stack
> > > pointer - search for STACKP.
> > Why do you add 36 to R13?
>
> Making the USR call itself uses the stack!
>
Yes but 36 bytes? I take it's for the reason Martin explains in the
next post.
> > > There is also no need to do the DIM H% -1
> > > trick from earlier versions of BASIC because FSA is returned by the
> > > function END.
> > What lies between TOP and END then?
>
> Note that =END is just the function that returns FSA; it would be
> confusing to think of it otherwise because the pseudo-variable END= is
> used to change the WimpSlot and HIMEM.
>
Yes I have found that
confusing ;-)
> The Heap lies between LOMEM and FSA - see the Memory Map - but LOMEM
> will be set to the word after TOP unless it is specifically changed.
>
A.Weston
--
Staffordshire, Great Britain.
Steve Drain
> Steve Drain wrote:
> > > > There is a tiny bit of code in my StrongHelp manual to return the stack
> > > > pointer - search for STACKP.
> > > Why do you add 36 to R13?
> > Making the USR call itself uses the stack!
> Yes but 36 bytes? I take it's for the reason Martin explains in the
> next post.
Essentially, yes. Looking back I realise I cannot remember working it
out, but AFAICR it goes like this: a USR call puts 7 words on the stack
and the result will have to be part of an evaluation that uses 2 words -
hence 9 words/36 bytes. I must have confirmed that by testing, but I am
open to quibbles, and the exact value is not going to be any use in
BASIC, is it? ;-)
Richard Russell
> > space then, indeed, it must be used in preference to expanding,
> > however *if no block of that size* exists in the deallocated string
> > space then it is OK to expand into contiguous free space rather than
> > allocate a new block.
>
> No, its still not OK.
I'm not convinced. The 'BBC BASIC for Windows' algorithm shows no
unwanted behaviour with the Minerva test program:
1048058 Bytes free
1048058 Bytes free
1048058 Bytes free
1048058 Bytes free
.....
and SThrash gives the following:
bytes entries time
10,000 allocations 195942 1102 33
100,000 allocations 208765 1225 337
which compares favourably with the BASIC 1.04 results (the times
are for a 200 MHz Pentium).
So unless you can provide some evidence to the contrary I still
maintain that my algorithm is as good as (if not actually
equivalent to) that used in BASIC 1.04 onwards.