_________________
http://WilsonMinesCo.com/ lots of 6502 resources
The "second front page" is http://wilsonminesco.com/links.html .
What's an additional VIA among friends, anyhow?

It's late, so I'm not going to launch into a full reply. However, I am inclined to think that the allocation algorithm to be used should be tailored to the environment in which it will be run. For example, in the UNIX and C world, malloc() is the "standard." However, some developers conjure something that may be very different than malloc() because the generality of the latter may be too inefficient for the specialized uses of memory that the application will make (Samba, for example, has talloc(), which is added to the system's run-time libraries when Samba is installed). So I would think the 6502 programmer should think in a similar fashion, especially since he's not working with an MPU that can manage several thousand MIPS.

_________________
x86?  We ain't got no x86.  We don't NEED no stinking x86!

_________________
http://WilsonMinesCo.com/ lots of 6502 resources
The "second front page" is http://wilsonminesco.com/links.html .
What's an additional VIA among friends, anyhow?

Managing blocks for a disk filing system is considerably simpler than general purpose memory allocation, for a start disk blocks are normally all the same size.

C/C++ programs allocate memory for structures that are of unknown size at start up (e.g. image files, documents, intermediate representations in compilers, etc.). Typically they will be either contiguous areas to allow fast array access or sets of smaller inter-linked areas for data structures.

Structures that are frequently malloc'd and free'd are usually managed through a pool of reusable memory areas to avoid the costs of performing fully allocation.

_________________
Andrew Jacobs
6502 & PIC Stuff - http://www.obelisk.me.uk/
Cross-Platform 6502/65C02/65816 Macro Assembler - http://www.obelisk.me.uk/dev65/
Open Source Projects - https://github.com/andrew-jacobs

I did have the idea, in some of my 6502 OS musings, to have buffer & string storage made up of 16-byte or so chunks, with link pointers between them, similar to simple filesystems. Obviously the advantages would be that each allocation unit is uniform, there are no issues of fragmentation, alloc/free and growing/shrinking buffers are all fast; but accessing data from those buffers would be slowed because it's not necessarily contiguous. But for serial reading/writing it could be okay, and if run from bytecode then all of those chunk & boundary issues are hidden from the programmer.

It's unknown to me whether the speed burden of not having a simple pointer+offset for buffers would be worth it. Alloc/free/resize calls do happen much more infrequently than byte access, although for high level programming you should be able to sling around temporary buffers freely without being burdened too much. Also, I'm not sure if such a mechanism would be appropriate for general data structures; if they're less than 16-bytes it might be, but then there could also be a lot of wasted space by rounding up small 4-8 byte structures to the 16 byte allocation size.

_________________
WFDis Interactive 6502 Disassembler
AcheronVM: A Reconfigurable 16-bit Virtual CPU for the 6502 Microprocessor

_________________
http://WilsonMinesCo.com/ lots of 6502 resources
The "second front page" is http://wilsonminesco.com/links.html .
What's an additional VIA among friends, anyhow?

If there is a C alloc(), I don't know if it's survived. alloc() sound like the primitive system in UCSD of mark and release.

talloc(), as mentioned by BDD is not so much a replacement for malloc, as a framework built on top of it. It allows you to associate memory allocations in to a tree like structure, to where if you free the root of the tree, then the entire structure is freed also, even when made up of several, separate allocations. While certainly handy, it's obviously more heavy weight than raw malloc.

The idea of using a FAT for a allocator, isn't really necessary. A FAT is necessary simply because its so expensive to ask the disk, well, anything, much less what blocks are free. A chain of free blocks doesn't suffer from that same performance overhead. Also, the FAT assumes a fixed length block size, which makes complete sense for a disk, but not so much for a something that is byte addressable like memory.

Memory allocators already suffer a bit for very fine allocations, simply due to their overhead. For scenarios of high numbers of small fixed blocks, the FAT idea makes more sense, as it reduced the per block overhead of each allocation, though it obviously relies on a contiguous block of memory. But it's still extensible, each time you fill up a larger block, allocated a new one, give it its own FAT, and then chain the FATs together. During the free() operation, you can do simple pointer math to identify what master block you're in, and back calculate to the FAT entry. You could also allocate chains of such blocks for larger allocations.

But, from a "wisdom of the crowds" point of view, the default malloc as shipped on modern systems does not do that, and, being as malloc is a pretty contentious little routine, with all sorts of issues, the fact that it does not use a FAT like implementation suggest simply that people far more invested, and more knowledgeable, than I in the implementation of something like malloc, after 40 years of trying, have decided against that approach. So, it's likely a good idea in the long run.

(Alloc and afree are introduced as examples in K&R, they are not part of C or of the standard library. Just before the bit you quoted:

)

A memory allocator is solving a very general problem, and won't have ideal behaviour in all cases. For that reason, you often find specialised allocators for more specific purposes: for small short-lived allocations, for large allocations, for allocations of a given size, for LIFO allocations. It's not uncommon for an application to allocate one or more large pieces of memory and then perform its own allocation tactics within - the application has a chance of knowing what kinds of allocation patterns will occur.

In fact the same sort of thing is true in storage: there are different filesystems which suit different workloads, and sometimes an application will use a large flat file and allocate space within it. Or even work directly with a partition.

Edit: It's probably the case, Garth, that if you're writing the applications which are using your allocator, you'll have some idea of what kinds of allocations you'll need, and your allocator will be good for the purpose. But it's also likely that you haven't anticipated all the patterns of allocation which applications can make, and so your idea wouldn't be as good an allocator as one written by experts and which has stood the test of time.

Edit: To summarise, there's no single best answer, and won't ever be, because memory allocation is about predicting the future, which is known to be hard. You'll find many allocators being proposed and compared - for example a few at https://locklessinc.com/benchmarks_allocator.shtml

Edit: There's certainly an advantage of an allocator which is good enough for your own purposes and as simple as it can be for those purposes.

_________________
http://WilsonMinesCo.com/ lots of 6502 resources
The "second front page" is http://wilsonminesco.com/links.html .
What's an additional VIA among friends, anyhow?

I remember being interested and impressed when I first came across tcmalloc - but much time has passed since then. There's an introductory article which might be useful:
http://jamesgolick.com/2013/5/15/memory ... s-101.html

Edit: also might be worth looking into the various allocators used by the Linux kernel:
https://en.wikipedia.org/wiki/SLOB

_________________
http://WilsonMinesCo.com/ lots of 6502 resources
The "second front page" is http://wilsonminesco.com/links.html .
What's an additional VIA among friends, anyhow?

Interesting idea to have the application give a base pointer.

I think the Mac had a similar idea - essentially double indirection - so each allocation points to an official pointer. Whereas the Amiga didn't, so allocations could not be moved, so fragmentation could be an issue.

_________________
http://WilsonMinesCo.com/ lots of 6502 resources
The "second front page" is http://wilsonminesco.com/links.html .
What's an additional VIA among friends, anyhow?