 |
C++Talk.NET
C++ language newsgroups
|
| View previous topic :: View next topic |
| Author |
Message |
Dhruv
Guest
|
 Posted: Tue Jan 13, 2004 10:31 am Post subject: Which Container should I use? |
 |
|
I'm writing a bitmapped allocator in C++, and I'm using a starategy
similar to what I'll be describing below. I'd like to know whether I
should used vector or map in such situations? I have written a few points
for and against their use, but in my mind, I still can not decide which
one to use. Any help would be appreciated. Also, if there is anything
wring with the allocation starategy, I'd like to hear. And if anyone has
implemented a better bitmapped allocator, I'd like to know.
Data Structures used:
typedef std::pair<pointer, pointer> block_pair; //Indicates the Range of
the memory block.
std::vector<block_pair> bp; //Stores a collection of block pairs.
1. Allocation:
==============
During Allocation, I search the free list bitmap for a free block, and if
found, I mark it as allocated. If no free block was found, I get more
memory, and add those ranges to the vector. eg:
Suppose I do:
void *temp = malloc (101);
Then, the pair of pointers I will be adding would be: temp, &temp[100].
2. Deallocation:
================
When a pointer is passed to the deallocation function, it checks each pair
of pointers in the vector to see whether the given pointer is between
these 2 pointer values. If so, then it gets that bitmap, and marks that
block as free. This is my MAIN use for the vector. As you can see, the
search is linear in the number of block pairs. So, I have decided to use
exponentially growing blocks of memory, meaning that if the first block is
of 32 bytes, the next one will be of 32*2 = 64 bytes. The next will be of
64*2 = 128 bytes, etc... So, after some time the linear factor in the
above search becomes insignificant. Now, using a vector, the cache
performance for the search is very good. However, if I use a map for
finding the block_pair, then I will be using much lesser comparisions, but
rthe cache performance may not be that great. And also coinsider that the
size of the map or vector will not increase beyond 32 entries for a 32 bit
system, so then again, linear in 32 seems to be not that bad, but I may be
wrong?
Regards,
-Dhruv.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
 |
Frank Birbacher
Guest
|
| Posted: Wed Jan 14, 2004 10:28 am Post subject: Re: Which Container should I use? |
|
|
Hi!
Dhruv wrote:
| Quote: | 2. Deallocation:
================
When a pointer is passed to the deallocation function, it checks each pair
of pointers in the vector to see whether the given pointer is between
these 2 pointer values. If so, then it gets that bitmap, and marks that
block as free.
|
I'm not sure how you map between mem ranges and bits.
| Quote: | This is my MAIN use for the vector. As you can see, the
search is linear in the number of block pairs.
|
So the vector is sorted? Then you can use std::lower_bound to do a
binary serach.
| Quote: | rthe cache performance may not be that great. And also coinsider that the
size of the map or vector will not increase beyond 32 entries for a 32 bit
system, so then again, linear in 32 seems to be not that bad, but I may be
wrong?
|
For 32 entries you could just use a plain array.
What benefit does the allocator offer?
Frank
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Michael Tiomkin
Guest
|
| Posted: Thu Jan 15, 2004 10:14 am Post subject: Re: Which Container should I use? |
|
|
"Dhruv" <dhruvbird (AT) gmx (DOT) net> wrote
| Quote: | I'm writing a bitmapped allocator in C++, and I'm using a starategy
similar to what I'll be describing below. I'd like to know whether I
should used vector or map in such situations? I have written a few points
for and against their use, but in my mind, I still can not decide which
one to use. Any help would be appreciated. Also, if there is anything
wring with the allocation starategy, I'd like to hear. And if anyone has
implemented a better bitmapped allocator, I'd like to know.
Data Structures used:
typedef std::pair<pointer, pointer> block_pair; //Indicates the Range of
the memory block.
std::vector<block_pair> bp; //Stores a collection of block pairs.
1. Allocation:
==============
During Allocation, I search the free list bitmap for a free block, and if
found, I mark it as allocated. If no free block was found, I get more
memory, and add those ranges to the vector. eg:
Suppose I do:
void *temp = malloc (101);
Then, the pair of pointers I will be adding would be: temp, &temp[100].
2. Deallocation:
================
When a pointer is passed to the deallocation function, it checks each pair
of pointers in the vector to see whether the given pointer is between
these 2 pointer values. If so, then it gets that bitmap, and marks that
block as free. This is my MAIN use for the vector. As you can see, the
search is linear in the number of block pairs. So, I have decided to use
exponentially growing blocks of memory, meaning that if the first block is
of 32 bytes, the next one will be of 32*2 = 64 bytes. The next will be of
64*2 = 128 bytes, etc... So, after some time the linear factor in the
above search becomes insignificant. Now, using a vector, the cache
performance for the search is very good. However, if I use a map for
finding the block_pair, then I will be using much lesser comparisions, but
rthe cache performance may not be that great. And also consider that the
size of the map or vector will not increase beyond 32 entries for a 32 bit
system, so then again, linear in 32 seems to be not that bad, but I may be
wrong?
|
It seems that your allocator doesn't allow more than 32 allocations.
If you need more and faster allocations, you can have different allocators
for different chunk sizes, AND have O(1) time for (de)allocation.
BTW, you can use a list for the free/allocated lists!-)
Define a template class for the sizes of your bitmap chunks:
class my_bitset_base
{
virtual ~my_bitset_base() = 0; // deallocation
virtual myptr_to_bitset get_value() = 0;
virtual size_t get_size() = 0;
}
template<size_t N>
class my_bitset: public my_bitset_base
{
public:
my_bitset() { if (!free_list) add_more_items;
value = free_list;
free_list = value->next;
value->next = allocated_list;
allocated_list = value; }
~my_bitset() { allocated_list = value->next;
value->next = free_list;
free_list = value; }
myptr_to_bitset get_value() {return value;}
size_t get_size() { return size;}
private:
static add_more_items(); // allocate more bit chunks,
// add them to the free list
typedef my_bitset<N> * self_ref;
static int size; // set to N
static self_ref free_list; // initially set to 0
static self_ref allocated_list; // initially 0
self_ref next;
myptr_to_bitset value;
};
Now, you can hide this type in another class (factory) and allocate
only chunks of certain size - for example, any size for N<=32, and
powers of 2 for N>32.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Michael Tiomkin
Guest
|
| Posted: Thu Jan 15, 2004 10:36 am Post subject: Re: Which Container should I use? |
|
|
"Dhruv" <dhruvbird (AT) gmx (DOT) net> wrote
| Quote: | I'm writing a bitmapped allocator in C++, and I'm using a starategy
similar to what I'll be describing below. I'd like to know whether I
should used vector or map in such situations? I have written a few points
for and against their use, but in my mind, I still can not decide which
one to use. Any help would be appreciated. Also, if there is anything
wring with the allocation starategy, I'd like to hear. And if anyone has
implemented a better bitmapped allocator, I'd like to know.
Data Structures used:
typedef std::pair<pointer, pointer> block_pair; //Indicates the Range of
the memory block.
std::vector<block_pair> bp; //Stores a collection of block pairs.
1. Allocation:
==============
During Allocation, I search the free list bitmap for a free block, and if
found, I mark it as allocated. If no free block was found, I get more
memory, and add those ranges to the vector. eg:
Suppose I do:
void *temp = malloc (101);
Then, the pair of pointers I will be adding would be: temp, &temp[100].
2. Deallocation:
================
When a pointer is passed to the deallocation function, it checks each pair
of pointers in the vector to see whether the given pointer is between
these 2 pointer values. If so, then it gets that bitmap, and marks that
block as free. This is my MAIN use for the vector. As you can see, the
search is linear in the number of block pairs. So, I have decided to use
exponentially growing blocks of memory, meaning that if the first block is
of 32 bytes, the next one will be of 32*2 = 64 bytes. The next will be of
64*2 = 128 bytes, etc... So, after some time the linear factor in the
above search becomes insignificant. Now, using a vector, the cache
performance for the search is very good. However, if I use a map for
finding the block_pair, then I will be using much lesser comparisions, but
rthe cache performance may not be that great. And also coinsider that the
size of the map or vector will not increase beyond 32 entries for a 32 bit
system, so then again, linear in 32 seems to be not that bad, but I may be
wrong?
|
For a map of at most 27 entries the cache performance wouldn't be
very bad anyway. BTW, the vector is not frequently updated,
and you can use a sorted array.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Michael Tiomkin
Guest
|
| Posted: Fri Jan 16, 2004 1:08 pm Post subject: Re: Which Container should I use? |
|
|
My previous post was irrelevant and wrong. Pls disregard it.
[email]tmk (AT) netvision (DOT) net.il[/email] (Michael Tiomkin) wrote in message news:<ef72c6cb.0401141328.cdaa8c2 (AT) posting (DOT) google.com>...
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
