Simple Single-Threaded Region Allocator...
Chris Thomasson
One advantage to using a region allocator is that you can usually skip most
calls to free. Instead you can merge multiple free calls into a single reset
call. Here is simple example:
___________________________________________________________________
int main(void) {
allocator this_allocator;
/* create allocator instance with initial region size of 8192 and
a low-watermark region count of 2
*/
if (! allocator_create(&this_allocator, 8192, 2)) {
for (;;) {
int i;
for (i = 1; i < 1024; ++i) {
allocator_request(&this_allocator, i);
}
allocator_reset(&this_allocator);
}
allocator_destroy(&this_allocator);
}
return 0;
}
___________________________________________________________________
The above program will never run out of memory... However, this algorihtm
does not prohibit you from using free. For example:
___________________________________________________________________
int main(void) {
allocator this_allocator;
if (! allocator_create(&this_allocator, 8192, 2)) {
for (;;) {
int i;
for (i = 1; i < 1024; ++i) {
void* const ptr = allocator_request(&this_allocator, i);
if (ptr) {
allocator_release(&this_allocator, ptr);
}
}
}
allocator_destroy(&this_allocator);
}
return 0;
}
___________________________________________________________________
Do you have any helpful comments/suggestions/critiques?
Thanks.
--
Chris M. Thomasson
http://appcore.home.comcast.net
Chris Thomasson
news:aL-dnXc1kID9_IfV...@comcast.com...[...]
WHOOPS! I posted wrong crappy version!
Here is the good one:
I am VERY sorry for that NON-SENSE!!!
;^(
Chris Thomasson
> "Chris Thomasson" <cri...@comcast.net> wrote in message
> news:aL-dnXc1kID9_IfV...@comcast.com...
>> Here is the code:
>>
>>
>> http://pastebin.com/m4a405e67
> [...]
>
> WHOOPS! I posted wrong crappy version!
>
>
> Here is the good one:
>
>
> http://pastebin.com/m31a4ad41
has error; but still seems to compile! :^/
Here is version that gets rid of error:
typedef struct region_s region;
typedef struct region_s {
unsigned char* buf;
size_t size;
size_t offset;
unsigned count;
dlnode node;
};
The leading typedef on 'struct region_s' is bad. Fix:
It seems to compile successfully. Even on Comeau... ;^)
Chris Thomasson
news:aL-dnXc1kID9_IfV...@comcast.com...
> Here is the code:
Has anybody tried this allocator yet:
?
Dann Corbit
What does it do that other allocators fail to do?
Is it faster?
<OT>
Is it robust and efficient under threading conditions?
</OT>
Does it track errors?
I have efficient memory allocators and debugging memory allocators and
clever sub-allocators etc. but I am always ready to try something new if I
see a good reason for it.
Does it have documentation?
** Posted from http://www.teranews.com **
Chris Thomasson
news:1e977$481bf01e$21...@news.teranews.com...
> "Chris Thomasson" <cri...@comcast.net> wrote in message
> news:R7idnRpzapM9UobV...@comcast.com...
>> "Chris Thomasson" <cri...@comcast.net> wrote in message
>> news:aL-dnXc1kID9_IfV...@comcast.com...
>>> Here is the code:
>> [...]
>>
>> Has anybody tried this allocator yet:
>>
>> http://pastebin.com/m52ba914
>
> What does it do that other allocators fail to do?
Nothing.
> Is it faster?
Mabey.
> <OT>
> Is it robust and efficient under threading conditions?
> </OT>
This C version is currently single-threaded, however, one could create an
instance per-thread, however, you could not perform any remote
deallocations. That is, thread_a cannot deallocate objects allocated by
thread_b. You can look on 'comp.programming.threads' for a crude
multi-threaded region allocator prototype:
http://groups.google.com/group/comp.programming.threads/browse_frm/thread/12a2d64acc3e3272
> Does it track errors?
Na.
> I have efficient memory allocators and debugging memory allocators and
> clever sub-allocators etc. but I am always ready to try something new if I
> see a good reason for it.
I am doing some experimentation with reducing the granularity of
multi-threaded region allocators. I have a commercial "closed-source"
distributed slab allocator shown here:
http://groups.google.com/group/comp.arch/browse_frm/thread/24c40d42a04ee855
(the first link has primitive C pseudo-code...)
> Does it have documentation?
No. You can Goolge for other region-based memory allocation algorithms.
Chris Thomasson
> news:R7idnRpzapM9UobV...@comcast.com...
>> "Chris Thomasson" <cri...@comcast.net> wrote in message
>> news:aL-dnXc1kID9_IfV...@comcast.com...
>>> Here is the code:
>> [...]
>>
>> Has anybody tried this allocator yet:
>>
>> http://pastebin.com/m52ba914
>
> What does it do that other allocators fail to do?
Well, it has a reset procedure. Most "traditional" allocators usually expect
that any successful call to malloc will eventually result in a successful
call to free. This is not true wrt region allocation in general. You can
merge several calls to free into a single call to a reset procedure. So, in
certain scenarios, region allocation can make reclaiming dynamic memory more
"simplistic" indeed...
user923005
> "Dann Corbit" <dcor...@connx.com> wrote in message
>
> news:1e977$481bf01e$21...@news.teranews.com...> "Chris Thomasson" <cris...@comcast.net> wrote in message
> >news:R7idnRpzapM9UobV...@comcast.com...
> >> "Chris Thomasson" <cris...@comcast.net> wrote in message
> >>news:aL-dnXc1kID9_IfV...@comcast.com...
> >>> Here is the code:
> >> [...]
>
> >> Has anybody tried this allocator yet:
>
> >>http://pastebin.com/m52ba914
>
> > What does it do that other allocators fail to do?
>
> [...]
>
> Well, it has a reset procedure. Most "traditional" allocators usually expect
> that any successful call to malloc will eventually result in a successful
> call to free. This is not true wrt region allocation in general. You can
> merge several calls to free into a single call to a reset procedure. So, in
> certain scenarios, region allocation can make reclaiming dynamic memory more
> "simplistic" indeed...
It sounds like "partially manual GC" in that you can run a free() on
command of whatever is outstanding. Is that right?
Chris Thomasson
news:f80e8289-3c5e-4b09...@s50g2000hsb.googlegroups.com...
Humm. I guess you could say that its roughly similar to a per-thread
semi-automatic GC. However, there are some caveats. It nice to keep in mind
that calling 'allocator_reset()' on an allocator object completely
invalidates and reclaims _all_ of its outstanding allocations. You could
have multiple allocators per-thread, so the reset procedure can be made
"granular"...
Chris Thomasson
news:1e977$481bf01e$21...@news.teranews.com...
> "Chris Thomasson" <cri...@comcast.net> wrote in message
> news:R7idnRpzapM9UobV...@comcast.com...
>> "Chris Thomasson" <cri...@comcast.net> wrote in message
>> news:aL-dnXc1kID9_IfV...@comcast.com...
>>> Here is the code:
>> [...]
>>
>> Has anybody tried this allocator yet:
>>
>> http://pastebin.com/m52ba914
>
> What does it do that other allocators fail to do?
It can be based on local thread stack memory... Think:
void ThreadEntry() {
unsigned char ThreadLocalBuffer[32767];
{
DynamicRegionAllocator DRAlloc(ThreadLocalBuffer);
pthread_setspecific(..., &RAlloc);
{
[...];
}
pthread_setspecific(..., NULL);
}
}
The initial buffer can be based on the calling threads stack...
Chris Thomasson
Nothing new. I had to put vzoom on a Quadros OS and implement the global
heap out of Per-Quadros Task space... It scaled very well:
http://groups.google.com/group/comp.arch/browse_frm/thread/6dc825ec9999d3a8
;^)
Chris Thomasson
There can be a serious performance problem. It has to do with the
region_aligner union. The code is attempting to calculate a "pseudo" maximum
alignment value from sizeof(region_aligner). Big problem... Here is how to
help alleviate some of the problem:
http://groups.google.com/group/comp.lang.c/browse_frm/thread/6fc4da438e08028b
The max alignment can potentially be much larger than it needs to be; sorry
about that...
;^(