Allocating and freeing memory blocks

[RichardRussell]

In BBC BASIC, a block of memory can be allocated either from the heap or from the stack; the statements to do this are as follows:

Code: Select all

      DIM memory%% size%

This statement allocates size%+1 bytes of contiguous memory from the heap and returns a pointer to the first byte in the variable memory%%. Because the heap grows upwards, and only ever increases in size, this block of memory can only be freed by using CLEAR, which destroys all variables, arrays, structures etc. (except the static integer variables A% to Z%). Therefore this kind of allocation is not suitable for 'dynamic' memory.

Code: Select all

      DIM memory%% LOCAL size%

This statement, which can only be used inside a function (FN) or procedure (PROC), allocates size%+1 bytes of memory from the stack and returns a pointer to the first byte in the variable memory%%. The memory is automatically freed on return from the function or procedure (or on execution of a RESTORE LOCAL statement). As such it is suitable for some dynamic memory applications but only when it's acceptable for the memory to exist only for the duration of a single FN/PROC, and when it's OK to exit and re-enter the FN/PROC in order to resize the block.

Although these two options will satisfy most memory allocation requirements, sometimes they may be too limiting. If you want to be able to allocate and free memory blocks without the constraints they impose, one option is to call an Operating System API function to do so. For example in BBC BASIC for Windows you can allocate memory using SYS "GlobalAlloc" and free it again using SYS "GlobalFree". Similarly in BBC BASIC for SDL 2.0 you can allocate memory using SYS "SDL_malloc" and free it with SYS "SDL_free".

But, when the amounts of memory you want to allocate are relatively small, there is an alternative approach that does not require API calls and works in both BB4W and BBCSDL. BBC BASIC already has a reasonably sophisticated dynamic memory management mechanism which it uses for strings, so the trick is to leverage this by allocating the memory block in a string! It turns out that this is relatively straightforward, as the function and procedure listed below demonstrate:

Code: Select all

      DEF FN_heapalloc(N%)
      LOCAL a$, p%%
      a$ = STRING$(N% + 23, CHR$0)
      p%% = PTR(a$) + 23 AND -16
      SWAP ](p%%-8), ]^a$
      = p%%

This function takes as a parameter the number of bytes of memory that you want to allocate, and returns a pointer to the first byte. The memory is automatically 16-byte aligned (which is typically the case for the OS-provided allocation functions too) and zero-filled.

Code: Select all

      DEF PROC_heapfree(p%%)
      LOCAL a$
      SWAP ]^a$, ](p%%-8)
      a$ = ""
      ENDPROC

This procedure takes as a parameter a pointer to a block of memory allocated with FN_heapalloc() and frees it.

These routines may not be as efficient or fast as the OS equivalents, and they use up space in BASIC's heap which the OS allocation functions don't, but nevertheless there may be occasions when they are useful.

[RichardRussell]

Code: Select all

      DEF FN_heapalloc(N%)
      LOCAL a$, p%%
      a$ = STRING$(N% + 23, CHR$0)
      p%% = PTR(a$) + 23 AND -16
      SWAP ](p%%-8), ]^a$
      = p%%

This function takes as a parameter the number of bytes of memory that you want to allocate, and returns a pointer to the first byte. The memory is automatically 16-byte aligned (which is typically the case for the OS-provided allocation functions too) and zero-filled.

Code: Select all

      DEF PROC_heapfree(p%%)
      LOCAL a$
      SWAP ]^a$, ](p%%-8)
      a$ = ""
      ENDPROC

This procedure takes as a parameter a pointer to a block of memory allocated with FN_heapalloc() and frees it.

Does anybody else share my enthusiasm for these routines? They are quite possibly the most elegant pieces of BBC BASIC code I have written or encountered in years, even though I say so myself. There's something about their compactness and efficiency that really appeals, and they make good use of language features. Admittedly I'm a BBC BASIC nerd and proud of it!

[DDRM]

Yes, it's very elegant - and I guess an unanticipated benefit of the decision to allow very large strings!



D

[RichardRussell]

I guess an unanticipated benefit of the decision to allow very large strings!

Yes to a degree, although I'm not sure I'd recommend using this approach to allocate memory blocks bigger than 64K. So the reduced (16-bit) string length limit in BB4W v5 (and Brandy for that matter) would still have allowed the technique to be useful.

The routines do take advantage of the recent introduction of the 64-bit indirection operator in BB4W v6.13a and the 32-bit editions of BBCSDL. Without that it would have been necessary to SWAP the string descriptor as two 32-bit chunks rather than all 64 bits in one go.

[hellomike]

It is so elegant that for now, its beyond me.

In an attempt to grasp what is going on, I have two questions.

1) What is the difference between ]^a$ and PTR(a$)?
2) Since all the variables used are defined as being LOCAL, wouldn't the (N%+23) bytes be reserved on the stack, i.e. just below HIMEM?

Thanks

Mike

[RichardRussell]

What is the difference between ]^a$ and PTR(a$)?

!^a$ is an implementation-specific way of obtaining the memory address of a string, that is it relies on knowing how the particular dialect of BBC BASIC you are using stores information about strings internally. PTR(a$) is an implementation-agnostic way of obtaining the memory address of a string, in any dialect of BBC BASIC (in principle).

It is directly comparable with the difference between !(^a$+4) and LEN(a$). The former returns the length of a string in BBC BASIC for Windows and BBC BASIC for SDL 2.0, but will not work in any other BBC BASIC dialect. The latter returns the length of a string in every dialect of BBC BASIC.

Specifically, !^a$ does not return the memory address of the string in 64-bit editions of BBCSDL, i.e. the 64-bit Linux edition, the MacOS edition or the iOS edition. In those you must use PTR(a$) if you want to discover the memory address of a string.

Since all the variables used are defined as being LOCAL, wouldn't the (N%+23) bytes be reserved on the stack, i.e. just below HIMEM?

Try it for yourself:

Code: Select all

      PROCtest
      END
      
      DEF PROCtest
      LOCAL a$, stack%
      a$ = STRING$(1000, "x")
      DIM stack% LOCAL -1
      PRINT "   LOMEM","   PTR(a$)","   END","   stack%","   HIMEM"
      PRINT ~ LOMEM PTR(a$) END stack% HIMEM
      ENDPROC

You will find that a$ is stored in the heap, not on the stack. I don't think any dialect of BBC BASIC stores strings on the stack, but I can't be 100% sure about Acorn versions or Brandy.

[hellomike]

Thanks for the reply.

So the content of a local string is taken from the heap.
As I assume the heap never shrinks, i.e. no garbage collector, what is the use in freeing that memory?

Please bare in mind that none of my questions or assumptions are meant as critic. Far, far, far from that I can assure you. They are just an attempt for me to better understand implications.

Regards,

Mike

[RichardRussell]

As I assume the heap never shrinks, i.e. no garbage collector, what is the use in freeing that memory?

What is the use in freeing the memory? To allow it to be reused later by another memory block, or a string, of course! The whole point of the exercise, as I tried to explain in the initial message in the thread, is to allow you to allocate and free blocks of memory without the restrictions of the DIM statement and without needing to call OS API functions.

For example suppose you want to allocate and free two memory blocks A & B in your program, in the sequence: alloc A, alloc B, free A, free B. That isn't possible using DIM because you can only free dynamic memory (on the stack) in the reverse order from that in which it was allocated. But using the routines I listed you can do it. The heap won't shrink, but the memory you freed will be available for other blocks, or strings (to the extent that the string allocation algorithm permits).

As for the heap never shrinking, putting to one side that it isn't true (BBC BASIC's heap can shrink, if not commonly), is that any different from the kind of heap that is maintained by the OS and from which more 'conventionally' allocated memory is taken? For example does the heap from which the Windows HeapAlloc API function allocates memory ever shrink? I don't know for sure, but I suspect it doesn't (until the process terminates).

[RichardRussell]

Incidentally, you may find the Memory Usage Monitor utility (slot 3 in both BB4W and SDLIDE) useful for monitoring heap usage. Two of the items it displays are Total heap usage and String free space. You probably won't see the former figure decrease (although it's possible) but you should see the latter rise and fall as strings - or memory blocks as discussed in this thread - are allocated and released. A program making heavy use of large strings should show this effect particularly well, Ceefax.bbc is a good example; it's compatible with both BB4W and BBCSDL.

memmon.png

[hellomike]

Ok, so your interpreter has algorithms in place which detects string space getting freed and the ability to re-use it. Nice and interesting information Richard. And yes, I already noticed the heap staying the same by combining a few routines from the above like this:

Code: Select all

      PROCtest
      PROC_heapfree(FN_heapalloc(100000))
      a=1
      PROC_heapfree(FN_heapalloc(100000))
      b=1
      PROC_heapfree(FN_heapalloc(100000))
      c=1
      PROC_heapfree(FN_heapalloc(100000))
      d=1
      PROC_heapfree(FN_heapalloc(100000))
      PROCtest
      END

The first and second PROCtest reports are almost the same values even though in between large(r) memory block have been allocated an freed.

I will play more with Memory Usage Monitor.

Thanks again.

Mike