From Newsgroup: comp.lang.misc
On 12/12/2023 20:03, James Harris wrote:
-On 28/11/2022 07:11, David Brown wrote:
On 26/11/2022 14:05, James Harris wrote:
On Friday, 25 November 2022 at 16:15:08 UTC, David Brown wrote:
On 25/11/2022 14:02, James Harris wrote:
I will get back to you guys on other topics but I need to improve
the memory allocator I use in my compiler and that has led to the
following query.
Imagine an allocator which carries out plain malloc-type
allocations (i.e. specified as a number of 8-bit bytes suitably
aligned for any type) without having to have compatibility with
malloc, and in a language which is not C.
For the sake of discussion the set of calls could be
m_alloc m_calloc m_realloc m_resize m_free
In a new language, I would not follow the names from C as closely.
For one thing, it could confuse people - they may think they do the
same thing as in C. For another, "calloc" in particular is a silly
name. And you don't need "realloc" and "resize".
The idea is that realloc could move the allocation whereas resize
could only resize it in place. The latter is not present in C's
malloc family.
Where would such a function be useful? If the application needs to
expand an object, it needs to expand it - if that means moving it, so be
it. I can't see where you would have use for a function that /might/ be
able to expand an object. Do you have /real/ use-cases in mind?
Sure. Imagine implementing a rope data structure
https://en.wikipedia.org/wiki/Rope_(data_structure)
or anything which could be in parts and/or of varying size.
You still don't need a "resize" that is distinct from "realloc". The
parts of your ropes would have a known allocation size (ideally matching
the appropriate units for the main allocator) and a "used" size. Small changes that can be handled within the existing allocated size for the
rope are easily done without any memory allocation functions, and if you
need more, you have a new block on your rope.
The number of times - even with a rope - that a "resize if possible
without a new allocation" function is useful is negligible.
/Vastly/ more useful, I think, would be to re-think allocation systems entirely - don't copy C. C's memory management was invented in a time
before caches, and before SMP. Stop trying to tweak C's outdated
choices with hacks that have almost no real-world uses, and starting
thinking differently.
For example, have your allocation functions return a tuple of address
and actual available memory in the allocation. For data structures
where you think "resize" might have relevance, store the real available
memory size in the blocks - then you have all the benefits of "resize"
for free.
And don't store the size of the allocation data in hidden parts of the allocation, as is traditional in C malloc/free implementations. For 95%
of all allocations, the software knows what the allocated size is when
it is time to free the allocation. And for the other 5%, the size can
easily be stored, tracked or calculated when needed. Including
allocation size and pointers to free lists or linked list chains of allocations in the allocated memory made sense before caches - it does
not make sense now. Keep the metadata separate.
It can make sense to distinguish between "alloc_zeroed" and
"alloc_unintialised", for performance reasons.
Agreed, but what exactly would you want for the calls? Maybe
m_alloc(size) m_alloc_a(size, flags)
?
There could be many different interfaces. Dmitry also pointed out other
possible distinctions for allocation of shared memory, unpageable
memory, and so on. Not all memory is created equal!
Maybe you want a more object-oriented interface, for supporting several
different pools or memory allocation choices.
There is use for (and, I would argue, a need for) various different
types of allocator. Some allocators are good for fixed-size objects,
some for space which does not need to be returned until a program terminates, and some for where releases are in the opposite order from requests, for example.
Yes.
But such allocators impose restrictions on how they can be used or how
they can be implemented, e.g. requiring meta space to manage the storage space.
Size-size allocators are particularly efficient for their metadata - all
you need is a single bit per allocation.
Metadata is always needed. Putting it within the allocated space is an outdated and inefficient solution, and does not save space.
There is still a need for one approach to be completely general:
Certainly there are uses for general allocations as well as more
specific ones. But often most allocations in a program can be better
handled by specific ones.
* not requiring fixed-size allocations
Yes.
* not requiring separate data structures to describe data space
No.
* permitting arbitrary order of allocation and deallocation
Yes.
Once one has a completely general allocator then it can take control of available address space and other, more specialised allocators can be
built on top of it - e.g. by requesting meta space and data space for an array-style allocator.
That is certainly possible.
...
The one thing I would avoid at all costs, in any interfaces, is the
"integer flag" nonsense found in many languages (such as C). If you
really want some kind of flags, then at least be sure your language has
strong type-checked enumerations.
I presume you mean not to combine flags into an integer such as
mem_allocator_call(size, flags)
where flags is such as
ALLOC_DATA | ALLOC_WRITABLE
but what would you use instead of an integer?
Use proper types - strong enumerations, sets, structs with bits or
flags, etc. /Strong/ types. It all boils down to words of some size in
the end, but the stronger your types as seen by the user in the
programming language, the less possibility there is for error or misunderstanding.
Would there be any value in giving the programmer a way to find
out the size of a given allocation? I don't mean the size
requested but the size allocated (which would be greater than or
equal to the size requested).
No. It is pointless.
Why would anyone want to know the result of such a function? The
only conceivable thought would be if they had first allocated space
for x units, and then they now want to store y units - calling
"get_real_size" could let them know if they need to call "resize"
or not.
The answer is that they should simply call "resize". If "resize"
does not need to allocate new memory because the real size is big
enough, it does nothing.
It's partly for performance, as Bart's comments have backed up. If
code can find out the capacity then it can fill that allocation up to
the stated capacity without having to make any other calls and
without risking moving what has been stored so far.
There is no performance benefit in real code - and you should not care
about silly cases.
On the contrary, there is huge potential for real benefit in real code. There is no advantage in toy code. That's the difference.
I completely disagree, and nothing you have suggested here or previously
has given me any reason to suspect that "resize" is useful. You've
given vague ideas about things where you think it might be helpful, but nothing that is concrete and nothing that - IMHO - would not be better
off handled in a very different way. However, this is /your/ language,
not mine, and if you want to disagree with me on this point then that is absolutely fine. I think we can call this one a dead donkey, and stop
beating it. There are surely many other points for which my suggestions
or recommendations could be more useful to you, and we should focus there.
I ask because it's simple enough to precede an aligned chunk of
memory with the allocation size. The allocator may well do that
anyway in order to help it manage memory. So there seems to be no
good reason to keep that info from the programmer. The question
is over whether there's value in allowing the programmer to get
such info. I am thinking that he could get the value with a call
such as
m_msize(p)
It seems simple enough, potentially useful, and should be
harmless. But it's noticeable that the malloc-type calls don't
have anything similar. So maybe there's a good reason why not.
I thought it might cause implementation issues such as requiring
a larger header if the allocator wants to search only free
memory. But whatever implementation is used I think the allocator
will still need to either store or calculate the size of the
memory allocated so I am not sure I see a problem with the idea.
What do you guys think? Opinions welcome!
I think you should not try to copy C's malloc/free mechanism. In
particular, I do not think the memory allocator should track the
sizes of allocations. "free" should always include the size,
matching the value used in "alloc". (And "resize" should pass the
old size as well as the new size.)
Bart said the same and the suggestion surprises me. It seems prone to
error.
Your choices with memory management are basically to either trust the
programmer, or do everything automatically with garbage collection.
Even if you use something like C++'s RAII mechanisms for allocating and
deallocating, you still have to trust the programmer to some extent. If
you are relying on the programmer to get their pointers right for calls
to "free", why are you worried that they'll get the size wrong?
The implementation has to know the sizes.
Nope.
There's no point in requiring
the client program to know the sizes as well.
The client /already/ knows the sizes - after all, it asked for the
memory of particular sizes in the first place. There is no point in the /implementation/ tracking that data as well as the client.
Make a bad interface now and you'll be stuck with it.
Indeed. Hence the original question.
Unfortunately, I have long forgotten the original question!
I still don't understand your targets - either in terms of computer
systems, or expected uses. If the target is modern PC-style systems
(so that you can, like in Bart's languages, assume that you have
64-bit integers and plenty of memory), then you can make a string
format that has uses, say, 256 byte lumps. Some of that is for
pointers and length counts to handle chains for big strings, and maybe
reference counting, with over 200 bytes free for the string itself.
The solid majority of all strings in practical use will fit in one
lump, and you have no challenges with memory allocators, resizing, or
the rest of it. That simplification will completely outweigh the
inefficiency of the wasted memory. And then for long strings, doing
everything in a single C-style block is inefficient anyway - you'll
want some kind of linked chain anyway.
The targets are simply 'computers'. They can be of different sizes -
e.g. 12-bit processors with tiny amounts of RAM up to 64-bit processors
with oodles of RAM, and beyond. The size of the machine shouldn't much matter.
The size of the target matters /enormously/ for the language.
If it has to work on very small systems, then the language has to be
small and limited. If it only needs to work on big systems, it can be
far higher level - and thus much more helpful to the programmer.
If your language and its standard library need to work on small microcontrollers, you need to make sure the runtime minimises ram usage
and is optimised for tiny data requirements. You probably don't want
dynamic memory at all, because people writing for such devices avoid
dynamic memory as much as possible. You will want no more than minimum
string handling, with blind handling of 8-bit characters, to avoid
library overheads. You won't have floating point support. You won't
have IO libraries, or network support, or file handling. You will
either have no multi-threading support, or you will have your own RTOS. Everything revolves around predictable timing with very small data needs.
If it is for big machines (Raspberry Pi, PC, etc.), then you have a
completely different world. It doesn't matter if your system uses a
megabyte of ram extra - that's a few microseconds of wasted time at
most. Memory allocation is vital - it needs to be fast and low
time-cost, with great care about cache lines, but it doesn't matter if
ram is wasted. You need to fit the threading world of the OS's you
support, and programmer tools to help avoid data races, false sharing,
and other hard to debug issues would be of great help. So would
language support for multi-threading of algorithms - perhaps also multi-processing, and even distributed computing (using OpenMP and MPI).
Vectorisation of code makes a huge difference. You need full IO,
networking and file support, using UTF-8 throughout - but with libraries
for other encodings for foreign function interfaces. Everything must be optimised for big data structures, because anything else is just noise.
These are completely different worlds. You can't make a language that
is good for both.
--- Synchronet 3.20a-Linux NewsLink 1.114