QL Heap

[bwinkel67]

Question about the heap and how it allocates blobs. I'm trying to figure out the block size it uses. My ZXSimulator, when presently running, seems to have about 30000'ish bytes left in the heap- i.e. I can do a DIM A(15000) and if I try to then DIM B(10) I get a MAX HEAP ERROR meaning that malloc failed (15000 represents 2-byte values). When I load in a 13000 byte program and then add a block to it (I define a block internally for me presently as 64 bytes) I automatically allocate a new blob that's 13000 plus block (i.e. 13064). With 30000 I should be able to do that once since it needs to keep both the old and new in place to copy from one to the other.

However, I can do it a second time, which leads me to believe the QDOS block size is bigger than 64. In other words, once I have 13064 I can allocate 13128 and copy again. If the heap is allocated by using biggest amount left and to the exact byte then this wouldn't work because the second blob would be sitting right above the 13064 and there would be no blob big enough to hold 13128...yet it works. So the QL grabs memory in some block size. Note that I allocated in 64 byte block sizes when loading a program so when it's 13000 bytes long in reality I load 13956 (i.e. 203 x 64). Does the QL do something like 128 bytes?

[mk79]

The reality is a bit more complicated and it differs between SMSQ/E, QDOS and compiled programs. First of all "DIM A(15000)" is NOT equivalent to malloc. Variables live in the variable area, not on the heap. On SMSQ/E the variable area is allocated from the heap and can be fragmented, on QDOS it's part of the basic data area. IIRC the basic area must be one block and moves if it must be enlarged. If it cannot be enlarged because there is stuff in the way then it will fail.

To answer your question, heap granularity/alignment is almost always 8 bytes, but that is not your problem.

But who outputs "MAX HEAP ERROR"? I'm not aware of this error message and greping my hard drive for it comes up empty.

[tofro]

To answer your question, heap granularity/alignment is almost always 8 bytes, but that is not your problem.

Then there's your C compiler's heap management in between which most probably allocates heap memory not in QL minimum chunks, but rather bigger ones. Note what your malloc call in C calls is almost certainly not a direct hand-over to mt.alchp, but any heap management in a C library will allocate memory in larger chunks as required and hand them over to you piece-meal.

[bwinkel67]

The reality is a bit more complicated and it differs between SMSQ/E, QDOS and compiled programs. First of all "DIM A(15000)" is NOT equivalent to malloc. Variables live in the variable area, not on the heap. On SMSQ/E the variable area is allocated from the heap and can be fragmented, on QDOS it's part of the basic data area. IIRC the basic area must be one block and moves if it must be enlarged. If it cannot be enlarged because there is stuff in the way then it will fail.

To answer your question, heap granularity/alignment is almost always 8 bytes, but that is not your problem.

But who outputs "MAX HEAP ERROR"? I'm not aware of this error message and greping my hard drive for it comes up empty.

Sorry for the confusion so let me clarify. In reality I'm doing a malloc(30000) within Digital 'C" SE when executing a parsed DIM(15000)... the DIM statement is not SuperBASIC but the BASIC within the ZXSimulator (A ZX81 pseudo emulator I've been developing).

So I deduced I have about 30000 bytes of heap space left with the current incarnation of ZXSimulator. I tested this as follows: I reset the QL (BBQL 128 running JSU ROM) and then started the ZXSimulator executable (via exec) and then malloc'ed 30000 bytes -- I can do this via DIM A(15000) as each integer is worth 2 bytes. I then tried to malloc an additional 20 bytes and the call failed (i.e. it returned NULL which causes me to give the aforementioned "MAX HEAP ERROR"). Nothing else was run within ZXSimulator so no other memory besides the normal startup of the interpreter happened (mostly stuff on the stack).

So next I tested the following: again, I reset the QL and started ZXSimulator and with nothing else I executed the following sequence:

a = malloc(12928); /* by loading a ZX81 BASIC program whose size is 12925 -- I chunk in 64 byte blocks (I first deduce the file size and allocate rounded to nearest 64 bytes) */
b = malloc(12992); /* i.e. 12928 + 64 -- I added exactly 64 bytes via adding a REM statement, accounting for the line number and the internal EOL */
free (a);
c = malloc (13056); /* i.e. 12992 + 64 -- once again, added exactly 63 more bytes */
free (b);

Then ran loaded BASIC program within ZXSimulator through all its paces, which does a number of malloc and free calls for internal interpretation and it ran perfectly.

So this suggests that heap allocation via malloc is greater than 64 bytes because when 'a' is freed, if QL heap is only allocated in 8 byte chunks, then that blob that 'a' pointed to would be 12928 in size and could not support the malloc for the 'c' variable. So you'd have a contiguous free chunk of no more than 12928 followed by an allocated chunk of 12992 and when a request of 13056 is made, it should fail since there is only about 30000 in heap overall -- but it doesn't. This leads me to believe that the initial malloc for 'a' gave a size big enough to, after it's freed, be able to handle the call for 13056.

So I don't think the heap is in 8 byte alignments as that doesn't follow what is happening in the sample above and seems to suggest something bigger than 64 bytes (perhaps 128 bytes) of block space when supporting a memory request from the heap. Now it could be from Digital 'C' SE's malloc call that this is done but I would have thought the block sizing would come from the OS not the compiler and having Digital 'C' SE's malloc blocking things at 128 bytes would be terribly inefficient if you need to write code that does a lot of small allocations like say a database of linked list/btree items as an example. You would waste a ton of memory if you allocate 128 minimum for anything you did.

If, on the other hand, the QL heap sets aside 128 byte block sizes when a heap allocation request is made, that would not be wasteful as not all of it would be used. Say you ask for 1 byte of heap space via a malloc and (being say a fist request) the QL sets aside 128 bytes of that and then allocates 1 byte. If another 1 byte request is made it is made within that initial 128 block, and so on. This then helps the QL heap deal a bit better with fragmentation so that it keeps contiguous blocks longer for smaller allocation and free requests. That's why I'm wondering what the QL heap is doing.

[mk79]

Then there's your C compiler's heap management in between which most probably allocates heap memory not in QL minimum chunks, but rather bigger ones. Note what your malloc call in C calls is almost certainly not a direct hand-over to mt.alchp, but any heap management in a C library will allocate memory in larger chunks as required and hand them over to you piece-meal.

Yes, the C68 memory allocator is more or less like the way SMSQ/E handles the Basic variable area: a private heap that gives out blocks (aligned to 8 bytes) and allocates more heap blocks from the common heap when necessary. On startup of the job this looks exactly like malloc allocating space from the common heap, but freeing the space will not return it.

[bwinkel67]

Note what your malloc call in C calls is almost certainly not a direct hand-over to mt.alchp, but any heap management in a C library will allocate memory in larger chunks as required and hand them over to you piece-meal.

But that would be terribly inefficient if you are creating structures of small chunks and if the C malloc hands over requests and chunks them at say 128 bytes (which seems to be what is happening). It would be more efficient for the OS to set aside chunks of space and allow smaller allocations to be made from it and so multiple small allocations stay in the initial chunk so as to keep the rest of the heap contiguous. Imagine if you have 20000 bytes free and you make a call for 10 byte followed by 10000 bytes followed by 10 byte...if you free 10000 bytes you'd then no longer have the ability to allocate anything bigger than 10000 bytes even though you are only using 20 bytes total and have most of the 20000 bytes free. If the OS chunks it at some small amount (128) of which it takes its allocation then the two 10 byte allocations would all be on the low end of the heap and most of the 20000 bytes would remain contiguous.

[tofro]

That assumes the C runtimes would ever hand back memory it once allocated to the OS. Almost no C compiler, at least none contemporary to the QL does that. Memory footage on nearly any C compiler I know can only grow, never shrink. C runtimes will obviously hand back any free()d memory to its own "unallocated" pool for re-use by the same job, but never hand back heap fragments to the OS. That is to keep heap memory allocated in per-program chunks rather than have applications spread their allocated memory all over the place (which is way worse).

If you take C68, for example, any heap management function will allocate memory in chunks of 8kBytes per default, any future memory allocation is satisfied from these large chunks, if this first chunk is depleted, C68 will allocate more in 4kBytes granularity. (all of these are adjustable)

[mk79]

Sorry for the confusion so let me clarify.

Wow, there truly were some details missing... I have no insight into the Digital C memory allocator, I don't think I have the source code for that. I do know how the QDOS allocator works, so take my word that THAT has an allocation alignment of 8 bytes.

C68 works pretty sanely in this respect, Digital C is much older and might be odder. Probably brk() based or something, no idea.

If, on the other hand, the QL heap sets aside 128 byte block sizes when a heap allocation request is made, that would not be wasteful as not all of it would be used. Say you ask for 1 byte of heap space via a malloc and (being say a fist request) the QL sets aside 128 bytes of that and then allocates 1 byte. If another 1 byte request is made it is made within that initial 128 block, and so on. This then helps the QL heap deal a bit better with fragmentation so that it keeps contiguous blocks longer for smaller allocation and free requests. That's why I'm wondering what the QL heap is doing.

Nice theory but definitely false. The QDOS memory allocator is as simple as it gets, no buckets or anything.

[bwinkel67]

Yes, the C68 memory allocator is more or less like the way SMSQ/E handles the Basic variable area: a private heap that gives out blocks (aligned to 8 bytes) and allocates more heap blocks from the common heap when necessary. On startup of the job this looks exactly like malloc allocating space from the common heap, but freeing the space will not return it.

I'd be surprised if Digital 'C' SE is that complex. They are a pretty small and rudimentary compiler and linker and I would have thought left most of this to the OS. Now if they choose to block things off in 128 byte minimum chunks, that would be horrible but other than that I just don't see how I could have done 3 malloc's with each being 64 bytes bigger and it worked. I guess I'll have to do some tests with Digital 'C' SE to find out.

[bwinkel67]

Nice theory but definitely false. The QDOS memory allocator is as simple as it gets, no buckets or anything.

I might just be dealing with 2 very simple schemes here (QDOS and Digital 'C' SE) which may end up being pretty wasteful if Digital 'C' SE does things badly. I'll need to investigate. I don't want to divert from this project with what I'm doing since the whole point was developing and running it on a BBQL and I know I can get Digital 'C' SE to do that. I think with C68 that model won't work. Maybe after I'm done and decide to go to further I'll compile it with C68. I have had request to eventually dump the QL and do a Windows port since the non-keyword entry makes the ZXSimulator much easier to develop ZX81 programs on...not sure if I'm interested but we will see. I kinda like that anyone that uses ZXSimulator needs to get to know the QL :-/

Thanks to all for the quick replies...