BBC BASIC for Windows: Re-dimensioning Arrays

BBC BASIC for Windows
Programming >> BBC BASIC language >> Re-dimensioning Arrays - Wiki Suggestion?
http://bb4w.conforums.com/index.cgi?board=language&action=display&num=1401729568

Re-dimensioning Arrays - Wiki Suggestion?
Post by Andy Parkes on Jun 2^nd, 2014, 5:19pm

Hello,

I've been looking at the Wiki article on re-dimensioning arrays...

http://bb4w.wikispaces.com/Re-dimensioning+arrays

...and if I've understood it correctly there may be a detail worth thinking about:

Near the bottom, there is the warning:

"Note that if you REDIM (not REDIM PRESERVE) a string array you must explicitly empty the array first:"

I understand that this is to prevent string 'loitering', but looking at PROCredimpreserve1d(), it looks like string pointers could still become inaccessible if a given string array is re-dimensioned to a smaller size. If that is correct, then something like the following routine might occasionally be useful. It will resize a string array in the same way as PROCredimpreserve1d(), but it prevents the possibility of leaving inaccessible string pointers:

Code:

      DEF PROCredimpreserve1d_string(RETURN a$(), D%)
      LOCAL P%,O%, A%,N%, S%,s{}, I%
      DIM s{a$}
      S% = DIM(s{}) : D% += 1 : P% = !^a$()
      N% = 5 + S% * D%
      O% = 5 + S% * P%!1
      IF N% = O% ENDPROC
      SYS "GlobalAlloc", 64, N% TO A%
      IF N% < O% THEN
        FOR I% = DIM(a$(), 1) - ((O% - N%) / S% - 1) TO DIM(a$(), 1)
          a$(I%) = ""
        NEXT
        SWAP N%, O%
      ENDIF
      SYS "RtlMoveMemory", A%, P%, O%
      IF P% < LOMEM OR P% > HIMEM SYS "GlobalFree", P%
      A%!1 = D%
      !^a$() = A%
      ENDPROC

As I understand it, PROCredimpreserve() will work fine and give better performance for most situations involving string arrays, such as stacks and queues where data is added contiguously and the array is always larger than and in proportion to the amount of data it holds. But again, if I have understood things correctly, someone may fall into the trap of shrinking a string array for some other reason, without first doing 'garbage collection'

Many Thanks

Andy

Re: Re-dimensioning Arrays - Wiki Suggestion?
Post by rtr on Jun 2^nd, 2014, 5:44pm

on Jun 2^nd, 2014, 5:19pm, Andy Parkes wrote:

if a given string array is re-dimensioned to a smaller size.....

Why would one ever re-dimension an array to a smaller size? Attempting to do so using PROCredimpreserve doesn't free memory, it uses up more memory (the memory occupied by the original array is leaked, and fresh memory is allocated for the smaller array)!

So, given that, isn't the simplest way to amend the Wiki article - if you really think it is necessary - to add the comment "use PROCredimpreserve only to increase the size of an array"?

Edit: And of course if you reduce the size of an array you cannot preserve its contents!

Richard.

Re: Re-dimensioning Arrays - Wiki Suggestion?
Post by Andy Parkes on Jun 3^rd, 2014, 1:34pm

Hi Richard,

Thanks for your reply. I get the feeling that there may be a few things for me to glean from it.

Quote:

Why would one ever re-dimension an array to a smaller size?

Off the top of my head, the only good examples I can think of, are elementary data structures implemented with a resizing array. As I acknowledged in the original post, PROCredimpreserse looks like it would work fine in such circumstances provided that string loitering was handled by the data structure's FN/PROC/methods, at the same time that an individual item of data is removed. So I take your point, I can't think of any specific scenario when I would want to reduce the size of an array while it still contained data in elements exceeding the new size. The reason for my post was really just to raise awareness of the need to be sure that strings are nullified before shrinking an array. That was the message that I thought might be worth raising here or adding to the Wiki page since PROCredimpreseve does seem to support array shrinking.

Quote:

Attempting to do so using PROCredimpreserve doesn't free memory, it uses up more memory (the memory occupied by the original array is leaked, and fresh memory is allocated for the smaller array)!

Do you mean that it is always leaked? I can see how there would be a memory leak the first time PROCredimpreserve was used to re-dimension an array which was created on the heap using DIM, but if you create an array as a global memory object using "GlobalAlloc", I thought the memory used for that (and consequently any array which had already been resized at least once) would be released with "GlobalFree" when resized, have I understood that correctly?

Quote:

So, given that, isn't the simplest way to amend the Wiki article - if you really think it is necessary - to add the comment "use PROCredimpreserve only to increase the size of an array"?

Putting string-loitering aside for a moment, I think that shrinking an array for the sake of implementing a resizing-array stack, queue, priority-queue, random-queue, deque, bag, list, etc. is at least, a valid reason to shrink an array. It's great that PROCredimpreserve supports array shrinking, so I think it would be better to keep that, both in function and documentation. I just would have added the reminder that shrinking the array could lead to string-loitering if your not careful with the design of your program. That would complement the caution given with regard to PROCredim.

If PROCredimpreserve is not intended to support array shrinking, is there a need to keep the line which selects for the smallest array:

Code:

IF N%>O% SWAP N%,O%

Would it be better to use the comparison to throw an error if the client tries to shrink an array:

Code:

IF N%<O% ERROR 100, "Can't shrink array"

I agree that either way, all the article might need (if anything) is an extra sentence or two.

Quote:

Edit: And of course if you reduce the size of an array you cannot preserve its contents!

But, if an array is only partially populated, and the new array size >= the total data size then its possible to preserve the contents, but again its a moot point as there would be no problem with string-loitering in that scenario.

Regards

Andy

Re: Re-dimensioning Arrays - Wiki Suggestion?
Post by rtr on Jun 3^rd, 2014, 3:56pm

on Jun 3^rd, 2014, 1:34pm, Andy Parkes wrote:

I agree that either way, all the article might need (if anything) is an extra sentence or two.

It's a Wiki, so if you think it needs altering alter it yourself!

Richard.

Re: Re-dimensioning Arrays - Wiki Suggestion?
Post by rtr on Jun 4^th, 2014, 03:50am

on Jun 3^rd, 2014, 1:34pm, Andy Parkes wrote:

I thought the memory used for that (and consequently any array which had already been resized at least once) would be released with "GlobalFree"

It's complicated. Imagine a scenario in which an array is gradually shrunk in size, in a series of steps, by calling PROCredimpreserve. The first call is guaranteed to increase overall memory usage, because the original array on the heap is leaked. The second call is also guaranteed to increase, not reduce, memory usage because in order to 'preserve' the contents of the array a new block of memory must be allocated first, and the contents of the old block copied into it.

On the third and subsequent calls to PROCredimpreserve it is impossible to say what will happen to overall memory usage because it depends on implementation detail of the Windows heap manager. In principle the 'new', smaller, array may be allocated from memory which was 'freed' during a previous call, but Windows may choose not to do that, for example if it could result in excessive heap fragmentation.

What one can say for certain is that, in the above scenario, the strategy which will use the least amount of overall memory is not to call PROCredimpreserve at all, but simply to shrink the array 'in place', i.e. on the heap where it was originally allocated!

Richard.