470,848 Members | 963 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 470,848 developers. It's quick & easy.

Simple Single-Threaded Region Allocator...

Here is the code:
http://pastebin.com/m4a405e67
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

Jun 27 '08 #1
11 1547
"Chris Thomasson" <cr*****@comcast.netwrote in message
news:aL******************************@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
I am VERY sorry for that NON-SENSE!!!

;^(

Jun 27 '08 #2
"Chris Thomasson" <cr*****@comcast.netwrote in message
news:t7******************************@comcast.com. ..
"Chris Thomasson" <cr*****@comcast.netwrote in message
news:aL******************************@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:

http://pastebin.com/m52ba914

It seems to compile successfully. Even on Comeau... ;^)

I am VERY sorry for that NON-SENSE!!!

;^(
Jun 27 '08 #3
"Chris Thomasson" <cr*****@comcast.netwrote in message
news:aL******************************@comcast.com. ..
Here is the code:
[...]

Has anybody tried this allocator yet:

http://pastebin.com/m52ba914

?

Jun 27 '08 #4
"Chris Thomasson" <cr*****@comcast.netwrote in message
news:R7******************************@comcast.com. ..
"Chris Thomasson" <cr*****@comcast.netwrote in message
news:aL******************************@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?
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 **
Jun 27 '08 #5
"Dann Corbit" <dc*****@connx.comwrote in message
news:1e******************@news.teranews.com...
"Chris Thomasson" <cr*****@comcast.netwrote in message
news:R7******************************@comcast.com. ..
>"Chris Thomasson" <cr*****@comcast.netwrote in message
news:aL******************************@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....a2d64acc3e3272

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....c40d42a04ee855
(the first link has primitive C pseudo-code...)

Does it have documentation?
No. You can Goolge for other region-based memory allocation algorithms.

Jun 27 '08 #6

"Dann Corbit" <dc*****@connx.comwrote in message
news:1e******************@news.teranews.com...
"Chris Thomasson" <cr*****@comcast.netwrote in message
news:R7******************************@comcast.com. ..
>"Chris Thomasson" <cr*****@comcast.netwrote in message
news:aL******************************@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...

Jun 27 '08 #7
On May 4, 3:49*pm, "Chris Thomasson" <cris...@comcast.netwrote:
"Dann Corbit" <dcor...@connx.comwrote in message

news:1e******************@news.teranews.com..."Chr is Thomasson" <cris...@comcast.netwrote in message
news:R7******************************@comcast.com. ..
"Chris Thomasson" <cris...@comcast.netwrote in message
news:aL******************************@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?
Jun 27 '08 #8
"user923005" <dc*****@connx.comwrote in message
news:f8**********************************@s50g2000 hsb.googlegroups.com...
On May 4, 3:49 pm, "Chris Thomasson" <cris...@comcast.netwrote:
"Dann Corbit" <dcor...@connx.comwrote in message

news:1e******************@news.teranews.com..."Chr is Thomasson"
<cris...@comcast.net wrote in message
>news:R7******************************@comcast.com ...
>"Chris Thomasson" <cris...@comcast.netwrote in message
>>news:aL******************************@comcast.co m...
>>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?
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"...

Jun 27 '08 #9
"Dann Corbit" <dc*****@connx.comwrote in message
news:1e******************@news.teranews.com...
"Chris Thomasson" <cr*****@comcast.netwrote in message
news:R7******************************@comcast.com. ..
>"Chris Thomasson" <cr*****@comcast.netwrote in message
news:aL******************************@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...

Jun 27 '08 #10
"Chris Thomasson" <cr*****@comcast.netwrote in message
news:rd******************************@comcast.com. ..
"Dann Corbit" <dc*****@connx.comwrote in message
news:1e******************@news.teranews.com...
>"Chris Thomasson" <cr*****@comcast.netwrote in message
news:R7******************************@comcast.com ...
>>"Chris Thomasson" <cr*****@comcast.netwrote in message
news:aL******************************@comcast.co m...
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...
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....c825ec9999d3a8

;^)

Jun 27 '08 #11
"Chris Thomasson" <cr*****@comcast.netwrote in message
news:R7******************************@comcast.com. ..
"Chris Thomasson" <cr*****@comcast.netwrote in message
news:aL******************************@comcast.com. ..
>Here is the code:
[...]

Has anybody tried this allocator yet:

http://pastebin.com/m52ba914
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....c4da438e08028b

The max alignment can potentially be much larger than it needs to be; sorry
about that...

;^(

Jun 27 '08 #12

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

3 posts views Thread by KevinD | last post: by
20 posts views Thread by Chris LaJoie | last post: by
5 posts views Thread by Tim::.. | last post: by
6 posts views Thread by sathyashrayan | last post: by
5 posts views Thread by Byron | last post: by
5 posts views Thread by Chelong | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.