Looking for a grow only allocator

[Thiago Adams]

Does anyone knows an generic allocator for C that
is intended to be used as alloc only?

I would like to try in some cases like this:


struct Tree tree;
LoadFile("file.txt", &tree);

where the process of LoadFile will make a heavy use
of allocations but not deallocations.

[Anton Shepelev]

Thiago Adams:

Does not realloc() with exponentially growing argument help,
in which you make sure that each subsequent allocation is at
least proportional to the currently allocated space, with
some fixed factor between sqrt(2) to 2? You will have to
take care of alignment and track a pointer to the first
unused address within the allocated block. Of course, I mean
using the standard realloc() function with the default
allocator. Are you asking for a custom low-level memory-
management facility that bypasses or replaces the standard
allocation algorithm that is used in realloc() uses by
default?

--
() ascii ribbon campaign - against html e-mail
/\ http://preview.tinyurl.com/qcy6mjc [archived]

[Thiago Adams]

I can try to implement it, as you said, one point we need
to take care is alignment. If I could find something ready
to use it would help.

I was thinking in chunks of data connect to each other.

[Bart]

If the allocations are big then just use malloc, and don't bother to
free. (There will be a tiny overhead to store the block size which is
never used.)

Otherwise a small-block allocator can be a simple set of routines. It
can use a series of memory pools obtained with malloc. When one pool
runs out of memory, just allocate another.

Or you can use malloc here too, if you are not concerned with allocation
speed or the overheads of storing extra data.

[Bonita Montero]

Allocata as many _virtual_ memory (through mmap()) as you
need maximally and allocate in a bump-the-pointer-scheme.

[Bonita Montero]

> Allocata as many _virtual_ memory (through mmap()) as you
> need maximally and allocate in a bump-the-pointer-scheme.

The idea behind that is the memory isn't really physically allocaed
until you make a write-access to a page. So allocating a huge amount
of memory that way doesn't really hurt.

[Anton Shepelev]

Thiago Adams:

> I can try to implement it, as you said, one point we need
> to take care is alignment. If I could find something ready
> to use it would help.

Not long ago, some member of this group (Ben?) posted his
static memory allocator, which came up in context of a
discussion about alignment. If I remember correctly, that
allocator is universal in that it may be put on top of a
dymamically allocated memory block.

> I was thinking in chunks of data connect to each other.

Would not that be slower than `realloc'-ing a solid block?

[Lew Pitcher]

That's a good way to induce the OS's "out of memory killer" to terminate
your program.


--
Lew Pitcher
"In Skills, We Trust"

[Bonita Montero]

>> The idea behind that is the memory isn't really physically allocaed
>> until you make a write-access to a page. So allocating a huge amount of
>> memory that way doesn't really hurt.

> That's a good way to induce the OS's "out of memory killer" to terminate
> your program.

Not true because if you mmap() several gigabytes, these are neither
separated from the pagefile, nor the pages are physically allcoated
until you write to them.
And as the thread-opener has a low fraction of allocations which
will not be used again this is appropriate here.

[Ben Bacarisse]

Anton Shepelev <anton.txt@g{oogle}mail.com> writes:

> Thiago Adams:
>
>> I can try to implement it, as you said, one point we need
>> to take care is alignment. If I could find something ready
>> to use it would help.

Not code, but some ideas. I've piggy-backed them on to my reply to
Anton, but are you sure you need anything at all? Have you measured the
cost of simply using malloc? If you hide all the allocation behind a
clean interface, you can replace malloc later on with something more
sophisticated, but I've often found lots of other things that need
attention before that.

> Not long ago, some member of this group (Ben?) posted his
> static memory allocator, which came up in context of a
> discussion about alignment.

I don't recall that. Maybe someone else. I often use an exponentially
growing allocation, but that is almost always for a single object that
must be contiguous in memory.

General remarks:

For trees, if individual allocation of nodes has too high an overhead, I
would allocate a block of them and hand them out one by one. For some
applications (one is an interpreted programming language) you get some
benefit from keeping a chain of "freed" nodes (you don't use the free
function of course) and using those first.

And if I need to free all the allocations at some point (for example, if
the code in embedded in some other program) then I chain the allocated
blocks together:

struct node_allocation {
struct node_allocation *next;
struct node nodes[HOW_MANY];
} *allocation_list;

struct node *free_list;

This is simple when the structure has a pointer to that type in it
already. The free_list just uses that to chain "freed" nodes.

If you want use the "exponential" trick of allocating more node each
time (based in the assumption that running out mean you need a lot more
rather just a few more), you can do that too without alignment issues
using a flexible array member:

struct node_allocation {
struct node_allocation *next;
size_t n_nodes;
struct node nodes[];
} *allocation_list;

struct node *free_list;

(I'm sure you can see how this would be used.)

--
Ben.

[Scott Lurndal]

https://pubs.opengroup.org/onlinepubs/9699919799/functions/posix_memalign.html

[Anton Shepelev]

Ben Bacarisse to Anton Shepelev:

> > Not long ago, some member of this group (Ben?) posted
> > his static memory allocator, which came up in context of
> > a discussion about alignment.
>
> I don't recall that. Maybe someone else. I often use an
> exponentially growing allocation, but that is almost
> always for a single object that must be contiguous in
> memory.

I meant a simple region allocator by Chris M. Thomasson:

https://pastebin.com/raw/f37a23918

One can put it on top of a block of dynamically allocated
memory, and with little modification, cause it to resize
that block as required.

[Thiago Adams]

On Monday, September 21, 2020 at 1:37:00 PM UTC-3, Ben Bacarisse wrote:
> Anton Shepelev <anton.txt@g{oogle}mail.com> writes:
>
> > Thiago Adams:
> >
> >> I can try to implement it, as you said, one point we need
> >> to take care is alignment. If I could find something ready
> >> to use it would help.
>
> Not code, but some ideas. I've piggy-backed them on to my reply to
> Anton, but are you sure you need anything at all? Have you measured the
> cost of simply using malloc?

The second reason to use a allocator is not performance,
but avoid to have to create "destructors" for each node type
and calling these destructors from the root node.

int main()
{
struct Allocator allocator = {0};
struct AbstractSyntaxTree tree = {0};

ParseFile("file.c", &tree, &allocator);

Allocator_Free(&allocator);
}


If I have 10 or more types of nodes inside of this
tree I dont need to create destructor like destroy_node_type1(), destroy_node_type2 etc..

The allocations would not be only nodes but also the strings etc
(everything ) inside.

[Thiago Adams]

On Monday, September 21, 2020 at 2:38:08 PM UTC-3, Thiago Adams wrote:
> On Monday, September 21, 2020 at 1:37:00 PM UTC-3, Ben Bacarisse wrote:
> > Anton Shepelev <anton.txt@g{oogle}mail.com> writes:
> >
> > > Thiago Adams:
> > >
> > >> I can try to implement it, as you said, one point we need
> > >> to take care is alignment. If I could find something ready
> > >> to use it would help.
> >
> > Not code, but some ideas. I've piggy-backed them on to my reply to
> > Anton, but are you sure you need anything at all? Have you measured the
> > cost of simply using malloc?
>
>
> The second reason to use a allocator is not performance,
> but avoid to have to create "destructors" for each node type
> and calling these destructors from the root node.
>
> int main()
> {
> struct Allocator allocator = {0};
> struct AbstractSyntaxTree tree = {0};
>
> ParseFile("file.c", &tree, &allocator);
>
> Allocator_Free(&allocator);
> }

or something like:

int main()
{
push_new_global_allocator();

struct AbstractSyntaxTree tree = {0};

ParseFile("file.c", &tree);

pop_global_allocator();
}

[Keith Thompson]

Or some other program. The Linux "OOM killer" uses heuristics to
pick a process to kill when it detects that memory is running short.
It doesn't necessarily pick the process that caused the problem.

--
Keith Thompson (The_Other_Keith) Keith.S.T...@gmail.com
Working, but not speaking, for Philips Healthcare
void Void(void) { Void(); } /* The recursive call of the void */

[John Dill]

On Monday, September 21, 2020 at 1:38:08 PM UTC-4, Thiago Adams wrote:
> On Monday, September 21, 2020 at 1:37:00 PM UTC-3, Ben Bacarisse wrote:

> > Anton Shepelev <anton.txt@g{o...> writes:
> >
> > > Thiago Adams:
> > >
> > >> I can try to implement it, as you said, one point we need
> > >> to take care is alignment. If I could find something ready
> > >> to use it would help.
> >
> > Not code, but some ideas. I've piggy-backed them on to my reply to
> > Anton, but are you sure you need anything at all? Have you measured the
> > cost of simply using malloc?
> The second reason to use a allocator is not performance,
> but avoid to have to create "destructors" for each node type
> and calling these destructors from the root node.
>
> int main()
> {
> struct Allocator allocator = {0};
> struct AbstractSyntaxTree tree = {0};
>
> ParseFile("file.c", &tree, &allocator);
>
> Allocator_Free(&allocator);
> }
>
>
> If I have 10 or more types of nodes inside of this
> tree I dont need to create destructor like destroy_node_type1(), destroy_node_type2 etc..
>
> The allocations would not be only nodes but also the strings etc
> (everything ) inside.

I'm not sure I entirely get what you're looking for.

Usually, if you want a fixed size allocator for localizing small object
allocations to improve performance, typically, you chunk page size
allocations into same-sized objects and then link pages together in
your allocator as your data structure grows. Those page allocations
are either through the OS level or you can use malloc as an approximation.

If you have a data structure with multiple sizes, in theory, you could
create an array of fixed size allocators for different block sizes
(4, 8, 12, etc...). Each size would round up depending on the amount
of overhead you allow (a 5-byte allocation would be put in a page
chunked to 8 byte objects). Each fixed size allocator would have their
own page sized regions.

At a higher level, instead of reclaiming individual objects in a fixed
size allocator, you can reclaim pages if they are empty. You could
have an interface to your allocator that simply reclaims all pages
that acts as your tree destructor.

This works best when the objects are relatively small and dense.
If you have a widely disparate range of object sizes, using a region
allocation strategy to allocate contiguously from pages may be
better for you. You really need a lot of small objects for the
payoff to be worth the effort. YMMV.

Best regards,
John D.

[Ben Bacarisse]

Thiago Adams <thiago...@gmail.com> writes:

> On Monday, September 21, 2020 at 1:37:00 PM UTC-3, Ben Bacarisse wrote:
>> Anton Shepelev <anton.txt@g{oogle}mail.com> writes:
>>
>> > Thiago Adams:
>> >
>> >> I can try to implement it, as you said, one point we need
>> >> to take care is alignment. If I could find something ready
>> >> to use it would help.
>>
>> Not code, but some ideas. I've piggy-backed them on to my reply to
>> Anton, but are you sure you need anything at all? Have you measured the
>> cost of simply using malloc?
>
> The second reason to use a allocator is not performance,
> but avoid to have to create "destructors" for each node type
> and calling these destructors from the root node.

Good point. Personally, I shy away from this sort of design because I
like to match allocations with deallocations. It allows the freeing
code to do more than free space (releasing other resources for example)
which can sometimes show up later as an unanticipated requirement.

But that's a feeling, not a sound argument. There is much code that
does multiple allocations with a single free.

> int main()
> {
> struct Allocator allocator = {0};
> struct AbstractSyntaxTree tree = {0};
>
> ParseFile("file.c", &tree, &allocator);
>
> Allocator_Free(&allocator);
> }

What you want is often called a pool allocator. There must be some open
source C code available but, if you have C11, you could mock something
up in a few lines (at the cost of some wasted space) just to get you
started:

struct block {
struct block *next;
_Alignas(max_align_t) char data[];
};

This allows you to use malloc for each object, and at the time chain all
the allocations together. The "allocator" is then little more that the
pointer to first allocated block.

> If I have 10 or more types of nodes inside of this
> tree I dont need to create destructor like destroy_node_type1(),
> destroy_node_type2 etc..

Those are, to my mind, not good names. As I said above, if they can be
avoided, and the space freed in a pool, then they aren't really
destructors. I know you are not planning to use them anyway, so
commenting on the names may seem odd, but my point is, I suppose, that
you should not even be thinking of them in terms of destructors if they
are replaceable by a pool deallocation. (Also there's the fact that C++
destructors don't free the object, so the word has become confusing in
this context.)

> The allocations would not be only nodes but also the strings etc
> (everything ) inside.

--
Ben.

[Bonita Montero]

Forget about special class-allocators. The fastest allocators like
mimalloc are that fast for small allocations (they're popped from
2^N-pools which are thread-local) that there's rarely a noticably
advantage from having a class-allocator.

[Thiago Adams]

On Monday, Septwrites:

I did something a little different with their own pros and cons.

(by the way, _Alignas is not working on VC++ I need to find
something similar)

I have a linked list of fixed length blocks. When the allocation
does not fit at the current block (tail) then a new block is
created and inserted at the list.
After mark 'used bytes' I fix the alignment but this part needs
do be improved for portability.

Each allocation needs to be smaller then block size. Actually
I expect that all allocations are much smaller.
I think this will be the case for instance for parsing files. The file
to be parsed can be allocated (using malloc) on one big string.
Then the structure that is allocated with this especial allocator
can have only "string views" that point to the file string. The
allocations will be the tree nodes and strings will be small structs
pointing to the start and size of the string.


#define BLOCK_SIZE 10 //1024

struct Block {
struct Block* pNext;
char data[]; /*TODO align*/
};

struct Allocator {
struct Block* pHead;
struct Block* pTail;
unsigned bytesUsed; /*bytes used on tail block*/
};

void* Malloc(struct Allocator* allocator, int sz) {
void* result = NULL;

assert(sz > 0 && sz < BLOCK_SIZE);

if (allocator->pHead == NULL) {
/*first use*/
struct Block* pNew = malloc(sizeof(struct Block) + BLOCK_SIZE);
if (pNew == NULL)
return NULL;
pNew->pNext = 0;

allocator->pHead = pNew;
allocator->pTail = pNew;
allocator->bytesUsed = 0;
}

if (BLOCK_SIZE - allocator->bytesUsed < sz) {

/*need a new block*/

struct Block* pNew = malloc(sizeof(struct Block) + BLOCK_SIZE);
if (pNew == NULL)
return NULL;
pNew->pNext = 0;

allocator->pTail->pNext = pNew;
allocator->pTail = pNew;
allocator->bytesUsed = 0;
}

if (allocator->pTail != NULL)
{
result = allocator->pTail->data + allocator->bytesUsed;

/*alignment*/
unsigned n = allocator->bytesUsed + sz / sizeof(long);
allocator->bytesUsed = (n + 1) * sizeof(long);
}

return result;
}

char* StrDup(struct Allocator* allocator, const char* s) {
int sz = strlen(s);
char* r = Malloc(allocator, sz + 1);
if (r)
memcpy(r, s, sz + 1);
return r;
}

void Free(struct Allocator* allocator) {
struct Block* p = allocator->pHead;
while (p) {
struct Block* temp = p;
p = p->pNext;
free(temp);

}
}

int main()
{
struct Allocator allocator = { 0 };

char* text = StrDup(&allocator, "123489");
text = StrDup(&allocator, "test2");

Free(&allocator);
}

[Ben Bacarisse]

Thiago Adams <thiago...@gmail.com> writes:

> I wrote:
>> struct block {
>> struct block *next;
>> _Alignas(max_align_t) char data[];
>> };
>>
>
> I did something a little different with their own pros and cons.
>
> (by the way, _Alignas is not working on VC++ I need to find
> something similar)

VC++ has alignas (apparently), but that's C++. Maybe it can use alignas
in C mode? Does it have max_align_t?

> struct Block {
> struct Block* pNext;
> char data[]; /*TODO align*/
> };

Maybe:

struct Block {
struct Block* pNext;

max_align_t data[];
};

Alternatively, you could insert a single max_align_t member before the
char data[] member and either ignore it or use it's address as the data
pointer.

--
Ben.

[Thiago Adams]

On Tuesday, September 22, 2020 at 12:58:50 PM UTC-3, Ben Bacarisse wrote:
> writes:
>
> > I wrote:
> >> struct block {
> >> struct block *next;
> >> _Alignas(max_align_t) char data[];
> >> };
> >>
> >
> > I did something a little different with their own pros and cons.
> >
> > (by the way, _Alignas is not working on VC++ I need to find
> > something similar)

_Alignas is one of the features that will be added soon.
(16.8 Preview 3)

https://devblogs.microsoft.com/cppblog/c11-and-c17-standard-support-arriving-in-msvc/

[Chris M. Thomasson]

Perhaps a region allocator? Or something like:

https://people.cs.umass.edu/~emery/pubs/berger-oopsla2002.pdf

[Chris M. Thomasson]

On 9/21/2020 9:57 AM, Anton Shepelev wrote:
> Ben Bacarisse to Anton Shepelev:
>
>>> Not long ago, some member of this group (Ben?) posted
>>> his static memory allocator, which came up in context of
>>> a discussion about alignment.
>>
>> I don't recall that. Maybe someone else. I often use an
>> exponentially growing allocation, but that is almost
>> always for a single object that must be contiguous in
>> memory.
>
> I meant a simple region allocator by Chris M. Thomasson:
>
> https://pastebin.com/raw/f37a23918
>
> One can put it on top of a block of dynamically allocated
> memory, and with little modification, cause it to resize
> that block as required.
>

Thank you for bringing it up. I have use it for many things in the past.
Wow, way back in 2009... How time flies. Thanks again.

[Chris M. Thomasson]

I think I remember posting about a partitioned region allocator that
used this code. Its been a while!